Euler Project

Problem 204:

A Hamming number is a positive number which has no prime factor larger than 5. So the first few Hamming numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15. There are 1105 Hamming numbers not exceeding . We will call a positive number a generalised Hamming number of type n, if it has no prime factor larger than n. Hence the Hamming numbers are the generalised Hamming numbers of type 5. How many generalised Hamming numbers of type 100 are there which don't exceed ?

Razlaga osnovnih pojmov:

• PRAŠTEVILO je naravno število, večje od 1, ki ima točno dva pozitivna delitelja, to sta število 1 in samega sebe.
• PRAFAKTOR nekega naravnega(celega) števila je vsak njegov faktor, ki je praštevilo in da skupaj z drugimi prafaktorji ali z 1 kot enoličen zmnožek število samo.
• Praštevilo ima natanko en pravi delitelj, to je 1 in en prafaktor, to je kar število samo.
• Sestavljeno število(to je vsako naravno število, ki ni praštevilo) pa ima več različnih pravih deliteljev in hkrati več različnih ali enakih prafaktorjev.

Razlaga navodila naloge:

Hammingovo število je pozitivno število, katerega noben prafaktor ni večji od 5. Splošno Hammingovo število (generalised Hamming number) tipa n, je tako pozitivno število, katerega noben prafaktor ni večji od n. Koliko je »splošnih« Hammingovih števil tipa 100, ki niso večja od ?

Najprej sem imela idejo, da bi za vsako število do preverila, če je Hammingovo, kar pomeni, da bi za vsako število poiskala njegove prafaktorje, nato pa bi pogledala, če je največji prafaktor manjši ali enak 100. Če bi to veljalo bi to število bilo Hammingovo. A izkazalo se je, da tak pristop k reševanju ni ustrezen, saj bi se pri računanju rešitve moralo izvesti preveč operacij in mi na ta način problema ni uspelo rešiti(izračunati se da le za nekoliko manjša števila kot je ). Koda tega programa je dosegljiva na datoteki euler.py: euler.py

Problem sem se zato odločila reševati drugače in sicer, da ne bom za vsa števila(do nekega števila n-npr. n=) preverjala če so Hammingova, ampak bom raje kar izračunala vsa Hammingova števila do n. Na primer, če si najprej ogledamo kako bi poiskali vsa Hammingova števila do 100:

• Hammingovo število ne sme imeti nobenega prafaktorja večjega od 5, kar pomeni, da najprej poiščemo praštevila do 5 in dobimo :

seznamPrastevil=[2,3,5].

• Hammingovo število bo torej oblike, pri čemer bodo a, b in c neka naravna števila. Če bomo vzeli vse različne kombinacije števil a,b in c ter bo pri vsaki kombinaciji veljalo, da je , bomo na ta način dobili vsa Hammingova števila do 100.
• Potrebno bo le še poiskati ustrezne vrednosti a,b in c.
• Iz seznama praštevil najprej vzamemo najmanjše število, to je 2 in izračunamo vse njegove potence do 100 ter dobimo:

[1,2,4,8,16,32,64]

• Nato seznam sez množimo z naslednjim praštevilom, to je 3 in sicer pri tem upoštevamo, da noben faktor v seznamu sez ne sme biti večji od 100:

[3,6,12,24,48,96]

• Ta seznam še naprej množimo s 3:

[9,18,36,72]

• Ta seznam še naprej množimo s 3:

[27,54]

• Ta seznam še naprej množimo s 3:

[81]

Tega pa ne moremo več množiti s 3, saj bi dobili faktor večji od 100.

• Združimo vse zgornje sezname:

sez=[1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96]

• Nato seznam sez množimo še z naslednjim praštevilom, to je 5 in sicer pri tem upoštevamo, da noben faktor v seznamu sez ne sme biti večji od 100:

[5, 10, 15, 20, 30, 40, 45, 60, 80, 90]

• Ta seznam še naprej m*nožimo s 5:

[25, 50, 75, 100]

Tega pa ne moremo več množiti s 5, saj bi bili vsi faktorji večji od 100.

• Končna rešitev: združimo vse zgornje sezname in dobim vsa Hammingova števila do 100

[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50,54, 60, 64, 72, 75, 80, 81, 90, 96, 100]

• Torej do 100 je 34 Hammingovih števil.

Iskanje »splošnih« Hammingovih števil tipa 100, ki ne presežejo pa bo potekalo na podoben način kot zgoraj opisani postopek. Razlika bo le v tem, da bomo na začetku poiskali vsa praštevila do 100. Nato bomo vzeli najmanjše praštevilo(to je 2), poiskali vse njegove potence tako, da bo faktor manjši od , nato pa ta seznam množili z vsemi praštevili do 100(na enak način kot zgoraj).

Koda programa se nahaja na datoteki hamming.py in je tam tudi sproti komentirana:

Hamming number

Program hamming sem naredila nekoliko bolj splošno in sicer glavna metoda hamming sprejme dva argumenta, n in maxSt, pri čemer nam n pove kateri tip Hammingovega števila iščemo(katera je lahko največja vrednost prafaktorjev), maxSt pa do katere največje vrednosti iščemo Hammingova števila. Npr. za točno moj problem bo potrebno poklicati metodo hamming(100,1000000000). Kot rezultat pa nam metoda hamming vrne koliko je Hammingovih števil tipa n, ki ne presežejo števila maxSt.

• 1. test: Koliko je Hammingovih števil (to je števil, katerih noben prafaktor ni večji od 5) manjših od 100?

Rezultat: 34

• 2. test: Koliko je Hammingovih števil manjših od ?

Rezultat: 1105 (podan že v navodilu naloge)

• 3. test: Koliko je »splošnih« Hammingovih števil tipa 100 (to je števil, katerih noben prafaktor ni večji od 100)manjših od ?

Rezultat:2944730(pravilnost rezultata sem preverila na strani Euler project)

Testiranje rešitve je prikazano tudi v spodnjem filmčku: