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:

  1. Ensiffriga tal (till exempel: 5)
  2. Upprepande siffror (till exempel: 555)
  3. 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:

(106−1) / 7 = 142857 (6 siffror)
(1016−1) / 17 = 0588235294117647 (16 siffror)
(1018−1) / 19 = 052631578947368421 (18 siffror)
(1022−1) / 23 = 0434782608695652173913 (22 siffror)
(1028−1) / 29 = 0344827586206896551724137931 (28 siffror)
(1046−1) / 47 = 0212765957446808510638297872340425531914893617 (46 siffror)
(1058−1) / 59 = 0169491525423728813559322033898305084745762711864406779661 (58 siffror)
(1060−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

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

  • 142857 (tal)
  • Upprepande decimal
  • Fermats lilla sats
  • Cyklisk permutation av heltal
  • Parasitiskt tal

Källor

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia, Cyclic number, 14 december 2013.
  1. ^ ”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