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:
(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, …
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 ä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
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, Wells, David; "The Penguin Dictionary of Curious and Interesting Numbers", Penguin Press.
Externa länkar
Youtube: "Cyclic Numbers - Numberphile"
Kategori:Talteori Kategori:Permutationer