جواب سوال 14 ProjectEuler: Longest Collatz sequence

پروژه اویلر

درود

قالب همیشگی مطالب وبلاگ را کمی تغییر دادم!

چالش چهاردهم سایت پروژه اویلر رو امروز با کمک زبان برنامه نویسی محبوب پایتون حل خواهیم کرد! سوال 14 پرسیده:

توالی تکراری زیر برای مجموعه اعداد صحیح مثبت تعریف شده است:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

با استفاده از قانون بالا و شروع با عدد 13 ، توالی زیر را ایجاد می شود:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

همانطور که مشاهده می کنید این توالی از 13 شروع می شود و در 1 به پایان می رسد و شامل 10 ترم است. اگرچه هنوز اثبات نشده است (مسئله Collatz) ، تصور می شود که تمام اعداد شروع شده به 1 ختم می شوند.
کدام عدد زیر یک میلیون بزرگترین زنجیره را می سازد؟

سوال خیلی جالبی هست. من برای حل این مسئله اول دو فانکشن تعریف کردم که برای اعداد زوج تقسیم بر 2 را برگشت داده و برای اعداد فرد ضربدر3 بعلاوه 1 را و سپس در یک حلقه اعداد از 14 تا یک میلیون رو به این توابع ارسال و در هر تکرار زنجیره هر عدد محاسبه و در یک دیکشنری قرار می گیرد و در انتها بزرگترین آنها به همراه عدد ابتدایی آن چاپ می شود. برای راحتی کار با ماکسیمم تکرار زنجیره را کلید و عدد شروع را مقدار دیکشنری قرار دادم:

def even_nums(num):
    return int(num/2)


def odd_nums(num):
    return (3*num+1)


chain_dict = {10: 13}
for my_n in range(14, 1000000):
    my_num = my_n
    chain = 1
    while my_num != 1:
        if my_num % 2 == 0:
            my_num = even_nums(my_num)
            chain += 1
        else:
            my_num = odd_nums(my_num)
            chain += 1
    chain_dict[chain] = my_n

print(max(chain_dict.items()))

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد.