Collatzova domneva

Naloga

Vzemimo poljubno število in z njim počnimo tole: če je sodo, ga delimo z 2, če je liho, pa ga pomnožimo s 3 in prištejmo 1. To ponavljamo, dokler ne dobimo 1.

Za primer vzemimo 12. Ker je sodo, ga delimo z 2 in dobimo 6. 6 je sodo, torej ga delimo z 2 in dobimo 3. 3 je liho, torej ga množimo s 3 in prištejemo 1 - rezultat je 10. 10 je sodo, zato ga delimo z 2 in dobimo 5... Celotno zaporedje je 12, 6, 3, 10, 5, 16, 8, 4, 2, 1. Ko pridemo do 1, se ustavimo.

Matematiki, ki vedno radi počnejo koristne reči, si belijo glavo z vprašanjem, ali se reč vedno izteče ali pa se lahko kdaj tudi zacikla tako, da se zaporedje ponavlja in ponavlja v nedogled. Lothar Collatz, konkretno je že od leta 1937 domneval, da se zaporedje vedno izteče. Kot pravi njegov življenjepis se je njegovo domnevanje končalo leta 1990 na neki matematični konferenci, matematiki pa domnevajo domnevo še naprej. Znani matematik Erdos je na to temo rekel, da matematika za takšna vprašanja še ni zrela.

Ogrevalna naloga

Napiši program, ki mu uporabnik vpiše poljubno število n. Program naj preveri, ali je število sodo in v tem primeru izpiše n/2; če je liho, pa naj izpiše 3n + 1.

Primer: Vnesi število: 12 6 In še en primer: Vnesi število: 5 16

Obvezna naloga

Napiši program, ki mu uporabnik vnese število, program pa izpiše zaporedje, ki se začne s tem številom.

Vnesi število: 12 12 6 3 10 5 16 8 4 2 1

Dodatna naloga

Napiši program, ki izpiše število med 1 in 100000, ki vodi v najdaljše zaporedje, in dolžino tega zaporedja (vključno s prvim številom in enico).

(Da boste vedeli, ali ste naračunali pravi rezultat: število, ki da najdaljše zaporedje, je deljivo le z dvema različnima prašteviloma - z enim od njiju kar petkrat, z drugim pa le enkrat.)

Rešitev

Ogrevalna in obvezna naloga

Ob ogrevalni se najbrž niste kaj prida ogreli, saj je preprosta. Spomni pa vas, da je za deljenje tule dobro uporabiti // in ne /, da ostanemo pri celih številih in ne dobimo nezaželenih ".0" v izpisu.

n = int(input("Vnesi število: ")) if n % 2 == 0: print(n // 2) else: print(n * 3 + 1)

Obvezna naloga zahteva, da tole zapremo v zanko.

n = int(input("Vnesi število: ")) while n != 1: print(n) if n % 2 == 0: n //= 2 else: n = n * 3 + 1 print(1)

Popaziti je potrebno, da izpišemo tako prvo kot zadnje število. Razislimo: deljenje bo znotraj zanke, prav tako bo znotraj zanke print. Število števil, ki jih je potrebno izpisati, je za 1 večje od števila deljenj. Torej bomo potrebovali še en print izven zanke - če si ne pomagamo s kakšnimi akrobacijami znotraj nje. Tule smo problem rešili preprosto tako, da zadnji člen zaporedja, 1, izpišemo po zanki.

Dodatna naloga

Dodatna naloga zahteva zanko znotraj zanke. Za mnoge je to kar težko, vsaj na začetku. Poleg tega zahteva, da poznamo "frazo" za iskanje največjega (najmanjšega, ali ne kakršenkoli drug način pomembnega) števila ali elementa.

naj_st = naj = i = 1 while i <= 100000: clenov = 1 n = i while n != 1: if n % 2 == 0: n //= 2 else: n = n * 3 + 1 clenov += 1 if clenov > naj: naj = clenov naj_st = i i += 1 print(naj_st, naj)

Zunanja zanka teče prek vseh števil, s katerimi začenjamo zaporedje - od 1 do 100000. Vanjo skopiramo, kar smo napisali kot rešitev obvezne naloge, le da izpisovanje zamenjamo s preštevanjem členov zaporedja.

Z zanko for gre seveda lepše: reši nas postavljanja i-ja na začetno vrednost in njegovega povečevanja.

naj_st = naj = 1 for i in range(1, 100001): clenov = 1 n = i while n != 1: if n % 2 == 0: n //= 2 else: n = n * 3 + 1 clenov += 1 if clenov > naj: naj = clenov naj_st = i print(naj_st, naj)

Packarije

Obvezno nalogo lahko rešimo tudi z if-else. Tri vrstice manj, a zato bistveno grše.

n = int(input("Vnesi število: ")) while n != 1: print(n) n = n // 2 if n % 2 == 0 else n * 3 + 1 print(1)

Vendar to še zdaleč ni najgrše, kar zmoremo. Tole še ni bistveno nepreglednejše...

n = int(input("Vnesi število: ")) while n != 1: print(n) n = n * 3 + 1 if n % 2 else n // 2 print(1)

... s tem pa definitivno zbegamo nasprotnika:

n = int(input("Vnesi število: ")) while n != 1: print(n) n = (n * 3 + 1 - n // 2) * (n % 2) + n // 2 print(1)

V bistvu pa gre tudi v eni vrstici, le da za to potrebujemo funkcijo (se mi zdi):

def coll(n): return "%s\n%s" % (n, coll(n * 3 + 1 if n % 2 else n // 2) if n != 1 else "") print(coll(int(input("Vnesi število: "))))

Ali se da nalogo rešiti v eni vrstici tudi brez takšne definicije funkcije, pa nisem prepričan (za tiste, ki veste, o čem govorim: problem je v tem, da Python nima spodobnih lambda-funkcij ali, še globje, ker v Pythonu ni vsaka reč tudi izraz).