Tvåpotenser

Talen på formen 2^n dyker upp på många ställen. Finns det en cell som fördubblar sig varje minut, så finns det efter en minut 2 celler. Efter ytterligare en minut finns det 4 celler, sedan 8, sedan 16, 32, 64, 128…

Väldigt ofta dyker även talen på formen 2^n-1 upp vid problemlösning. 2^{243112609}-1 är det största hittills kända primtalet till exempel. Men inte alla tal på formen 2^n-1 är primtal (kan du komma på ett motexempel?).

Försöker du lösa problemet nedan, kommer du upptäcka att de två formerna har mycket med varandra att göra. Fler problem och beskrivningen om hur du vinner oändligt med pengar finns under fliken Cirkel.

Rekommenderad från: 12 år


Du har 127 enkronorsmynt och 7 tomma plånböcker, och du måste lägga in alla mynten i plånböckerna. Om någon ber dig om
en summa pengar, skall du kunna ge dem några plånböcker, så att det tillsammans i dem finns precis så många kronor som det frågades efter. Hur skall du fördela mynten mellan plånböckerna på så sätt att du kan ge ut vilken summa under 128 kronor som helst utan att öppna dem, om någon ber om det?

Visa lösningen

4 reaktioner till “Tvåpotenser”

  1. Ett annat problem i samma härad som jag gillar:
    En kung ska bjuda till gästabud om en månad. Han har fått reda på att en av hans tusen flaskor vin innehåller ett oerhört dödligt gift (ospårbart, några molekyler räcker för att döda) som verkar först efter fyra veckor.Han vill inte döda en slumpmässig undersåte genom att låta tusen stycken smaka, men kan tänka sig att offra sina tio dödsdömda fångar.
    Hur kan kungen hitta den förgiftade flaskan i tid till gästabudet?

  2. Ja, det är ett jättesnyggt problem! Jag och en kompis håller på att skriva en bok om 40 snygga problem, och “Det förgiftade vinet” är ett av dem :)

    Du råkar inte veta var du först såg problemet?

  3. Det går att ställa ett villkor för att 2^n-1 ska kunna vara ett primtal. Det bygger på den ganska enkla polynomfaktoriseringen x^m-1=(x-1)(x^(m-1)+x^(m-2)+…+x+1),
    Ifall vi antar att n inte är ett primtal så kan den skrivas på formen n=ab där både a och b är större än 1. Låt 2^a=x och b=m i vår formel så får vi att
    2^n-1=(2^a-1)((2^a)^(m-1)+(2^a)^(m-2)+…+(2^a)+1), Då a,b båda var större än 1 så har vi nu faktoriserat 2^n-1 i två faktorer som är större än 1. Alltså så
    r inte 2^n-1 ett primtal om inte n är ett primtal (vilket gör det lätt att generera motexempel). Primtal på denna form kallas Mersenneprimtal.

    Tyvärr så är inte alla tal på formen 2^p primtal, det finns motexempel redan på ganska låga primtal.

  4. Det går att ställa ett villkor för att 2^n-1 ska kunna vara ett primtal. Det bygger på den ganska enkla polynomfaktoriseringen x^m-1=(x-1)(x^(m-1)+x^(m-2)+…+x+1),
    Ifall vi antar att n inte är ett primtal så kan den skrivas på formen n=ab där både a och b är större än 1. Låt 2^a=x och b=m i vår formel så får vi att
    2^n-1=(2^a-1)((2^a)^(m-1)+(2^a)^(m-2)+…+(2^a)+1), Då a,b båda var större än 1 så har vi nu faktoriserat 2^n-1 i två faktorer som är större än 1. Alltså så
    r inte 2^n-1 ett primtal om inte n är ett primtal (vilket gör det lätt att generera motexempel). Primtal på denna form kallas Mersenneprimtal.

    Tyvärr så är inte alla tal på formen 2^p-1 primtal, det finns motexempel redan på ganska låga primtal.

Kommentera