Cyklické číslo - Cyclic number

A cyklické číslo je celé číslo ve kterém cyklické permutace číslic je postupných celočíselné násobky čísla. Nejznámější je šestimístné číslo 142857, jehož prvních šest celočíselných násobků je

142857 × 1 = 142857

142857 × 2 = 285714

142857 × 3 = 428571

142857 × 4 = 571428

142857 × 5 = 714285

142857 × 6 = 857142

Detaily

Chcete-li se kvalifikovat jako cyklické číslo, je nutné, aby po sobě jdoucí násobky byly cyklické permutace. Číslo 076923 by tedy nebylo považováno za cyklické číslo, protože i když jsou všechny cyklické obměny násobky, nejedná se o po sobě jdoucí celočíselné násobky:

076923 × 1 = 076923

076923 × 3 = 230769

076923 × 4 = 307692

076923 × 9 = 692307

076923 × 10 = 769230

076923 × 12 = 923076

Následující triviální případy jsou obvykle vyloučeny:

1. jednotlivé číslice, např .: 5
2. opakované číslice, např .: 555
3. opakovaná cyklická čísla, např .: 142857142857

Pokud úvodní nuly nejsou povoleny na číslicích, pak 142857 je jediné cyklické číslo v desetinný, vzhledem k nezbytné struktuře uvedené v následující části. Po povolení úvodních nul začíná posloupnost cyklických čísel:

(10⁶ − 1) / 7 = 142857 (6 číslic)

(10¹⁶ − 1) / 17 = 0588235294117647 (16 číslic)

(10¹⁸ − 1) / 19 = 052631578947368421 (18 číslic)

(10²² − 1) / 23 = 0434782608695652173913 (22 číslic)

(10²⁸ − 1) / 29 = 0344827586206896551724137931 (28 číslic)

(10⁴⁶ − 1) / 47 = 0212765957446808510638297872340425531914893617 (46 číslic)

(10⁵⁸ − 1) / 59 = 0169491525423728813559322033898305084745762711864406779661 (58 číslic)

(10⁶⁰ − 1) / 61 = 016393442622950819672131147540983606557377049180327868852459 (60 číslic)

(10⁹⁶ − 1) / 97 = 010309278350515463917525773195876288659793814432989690721649484536082474226804123711340206185567 (96 číslic)

Vztah k opakujícím se desetinným místům

Cyklická čísla souvisejí s opakující se digitální reprezentace z jednotkové zlomky. Cyklické číslo délky L je digitální reprezentace

1/(L + 1).

Naopak, pokud digitální období 1 /p (kde p je primární ) je

p − 1,

pak číslice představují cyklické číslo.

Například:

1/7 = 0.142857 142857...

Násobky těchto frakcí vykazují cyklickou permutaci:

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...

Forma cyklických čísel

Ze vztahu k jednotkovým zlomkům lze ukázat, že cyklická čísla mají tvar Fermatův kvocient

${ displaystyle { frac {b ^ {p-1} -1} {p}}}$

kde b je číselná základna (10 pro desetinný ), a p je primární to není rozdělit b. (Připraví p které dávají cyklická čísla v základu b jsou nazývány plný reptend připraví nebo dlouhé prvočísla v základně b).

Například případ b = 10, p = 7 dává cyklické číslo 142857 a případ b = 12, p = 5 dává cyklické číslo 2497.

Ne všechny hodnoty p získá cyklické číslo pomocí tohoto vzorce; například případ b = 10, p = 13 dává 076923076923 a případ b = 12, p = 19 dává 076B45076B45076B45. Tyto neúspěšné případy budou vždy obsahovat opakování číslic (možná několik).

První hodnoty p pro které tento vzorec vytváří cyklická čísla v desetinný (b = 10) jsou (sekvence A001913 v OEIS )

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, ...

Pro b = 12 (duodecimální ), tyto ps jsou (sekvence A019340 v OEIS )

5, 7, 17, 31, 41, 43, 53, 67, 101, 103, 113, 127, 137, 139, 149, 151, 163, 173, 197, 223, 257, 269, 281, 283, 293, 317, 353, 367, 379, 389, 401, 449, 461, 509, 523, 547, 557, 569, 571, 593, 607, 617, 619, 631, 641, 653, 691, 701, 739, 751, 761, 773, 787, 797, 809, 821, 857, 881, 929, 953, 967, 977, 991, ...

Pro b = 2 (binární ), tyto ps jsou (sekvence A001122 v OEIS )

3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107, 131, 139, 149, 163, 173, 179, 181, 197, 211, 227, 269, 293, 317, 347, 349, 373, 379, 389, 419, 421, 443, 461, 467, 491, 509, 523, 541, 547, 557, 563, 587, 613, 619, 653, 659, 661, 677, 701, 709, 757, 773, 787, 797, 821, 827, 829, 853, 859, 877, 883, 907, 941, 947, ...

Pro b = 3 (trojice ), tyto ps jsou (sekvence A019334 v OEIS )

2, 5, 7, 17, 19, 29, 31, 43, 53, 79, 89, 101, 113, 127, 137, 139, 149, 163, 173, 197, 199, 211, 223, 233, 257, 269, 281, 283, 293, 317, 331, 353, 379, 389, 401, 449, 461, 463, 487, 509, 521, 557, 569, 571, 593, 607, 617, 631, 641, 653, 677, 691, 701, 739, 751, 773, 797, 809, 811, 821, 823, 857, 859, 881, 907, 929, 941, 953, 977, ...

Žádní takoví nejsou pje v hexadecimální Systém.

Známý vzor této sekvence pochází z algebraická teorie čísel, konkrétně, tato sekvence je sada prvočísel p takhle b je primitivní root modulo p. A dohad Emila Artina^[1] je, že tato sekvence obsahuje 37 395 ..% prvočísel (pro b v OEIS: A085397).

Konstrukce cyklických čísel

Cyklická čísla lze sestrojit následovně postup:

Nechat b být číselná základna (10 pro desetinná místa)
Nechat p být prime, který se nerozdělí b.
Nechat t = 0.
Nechat r = 1.
Nechat n = 0.
smyčka:

Nechat t = t + 1

Nechat X = r · b

Nechat d = int (X / p)

Nechat r = X mod p

Nechat n = n · b + d

Li r ≠ 1 a poté opakujte smyčku.

-li t = p - 1 tedy n je cyklické číslo.

Tento postup funguje výpočtem číslic 1 /p v základně btím, že dlouhé rozdělení. r je zbytek v každém kroku a d je vytvořená číslice.

Krok

n = n · b + d

slouží pouze ke sběru číslic. U počítačů, které nejsou schopné vyjádřit velmi velká celá čísla, mohou být číslice vydávány nebo shromažďovány jiným způsobem.

Li t kdy překročí p/ 2, pak číslo musí být cyklické, aniž by bylo nutné počítat zbývající číslice.

Vlastnosti cyklických čísel

• Po vynásobení jejich generujícím prvočíslem je výsledkem posloupnost b - 1 číslice, kde b je základ (např. 9 v desítkové soustavě). Například v desítkové soustavě 142857 × 7 = 999999.
• Když se rozdělí do dvou, tří, čtyř atd. Číslic a skupiny se přidají, výsledkem bude sekvence 9 s. Například 14 + 28 + 57 = 99, 142 + 857 = 999, 1428 + 5714+ 2857 = 9999 atd. ... Toto je speciální případ Midyho věta.
• Všechna cyklická čísla jsou dělitelná b - 1 kde b je základ (např. 9 v desítkové soustavě) a součet zbytku je násobkem dělitele. (To vyplývá z předchozího bodu.)

Další číselné báze

Pomocí výše uvedené techniky lze cyklická čísla nalézt v jiných numerických základnách. (Ne všechny z nich se řídí druhým pravidlem (všechny po sobě jdoucí násobky jsou cyklické permutace) uvedené v části Zvláštní případy výše) V každém z těchto případů se číslice v polovině období sečtou k základnímu minus jednomu. Pro binární tedy je součet bitů v polovině periody 1; pro ternární je to 2 atd.

v binární začíná sekvence cyklických čísel: (sekvence A001122 v OEIS )

11 (3) → 01

101 (5) → 0011

1011 (11) → 0001011101

1101 (13) → 000100111011

10011 (19) → 000011010111100101

11101 (29) → 0000100011010011110111001011

100101 (37) → 00000110101011100101111100101010001101

110101 (53) → 00000100101101001111001001101101111101101001011000011011001001

v trojice: (sekvence A019334 v OEIS )

2 (2) → 1

12 (5) → 0121

21 (7) → 010212

122 (17) → 0011202122110201

201 (19) → 001102100221120122

v kvartérní:

(žádný)

v quinární: (sekvence A019335 v OEIS )

2 (2) → 2

3 (3) → 13

12 (7) → 032412

32 (17) → 0121340243231042

43 (23) → 0102041332143424031123

122 (37) → 003142122040113342441302322404331102

133 (43) → 002423141223434043111442021303221010401333

v senary: (sekvence A167794 v OEIS )

15 (11) → 0313452421

21 (13) → 024340531215

25 (17) → 0204122453514331

105 (41) → 0051335412440330234455042201431152253211

135 (59) → 0033544402235104134324250301455220111533204514212313052541

141 (61) → 003312504044154453014342320220552243051511401102541213235335

211 (79) → 002422325434441304033512354102140052450553133230121114251522043201453415503105

V základně 7: (sekvence A019337 v OEIS )

2 (2) → 3

5 (5) → 1254

14 (11) → 0431162355

16 (13) → 035245631421

23 (17) → 0261143464055232

32 (23) → 0206251134364604155323

56 (41) → 0112363262135202250565543034045314644161

v osmičkový: (sekvence A019338 v OEIS )

3 (3) → 25

5 (5) → 1463

13 (11) → 0564272135

35 (29) → 0215173454106475626043236713

65 (53) → 0115220717545336140465103476625570602324416373126743

73 (59) → 0105330745756511606404255436276724470320212661713735223415

123 (83) → 0061262710366576352321570224030531344173277165150674112014254562075537472464336045

v notář:

2 (2) → 4

(žádné další)

V základně 11: (sekvence A019339 v OEIS )

2 (2) → 5

3 (3) → 37

12 (13) → 093425A17685

16 (17) → 07132651A3978459

21 (23) → 05296243390A581486771A

27 (29) → 04199534608387A69115764A2723

29 (31) → 039A32146818574A71078964292536

v duodecimální: (sekvence A019340 v OEIS )

5 (5) → 2497

7 (7) → 186A35

15 (17) → 08579214B36429A7

27 (31) → 0478AA093598166B74311B28623A55

35 (41) → 036190A653277397A9B4B85A2B15689448241207

37 (43) → 0342295A3AA730A068456B879926181148B1B53765

45 (53) → 02872B3A23205525A784640AA4B9349081989B6696143757B117

V základně 13: (sekvence A019341 v OEIS )

2 (2) → 6

5 (5) → 27A5

B (11) → 12495BA837

16 (19) → 08B82976AC414A3562

25 (31) → 055B42692C21347C7718A63A0AB985

2B (37) → 0474BC3B3215368A25C85810919AB79642A7

32 (41) → 04177C08322B13645926C8B550C49AA1B96873A6

V základně 14: (sekvence A019342 v OEIS )

3 (3) → 49

13 (17) → 0B75A9C4D2683419

15 (19) → 0A45C7522D398168BB

19 (23) → 0874391B7CAD569A4C2613

21 (29) → 06A89925B163C0D73544B82C7A1D

3B (53) → 039AB8A075793610B146C21828DA43253D6864A7CD2C971BC5B5

43 (59) → 03471937B8ACB5659A2BC15D09D74DA96C4A62531287843B21C80D4069

V základně 15: (sekvence A019343 v OEIS )

2 (2) → 7

D (13) → 124936DCA5B8

14 (19) → 0BC9718A3E3257D64B

18 (23) → 09BB1487291E533DA67C5D

1E (29) → 07B5A528BD6ACDE73949C6318421

27 (37) → 061339AE2C87A8194CE8DBB540C26746D5A2

2B (41) → 0574B51C68BA922DD80AE97A39D286345CC116E4

v hexadecimální:

(žádný)

V základně 17: (sekvence A019344 v OEIS )

2 (2) → 8

3 (3) → 5B

5 (5) → 36DA

7 (7) → 274E9C

B (11) → 194ADF7C63

16 (23) → 0C9A5F8ED52G476B1823BE

1E (31) → 09583E469EDC11AG7B8D2CA7234FF6

V základně 18: (sekvence A019345 v OEIS )

5 (5) → 3AE7

B (11) → 1B834H69ED

1B (29) → 0B31F95A9GDAE4H6EG28C781463D

21 (37) → 08DB37565F184FA3G0H946EACBC2G9D27E1H

27 (43) → 079B57H2GD721C293DEBCHA86CA0F14AFG5F8E4365

2H (53) → 0620C41682CG57EAFB3D4788EGHBFH5DGB9F51CA3726E4DA9931

35 (59) → 058F4A6CEBAC3BG30G89DD227GE0AHC92D7B53675E61EH19844FFA13H7

V základně 19: (sekvence A019346 v OEIS )

2 (2) → 9

7 (7) → 2DAG58

B (11) → 1DFA6H538C

D (13) → 18EBD2HA475G

14 (23) → 0FD4291C784I35EG9H6BAE

1A (29) → 0C89FDE7G73HD1I6A9354B2BF15H

1I (37) → 09E73B5C631A52AEGHI94BF7D6CFH8DG8421

v základna 20: (sekvence A019347 v OEIS )

3 (3) → 6D

D (13) → 1AF7DGI94C63

H (17) → 13ABF5HCIG984E27

13 (23) → 0H7GA8DI546J2C39B61EFD

1H (37) → 0AG469EBHGF2E11C8CJ93FDA58234H5II7B7

23 (43) → 0960IC1H43E878GEHD9F6JADJ17I2FG5BCB3526A4D

27 (47) → 08A4522B15ACF67D3GBI5J2JB9FEHH8IE974DC6G381E0H

V základně 21: (sekvence A019348 v OEIS )

2 (2) → A

J (19) → 1248HE7F9JIGC36D5B

12 (23) → 0J3DECG92FAK1H7684BI5A

18 (29) → 0F475198EA2IH7K5GDFJBC6AI23D

1A (31) → 0E4FC4179A382EIK6G58GJDBAHCI62

2B (53) → 086F9AEDI4FHH927J8F13K47B1KCE5BA672G533BID1C5JH0GD9J

38 (71) → 06493BB50C8I721A13HFE42K27EA785J4F7KEGBH99FK8C2DIJAJH356GI0ID6ADCF1G5D

V základně 22: (sekvence A019349 v OEIS )

5 (5) → 48HD

H (17) → 16A7GI2CKFBE53J9

J (19) → 13A95H826KIBCG4DJF

19 (31) → 0FDAE45EJJ3C194L68B7HG722I9KCH

1F (37) → 0D1H57G143CAFA2872L8K4GE5KHI9B6BJDEJ

1J (41) → 0BHFC7B5JIH3GDKK8CJ6LA469EAG234I5811D92F

23 (47) → 0A6C3G897L18JEB5361J44ELBF9I5DCE0KD27AGIFK2HH7

V základně 23: (sekvence A019350 v OEIS )

2 (2) → B

3 (3) → 7F

5 (5) → 4DI9

H (17) → 182G59AILEK6HDC4

21 (47) → 0B5K1AHE496JD4KCGEFF3L0MBH2LC58IDG39I2A6877J1M

2D (59) → 08M51CJK65AC1LJ27I79846E9H3BFME0HLA32GHCAL13KF4FDEIG8D5JB7

3K (89) → 05LG6ADG0BK9CL4910HJ2J8I21CF5FHD4327B8C3864EMH16GC96MB2DA1IDLM53K3E4KLA7H759IJKFBEAJEGI8

V základně 24: (sekvence A019351 v OEIS )

7 (7) → 3A6KDH

B (11) → 248HALJF6D

D (13) → 1L795CM3GEIB

H (17) → 19L45FCGME2JI8B7

17 (31) → 0IDMAK327HJ8C96N5A1D3KLG64FBEH

1D (37) → 0FDEM1735K2E6BG54CN8A91MGKI3L9HC7IJB

1H (41) → 0E14284G98IHDB2M5KBGN9MJLFJ7EF56ACL1I3C7

V základně 25:

2 (2) → C.

(žádné další)

V ternární (b = 3), případ p = 2 získá 1 jako cyklické číslo. Zatímco jednotlivé číslice lze považovat za triviální případy, může být užitečné pro úplnost teorie uvažovat o nich pouze v případě, že jsou generovány tímto způsobem.

Je možné ukázat, že žádná cyklická čísla (kromě triviálních jednotlivých číslic, tj. p = 2) existují v jakékoli číselné základně, která je a perfektní čtverec, tj. základna 4, 9, 16, 25 atd.

Viz také

• Opakování desetinného místa
• Fermatova malá věta
• Cyklická permutace celého čísla
• Parazitické číslo

Reference

Další čtení

• Gardner, Martin. Mathematical Circus: More Puzzles, Games, Paradoxes and Other Mathematical Entertainments from Scientific American. New York: The Mathematical Association of America, 1979. s. 111–122.
• Kalman, Dan; „Frakce s cyklickými číslicovými vzory“ The College Mathematics Journal, sv. 27, č. 2 (březen, 1996), s. 109–115.
• Leslie, John. „The Philosophy of Arithmetic: Exhibiting a Progressive View of the Theory and Practice of ....“, Longman, Hurst, Rees, Orme a Brown, 1820, ISBN  1-4020-1546-1
• Wells, David; "Slovník tučňáků zvědavých a zajímavých čísel ", Penguin Press. ISBN  0-14-008029-5

externí odkazy

• Weisstein, Eric W. „Cyklické číslo“. MathWorld.
• Youtube: „Cyklická čísla - Numberphile“