با چالش 23 از پروژه اویلر برگشتیم!
عدد کامل عددی است که مجموع مقسوم علیه های آن با خود آن عدد برابر باشد. برای مثال مجموع مقسوم علیه های عدد 28 برابر است با 1 + 2 + 4 + 7 + 14 = 28 که به این معنی است که عدد 28 یک عدد کامل است.
عدد n را ناکارا (deficient) می نامیم وقتی که مجموع مقسوم علیه های آن از خود عدد کمتر باشد و آن را وافر (abundant) می نامیم اگر مجموع مقسوم علیه های آن از خود عدد بزرگتر باشد.
از آنجایی که عدد 12 کوچکترین عدد وافر است 1 + 2 + 3 + 4 + 6 = 16 ، کوچکترین عددی که بتوان از مجموع دوعدد وافر به دست بیاید 24 است. با تجزیه و تحلیل ریاضی می توان به این نتیجه رسید که تمامی اعداد بزرگتر از 28123 را می توان از مجموعه دوعدد وافر به دست آورد.
جمع تمامی اعداد صحیح مثبتی را که نمی توانند از جمع دوعدد وافر به دست بیایند را پیدا کنید.
سوال چندان سختی نیست و فقط کافی است اون رو به چند قسمت تقسیم کنیم، اما راه حلی که من توسط اون مسئله رو حل کردم بهینه نیست، و حقیقتش زمان لازم رو نداشتم که بیشتر از این روی اون کار کنم تا بتونم راه حل مناسب تری رو برای اون به دست بیارم.
راه حل من به این مراحل تقسیم بندی شد:
- پیدا کردن اعداد وافر و قراردادن اونها درون یک لیست.
- پیدا کردن اعدادی که می توانند از طریق جمع دوعدد وافر به دست بیایند و قرار دادن آنها در یک لیست.
- ساخت یک لیست از اعداد صحیح تا عدد لیمیت و حذف اعدادی که می توانند از جمع دو عدد وافر به دست آیند.
- محاسبه جمع اعداد لیست سوم و رسیدن به جواب مسئله
البته راه حل های زیاد دیگری برای این مسئله وجود داره که تعدادی از اونها رو تست کردم و بهینه سازی چندانی در یافتن مسئله به وجود نیامد به خاطر همین کد خودم رو به همین صورت منتشر می کنم.
شما میتونید راه های دیگه رو تست کنید و یا با ساخت فایل متنی برای لیست هر مرحله باعث بشید با یک بار اجرای کد در اجراهای بعدی نیاز به محاسبات مجدد وجود نداشته باشد و درصورت وجود فایل از اونها استفاده کند.
limit = 28124
def isAabundant(num):
divisorsOfNum = []
for i in range(1, num//2+1):
if num % i == 0:
divisorsOfNum.append(i)
if sum(divisorsOfNum) > num:
return True
else:
return False
def isSumAbundant(num):
for item1 in abundantNums:
if item1 < num:
for item2 in abundantNums:
if item2 < num:
if item1+item2 == num:
return True
elif item1+item2 > num:
break
return False
abundantNums = []
for i in range(1, limit):
if isAabundant(i):
abundantNums.append(i)
sumAbundantNum = []
for i in range(1, limit):
if isSumAbundant(i):
sumAbundantNum.append(i)
notSumAbundantNum = list(range(1, limit))
for item in sumAbundantNum:
notSumAbundantNum.remove(item)
print(sum(notSumAbundantNum))