A cyclic number is an integer in which cyclic permutations of the digits are successive multiples of the number. The most widely known is 142857:
Contents
142857 × 1 = 142857142857 × 2 = 285714142857 × 3 = 428571142857 × 4 = 571428142857 × 5 = 714285142857 × 6 = 857142Details
To qualify as a cyclic number, it is required that consecutive multiples be cyclic permutations. Thus, the number 076923 would not be considered a cyclic number, because even though all cyclic permutations are multiples, they are not consecutive integer multiples:
076923 × 1 = 076923076923 × 3 = 230769076923 × 4 = 307692076923 × 9 = 692307076923 × 10 = 769230076923 × 12 = 923076The following trivial cases are typically excluded:
- single digits, e.g.: 5
- repeated digits, e.g.: 555
- repeated cyclic numbers, e.g.: 142857142857
If leading zeros are not permitted on numerals, then 142857 is the only cyclic number in decimal, due to the necessary structure given in the next section. Allowing leading zeros, the sequence of cyclic numbers begins:
(106-1) / 7 = 142857 (6 digits)(1016-1) / 17 = 0588235294117647 (16 digits)(1018-1) / 19 = 052631578947368421 (18 digits)(1022-1) / 23 = 0434782608695652173913 (22 digits)(1028-1) / 29 = 0344827586206896551724137931 (28 digits)(1046-1) / 47 = 0212765957446808510638297872340425531914893617 (46 digits)(1058-1) / 59 = 0169491525423728813559322033898305084745762711864406779661 (58 digits)(1060-1) / 61 = 016393442622950819672131147540983606557377049180327868852459 (60 digits)(1096-1) / 97 = 010309278350515463917525773195876288659793814432989690721649484536082474226804123711340206185567 (96 digits)Relation to repeating decimals
Cyclic numbers are related to the recurring digital representations of unit fractions. A cyclic number of length L is the digital representation of
1/(L + 1).Conversely, if the digital period of 1 /p (where p is prime) is
p − 1,then the digits represent a cyclic number.
For example:
1/7 = 0.142857 142857….Multiples of these fractions exhibit cyclic 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 of cyclic numbers
From the relation to unit fractions, it can be shown that cyclic numbers are of the form of the Fermat quotient
where b is the number base (10 for decimal), and p is a prime that does not divide b. (Primes p that give cyclic numbers in base b are called full reptend primes or long primes in base b).
For example, the case b = 10, p = 7 gives the cyclic number 142857, and the case b = 12, p = 5 gives the cyclic number 2497.
Not all values of p will yield a cyclic number using this formula; for example, the case b = 10, p = 13 gives 076923076923, and the case b = 12, p = 19 gives 076B45076B45076B45. These failed cases will always contain a repetition of digits (possibly several).
The first values of p for which this formula produces cyclic numbers in decimal (b = 10) are (sequence A001913 in the 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, …For b = 12 (duodecimal), these ps are (sequence A019340 in the 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, ...For b = 2 (binary), these ps are (sequence A001122 in the 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, ...For b = 3 (ternary), these ps are (sequence A019334 in the 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, ...There are no such ps in the hexadecimal system.
The known pattern to this sequence comes from algebraic number theory, specifically, this sequence is the set of primes p such that b is a primitive root modulo p. A conjecture of Emil Artin is that this sequence contains 37.395..% of the primes (for b in A085397).
Construction of cyclic numbers
Cyclic numbers can be constructed by the following procedure:
Let b be the number base (10 for decimal)
Let p be a prime that does not divide b.
Let t = 0.
Let r = 1.
Let n = 0.
loop:
if t = p − 1 then n is a cyclic number.
This procedure works by computing the digits of 1 /p in base b, by long division. r is the remainder at each step, and d is the digit produced.
The step
n = n · b + dserves simply to collect the digits. For computers not capable of expressing very large integers, the digits may be output or collected in another way.
Note that if t ever exceeds p/2, then the number must be cyclic, without the need to compute the remaining digits.
Properties of cyclic numbers
Other numeric bases
Using the above technique, cyclic numbers can be found in other numeric bases. (Note that not all of these follow the second rule (all successive multiples being cyclic permutations) listed in the Special Cases section above) In each of these cases the digits across half the period add up to the base minus one. Thus for binary the sum of the bits across half the period is 1; for ternary it is 2, and so on.
In binary, the sequence of cyclic numbers begins: (sequence A001122 in the OEIS)
11 (3) → 01101 (5) → 00111011 (11) → 00010111011101 (13) → 00010011101110011 (19) → 00001101011110010111101 (29) → 0000100011010011110111001011100101 (37) → 000001101110101100111110010001010011In ternary: (sequence A019334 in the OEIS)
2 (2) → 112 (5) → 012121 (7) → 010212122 (17) → 0011202122110201201 (19) → 0011021002211201221002 (29) → 00022101020111222001212021111011 (31) → 000212111221020222010111001202In quaternary:
(none)In quinary: (sequence A019335 in the OEIS)
2 (2) → 23 (3) → 1312 (7) → 03241232 (17) → 012134024323104243 (23) → 0102041332143424031123122 (37) → 003142122040113342441302322404331102133 (43) → 002423141223434043111442021303221010401333In senary: (sequence A167794 in the OEIS)
15 (11) → 031345242121 (13) → 02434053121525 (17) → 0204122453514331105 (41) → 0051335412440330234455042201431152253211135 (59) → 0033544402235104134324250301455220111533204514212313052541141 (61) → 003312504044154453014342320220552243051511401102541213235335211 (79) → 002422325434441304033512354102140052450553133230121114251522043201453415503105In base 7: (sequence A019337 in the OEIS)
2 (2) → 35 (5) → 125414 (11) → 043116235516 (13) → 03524563142123 (17) → 026114346405523232 (23) → 020625113436460415532356 (41) → 0112363262135202250565543034045314644161In octal: (sequence A019338 in the OEIS)
3 (3) → 255 (5) → 146313 (11) → 056427213535 (29) → 021517345410647562604323671365 (53) → 011522071754533614046510347662557060232441637312674373 (59) → 0105330745756511606404255436276724470320212661713735223415123 (83) → 0061262710366576352321570224030531344173277165150674112014254562075537472464336045In nonary:
2 (2) → 4(no others)In base 11: (sequence A019339 in the OEIS)
2 (2) → 53 (3) → 3712 (13) → 093425A1768516 (17) → 07132651A397845921 (23) → 05296243390A581486771A27 (29) → 04199534608387A69115764A272329 (31) → 039A32146818574A71078964292536In duodecimal: (sequence A019340 in the OEIS)
5 (5) → 24977 (7) → 186A3515 (17) → 08579214B36429A727 (31) → 0478AA093598166B74311B28623A5535 (41) → 036190A653277397A9B4B85A2B1568944824120737 (43) → 0342295A3AA730A068456B879926181148B1B5376545 (53) → 02872B3A23205525A784640AA4B9349081989B6696143757B117In base 13: (sequence A019341 in the OEIS)
2 (2) → 65 (5) → 27A5B (11) → 12495BA83716 (19) → 08B82976AC414A356225 (31) → 055B42692C21347C7718A63A0AB9852B (37) → 0474BC3B3215368A25C85810919AB79642A732 (41) → 04177C08322B13645926C8B550C49AA1B96873A6In base 14: (sequence A019342 in the OEIS)
3 (3) → 4913 (17) → 0B75A9C4D268341915 (19) → 0A45C7522D398168BB19 (23) → 0874391B7CAD569A4C261321 (29) → 06A89925B163C0D73544B82C7A1D3B (53) → 039AB8A075793610B146C21828DA43253D6864A7CD2C971BC5B543 (59) → 03471937B8ACB5659A2BC15D09D74DA96C4A62531287843B21C80D4069In base 15: (sequence A019343 in the OEIS)
2 (2) → 7D (13) → 124936DCA5B814 (19) → 0BC9718A3E3257D64B18 (23) → 09BB1487291E533DA67C5D1E (29) → 07B5A528BD6ACDE73949C631842127 (37) → 061339AE2C87A8194CE8DBB540C26746D5A22B (41) → 0574B51C68BA922DD80AE97A39D286345CC116E4In hexadecimal:
(none)In base 17: (sequence A019344 in the OEIS)
2 (2) → 83 (3) → 5B5 (5) → 36DA7 (7) → 274E9CB (11) → 194ADF7C6316 (23) → 0C9A5F8ED52G476B1823BE1E (31) → 09583E469EDC11AG7B8D2CA7234FF6In base 18: (sequence A019345 in the OEIS)
5 (5) → 3AE7B (11) → 1B834H69ED1B (29) → 0B31F95A9GDAE4H6EG28C781463D21 (37) → 08DB37565F184FA3G0H946EACBC2G9D27E1H27 (43) → 079B57H2GD721C293DEBCHA86CA0F14AFG5F8E43652H (53) → 0620C41682CG57EAFB3D4788EGHBFH5DGB9F51CA3726E4DA993135 (59) → 058F4A6CEBAC3BG30G89DD227GE0AHC92D7B53675E61EH19844FFA13H7In base 19: (sequence A019346 in the OEIS)
2 (2) → 97 (7) → 2DAG58B (11) → 1DFA6H538CD (13) → 18EBD2HA475G14 (23) → 0FD4291C784I35EG9H6BAE1A (29) → 0C89FDE7G73HD1I6A9354B2BF15H1I (37) → 09E73B5C631A52AEGHI94BF7D6CFH8DG8421In base 20: (sequence A019347 in the OEIS)
3 (3) → 6DD (13) → 1AF7DGI94C63H (17) → 13ABF5HCIG984E2713 (23) → 0H7GA8DI546J2C39B61EFD1H (37) → 0AG469EBHGF2E11C8CJ93FDA58234H5II7B723 (43) → 0960IC1H43E878GEHD9F6JADJ17I2FG5BCB3526A4D27 (47) → 08A4522B15ACF67D3GBI5J2JB9FEHH8IE974DC6G381E0HIn base 21: (sequence A019348 in the OEIS)
2 (2) → AJ (19) → 1248HE7F9JIGC36D5B12 (23) → 0J3DECG92FAK1H7684BI5A18 (29) → 0F475198EA2IH7K5GDFJBC6AI23D1A (31) → 0E4FC4179A382EIK6G58GJDBAHCI622B (53) → 086F9AEDI4FHH927J8F13K47B1KCE5BA672G533BID1C5JH0GD9J38 (71) → 06493BB50C8I721A13HFE42K27EA785J4F7KEGBH99FK8C2DIJAJH356GI0ID6ADCF1G5DIn base 22: (sequence A019349 in the OEIS)
5 (5) → 48HDH (17) → 16A7GI2CKFBE53J9J (19) → 13A95H826KIBCG4DJF19 (31) → 0FDAE45EJJ3C194L68B7HG722I9KCH1F (37) → 0D1H57G143CAFA2872L8K4GE5KHI9B6BJDEJ1J (41) → 0BHFC7B5JIH3GDKK8CJ6LA469EAG234I5811D92F23 (47) → 0A6C3G897L18JEB5361J44ELBF9I5DCE0KD27AGIFK2HH7In base 23: (sequence A019350 in the OEIS)
2 (2) → B3 (3) → 7F5 (5) → 4DI9H (17) → 182G59AILEK6HDC421 (47) → 0B5K1AHE496JD4KCGEFF3L0MBH2LC58IDG39I2A6877J1M2D (59) → 08M51CJK65AC1LJ27I79846E9H3BFME0HLA32GHCAL13KF4FDEIG8D5JB73K (89) → 05LG6ADG0BK9CL4910HJ2J8I21CF5FHD4327B8C3864EMH16GC96MB2DA1IDLM53K3E4KLA7H759IJKFBEAJEGI8In base 24: (sequence A019351 in the OEIS)
7 (7) → 3A6KDHB (11) → 248HALJF6DD (13) → 1L795CM3GEIBH (17) → 19L45FCGME2JI8B717 (31) → 0IDMAK327HJ8C96N5A1D3KLG64FBEH1D (37) → 0FDEM1735K2E6BG54CN8A91MGKI3L9HC7IJB1H (41) → 0E14284G98IHDB2M5KBGN9MJLFJ7EF56ACL1I3C7In base 25:
2 (2) → C(no others)Note that in ternary (b = 3), the case p = 2 yields 1 as a cyclic number. While single digits may be considered trivial cases, it may be useful for completeness of the theory to consider them only when they are generated in this way.
It can be shown that no cyclic numbers (other than trivial single digits) exist in any numeric base which is a perfect square, that is, base 4, 9, 16, 25, etc.