Cyclic number

Details

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 = 076923 076923 × 3 = 230769 076923 × 4 = 307692 076923 × 9 = 692307 076923 × 10 = 769230 076923 × 12 = 923076

The following trivial cases are typically excluded:

1. single digits, e.g.: 5
2. repeated digits, e.g.: 555
3. 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:

(10⁶-1) / 7 = 142857 (6 digits) (10¹⁶-1) / 17 = 0588235294117647 (16 digits) (10¹⁸-1) / 19 = 052631578947368421 (18 digits) (10²²-1) / 23 = 0434782608695652173913 (22 digits) (10²⁸-1) / 29 = 0344827586206896551724137931 (28 digits) (10⁴⁶-1) / 47 = 0212765957446808510638297872340425531914893617 (46 digits) (10⁵⁸-1) / 59 = 0169491525423728813559322033898305084745762711864406779661 (58 digits) (10⁶⁰-1) / 61 = 016393442622950819672131147540983606557377049180327868852459 (60 digits) (10⁹⁶-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

b p − 1 − 1 p

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:

Let t = t + 1 Let x = r · b Let d = int(x / p) Let r = x mod p Let n = n · b + d If r ≠ 1 then repeat the 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 + d

serves 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

When multiplied by their generating prime, results in a sequence of 'base−1' digits (9 in decimal). Decimal 142857 × 7 = 999999.

When split in two,three four etc...regarding base 10,100,1000 etc.. by its digits and added the result is a sequence of 9's. 14 + 28 + 57 = 99, 142 + 857 = 999, 1428 + 5714+ 2857 = 9999 etc. ... (This is a special case of Midy's Theorem.)

All cyclic numbers are divisible by 'base−1' (9 in decimal) and the sum of the remainder is the a multiple of the divisor. (This follows from the previous point.)

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) → 01 101 (5) → 0011 1011 (11) → 0001011101 1101 (13) → 000100111011 10011 (19) → 000011010111100101 11101 (29) → 0000100011010011110111001011 100101 (37) → 000001101110101100111110010001010011

In ternary: (sequence A019334 in the OEIS)

2 (2) → 1 12 (5) → 0121 21 (7) → 010212 122 (17) → 0011202122110201 201 (19) → 001102100221120122 1002 (29) → 0002210102011122200121202111 1011 (31) → 000212111221020222010111001202

In quaternary:

(none)

In quinary: (sequence A019335 in the OEIS)

2 (2) → 2 3 (3) → 13 12 (7) → 032412 32 (17) → 0121340243231042 43 (23) → 0102041332143424031123 122 (37) → 003142122040113342441302322404331102 133 (43) → 002423141223434043111442021303221010401333

In senary: (sequence A167794 in the OEIS)

15 (11) → 0313452421 21 (13) → 024340531215 25 (17) → 0204122453514331 105 (41) → 0051335412440330234455042201431152253211 135 (59) → 0033544402235104134324250301455220111533204514212313052541 141 (61) → 003312504044154453014342320220552243051511401102541213235335 211 (79) → 002422325434441304033512354102140052450553133230121114251522043201453415503105

In base 7: (sequence A019337 in the OEIS)

2 (2) → 3 5 (5) → 1254 14 (11) → 0431162355 16 (13) → 035245631421 23 (17) → 0261143464055232 32 (23) → 0206251134364604155323 56 (41) → 0112363262135202250565543034045314644161

In octal: (sequence A019338 in the OEIS)

3 (3) → 25 5 (5) → 1463 13 (11) → 0564272135 35 (29) → 0215173454106475626043236713 65 (53) → 0115220717545336140465103476625570602324416373126743 73 (59) → 0105330745756511606404255436276724470320212661713735223415 123 (83) → 0061262710366576352321570224030531344173277165150674112014254562075537472464336045

In nonary:

2 (2) → 4 (no others)

In base 11: (sequence A019339 in the OEIS)

2 (2) → 5 3 (3) → 37 12 (13) → 093425A17685 16 (17) → 07132651A3978459 21 (23) → 05296243390A581486771A 27 (29) → 04199534608387A69115764A2723 29 (31) → 039A32146818574A71078964292536

In duodecimal: (sequence A019340 in the OEIS)

5 (5) → 2497 7 (7) → 186A35 15 (17) → 08579214B36429A7 27 (31) → 0478AA093598166B74311B28623A55 35 (41) → 036190A653277397A9B4B85A2B15689448241207 37 (43) → 0342295A3AA730A068456B879926181148B1B53765 45 (53) → 02872B3A23205525A784640AA4B9349081989B6696143757B117

In base 13: (sequence A019341 in the OEIS)

2 (2) → 6 5 (5) → 27A5 B (11) → 12495BA837 16 (19) → 08B82976AC414A3562 25 (31) → 055B42692C21347C7718A63A0AB985 2B (37) → 0474BC3B3215368A25C85810919AB79642A7 32 (41) → 04177C08322B13645926C8B550C49AA1B96873A6

In base 14: (sequence A019342 in the OEIS)

3 (3) → 49 13 (17) → 0B75A9C4D2683419 15 (19) → 0A45C7522D398168BB 19 (23) → 0874391B7CAD569A4C2613 21 (29) → 06A89925B163C0D73544B82C7A1D 3B (53) → 039AB8A075793610B146C21828DA43253D6864A7CD2C971BC5B5 43 (59) → 03471937B8ACB5659A2BC15D09D74DA96C4A62531287843B21C80D4069

In base 15: (sequence A019343 in the OEIS)

2 (2) → 7 D (13) → 124936DCA5B8 14 (19) → 0BC9718A3E3257D64B 18 (23) → 09BB1487291E533DA67C5D 1E (29) → 07B5A528BD6ACDE73949C6318421 27 (37) → 061339AE2C87A8194CE8DBB540C26746D5A2 2B (41) → 0574B51C68BA922DD80AE97A39D286345CC116E4

In hexadecimal:

(none)

In base 17: (sequence A019344 in the OEIS)

2 (2) → 8 3 (3) → 5B 5 (5) → 36DA 7 (7) → 274E9C B (11) → 194ADF7C63 16 (23) → 0C9A5F8ED52G476B1823BE 1E (31) → 09583E469EDC11AG7B8D2CA7234FF6

In base 18: (sequence A019345 in the OEIS)

5 (5) → 3AE7 B (11) → 1B834H69ED 1B (29) → 0B31F95A9GDAE4H6EG28C781463D 21 (37) → 08DB37565F184FA3G0H946EACBC2G9D27E1H 27 (43) → 079B57H2GD721C293DEBCHA86CA0F14AFG5F8E4365 2H (53) → 0620C41682CG57EAFB3D4788EGHBFH5DGB9F51CA3726E4DA9931 35 (59) → 058F4A6CEBAC3BG30G89DD227GE0AHC92D7B53675E61EH19844FFA13H7

In base 19: (sequence A019346 in the OEIS)

2 (2) → 9 7 (7) → 2DAG58 B (11) → 1DFA6H538C D (13) → 18EBD2HA475G 14 (23) → 0FD4291C784I35EG9H6BAE 1A (29) → 0C89FDE7G73HD1I6A9354B2BF15H 1I (37) → 09E73B5C631A52AEGHI94BF7D6CFH8DG8421

In base 20: (sequence A019347 in the OEIS)

3 (3) → 6D D (13) → 1AF7DGI94C63 H (17) → 13ABF5HCIG984E27 13 (23) → 0H7GA8DI546J2C39B61EFD 1H (37) → 0AG469EBHGF2E11C8CJ93FDA58234H5II7B7 23 (43) → 0960IC1H43E878GEHD9F6JADJ17I2FG5BCB3526A4D 27 (47) → 08A4522B15ACF67D3GBI5J2JB9FEHH8IE974DC6G381E0H

In base 21: (sequence A019348 in the OEIS)

2 (2) → A J (19) → 1248HE7F9JIGC36D5B 12 (23) → 0J3DECG92FAK1H7684BI5A 18 (29) → 0F475198EA2IH7K5GDFJBC6AI23D 1A (31) → 0E4FC4179A382EIK6G58GJDBAHCI62 2B (53) → 086F9AEDI4FHH927J8F13K47B1KCE5BA672G533BID1C5JH0GD9J 38 (71) → 06493BB50C8I721A13HFE42K27EA785J4F7KEGBH99FK8C2DIJAJH356GI0ID6ADCF1G5D

In base 22: (sequence A019349 in the OEIS)

5 (5) → 48HD H (17) → 16A7GI2CKFBE53J9 J (19) → 13A95H826KIBCG4DJF 19 (31) → 0FDAE45EJJ3C194L68B7HG722I9KCH 1F (37) → 0D1H57G143CAFA2872L8K4GE5KHI9B6BJDEJ 1J (41) → 0BHFC7B5JIH3GDKK8CJ6LA469EAG234I5811D92F 23 (47) → 0A6C3G897L18JEB5361J44ELBF9I5DCE0KD27AGIFK2HH7

In base 23: (sequence A019350 in the OEIS)

2 (2) → B 3 (3) → 7F 5 (5) → 4DI9 H (17) → 182G59AILEK6HDC4 21 (47) → 0B5K1AHE496JD4KCGEFF3L0MBH2LC58IDG39I2A6877J1M 2D (59) → 08M51CJK65AC1LJ27I79846E9H3BFME0HLA32GHCAL13KF4FDEIG8D5JB7 3K (89) → 05LG6ADG0BK9CL4910HJ2J8I21CF5FHD4327B8C3864EMH16GC96MB2DA1IDLM53K3E4KLA7H759IJKFBEAJEGI8

In base 24: (sequence A019351 in the OEIS)

7 (7) → 3A6KDH B (11) → 248HALJF6D D (13) → 1L795CM3GEIB H (17) → 19L45FCGME2JI8B7 17 (31) → 0IDMAK327HJ8C96N5A1D3KLG64FBEH 1D (37) → 0FDEM1735K2E6BG54CN8A91MGKI3L9HC7IJB 1H (41) → 0E14284G98IHDB2M5KBGN9MJLFJ7EF56ACL1I3C7

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