primtal

Perfekta tal och deras binära motsvarigheter

Nyligen fyllde jag 28 år vilket är en ”perfekt” ålder på flera sätt :)

Nämligen är 28 det andra perfekta talet, matematiskt sett. Det vill säga, 28 är lika med summan av alla dess delare, exklusive talet självt:

28 = 1 + 2 + 4 + 7 + 14

Det första perfekta talet är 6, det tredje, 496, kommer jag nog inte att fylla…

På antiken kände man till bara fyra perfekta tal, i nuläget har man hittat totalt 48 (senaste talet hittades 2013). Man vet inte om perfekta tal någonsin tar slut. Man vet inte heller om det finns några udda perfekta tal, för alla man hittat hittills är jämna.

Det lustiga är att man inte hittat mönstret med vilket de perfekta tal förekommer. Men om man skriver perfekta tal i det binära talsystemet så ser det väldigt regelbundet ut:

Perfekt tal i bas 10	I bas 2
6	110
28	11100
496	111110000
8128	1111111000000
33550336	1111111111111000000000000
8589869056	111111111111111110000000000000000
137438691328	1111111111111111111000000000000000000
2305843008139952128	1111111111111111111111111111111000000000000000000000000000000
…	…

Det här verkar rätt kusligt. Varför beter sig perfekta tal binär regelbundet på det här sättet? Alltid med ett primt antal ettor och precis en mindre nolla efter!

Jag tyckte det här var lite alienaktigt och gick in på Wikipedia för att läsa på om perfekta tal. Svaret låg i resultaten om vilka perfekta tal vi hittat fram tills nu.

För det första har vi ju inte hittat några udda perfekta tal. För det andra har redan Euklides visat att om $2^{n}-1$ är ett primtal (kallas för Mersenneprimtal), så är $2^{n-1}(2^{n}-1)$ ett perfekt tal.

Det betyder att så fort ett nytt Mersenneprimtal beräknas, så får vi ett perfekt tal på köpet. Det finns faktiskt exakt 48 hittills kända Mersenneprimtal, precis samma antal som perfekta tal. Detta visar sig inte vara någon slump. Euler visade att alla jämna perfekta tal faktiskt har den här formen, det vill säga motsvarar ett Mersenneprimtal.

Till exempel, 3 är det första Mersenneprimtalet ( $2^2-1$ ) som motsvarar det första perfekta talet $2^1(2^2-1) = 2\cdot3 = 6$ .

Nu är det inte så svårt att bevisa det binära sambandet. $2^{n-1}$ skrivet binärt blir $100...00$ med $n-1$ stycken nollor. $2^{n}-1$ binärt blir $111...11$ med $n$ ettor.
Multiplicerat med varandra blir det såklart $111...1100...00$ med $n$ ettor och $n-1$ nollor. Dessutom är $n$ ett primtal, annars skulle inte talet $2^{n}-1$ vara ett primtal!

Förklaringen på mönstret är klar, men det intressanta är egentligen Euklides och Eulers bevis, som båda lämnas åt läsaren :)

Rätt antal

[kkratings]

Fabian sade till Artem att räkna antalet grafer han hade ritat i skrivblocket. ”Ta antalet grafer, addera 7, sedan dividera resultatet med 8, sedan multiplicera med 6 och sedan subtrahera 9. Då kommer du få ett primtal!”

Artem blandade ihop vad Fabian hade sagt till honom. Han räknade antalet grafer rätt, men sedan multiplicerade han det antalet med 7, subtraherade 8 från resultatet, dividerade allt med 6 och sedan adderade 9.
Vad fick han för resultat?

Ett primtal är ett positivt heltal som har exakt två delare: 1 och talet självt.

Till exempel är 2, 3, 5 och 7 primtal.

Men 1, 4, 6, 8 och 9 är inte primtal: 1 har endast en delare (1), 4 har tre delare (1, 2, 4), 6 har fyra delare (1, 2, 3, 6), 8 har fyra delare (1, 2, 4, 8) och 9 har tre delare (1, 3, 9).

Visa lösningen

Problem vecka 12

Syskon (1 poäng). I en familj finns sex barn. Fem av barnen är 2, 6, 8, 12 respektive 14 år äldre än det minsta barnet. Alla åldrarna i familjen är primtal. Hur gammalt är det minsta barnet?

Primtal

Ett primtal är ett positivt heltal som har exakt två delare: 1 och talet självt.

Till exempel är 2, 3, 5 och 7 primtal.

Men 1, 4, 6, 8 och 9 är inte primtal: 1 har endast en delare (1), 4 har tre delare (1, 2, 4), 6 har fyra delare (1, 2, 3, 6), 8 har fyra delare (1, 2, 4, 8) och 9 har tre delare (1, 3, 9).

Sannolikheter (3 poäng). Två vänner singlar slant: den första singlar 10 gånger och den andra singlar 11 gånger. Hur stor är sannolikheten att den andra vännen får klave fler gånger än den första vännen?

Etikett: primtal

Perfekta tal och deras binära motsvarigheter

Rätt antal

Rätt antal

Primtal

Problem vecka 12

Primtal

Visa lösningar