Cykliskt tal

Cykliskt tal är ett heltal i vilket cykliska permutationer av siffrorna är successiva multiplar av talet. Det mest kända är 142 857:

142857 × 1 = 142857

142857 × 2 = 285714

142857 × 3 = 428571

142857 × 4 = 571428

142857 × 5 = 714285

142857 × 6 = 857142

Detaljer

För att ett tal ska kunna klassificeras som cykliskt tal krävs det att successiva multiplar är cykliska permutationer. Därmed skulle talet 076923 inte betraktas som ett cyklisk tal, även om alla cykliska permutationer är multiplar:

076923 × 1 = 076923

076923 × 3 = 230769

076923 × 4 = 307692

076923 × 9 = 692307

076923 × 10 = 769230

076923 × 12 = 923076

Följande triviala fall är oftast uteslutna:

Ensiffriga tal (till exempel: 5)
Upprepande siffror (till exempel: 555)
Upprepande cykliska tal (till exempel: 142857142857)

Om inledande nollor inte är tillåtna i tal så är 142857 det enda cykliska talet i decimala talsystemet, på grund av strukturen (se nästa avsnitt). Om inledande nollor är tillåtna så är de första talen i talföljden över cykliska tal:

(10⁶−1) / 7 = 142857 (6 siffror)

(10¹⁶−1) / 17 = 0588235294117647 (16 siffror)

(10¹⁸−1) / 19 = 052631578947368421 (18 siffror)

(10²²−1) / 23 = 0434782608695652173913 (22 siffror)

(10²⁸−1) / 29 = 0344827586206896551724137931 (28 siffror)

(10⁴⁶−1) / 47 = 0212765957446808510638297872340425531914893617 (46 siffror)

(10⁵⁸−1) / 59 = 0169491525423728813559322033898305084745762711864406779661 (58 siffror)

(10⁶⁰−1) / 61 = 016393442622950819672131147540983606557377049180327868852459 (60 siffror)

Relation till upprepande decimaler

Cykliska tal är relaterade till de upprepande decimalerna i enhetsbråk. Ett cyklisk tal med längden L är den digitala representationen av

1/(L + 1).

Omvänt, om den digitala perioden av 1 /p (där p är ett primtal) är

p − 1,

så representerar siffrorna ett cykliskt tal

Till exempel:

1/7 = 0,142857 142857….

Flera av följande bråk uppvisar cyklisk permutation

1/7 = 0,142857 142857…

2/7 = 0,285714 285714…

3/7 = 0,428571 428571…

4/7 = 0,571428 571428…

5/7 = 0,714285 714285…

6/7 = 0,857142 857142….

Form av cykliska tal

Ur relation till enhetsbråk kan det visas att cykliska tal är på formen

{\frac {b^{p-1}-1}{p}}

där b är talbasen (10 för decimala talsystemet) och p är ett primtal som inte delar b. (Primtal p som ger cykliska tal kallas för fullreptenda primtal eller långa primtal).

Till exempel så ger fallet b = 10, p = 7 det cykliska talet 142857.

Inte alla värden på p kommer att ge ett cykliskt tal med denna formel, till exempel så ger p = 13 talet 076923076923. Dessa misslyckade fall kommer alltid att innehålla en upprepning av siffror (eventuellt flera).

De första värdena för p, för vilka denna formel ger cykliska tal i decimala talsystemet är:

7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193, 223, 229, 233, 257, 263, 269, 313, 337, 367, 379, 383, 389, 419, 433, 461, 487, 491, 499, 503, 509, 541, 571, 577, 593, 619, 647, 659, 701, 709, 727, 743, 811, 821, 823, 857, 863, 887, 937, 941, 953, 971, 977, 983, … (talföljd A001913 i OEIS)

Det kända mönstret till denna talföljd kommer från algebraisk talteori. Specifikt är denna talföljd är en mängd primtal p sådana att 10 är en primitiv rot modulo p.

En hypotes av Emil Artin^[1] är att denna talföljd innehåller 37,395… % av primtalen.

Konstruktion av cykliska tal

Cykliska tal kan konstrueras med följande algoritm:

Låt b vara talbasen (10 för decimala talsystemet)
Låt p vara ett primtal som inte delar b.
Låt t = 0.
Låt r = 1.
Låt n = 0.
Loop:

Låt t = t + 1

Låt x = r · b

Låt d = int(x / p)

Låt r = x mod p

Låt n = n · b + d

Om r ≠ 1, upprepa loopen.

Om t = p − 1 så är n ett cykliskt tal.

Denna algoritm fungerar genom beräkning av siffrorna i 1 /p i basen B, av lång division. r är resten vid varje steg, och d är den siffra som ges.

Steget

n = n · b + d

tjänar helt enkelt att samla in siffrorna. För datorer som inte kan uttrycka mycket stora heltal, kan siffrorna matas ut eller samlas in på annat sätt.

Observera att om t någonsin överstiger p/2 så måste talet vara cykliskt utan behov av att beräkna de återstående siffrorna.

Andra talbaser

Med användning av ovanstående teknik kan cykliska tal hittas i andra talbaser. Observera att inte alla av dessa följer den andra regeln (alla efterföljande multiplar är cykliska permutationer) som anges i specialfall-avsnittet ovan.

I binära talsystemet (bas 2) inleds följden av cykliska tal med:

11 (3) → 01

101 (5) → 0011

1011 (11) → 0001011101

1101 (13) → 000100111011

10011 (19) → 000011010111100101

I ternära talsystemet (bas 3):

12 (5) → 0121

21 (7) → 010212

122 (17) → 0011202122110201

201 (19) → 001102100221120122

1002 (29) → 0002210102011122200121202111

I kvarternära talsystemet (bas 4):

Inget

I kvinära talsystemet (bas 5):

3 (3) → 13

12 (7) → 032412

32 (17) → 0121340243231042

122 (37) → 003142122040113342441302322404331102

133 (43) → 002423141223434043111442021303221010401333

I senära talsystemet (bas 6):

15 (11) → 0313452421

21 (13) → 024340531215

25 (17) → 0204122453514331

31 (19) → 015211325015211325

105 (41) → 0051335412440330234455042201431152253211

I septenära talsystemet (bas 7):

5 (5) → 1254

14 (11) → 0431162355

16 (13) → 035245631421

23 (17) → 0261143464055232

32 (23) → 0206251134364604155323

I oktala talsystemet (bas 8):

3 (3) → 25

5 (5) → 1463

13 (11) → 0564272135

35 (29) → 0215173454106475626043236713

65 (53) → 0115220717545336140465103476625570602324416373126743

I nonära talsystemet (bas 9):

Inget

I undecimala talsystemet (bas 11):

3 (3) → 37

12 (13) → 093425A17685

16 (17) → 07132651A3978459

21 (23) → 05296243390A581486771A

27 (29) → 04199534608387A69115764A2723

I duodecimala talsystemet (bas 12):

5 (5) → 2497

7 (7) → 186A35

15 (17) → 08579214B36429A7

27 (31) → 0478AA093598166B74311B28623A55

35 (41) → 036190A653277397A9B4B85A2B15689448241207

I tridecimala talsystemet (bas 13):

5 (5) → 27A5

B (11) → 12495BA837

16 (19) → 08B82976AC414A3562

25 (31) → 055B42692C21347C7718A63A0AB985

I tetradecimala talsystemet (bas 14):

3 (3) → 49

13 (17) → 0B75A9C4D2683419

15 (19) → 0A45C7522D398168BB

I pentadecimala talsystemet (bas 15):

D (13) → 124936DCA5B8

14 (19) → 0BC9718A3E3257D64B

18 (23) → 09BB1487291E533DA67C5D

I hexadecimala talsystemet (bas 16):

Inget

I bas 17:

3 (3) → 5B

5 (5) → 36DA

7 (7) → 274E9C

B (11) → 194ADF7C63

I oktodecimala talsystemet (bas 18):

B (11) → 1B834H69ED

1B (29) → 0B31F95A9GDAE4H6EG28C781463D

21 (37) → 08DB37565F184FA3G0H946EACBC2G9D27E1H

I bas 19:

7 (7) → 2DAG58

B (11) → 1DFA6H538C

D (13) → 18EBD2HA475G

I vigesimala talsystemet (bas 20):

3 (3) → 6D

D (13) → 1AF7DGI94C63

H (17) → 13ABF5HCIG984E27

I bas 21:

J (19) → 1248HE7F9JIGC36D5B

12 (23) → 0J3DECG92FAK1H7684BI5A

18 (29) → 0F475198EA2IH7K5GDFJBC6AI23D

I bas 22:

5 (5) → 48HD

H (17) → 16A7GI2CKFBE53J9

J (17) → 13A95H826KIBCG4DJF

I bas 23:

3 (3) → 7F

5 (5) → 4DI9

H (17) → 182G59AILEK6HDC4

I tetravigesimala talsystemet (bas 24):

7 (7) → 3A6KDH

B (11) → 248HALJF6D

D (13) → 1L795CM3GEIB

H (17) → 19L45FCGME2JI8B7

Notera att i ternära talsystemet (b = 3) så ger fallet p = 2 talet 1 som cykliskt tal. Även om enstaka siffror kan anses triviala fall kan det vara användbart för fullständigheten i teorin att betrakta dem bara när de ges på detta sätt.

Man kan bevisa att inga cykliska tal (utom triviala ensiffriga tal) finns i varje talbas som är en perfekt kvadrat, och därför finns det inga cykliska tal i hexadecimala talsystemet (bas 16), kvarternära talsystemet (bas 4) och nonära talsystemet (bas 9).

Se även

Källor

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia, Cyclic number, 14 december 2013.

^ ”Artin's Constant” (på engelska). MathWorld. http://mathworld.wolfram.com/ArtinsConstant.html. Läst 14 december 2013.

Vidare läsning

Gardner, Martin. Mathematical Circus: More Puzzles, Games, Paradoxes and Other Mathematical Entertainments From Scientific American. New York: The Mathematical Association of America, 1979. pp. 111-122.
Kalman, Dan; 'Fractions with Cycling Digit Patterns' The College Mathematics Journal, Vol. 27, No. 2. (Mar., 1996), pp. 109-115.
Leslie, John. "The Philosophy of Arithmetic: Exhibiting a Progressive View of the Theory and Practice of ....", Longman, Hurst, Rees, Orme, and Brown, 1820, ISBN 1-4020-1546-1
Wells, David; "The Penguin Dictionary of Curious and Interesting Numbers", Penguin Press. ISBN 0-14-008029-5

Externa länkar

Weisstein, Eric W., "Cyclic Number", MathWorld. (engelska)
Youtube: "Cyclic Numbers - Numberphile" (engelska)

[1] ”Artin's Constant” (på engelska). MathWorld. http://mathworld.wolfram.com/ArtinsConstant.html. Läst 14 december 2013.

[1]