Normat 55:1, 25–36 (2007) 25
Om Josefus’ permutation
Anders Thorup
Institut for Matematiske Fag
Køpenhavns Universitet
Køpenhavn
thorup@math.ku.dk
1 Introduktion
På et indledende algebrakursus i København lærer man, at enhver p ermutation
af tallene 1, 2, . . . , n entydigt kan fremstilles som et produkt (sammensætning)
af disjunkte cykler. Ved undervisningen i kurset stilles blandt andet følgende to
opgaver:
Opgave 1. Bestem cykelfremstillingen af følgende permutation:
(1) ω = (1 2 3 4 . . . n) · · · (1 2 3 4) (1 2 3) (1 2).
Opgave 2*. Samme spørgsmål for permutationen,
(2) σ = (1 2) (1 2 3) (1 2 3 4) · · · (1 2 3 4 . . . n).
Opgaverne er gode øvelser i at arbejde med permutationer og cykler. De to per-
mutationer er angivet som produkter af cykler, der ikke er disjunkte. Det er ikke
så svært at vise for ω, at cykelfremstillingen er et produkt af disjunkte 2-cykler
(transpositioner),
(3) ω = (1 n) (2 n−1) (3 n−2) · · · ;
hvis n er lige, n = 2i, ender fremstillingen med transpositionen (i i+1), og hvis n
er ulige, n = 2i + 1, er tallet i + 1 fixpunkt, og fremstillingen ender med (i i+2).
Ækvivalent betyder det, at ω er permutationen, der ombytter rækkefølgen af tallene
1, 2, . . . , n, og ω er eksplicit givet ved udtrykket,
(4) ω(x) = n + 1 − x.
26 Anders Thorup Normat 1/2007
Opgave 2 ligner overfladisk den første, det er de samme faktorer, der indgår, blot i
omvendt rækkefølge. I kurset er opgaven markeret som svær. Faktisk er den i hvert
fald så svær, at jeg ikke selv kan løse den! Det er selvfølgelig nemt nok for et givet,
ikke for stort, n at beste mme fremstillingen, men problemet e r, at det er svært at
se et mønster i hvordan fremstillingerne varierer med n. Man kan nøjes med at
spørge efter cykeltypen af σ, dvs en angivelse af det antal p-cykler for p = 1, 2, . . . ,
der indgår i fremstillingen af σ (her svarer 1-cykler til fixpunkter og 2-cykler til
transpositioner).
Opgaven har gennem årene udfordret nogle af deltagerne i kurset, både stude-
rende og lærere. Et par stykker er blevet lidt s ure over at have prøvet kræfter med
en opgave, der “ikke kan regnes”, men gennem årene er der faktisk blevet opdaget
et par overraskende egenskaber ved permutationen σ. De fleste er er fundet ved at
lade en computer udskrive cykelfremstillingen af σ for forskellige værdier af n. Det
følgende er en beretning om disse opdagelser. Det vil fremgå af afsnit 2, hvorfor
permutationen σ kunne kaldes Josefus’ permutation. Spørgsmålet om cykeltypen
af σ besvares i tilfældet, hvor n er af formen 2
m−1
eller 2
m−1
− 1. Svaret er ganske
kompliceret. For n i almindelighed er opgave 2 stadig en udfordring.
2 En færdig formel
Som nævnt er cykelfremstillingen af σ ikke kendt i almindelighed, og når man
kigger på fremstillingen for små værdier af n er det svært at finde et mønster. Det
var derfor ret overraskende, da Niels Peter Jørgensen i 1997 opdagede en færdig
“formel” for σ, nemlig følgende udtryk:
(5) σ(x) =
odd(x + n) + 1
2
, for x = 1, . . . , n.
Her betegner odd(a) den ulige del af det naturlige tal a, opnået ved at dividere
a med den størst mulige potens af 2. For eksempel finder man, for n = 100, at
odd(n + 26) = odd(126) = 63 σ(26) = 64/2 = 32. Den inverse til σ er bestemt
ved σ
−1
(u) = 2
ν
(2u − 1) − n hvor ν er det mindste tal, så at resultatet er s trikt
positivt.
Bevis. Permutationen i (2) afhænger af n. I beviset betegner vi den mere præcist
σ
n
. Lad f
n
være funktionen defineret ved højresiden i (5). Vi viser ved induktion
efter n, at σ
n
(x) = f
n
(x) for x = 1, . . . , n.
For n = 1 og n = 2 er påstanden triviel. Antag, at n > 2 og at påstanden gælder
for n − 1. Af fremstillingen (2) ses klart, at
σ
n
= σ
n−1
γ, hvor γ := (1 2 3 4 . . . n).
Heraf følger:
for 1 ≤ x ≤ n −2 af induktionsantagelsen: σ
n
(x) = σ
n−1
(x + 1) = f
n−1
(x + 1) =
f
n
(x),
for x = n − 1 ved en triviel omskrivning: σ
n
(n − 1) = n = (odd(2n − 1) + 1)/2 =
f
n
(n),
Normat 1/2007 Anders Thorup 27
og for x = n igen af induktionsantagelsen: σ
n
(n) = σ
n−1
(1) = f
n−1
(1) =
1
2
odd(n) + 1
=
1
2
odd(2n) + 1
= f
n
(n).
Hermed er ligheden vist for x = 1, . . . , n.
3 Josefus’ permutation.
Gunnar Forst opdagede i 1998, at permutationen σ hænger tæt sammen med
Josefus-problemet: For et givet n bestemmes Josefus’ permutation J på følgende
måde: Sæt tallene 1, . . . , n ordnet i en ring. Spring over 1 og skub 2 ud af ringen,
spring over 3 og skub 4 ud, og gentag: springer over et tal og skub det næste ud af
ringen. Fortsæt indtil alle er skubbet ud. Sæt
(6) J(y) := det y’te tal, der skubbes ud.
Josefus-problemet er så at bestemme J(n), altså det tal, der bliver skubbet sidst
ud af ringen. I det rigtige Josefus-problem er det hvert tredje tal, der skubbes ud,
men det er en anden historie, se fx Graham–Knuth–Patashnik [1, s. 8–16], eller i
Afsnit 10 herunder.
Det er ikke så svært at vise, for givet n, at Josefus-permutationen J er bestemt
som følgende produkt:
(7) J = (1 2 3 . . . n) (2 3 . . . n) (3 . . . n) . . . (n−1 n).
Bevis. Lad J = J
n
være permutationen defineret i (7). Øjensynlig er er
J = (1 2 3 . . . n)J
0
, hvor J
0
= (2 3 . . . n) (3 . . . n) . . . (n−1 n)
Permutationen J
0
har 1 som fixpunkt, J
0
(1) = 1, men har i øvrigt samme form som
J, bortset fra at det kun er de n − 1 tal 2, 3, . . . , n, der permuteres.
Vi viser ved induktion efter n, at J er Josefus-permutationen bestemt ved legen
ovenfor. Den originale leg begynder med, at man springer over 1 og skubber 2 ud,
og så fortsætter: springer over et tal i cirklen og skubber det efterfølgende ud. Leg
nu i stedet en ny leg, hvor man begynder med at springe over n, således at 1 er
det første, der skubbes ud, og fortsæt. Efter det første trin svarer den nye leg til,
at det er de n − 1 tal 2, . . . , n, der er anbragt i cirklen og at man begynder med at
springe over 2. Heraf følger, ved induktion efter n, at permutationen bestemt ved
den nye leg netop er permutationen J
0
. Derfor er J p e rmutationen bestemt ved
den originale leg.
Idet ω er rækkefølgeombytningen fra (1), altså ω(x) = n + 1 − x, følger det, at
(8) J
−1
= ωσω
−1
.
Med formlen (5) for σ får vi derfor et eksplicit udtryk for den inverse Josefus-
permutation:
(9) J
−1
(y) = n + 1 −
1
2
odd(2n + 1 − y) + 1
,
28 Anders Thorup Normat 1/2007
og heraf fås videre:
(10) J(x) = 2n + 1 − 2
ν
(2n + 1 − 2x), med ν ≥ 1 størst mulig og J(x) ≥ 1.
Specielt, for x = n, fås formlen for det tal, der bliver skubbet ud til sidst:
(11) J(n) = 2n + 1 − 2
ν
, med ν ≥ 1 størst mulig.
Eksempel, for n = 10:
J(10) = 21 − 16 · 1 = 5, J(9) = 21 − 4 · 3 = 9, J(8) = 21 − 4 · 5 = 1,
J(7) = 21 − 2 · 7 = 7, osv.
4 Fixpunkter
Det er let at bestemme fixpunkter for σ (svarende til “1-cykler” i cykelfremstillin-
gen) ud fra formlen (5). Funktionen på højresiden er defineret for alle naturlige
tal x. Skriv x + n = u2
ν
, hvor u er ulige. Så er x et fixpunkt for funktionen på
højresiden, hvis og kun hvis (u + 1)/2 = 2
ν
u − n, eller:
(12)
2
ν+1
− 1
u = 2n + 1.
Fixpunkterne svarer altså til divisorer i 2n + 1 af formen 2
ν+1
− 1. Med ν = 0 fås
løsningen u = 2n + 1, altså x = n + 1, som ligger uden for definitionsmængden for
σ. For de øvrige løsninger til (12) er x = 2
ν
u et fixpunkt for σ. Altså gælder det
følgende resultat.
Observation 1. Fixpunkter x for σ svarer til divisorer i 2n +1 af formen 2
ν+1
−1
med ν ≥ 1, idet x ud fra ligning (12) er bestemt ved x = 2
ν
u − n.
For eksempel, med 2n + 1 = 3
2
· 5 · 7 = 315, altså n = 157, er der 4 fixpunkter
svarende til divisorerne d = 3, 7, 15 og 63.
d u v x
3 105 1 53
7 45 2 23
15 21 3 11
63 5 5 3
5 Et specialtilfælde: n = 2
m−1
Troels Windfeldt Hansen opdagede i 2003 på udskrifter fra en computer, at cykel-
typen for σ ikke var helt tilfældig, når n er en potens af 2. Fx kunne det “ses”, at
når n = 2
m−1
med et primtal m, så er der ét fixpunkt og ellers lutter m-cykler i
fremstillingen af σ.
Troels’ resultater var udgangspunkt for overvejelserne om fixpunkter, og for de
efterfølgende resultater.
Normat 1/2007 Anders Thorup 29
Observation 2. Antag, at n = 2
m−1
. Så har σ præcis 1 fixpunkt når m er ulige,
og ingen fixpunkter, når m er lige.
Bevis. Fixpunkter for σ svarer til divisorer i 2n + 1 af formen 2
ν+1
− 1 med ν ≥ 1.
Betragt et tal d = 2
ν+1
− 1 af denne form, og regn modulo d. Så er 2
ν+1
≡ 1. Skriv
m = q(ν + 1) + r med 0 ≤ r < ν + 1. Da er 2n + 1 = 2
m
+ 1 ≡ 2
r
+ 1. Da r < ν + 1
følger det, at d er divisor i 2n + 1, hvis og kun hvis ν = r = 1, og da r desuden var
den principale rest af m ved division med ν + 1, indtræffer det, hvis og kun hvis m
er ulige.
Observation 3. Hvis n = 2
m−1
, så er σ
m
= id.
Afbildningen x 7→ n − x afbilder mængden {0, . . . , n − 1} bijektivt på mængden
{1, . . . , n}. Det er bekvemt i beviset at konjugere σ med denne afbildning. Herved
erstattes σ med permutationen σ af {0, . . . , n−1} bestemt ved σ(x) = n−σ(n−x).
Udtrykket (5) for σ giver σ(x) = n −
1
2
odd(2n − x) + 1
, som vi omskriver til
følgende:
(13) σ(n) = 2n − 1 −
odd(2n − 1 − x + 1) − 1
2
− n, 0 ≤ x < n.
Afbildningen σ er sammensat af afbildninger, som det er let at beskrive ud fra
den binære fremstilling af tallene: Tallene x med 0 ≤ x ≤ 2n − 1 = 2
m
− 1 kan
fremstilles binært, x = x
0
+ x
1
2 + · · · + x
m−1
2
m−1
med m bits (cifre), der alle er
enten 0 eller 1. Vi identificerer i det følgende tallene med deres bitfølge,
x = x
0
x
1
. . . x
m−1
,
idet vi altid medtager alle m bits, ogs å når det ledende bit x
m−1
er 0. Fx har tallene
med 0 ≤ x < n−1 alle 0 som det ledende bit. Operationerne, der indgår i udtrykket
for σ kan let udføres på de tilsvarende bitfølger. Specielt er operationen x 7→
2n−1−x simpel: den fører bitfølgen x over i komplementære bitfølge x fremkommet
fra x ved at erstatte 0 med 1 og 1 med 0.
Betragt nu et tal x med 0 ≤ x ≤ n − 1. Det ledende bit er da 0. Antag først,
at x > 0. Læst fra venstre b e står bitfølgen x så af et antal, lad os sige ν, af 0-
bits efterfulgt at et 1-bit, efterfulgt af en bitfølge z med m − ν − 1 bits (det er
ikke udelukket, at ν = 0; det indtræffer præcis når x er ulige). Bitfølgen for x har
altså formen 00 . . . 01z med ν 0-bits. I denne beskrivelse er det let at se, hvordan
bitfølgen ændres af operationerne, der indgår i σ(x):
x =
ν
z }| {
00 . . . 0 1z, x = 2n − 1 − x =
ν
z }| {
11 . . . 1 0z,
x + 1 =
ν
z }| {
00 . . . 0 1z, odd(x + 1) = 1z
ν
z }| {
00 . . . 0,
odd(x + 1) − 1 = 0z
ν
z }| {
00 . . . 0, u =
1
2
odd(x + 1) − 1
= z
ν
z }| {
00 . . . 0 0,
u = z
ν
z }| {
11 . . . 1 1, σ(x) = u − n = z
ν
z }| {
11 . . . 1 0,
30 Anders Thorup Normat 1/2007
altså
(14) x =
ν
z }| {
00 . . . 0 1z, σ(x) = z
ν
z }| {
11 . . . 1 0.
Ændringen i bitfølgen fra x til σ(x) kan beskrives dynamisk: Betragt en uendelig
følge af bits med en “pointer”,
y
1
y
2
. . . y
i
↑
y
i+1
. . .
Lad os vedtage, at p ointeren, placeret umiddelbart til venstre for et bit, udpeger det
tal, hvis bitfølge består af de m bits, der står umiddelbart til højre for pointeren.
Med pointeren som ovenfor udpeges altså tallet y = y
i+1
. . . y
i+m
. Betragt nu den
uendelige bitfølge,
xxxx · · · =
↑
ν
z }| {
00 . . . 0 1
↑
z
ν
z }| {
11 . . . 1 0z . . .
bestående af de m bits i x efterfulgt af de m bits i x, efterfulgt af . . . . Den første
pointer, til venstre for det første bit i følgen, udpeger øjensynlig x. Placeringen
af den anden pointer er opnået ved at flytte den første pointer til højre indtil den
passerer det første 1-bit. Af udregningen 14 fremgår, at den anden pointer udpeger
σ(x). Det var antaget, at x > 0, men det er let at se, at påstanden også gælder for
x = 0, hvor følgen xxx . . . er 00 . . . 011 . . . 100 . . . 0 . . . . For 0 ≤ x < 2
m
− 1 gælder
altså den følgende opskrift.
Opskrift A. Hvis pointeren i følgen xxxx . . . udpeger x, så bestemmes σ(x) ved
et flytte pointerne til højre forbi det førstkommende 1-bit.
Følgen xxxx . . . har perioden 2m, endda med y
i+m
= 1−y
i
(hvor y
i
er det i’te le d).
Heraf ses, at når pointeren i følgen udpeger tallet y, så er bitfølgen efter pointeren
bestemt ved yyyy . . . . Opskriften er derfor gyldig for enhver placering af pointeren:
Hvis pointeren udpeger y, så bestemmes σ(y) ved at flytte pointeren til højre hen
forbi det førstkommende 1-bit. Specielt kan opskriften itereres:
Opskrift B. Hvis pointeren i følgen xxxx . . . udpeger x, så udpeges σ
k
(x) ved at
flytte pointeren til højre forbi de k førstkommende 1-bits
Af det sidste fremgår, at for at vise Observation 3 skal følgende vises.
Observation 4. Antag, at 0 ≤ x < 2
m−1
− 1, Hvis pointeren i følgen xxxx . . .
udpeger x, og den flyttes til højre forbi de m førstkommende 1-bits, så udpeger den
igen x.
Bevis. Det kan indses således: I xx indgår 2m bits. Der er et antal 1-bits i x og
det komplementære antal 1-bits i x. I xx er antallet af 1 bits derfor præcis m.
Yderligere er x < 2
m−1
, så det ledende bit i x er et 0-bit. Derfor er det ledende
bit (det sidste bit) i x et 1-bit. Når pointeren har passeret alle 1-bits i xx har den
derfor passeret samtlige bits i xx; derfor peger den igen x.
Observation 5. Hvis n = 2
m−1
, hvor m er et ulige primtal, så har σ cykeltypen
1
1
m
k
, hvor k = (2
m−1
− 1)/m.
Normat 1/2007 Anders Thorup 31
Bevis. Det er Troels’ opdagelse, og det følger umiddelbart: Da σ
m
= id, er hver
cykels længde divisor i m, og dermed 1 eller m. Ifølge Observation 2 er der kun 1
fixpunkt. Derfor må de øvrige cykler have længde m.
6 Cykeltypen, for n = 2
m−1
.
Opskrift A i bevise t for Observation 3 kan bruges til at bestemme cykeltypen helt,
stadig i tilfældet n = 2
m−1
. Permutationerne σ og σ har samme cykeltype, og vi
holder os til σ. Af Observation 3 følger, at hvis x beste mmer en p-cykel for σ, så
er p divisor i m (og naturligvis er σ
p
(x) = x).
Lad nu p være en sådan divisor, m = pd. Betragt for en bitfølge x, med 0 ≤ x <
n = 2
m−1
, ligningen σ
p
(x) = x. Den betyder, at når pointeren i følgen xxxx . . .
udp e ger x, og så flyttes p gange (hver flytning er til højre forbi det førstkommende
1-bit), så udpeger den igen x. Lad h være det samlede antal bits, som overspringes
ved de p flytninger. Når de p flytninger er gentaget d gange, er der flyttet m
gange; ifølge lemmaet er der så præcis oversprunget samtlige 2m bits i xx. Altså
er dh = 2m, og derfor er h = 2p. Lad z være bitfølgen bestående af de første p af
de oversprungne bits, og lad w være bitfølgen bestående af de næste p bits. Da er
xx = zw . . . zwzw,
med d gentagelser af de 2p bits i zw. Af denne ligning følger først, at d må være
ulige, d = 2e − 1 (ellers var x = x), og dernæst, at w = z. Altså har x har formen,
(15) x = zzzz . . . zzz,
hvor z har længde p, og z forekommer e gange og z forekommer e − 1 gange.
Omvendt, hvis z er følge med p bits, så ender følgen 15 med det ledende bit i z,
dvs 0 ≤ x < n. hvis og kun hvis det ledende bit i z er 0. Med andre ord gælder
følgende resultat.
Observation 6. For hver divisor p i m, med m = dp, er σ
p
(x) = x, hvis og kun
hvis d er ulige og x har formen 15, hvor z er en følge af p bits med ledende bit lig
med 0.
Der er 2
p−1
muligheder for en sådan bitfølge z. Derfor er der præcis 2
p−1
muligheder
for et tal x < n med σ
p
(x) = x.
Lad nu α(p) betegner antallet af tal x < n for hvilke cyklen bestemt ved x har
længde p. Antallet af muligheder bestemt oven for er antallet at tal x < n for hvilke
cyklen bestemt ved x har en længde, der er divisor i p. Der gælder altså:
X
q|p
α(q) =
(
2
p−1
hvis p | m og m/p er ulige,
0 ellers.
Herefter bestemmes α(p) ved Möbius-inversion: Med Möbius funktionen µ(d) er
(16) α(p) =
X
0
q|p
µ(p/q)2
q−1
,
32 Anders Thorup Normat 1/2007
hvor summen er over de divisorer q i m for hvilke m/q er ulige.
Ækvivalent, hvis m = 2
ν
u, hvor u er ulige, så er α(p) = 0 med mindre p er en
divisor i m af formen 2
ν
v. I det sidste tilfælde er
(17) α(2
ν
v) =
X
w|v
µ(v/w)2
2
ν
w−1
.
Observation 7. Antag, at n = 2
m−1
. Da forekommer der p-cykler i σ, hvis og kun
hvis p | m og m/p er ulige. Antallet af p-cykler, for p | m og m/p ulige, er α (p)/p,
hvor α (p) er summen i 16 (eller i 17).
7 Eksempel.
For n = 2
9
= 512 er m = 10 = 2 · 5, så der er 2-cykler og 10-cykler, nemlig
#(2-cykler) =
1
2
µ(1)2
2−1
= 1, #(10-cykler) =
1
10
(−1)2
2−1
+ 2
10−1
= 51.
8 Et specialtilfælde: n = 2
m−1
− 1.
Lasse Nielsen opdagede i 2003, at der for vilkårligt n gælder, at tallene x
k
=
n − (2
k
− 1), for k = 0, 1, . . . og x
k
≥ 1, ligger i samme cykel, idet σ(x
k
) = x
k−1
:
x
k
7→ x
k−1
7→ · · · 7→ x
2
= n − 3 7→ n − 1 7→ n = x
0
.
Det størst mulige k er bestemt ved 2
k
−1 < n, altså 2
k
≤ n, dvs k er den hele del af
log
2
n. Der indgår mindst k + 1 elementer i cyklen. Altså gælder følgende resultat.
Observation 8. Længden af den største cykel, der forekommer i σ, er altid mindst
lig med k + 1, hvor k er den hele del af tallet log
2
n.
Lasse opdagede videre, ved udskrifter fra en computer, det efterfølgende resultat.
Observation 9. Antag, at n = 2
m−1
− 1. I cykelfremstillingen af σ forekommer
da p-cykler for alle p = 1, . . . , m − 1, og ikke for andre p.
For at vise denne påstand konjugerer vi σ med permutationen ω(x) = n + 1 − x fra
1, og betragter altså permutationen σ
0
bestemt ved σ
0
(x) = n + 1 − σ(n + 1 − x),
for 1 ≤ x ≤ 2
m−1
. Indsættes formlen 5 for σ fås, efter en lille omskrivning,
(18) σ
0
(x) = 2n + 1 −
odd(2n + 1 − x) − 1
2
− (n + 1).
Her er 1 ≤ x < n = 2
m−1
, og som i Afsnit 4 kan vi identificere disse tal med deres
bitfølger med m bits og ledende bit 0, men nu med undtagelse af nulfølgen 00 . . . 0.
Operationerne, som indgår i udtrykket 18 for σ
0
svarer til simple operationer med
Normat 1/2007 Anders Thorup 33
bitfølger. Da 2n + 1 = 2
m
− 1, svarer operationen x 7→ 2n+1 − x på bitfølger til
x 7→ x.
Bitfølgen for et tal x med 1 ≤ x < n har formen 11 . . . 10y med ν 1-bits inden det
først 0-bit (det er ikke udelukket, at ν = 0 eller at y er tom). Med denne beskrivelse
er det let at se, som i Afsnit 4, hvordan bitfølgen ændres af σ
0
:
(19) x =
ν
z }| {
11 . . . 1 0y, σ
0
(x) = y
ν
z }| {
11 . . . 1 0,
Beskrivelsen 19, sammenholdt med den uendelige bitfølge xxx . . . ,
xxxx · · · =
↑
ν
z }| {
11 . . . 1 0
↑
y
ν
z }| {
11 . . . 1 0y . . . ,
leder s om i Afsnit 4 til en opskrift.
Opskrift C. Betragt for 1 ≤ x ≤ 2
m−1
− 1 den uendelige bitfølge xxxx . . . . Hvis
en pointer i følgen udpeger x, så udpeges σ
0
(x) ved et flytte pointeren til højre forbi
det førstkommende 0-bit.
Som i Afsnit 4 kan opskriften itereres. Antag, at k er antallet af 0-bits i x. Hvis
pointeren i følgen xxx . . . udpeger x, og den flyttes k gange efter opskriften, så
udp e ger den σ
k
0
(x). Pointeren har så præcis oversprunget samtlige 0-bits i x, og
da det ledende bit i x er et 0-bit, har den altså præcis oversprunget samtlige bits
i x; den udpeger derfor igen x. Altså er σ
k
0
(x) = x. Specielt er perioden for x, dvs
længden af den cykel under σ
0
, s om beste mme s ved x, divisor i k.
Antallet af 0-bits i x kan højst være m − 1, da x > 0. Derfor har en cykel,
der indgår i σ
0
, højst længden m − 1. Desuden ses for k = 1, . . . , m − 1, at tallet
x := 1 . . . 100 . . . 0, hvor antallet af 0-bits er k, præcis har perioden k.
Hermed er Lasses observation 9 eftervist.
9 Cykeltypen, n = 2
m−1
− 1
Antallet af p-cykler kan bestem mes således: Lad M
λ
(d) være mængden af de bit-
følger af længde d, som ikke er lutter 0-bits, hvor det ledende (højre) bit er et 0-bit,
og hvor λd er det samlede antal 0-bits. Hvis mængden ikke er tom, må λd være et
helt tal me d 1 ≤ λd < d. Lad β
λ
(d) være antallet af bitfølger i M
λ
(d). Øjensynlig
gælder, når λd er et helt tal med 1 ≤ λd < d, at
(20) β
λ
(d) =
d − 1
λd − 1
.
Lad nu β
prim
λ
(d) b e tegne antallet af primitive bitfølger i M
λ
(d), dvs bitfølger i
M
λ
(d) som er primitive, dvs følger der ikke er af formen zz . . . z med en følge z
i M
λ
(e) med e n ægte divisor e | d. Det er klart, at β
λ
(d) =
P
e|d
β
prim
λ
(e). Ved
Möbius-inversion fås så:
(21) β
prim
λ
(e) =
X
d|e
µ(d)β
λ
(e/d).
34 Anders Thorup Normat 1/2007
Det følger af b e skrivelsen ovenfor, når 1 ≤ x ≤ 2
m−1
− 1, at x har periode p under
σ
0
, hvis og kun hvis bitfølgen x har formen x = zz . . . z, hvor z er en primitiv
bitfølge i M
p/e
(e) (dvs længde e, antal 0-bits lig med p, ledende bit 0, og z > 0.
Lad α(p) være antallet af tal x med 1 ≤ x ≤ n for hvilke perioden for x er lig med
p. Antallet er 0 for p ≥ m. For 1 ≤ p ≤ m − 1 gælder i følge det foregående, at
α(p) =
X
e|m
β
prim
p/e
(e).
Der e r kun bidrag, når e > p. Summen kan omskrives ved 20 og 21:
(22) α(p) =
X
d|e|m
µ(d)β
p/e
(e/d) =
0
X
0
d|e|m
µ(d)
e/d − 1
p/d − 1
,
hvor der i den sidste sum kun medtages led, når e > p og d | p.
Observation 10. Antag, at n = 2
m−1
− 1. Da gælder for p = 1, . . . , m − 1, at
antallet af p-cykler i σ er lig med α(p)/p, hvor α(p) er summen 22. Specielt, hvis
m er et primtal, så er antallet af p-cykler lig med
(23)
1
p
m − 1
p − 1
, p = 1, . . . , m − 1.
Bevis. Den almindelige formel blev vis ovenfor. Antag, at m er et primtal. For et
led i summen 22 er e > p og e | m, så e = m og da d | e og d | p, er d = 1.
Der er altså kun 1 led i summen, og det er binomialkoefficienten i 23. Heraf følger
påstanden.
10 Eksempel
n = 2
9
− 1 = 511 giver m + 1 = 10 med divisorer e = 10, 5, 2 idet e > 1.
p = 9, (e, d) = (10, 1):
9
8
/9 = 1.
p = 8, (e, d) = (10, 1), (10, 2):
9
7
−
4
3
/8 = 4.
p = 7, (e, d) = (10, 1):
9
6
7 = 12.
p = 6, (e, d) = (10, 1), (10, 2):
9
5
−
4
2
/6 = 20.
p = 5, (e, d) = (10, 1), (10, 5):
9
4
+
4
0
+
4
1
/5 = 25.
p = 4, (e, d) = (10, 1), (10, 2), (5, 1):
9
3
−
4
1
+
4
3
/4 = 21.
p = 3, (e, d) = (10, 1), (5, 1):
9
2
+
4
2
/3 = 14.
p = 2, (e, d) = (10, 1), (10, 2), (5, 1):
9
1
−
4
0
+
4
1
/2 = 6.
p = 1, (e, d) = (10, 1), (5, 1), (2, 1):
9
0
+
4
0
+
1
0
/1 = 3.
Normat 1/2007 Anders Thorup 35
11 Den generelle Josefus permutation
Den generelle udfordring, se [1, s. 79–81], er følgende: Stil tallene 1, 2, . . . , n i ringen
og skub hvert q’te tal ud (tilfældet ovenfor er q = 2, Josefus’ oprindelige problem
svarer til q = 3). Lad J
q
= J
q, n
være permutationen i S
n
bestemt ved at J
q
(x) er
lig med det x’te tal, der skubbes ud. Findes der en formel for permutationen J
q
?
Som ovenfor ses, at
J
q
= (1 2 3 . . . n)
q−1
(2 3 . . . n)
q−1
· · · (n − 1 n)
q−1
,
og heraf:
J
−1
q
= ωσ
q
ω
−1
,
hvor
σ
q
= σ
q, n
= (1 2)
q−1
(1 2 3)
q−1
· · · (1 2 3 . . . n)
q−1
Findes der en formel for σ
q
, s om tillader at bestemme σ
−1
q
?
Det er let at bestemme et rekursivt udtryk: Hold q fast, og prøv med et udtryk
af formen
σ
q ,n
(x) = f(x + (q−1)n).
Induktivt kan antages, for 1 ≤ x ≤ n − q, at
σ
q, n
(x) = σ
q, n−1
(x+q−1)) = f (x+q−1 + (q−1)(n−1)) = f(x + (q−1)n),
så ligningen gælder, når bare den gælder for n − q < x ≤ n. For x = n − q + 1 er
σ
q ,n
(x) = n, så kravet her er
f(n−q+1 + (q−1)n) = n, altså f(qn − q + 1) = n.
For n − q + 1 < x ≤ n er x = n − a med 0 ≤ a < q − 1, og her er σ
q, n
(n − a) =
σ
q, n−1
(q − 1 − a) = f(q − 1 − a + (q − 1)(n − 1)); kravet er
f(−a + qn) = f(−a + (q − 1)n), for 0 ≤ a < q − 1.
Erstattes n med t + 1 i det første krav, og n med t i de øvrige, er betingelserne:
f(qt − a) = f((q−1)t − a) for a = 0, . . . , q − 2, f (qt + 1) = t + 1.
Eksempel. For q = 2 fås f (2t) = f (t), f(2t + 1) = t, hvoraf f (x) = [odd(x) + 1]/2.
Og for q = 3 fås:
f(3t − 1) = f(2t − 1), f(3t) = f(2t), f(3t + 1) = t + 1.
Man får altså f (z) ved først at reducere, gentagne gange, argumentet z med de
to ope rationer 3t − 1 7→ 2t − 1 og 3t 7→ 2t indtil der fremkommer et tal ≡ 1
36 Anders Thorup Normat 1/2007
(mod 3); denne reduktion kunne betegnes odd
3
(z). Med denne betegnelse er f (z) =
(odd
3
(z) + 2)/3, og altså
σ
3
(x) =
odd
3
(x + 2n) + 2
3
.
Den omvendte af reduktionen ovenfor, 2t 7→ 3t og 2t − 1 7→ 3t − 1, kan fås ved
at multiplicere med 3/2 og runde op; med en ikke-standard notation kan denne
afbildning betegnes d3/2e. Med denne notation bestemmes den inverse sådan:
x = σ
−1
3
(y) = d 3/2e
ν
(3y − 2) − 2n,
med ν mindst mulig og x ≥ 1 (eller ν størst og x ≤ n). For den konjugerede,
J
3
= ωσ
−1
3
ω
−1
, fås:
J
3
(y) = 3n + 1 − d3/2e
ν
(3n + 1 − 3y) med ν størst mulig.
Specielt, “Josefus-tallet” J
3
(n), dvs tallet, der skubbes ud til sidst, er
J
3
(n) = 3n + 1 − d3/2e
ν
(1), ν størst mulig.
Generaliseringen til q > 3 er umiddelbar.
Litteratur
[1] R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, Second
edition, Addison–Wesley, 1995.
Appendix: Redaktörens anmärkningar
För den läsare som händelsevis är obekant med notationen vill jag presentera
en liten snabbkurs. Med en permutation av talen (1, 2, . . . n) menas en omord-
ning av talen. En typisk permutation av talen (1, 2, 3, 4, 5, 6) kan presenteras av
(2, 4, 3, 6, 1, 5). En permutation σ är en bijektion av objekten, och notationen ovan
är helt enkelt en presentation (σ(1), σ(2), σ(3), σ(4), . . . σ(n)). Notera att alla såda-
na presentationer har längden n. I artikeln används istället en cykelpresentation.
Varje element x ger upphov till en cykel (x, σ(x), σ(σ(x)), σ(σ(σ(x))), . . . , σ
m−1
(x))
där σ
m
(x) = x. Två cykler som är disjunkta kommuterar, och varje permutation
kan skrivas på unikt sätt b ortsett från ordningen som en produkt av disjunkta
cykler. Vårt exempel ovan inses lätt få representationen (12465)(3) (ofta utesluter
man cykler av längd 1, dessa motsvaras av fixpunkter). Till varje p e rmutation as -
socieras en cykelstruktur,detta är ingenting annat än en partition av talet n där
varje summand ger längden på en cykel. En mycket viktig operation inom grup-
pteori är konjugationer. Man säger att elementet στσ
−1
är konjugatet av τ med
avseende på σ. Konjugatet av en cykel (xyz . . . ) blir då (σ(x)σ(y)σ(z) . . . ) (jmfr
(8) s. 27 nederst på sidan). Vi inser att cykelstrukturen hos ett element inte ändras
under konjugering. Omvänt är det lätt att visa att två permutationer med samma
cykelstruktur är konjugerade.
