En uzun Collatz dizisi - $1$ milyondan küçük hangi başlangıç terimi için, oluşturulan dizinin terim sayısı en fazla olur?

Question

$n$ pozitif bir tamsayı olsun. Başlangıç terimi $n$ olan bir dizi tanımlayalım. Dizinin bir sonraki terimi $n$ sayısı çift ise $\frac{n}{2}$, tek ise $3n+1$ şeklinde olsun. Amaç, oluşturacağımız dizide son terimi $1$ bulmaya çalışmak olsun. Örneğin başlangıç terimi $13$ olan, bu kuralla oluşturulan bir dizi şu şekildedir:

$13 \rightarrow 40\rightarrow 20\rightarrow 10\rightarrow 5\rightarrow 16\rightarrow 8\rightarrow 4\rightarrow 2\rightarrow 1$

Yani dizinin terimlerinde $1$ sayısını gördüğümüzde diziyi sonlandırmalıyız. $13$ ile başlayan, $1$ ile biten bu dizinin terim sayısının $10$ olduğu görülebilir.

$\underline{Soru :}$ $1$ milyondan küçük hangi başlangıç terimi için, oluşturulan dizinin terim sayısı en fazla olur?

(Matematiksel açıdan nasıl bir strateji oluşturulabilir?)

Comments

Umarım Sayın okkes dulgerci hocamız,basit bit matehamatica kodu ile bizi bilgilendirir :)

onun haricinde basit matematik kullanarak,döngülerle, kısa sürede sonuç alınabilecek bir problem değil gibi görünüyor.

---

Genel yaklasim su olmali: Kucuk sayilardan baslayarak Kaba Kuvvet kulanmak ama buldugumuz her bir diziyi hafizaya atmak. Baska bir sayi icin hafizada varsa onu tekrar hesaplamamak.

---

"onun haricinde basit matematik kullanarak,döngülerle, kısa sürede sonuç alınabilecek bir problem değil gibi görünüyor." Hold my beer :P

---

bende az uyanık değilim ^^

"Umarım Sayın okkes dulgerci hocamız,basit bit matehamatica kodu ile bizi bilgilendirir :)"

beer'i dolu geri alamayabilirsiniz :P

Answer 1

Yorumda da dedigim gibi daha onceki hesaplari hafizaya atma islemleri kisaltir.

Mathematica da bu soyle yapiliyor.

f[x_]:=istenilen fonksiyon (*normal fonksiyon tanimlamak icin*)

f[x_]:=f[x]=istenilen fonksiyon (*hafizali fonksiyon tanimlamak icin*)

 

 Surdaki kod diziyi degilde sadece dizilerin uzunluklarini hesapladigi icin, bize de bu gerekli zaten, baya hizli: Yaklasik $1$ saniyede en uzun dizinin uzunlugunu buluyor: $525$

 

collatzLength[n_Integer] := collatzLength[n] = If[EvenQ[n], collatzLength[n/2], collatzLength[3*n + 1]]

AbsoluteTiming[1 + Max[collatzLength /@ Range[1000000]]]

{1.0798, 525}

 

Soru hangi sayi icin en uzun dizi elde edilir diye sormus, kodu birazcik degistirirsek, cevabi $837799$ olarak buluruz.

AbsoluteTiming[Last[Ordering[collatzLength /@ Range[1000000] - 1]]]

{1.82749, 837799}

 

 

 

Surda  baslanilan her sayinin, agacin dallarindan govdesine gitmesi misali, $1$'e gittigini gosteren bir grafik var.

 

 

Comments

grafik guzelmis acaba algoritmik sanat diye bir etiket mi baslatsak

---

O kadar guzel ki kac yildir biraz oynanmis hali telefonumun arka yuzunde

---

Aa ne güzelmiş hakikaten.

---

Sercan hocam görmesin,yuvarlak masasına yapıştırır hemen..:P

Answer 2

Pythonda soyle bir denemem oldu

def collatz_sonraki(n):
    if(n==1):
        return 1
    if(n%2==0):
        return n//2
    else:
        return 3*n+1

def collatz_uzunlugu(sayi,hafiza):
    dizi = [sayi]
    n=sayi
    while n not in hafiza.keys():
        n = collatz_sonraki(n)
        dizi.append(n)       
    ret = len(dizi)+hafiza[n]-1
    hafiza[sayi] = ret
    dizi.reverse()
    for idx,i in enumerate(dizi[1:]):
        hafiza[i]=idx+1+hafiza[dizi[0]]
    return ret


hafiza = {1:1}
for i in range(2,1000000):
    collatz_uzunlugu(i,hafiza)


en_uzun_collatz_dizisi = max(hafiza, key=hafiza.get)
print("Sonuc ",en_uzun_collatz_dizisi)

 

Tum zinciri 1 e kadar takip etmek yerine daha once hesapladigimiz bir sayi gordugumuzde duruyoruz. Daha verimli yazilabilir eminim ki mesela $3n+1$ in hep cift oldugunu farkedip kodu biraz daha degistirerek hizlandirmak mumkun.