PY12-15. Eng uzun Kollats zanjiri

Kollats qoidasi: son juft bo‘lsa — ikkiga bo‘linadi, toq bo‘lsa — 3x + 1 ga almashtiriladi. x ning zanjir uzunligi — 1 ga yetguncha qilingan qadamlar soni: 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 — 8 qadam.

1 … n orasida zanjiri eng uzun sonni toping (bir nechta bo‘lsa — eng kichigini). Dasturchi yozgan kod:

def steps(x):
    if x == 1:
        return 0
    if x % 2 == 0:
        return 1 + steps(x // 2)
    return 1 + steps(3 * x + 1)


n = int(input())
best = max(range(1, n + 1), key=steps)
print(best, steps(best))

Natija to‘g‘ri, lekin katta n da «Vaqt chegarasi». Tezlashtiring.

Kirish ma’lumotlari

Bitta butun son n.

Chiqish ma’lumotlari

Ikki son: zanjiri eng uzun son va uning zanjir uzunligi.

Cheklovlar

2 ≤ n ≤ 3·10⁵

n = 10: 9 ning zanjiri 19 qadam — eng uzun. Javob 9 19.