Python :: Aufgabe #69

2 Lösungen Lösungen öffentlich

Gesellige Zahlen finden

Fortgeschrittener - Python von eulerscheZhl - 13.02.2015 um 19:56 Uhr
Eine Zahl ist dann vollkommen, wenn sie gleich der Summe ihrer Teiler ist. (Bsp.: die Teiler von 6 sind 1,2,3 und 1+2+3=6)
Es gibt aber auch Zahlenpaare, die jeweils die andere Zahl als Teilersumme besitzen (Bsp.: 220 und 284), befreundete Zahlen.
Dies lässt sich mit den geselligen Zahlen sogar noch steigern: hier ergibt nicht die Teilersumme von zwei Zahlen die jeweils andere, sondern es lässt sich eine Kette aus mehreren Zahlen bilden (Bsp.: 12496, 14288, 15472, 14536, 14264)

Finde alle Gruppen von geselligen Zahlen, bei denen keine eine Obergrenze (z.B. 10^7) übersteigt.

Lösungen:

vote_ok
von Veigar (1120 Punkte) - 15.02.2016 um 00:28 Uhr
Quellcode ausblenden Python-Code
import math
#Schritt 1: Erstellung einer Liste mit allen zu überprüfenden Zahlen die
#jeweils ihre eigene Liste bekommen um Überprüfungszustand und Gruppenzugehörigkeit anzugeben
#Schritt 2: Alle Zahlen in dieser Liste werden wie folgt bearbeitet:
#Zahl wird in Hilfsliste eingefügt. Wenn keine zahl in der Hilfsliste größer ist als
#die Obergrenze UND sich keine zahl doppelt wird die Summe der Teiler nach den gleichen Muster bearbeitet
#Wenn eine Dopplung in der Hilfsliste: alle Zahlen hinter der ersten Doppelten werden als Gruppenzugehörig markiert
#Wenn Obergenze überschritten: Hilfsliste wird geleert und mit kleinster nicht überprüfter Zahl fortgefahren

def summeteiler(x):
    a=[]
    k=0
    for i in range(int(math.sqrt(x))):
        if x/(i+1)==int(x/(i+1)):
            a.append(x/(i+1))
    for j in range((int(x/(1+int(math.sqrt(x)))))):
            if x/(j+1)==int(x/(j+1)):
                a.append((j+1))
    for d in range(len(a)-1):
        k=a[d+1]+k
    return(k)

def einmalinliste(c):
    d=0
    l=-1
    for o in range(len(c)-1):
        for m in range(len(c)-o-1):
            if c[o]==c[o+m+1]:
                d=d+1
                if l==-1:
                    l=o
    return((d,l))

def einordner(x,g):
    t=g
    y[int(x)][1]=1
    t.append(int(x))
    if summeteiler(x)<=int(a) and summeteiler(x)>0 and einmalinliste(t)[0]==0:
        einordner(summeteiler(x),t)
    if einmalinliste(t)[1]!=-1:
        ä=int(einmalinliste(t)[1])
        for q in range(int(len(t)-einmalinliste(t)[1])):
            y[t[q+ä]][2]=y[-1]
        y[-1]=y[-1]+1

y=[]
s=[]


a=input("zahlen bis zu welcher Obergrenze?")
for l in range(int(a)+1):
    y.append([l,0,0])
y.append(1)

for i in range(int(a)):
    if y[i][1]==0:
        einordner(int(i),[])

for j in range(len(y)-1):
    if y[j][2]!=0:
        s.append(y[j])

print("alle geselligen Zahlen kleiner ",a," sind: ")
for vb in range(len(s)):
    print("Zahl: ",s[vb][0]," Gruppe: ",s[vb][2])
    

1x
vote_ok
von eulerscheZhl (5230 Punkte) - 19.02.2016 um 08:55 Uhr
Als Antwort auf Veigars Frage hier mein Code. Eine Erklärung gibt es im C# Bereich.
Quellcode ausblenden Python-Code
import time

def calcSigma(limit):
	result = [0, 0]
	for i in xrange(2, limit+1):
		result.append(1)
	for i in xrange(2, limit//2 + 1):
		for j in xrange(2*i, limit+1, i):
			result[j] += i
	return result

def socialNumbers(limit):
	result = []
	sigma = calcSigma(limit)
	for i in xrange(2, limit+1):
		chain = []
		tmp = i
		while tmp > 0 and tmp <= limit and not tmp in chain:
			chain.append(tmp)
			tmp = sigma[tmp]
		if len(chain) > 2 and tmp == chain[0]:
			result.append(chain)
		if tmp == 0 or tmp > limit or tmp == chain[0]:
			for j in chain:
				sigma[j] = 0
	return result

start = time.time()
print socialNumbers(10**7)
end = time.time()
print end - start