Collatzova domneva 2

Testi

testi-collatzova-domneva-2.py

Naloga

Napišite funkcijo collatz(n), ki kot argument prejme začetno število, kot rezultat pa vrne seznam števil v "Collatzovem zaporedju", ki se začnejo s podanim številom. Če, recimo, pokličemo funkcijo s collatz(12), mora vrniti seznam [12, 6, 3, 10, 5, 16, 8, 4, 2, 1].

Tule le vzamemo rešitev prejšnje domače naloge in zamenjamo print-e z append-i. Pa vse skupaj zapakiramo v funkcijo, seveda.

def collatz(n): s = [n] while n != 1: if n % 2 == 0: n //= 2 else: n = n * 3 + 1 s.append(n) return s

Napišite funkcijo collatz_dolzina(n), ki kot argument prejme začetno število, kot rezultat pa vrne dolžino "Collatzovega zaporedja", ki se začne s tem številom. Če, recimo pokličemo funkcijo s collatz_dolzina(12), mora vrniti 10.

Tole je pa trivialno: vrnemo dolžino tistega, kar vrne prejšnja funkcija.

def collatz_dolzina(n): return len(collatz(n))

Napišite funkcijo najdaljsi_dolz(n), ki vrne dolžino najdaljšega zaporedje, ki ga lahko dobimo, če začnemo s števili med 1 in (vključno) n. Tako mora, recimo, najdaljsi_dolz(10000) vrniti 262, saj je to najdaljše možno zaporedje med števili do 10000 (dobimo ga, če začnemo s 6171).

Tudi ta vzorec nam je znan: iskanje največjega. Pri tem spet uporabljamo prejšnjo funkcijo.

def najdaljsi_dolz(n): naj = 0 for i in range(1, n+1): t = collatz_dolzina(i) if t > naj: naj = t return naj

Napišite funkcijo najdaljsi_stev(n), ki vrne tisto število med 1 in (vključno) n, ki da najdaljše Collatzovo zaporedje. Tako mora, recimo, najdaljsi_stev(10000) vrniti 6171, saj dobimo najdaljše zaporedje, med števili do 10000 takrat, ko začnemo s 6171 (zaporedje ima 262 členov).

Tole je malenkost težje, saj si moramo poleg dolžina najdaljšega zaporedja zapomniti tudi, s katerim številom se je začelo.

def najdaljsi_stev(n): naj = naj_t = 0 for i in range(1, n+1): t = collatz_dolzina(i) if t > naj_t: naj, naj_t = i, t return naj

Napišite funkcijo nad_n(s), ki vrne najmanjše število, s katerim dobimo Collatzovo zaporedje, ki je daljše ali enako s. Tako mora, recimo, nad_n(10) vrniti 7, saj je 7 prvo število, pri katerem dobimo Collatzovo zaporedje z več kot 10 členi (konkretno, zaporedje pri 7 je dolgo 17). Pri tem spet kličite ustrezno izmed gornjih funkcij.

Tule kličemo collatz_dolzina(i) z vedno večjimi začetnimi števili, dokler se enkrat ne zgodi, da dobimo vrsto, ki ima toliko členov, kolikor jih zahtevamo (ali pa celo več). Ker ne vemo, kako daleč bo potrebno iti, namesto uporabimo zanko while. Še več, vzamemo kar while True, ki jo prekinemo z return-om.

def nad_n(n): i = 1 while True: if collatz_dolzina(i) >= n: return i i += 1

Dodatna naloga

Če začnemo zaporedje z 906, dobimo tole: 906, 453, 1360, 680, 340, 170, 85, 256, 128, 64, 32, 16, 8, 4, 2, 1. Zaporedje je zanimivo, ker nobeno število v njem ni praštevilo (razen zadnjih dveh, ki sta vedno 2 in 1, saj se ne more končati drugače). Bolj učeno bi temu rekli, da so vsa števila sestavljena. Poleg tega je zanimivo tudi zato, ker je to med zaporedji, ki se začnejo s števili manjšimi od 1000, najdaljše zaporedje, v katerem ni praštevil.

Napišite funkcijo sest_collatz(n), ki vrne tisto število med 1 in (vključno) n, ki da najdaljše zaporedje, ki je sestavljeno iz samih sestavljenih števil (razen zadnjih dveh). Če je najdaljših zaporedij več, izberite tistega, ki se začne z manjšim številom. Tako mora, na primer, collatz(1000) vrniti 906 in ne 909, ki ima tudi 16 elementov.

Tole ni nič težkega, eno samo nakladanje. Pripravimo si funkciji, ki povesta ali je dano število praštevilo in ali seznam vsebuje sama sestavljena števila. Slednjo stlačimo v pogoj, s katerim presojamo, ali nas zaporedje zanima ali ne.

def je_prastevilo(n): for i in range(2, n): if n % i == 0: return False return True def sama_sestavljena(s): for i in s: if je_prastevilo(i): return False return True def sest_collatz(n): naj_dolz = naj_st = 0 for i in range(1, n + 1): s = collatz(i) if len(s) > naj_dolz and sama_sestavljena(s[:-2]): naj_dolz, naj_st = len(s), i return naj_st