Gesellige Zahlen finden

2 Lösungen

#69

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.

Fragen einsehen (3)

Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.

Frage stellen

Bitte melden Sie sich an um eine Lösung einzureichen.

Lösung einreichen

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.

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