Python :: Aufgabe #69
2 Lösungen

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.
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:

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])
Als Antwort auf Veigars Frage hier mein Code. Eine Erklärung gibt es im C# Bereich.
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