Prvi dve zaporedni številki, ki imata dva različna prafaktorja sta:

Prve tri zaporedne številke, ki imajo tri različne prafaktorje so:

Poišči prva štiri zaporedna cela števila, ki imajo štiri različne prafaktorje. Katero je prvo izmed teh števil?

Naloga je precej nenavadno zastavljena, saj avtor pri razcepu števila na prafaktorje dopušča, da je potencirano praštevilo prafaktor. Zato bomo pri razcepu števila na prafaktorje število zapisali kot , kjer so števila ,, … prafaktorji; ,, … pa stopnje potenc prafaktorjev.

Privzeli bomo, da ima število toliko različnih prafaktorjev, kolikor ima različnih potenc. Zato najprej sestavimo program, ki nam bo vneseno število razcepil na prafaktorje in nam vrnil seznam dvojic (prafaktor, potenca), urejen po naraščajočih vrednostih prafaktorjev (primer: če vnesemo 24, nam program vrne [(2,3),(3,1)] . Zgoraj opisan program bomo nato uporabili v programu, ki nam bo vrnil prva štiri zaporedna števila s štirimi različnimi prafaktorji. Sestavimo bomo program, ki bo kot parameter n sprejme števila 2,3 ali 4 (za n=2 in n=3 namreč že poznamo rešitve in bomo s tem lahko preverili, če naš program pravilno deluje). Z zanko while bomo pregledovali števila z n-timi različnimi prafaktorji, v zanki pa bomo število povečevali za 1. Ko bo takšno število najdeno, ga bomo shranil v nek seznam. Če bo imel tudi naslednik najdenega števila n različnih prafaktorjev, ga bomo dodali na seznam, sicer pa bomo vsa obstoječa števila v seznamu zamenjali s prvim številom, ki bo imel n različnih prafaktorjev.

Metoda prafaktorji(n) : S to metodo računamo prafaktorje števila n, kjer je n naravno število večje od 1. Ta pogoj je zapisan v četrti in peti vrstici. V naslednji vrstici ustvarimo prazen seznam sez, kamor bomo shranjevali dvojice (prafaktor, potenca), ki jih bomo iskali v rangu od 2 do n. Zato v sedmi vrstici napišemo zanko, ki bo tekla od 2 do n+1, in v naslednji vrstici nastavimo števec, ki bo meril stopnjo potence, na 0. Nato z while zanko poiščemo kolikokrat je število deljivo z 2, 3, 5, 7, … Če je ostanek pri deljenju števila n z 2 enak 0, potem števec povečamo za 1 in število n delimo z 2. To ponavljamo, dokler je n deljivo z 2. Ko pa se zanka while zaustavi, v seznam sez dodamo dvojico (2, stopnja potence 2), in nato preverjamo deljivost števila n s 3. Števec se pred zanko while ponastavi na 0. Podobno naprej za ostala praštevila. Na koncu vrnemo seznam, ki je oblike [(a,l), (b,m), ... ] , kjer je n = a^l  * b^m* …  .

Metoda problem(n) : Parameter n je definiran samo za števila 2, 3 in 4. To omejimo z assert stavkoma v osemnajsti in devetnajsti vrstici. Za iskanje števila, ki ima n različnih prafaktorjev, lahko pričnemo s številom, ki je enako produktu prvih n praštevil. Tako za n=3 pričnemo iskati rešitev od 2*3*5=30 dalje, za n=4 lahko pričnemo z 210. V 21. vrstici zato ustvarimo seznam prvih štirih praštevil, v naslednji vrstici pa for zanko, ki izračuna produkt prvih n števil iz seznama prastevila. Ustvarimo seznam sez, kamor bomo shranjevali števila z n različnimi prafaktorji. V seznamu sez je od samega začetka število st – produkt prvih n praštevil. Število st zato v naslednji vrstici povečamo za 1. Nato definiramo zanko, ki teče vse dokler je dolžina seznama manjša od n. V zanki preverjamo, če je število različnih prafaktorjev enako n. Ločimo dva primera:

• če ima tekoče število v seznamu sez na zadnjem mestu svoje predhodno število, potem tekoče število dodamo na konec seznama,
• sicer vsa števila v seznamu zamenjamo s tekočim številom in tako dolžino seznama spremenimo nazaj na ena. V zanki število st povečujemo za 1. Na koncu vrnemo seznam sez.

from math import *

def prafaktorji(n): # izračuna prafaktorje števila n
    assert n!=1, 'Število 1 nima prafaktorjev!'
    assert n>1 and int(n)==n, 'Vnesti je potrebno naravno število!'
    sez=[]
    for i in range(2,n+1):
        s=0
        while n%i==0:
            s+=1
            n=n/i
        if s>0:
            sez.append((i, s))
    return sez # rešitev za število n vrne v obliki [(a,l),(b,m), ... ], kjer je n = a^l * b^m* ...

def problem(n):
     S programom iščemo prva n zaporednih cela števila, ki imajo n različnih prafaktorjev, n je največ 4!
    assert n<=4 and n>1, 'n je lahko le 2, 3 ali 4!'
    assert int(n)==n, 'Vnesti je potrebno celo število!'

    prastevila=[2,3,5,7];st=1
    for i in prastevila[:n]: # Vzamemo prvih n števil iz seznama prastevila, in se tako izognemo parim korakom. Če je npr. n štiri, potem je prvo število s štirimi različnimi prafaktorji 210 (=2*3*5*7).
        st*=i # Pri n=3 je st=1*2*3=6, pri n=4 je st=1*2*3*5*7=210.
    sez=[st] # Ustvarimo seznam, v katerega bomo shranjevali števila, ki imajo n različnih prafaktorjev.
    st+=1

    while len(sez)<n: # Dokler ni v seznamu n števil. Preverjati začnemo s številom st.
        if len(prafaktorji(st))==n: # Zanimajo nas samo primeri, kjer ima število st n različnih prafaktorjev.
            if sez[-1]+1==st: # Če ima število st v seznamu na zadnjem mestu predhodno število, ga dodamo na konec seznama.
                sez.append(st)
            else: # Sicer obstoječe vrednosti v seznamu zamenjamo s števiom st. Dolžina seznama je tako zopet postavljena na 1.
                sez=[st]
        st+=1 # Število st v zanki povečujemo za 1.
    return sez # Ko v seznamu sez dobimo n zaporednih števil, se delovanje zanke zaključi in vrnemo rešitev.

print(problem(2)==[14,15])
print(problem(3)==[644,645,646])

V 37. in 38. vrstici sta testna primera, ki preverita rešitev za n=2 in n=3. Ker je v navodilih lepo pojasnjena rešitev za ta dva n-ja in ker je pravilna, primerjamo če sestavljena metoda vrne seznam s pravimi števili. Obakrat nam vrne True!

Euler_project:_Problem_47