(Euler 14) En Uzun Collatz Dizisi

Aşağıdaki yinelemeli dizi pozitif tamsayılar kümesi için tanımlanmıştır:

n → n/2 (n çift ise)
n → 3n + 1 (n tek ise)

Yukarıdaki kurala göre, 13 sayısından başlayarak aşağıdaki diziyi elde ederiz:

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

13 ile başlayıp 1 ile biten bu dizinin 10 elemanlı olduğu görünüyor. Henüz kanıtlanamamış olsa da, tüm başlangıç sayılarının 1 sayısına ulaştığı düşünülüyor.

Bir milyonun altındaki hangi başlangıç sayısı ile en uzun dizi elde edilir?

Not: Dizi başladıktan sonra bir milyon üzerine çıkabilir.

Birden başlayıp bir milyona kadar olan sayılar için Collatz dizisi uzunluğunu karşılaştırmamız gerekiyor. Sık sık aynı hesapları yapmamak için daha önce bulduğumuz sonuçları hafızada tutacağız.

Collatz Serisi

Taramayı küçük sayılardan büyük sayılara doğru yapacağız. Collatz dizisini oluştururken, başladığımız sayıdan daha küçük bir sayıya rastlarsak, dizinin kalan kısmını daha önceki taramalarda bulmuş olacağımız için, bu kısmın uzunluğunu hafızadan okuyacağız. Örneğin, 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 serisinde, 10 sayısının Collatz uzunluğunu hafızadan bulup, üzerine 3 ekleyeğiz, 13'ün Collatz uzunluğunu hafızaya kaydedeceğiz. Ancak, 40 ve 20'nin Collatz uzunluğunu hafızaya kaydetmeyeceğiz. Böylece, neyin hafıza olduğunu, hafızayı okumadan biliriz. Ayrıca, hafızanın aşırı büyümesinin önüne geçmiş oluruz. Algoritmanın Python ve C dillerinde uygulaması aşağıdaki şekilde;

#!/usr/bin/python
cache = [0] * 1000000
cache[1] = 1
cache[2] = 2
cache[4] = 3
if __name__ == "__main__":
    m, m_i = 0,0
    for a in range(2, 1000000):
        b = a
        c = 0
        while b>=a:
            c+=1
            "Python 3 ile yazilacaksa, en sondaki +2 yerine +1 yazilacak"
            b = b/2 + (b%2) * (b/2 + 2*b + 2)
        c = c+cache[b]
        cache[a]=c
        if c > m:
            m = c
            m_i = a
    print("En uzun dizi %s ile basliyor ve %s elemanli" % (m_i, m))


#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
// int 4 byte iken yaklaşık 4MB
#define CACHE_SIZE 1000000
int cache[CACHE_SIZE];
int main(int argc, char const *argv[])
{
    // İlk birkaç seriyi hafızaya alabiliriz
    cache[1] = 1;
    cache[2] = 2;
    cache[4] = 3;
    uint32_t max = 0;
    uint32_t max_i = 0;
    uint32_t a,b,c;
    for(a = 2; a<1000000;a++)
    {
        b = a;
        c = 0;
        while(b >= a)
        {
            c++;
            b = b/2 + (b%2) * ( (b/2) + 2*b + 2);
        }
        c = c+cache[b];
        cache[a] = c;
        if(c > max)
        {
            max = c;
            max_i = a;
        }
    }
    printf("En uzun dizi %d ile basliyor ve %d elemanli.\n", max_i, max);
    return 0;
}

Python versiyonu 1.7 saniye gibi bir sürede tamamlanırken, C versiyonu 15 milisaniyede tamamlanıyor. Eğer hafızadan değer kullanmayı iptal edersek, Python versiyonunun çalışma süresi 35 saniyeye, C versiyonunun çalışma süresi ise 324 milisaniyeye çıkıyor.

Gelecek Problem

2x2 ızgaranın sol üst köşesinden başlayarak, ve sadece sağa veya aşağıya hareket ederek, sağ alt köşeye tam olarak 6 yol vardır.

20x20 ızgarada bu şekilde kaç adet yol vardır?