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 :)

11 reaktioner till “Perfekta tal och deras binära motsvarigheter”

  1. Spännande! Men det verkar blivit konstigt i typsättningen i rad 3 efter tabellen, det ska väl stå 2^{n-1}(2^n-1)

  2. Samma misstag lite senare, “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” samt “annars skulle inte talet 2^{n-1} vara ett primtal!”. Trevlig text :)

  3. Förlåt lite pedanteri, men det finns inget “i” i “Mersenne” :)

    Det här påminner mig om ett annat trevligt problem. Visa att varje godtyckligt naturligt tal har en multipel på formen “11…10…00” (i bas 10 (eller i vilken bas som helst, egentligen)).

  4. Hej Val.
    26 är också ett intressant tal.
    5^2 < 26 < 3^3
    26 är det enda heltal som ligger mellan ett kvadrattal och ett kubtal.
    Ett svårt bevis men vill du ha ett så kan jag skicka ett från 2006.
    Hälsningar
    Sture

  5. Ah, tack för era anmärkninar. Rätt ska vara rätt!

    Yes, Fabian, det är ett bra problem som vi i princip har i boken som andra problem på nivå 2 :)

    Sture, det visste jag inte. Det borde jag ha tänkt på på min förrförra födelsedag!

  6. Hej Val och Johan B!
    Problemet handlade om födelsedagar.
    Val, du kan väl skicka beviset till Johan B

  7. Det borde gå att göra med lite algebra. Vi vill lösa ekvationen x^2+2=y^3 med heltal (eller motsvarande för -2 istället, men det lämnas som en övning…).

    Om vi istället för att titta bland heltalen tittar bland tal på formen a+bisqrt(2) (dvs vi “lägger till” kvadratroten till -2 precis som man lägger till kvadratroten till -1 när man kommer till komplexa tal) så kan vi faktorisera vänsterledet, låt k=isqrt(2) så jag slipper skriva så mycket. (x+k)(x-k)=y^3. Det gäller att Z[k] är en euklidisk ring, dvs vi kan prata om unik faktorisering i primelement precis som för heltal.

    Vi söker gemensamma faktorer till (x+k),(x-k). En gemensam delare måste dela differensen mellan dem. Differensen är 2k.Så potentiella delare är 2,k,2k. Alla delas av k (k*-k=2). Om k delar x+k så måste k dela x. Då x är ett heltal så måste x delas av k^2, och alltså vara jämnt.
    Då x^2+2=y^3 Så måste y vara jämnt, och vi kan ser att 4 delar x^2 och y^3, men inte 2, dvs motsägelse. Så (x+k),(x-k) saknar gemensamma faktorer. Då måste de vara kuber, ty varje primelement som delar y måste dela endast en av (x+k),(x-k). Så vi har (x+k)=z^3 för något z på formen a+bk (a,b heltal).

    x+k=(a+bk)^3=a^3+3bka^2+3b^2k^2a+k^3b^3.

    Om vi grupperar k-termer och heltals termerna för sig så får vi att x=a^3-6ab^2 (kom ihåg att k^2=-2) och k=(3ba^2-2b^3)k. Division med k ger att (3ba^2-2b^3)=b(3a^2-2b^2)=1. Vi vill ha heltalslösningar, så b måste vara 1 eller -1 då det delar 1.
    Vi får då lösningarna (a,b)= (1,1),(-1,1) (b=-1 ger inga lösningar).
    Dessa ger x=-5,x=5. Testar vi dessa ser vi att 5^2+2=3^3 och (-5)^2+2=3^3.

    Man kan göra motsvarande “trick” med x^2-2=y^3 men att lägga till sqrt(2) istället för sqrt(-2).

  8. Johan B.
    Lösningen -1, 0, 1 är ju lite speciell och urartad (-1)^5, 0, 1^4.
    När man härleder Pythagoreiska trianglar där skillnaden mellan kateterna är en längdenhet
    kan man anse att (0,1,1)är en rätvinklig triangel. De tre första rätvinkliga trianglarna
    i den serien blir då: (0,1,1), (3,4,5), (20,21,29)

Kommentera