View source for Cyclic number

{{Short description|Integer whose multiples are digit rotations}}
{{underreferenced|date=January 2021}}
{{about|numbers where permutations of their digits (in some base) yield related numbers|the number theoretic concept|cyclic number (group theory)}}

A '''cyclic number''' is an [[integer]] for which [[cyclic permutation]]s of the digits are successive [[integer multiple]]s of the number.  The most widely known is the six-digit number [[142857 (number)|142857]], whose first six integer multiples are
:142857 &times; 1 = 142857
:142857 &times; 2 = 285714
:142857 &times; 3 = 428571
:142857 &times; 4 = 571428
:142857 &times; 5 = 714285
:142857 &times; 6 = 857142

== 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 &times; 1 = 076923
:076923 &times; 3 = 230769
:076923 &times; 4 = 307692
:076923 &times; 9 = 692307
:076923 &times; 10 = 769230
:076923 &times; 12 = 923076

The 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:

:(10<sup>6</sup> −&thinsp;1) / '''7''' = 142857 (6 digits)
:(10<sup>16</sup> −&thinsp;1) / '''17''' = 0588235294117647 (16 digits)
:(10<sup>18</sup> −&thinsp;1) / '''19''' = 052631578947368421 (18 digits)
:(10<sup>22</sup> −&thinsp;1) / '''23''' = 0434782608695652173913 (22 digits)
:(10<sup>28</sup> −&thinsp;1) / '''29''' = 0344827586206896551724137931 (28 digits)
:(10<sup>46</sup> −&thinsp;1) / '''47''' = 0212765957446808510638297872340425531914893617 (46 digits)
:(10<sup>58</sup> −&thinsp;1) / '''59''' = 0169491525423728813559322033898305084745762711864406779661 (58 digits)
:(10<sup>60</sup> −&thinsp;1) / '''61''' = 016393442622950819672131147540983606557377049180327868852459 (60 digits)
:(10<sup>96</sup> −&thinsp;1) / '''97''' = 010309278350515463917525773195876288659793814432989690721649484536082474226804123711340206185567 (96 digits)

== Relation to repeating decimals ==
Cyclic numbers are related to the [[Repeating decimal|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 number|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]]

:<math>\frac{b^{p-1}-1}{p}</math>

where ''b'' is the [[Radix|number base]] (10 for [[decimal]]), and ''p'' is a [[Prime number|prime]] that does not [[Divisor|divide]] ''b''. (Primes ''p'' that give cyclic numbers in base ''b'' are called [[full reptend prime]]s 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 {{OEIS|id=A001913}}

: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 ''p''s are {{OEIS|id=A019340}}
: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 number|binary]]), these ''p''s are {{OEIS|id=A001122}}
: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 numeral system|ternary]]), these ''p''s are {{OEIS|id=A019334}}
: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 ''p''s 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 n|primitive root modulo ''p'']]. A [[Artin's conjecture on primitive roots|conjecture of Emil Artin]]<ref>{{cite web|url=http://mathworld.wolfram.com/ArtinsConstant.html|title=Artin's Constant|first=Eric W.|last=Weisstein|website=mathworld.wolfram.com}}</ref> is that this sequence contains 37.395..% of the primes (for ''b'' in {{oeis|id=A085397}}).

== Construction of cyclic numbers ==

Cyclic numbers can be constructed by the following [[Algorithm|procedure]]:

Let ''b'' be the number base (10 for decimal)<br>
Let ''p'' be a prime that does not divide ''b''.<br>
Let ''t'' = 0.<br>
Let ''r'' = 1.<br>
Let ''n'' = 0.<br>
loop:
:Let ''t'' = ''t'' +&thinsp;1
:Let ''x'' = ''r'' &sdot; ''b''
:Let ''d'' = [[Floor function|int]](''x'' / ''p'')
:Let ''r'' = ''x'' [[modulo operation|mod]] ''p''
:Let ''n'' = ''n'' &sdot; ''b'' + ''d''
:If ''r'' ≠&thinsp;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'' &sdot; ''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.

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, the result is a sequence of ''b'' − 1 digits, where ''b'' is the base (e.g. 10 in decimal). For example, in decimal, 142857 × 7 = 999999.
*When split into groups of equal length (of two, three, four, etc... digits), and the groups are added, the result is a sequence of ''b'' - 1 digits. For example, 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 ''b'' − 1 where ''b'' is the base (e.g. 9 in decimal) and the sum of the remainder is 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. (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 numeral system|binary]], the sequence of cyclic numbers begins: {{OEIS|id=A001122}}
:11 (3) → 01
:101 (5) → 0011
:1011 (11) → 0001011101
:1101 (13) → 000100111011
:10011 (19) → 000011010111100101
:11101 (29) → 0000100011010011110111001011

In [[Ternary numeral system|ternary]]: {{OEIS|id=A019334}}
:2 (2) → 1
:12 (5) → 0121
:21 (7) → 010212
:122 (17) → 0011202122110201
:201 (19) → 001102100221120122

In [[Quaternary numeral system|quaternary]], there are none.

In [[quinary]]: {{OEIS|id=A019335}}
:2 (2) → 2
:3 (3) → 13
:12 (7) → 032412 	
:32 (17) → 0121340243231042
:43 (23) → 0102041332143424031123
:122 (37) → 003142122040113342441302322404331102

In [[senary]]: {{OEIS|id=A167794}}
:15 (11) → 0313452421
:21 (13) → 024340531215
:25 (17) → 0204122453514331
:105 (41) → 0051335412440330234455042201431152253211
:135 (59) → 0033544402235104134324250301455220111533204514212313052541
:141 (61) → 003312504044154453014342320220552243051511401102541213235335

In base 7: {{OEIS|id=A019337}}
:2 (2) → 3
:5 (5) → 1254
:14 (11) → 0431162355
:16 (13) → 035245631421
:23 (17) → 0261143464055232
:32 (23) → 0206251134364604155323

In [[octal]]: {{OEIS|id=A019338}}
:3 (3) → 25
:5 (5) → 1463
:13 (11) → 0564272135
:35 (29) → 0215173454106475626043236713
:65 (53) → 0115220717545336140465103476625570602324416373126743
:73 (59) → 0105330745756511606404255436276724470320212661713735223415

In [[nonary]], the unique cyclic number is
:2 (2) → 4

In base 11: {{OEIS|id=A019339}}
:2 (2) → 5
:3 (3) → 37
:12 (13) → 093425A17685
:16 (17) → 07132651A3978459
:21 (23) → 05296243390A581486771A
:27 (29) → 04199534608387A69115764A2723

In [[duodecimal]]: {{OEIS|id=A019340}}
:5 (5) → 2497
:7 (7) → 186A35
:15 (17) → 08579214B36429A7
:27 (31) → 0478AA093598166B74311B28623A55
:35 (41) → 036190A653277397A9B4B85A2B15689448241207
:37 (43) → 0342295A3AA730A068456B879926181148B1B53765

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, i.e. ''p'' = 2) exist in any numeric base which is a [[Square number|perfect square]], that is, base 4, 9, 16, 25, etc.

== See also ==
*[[Repeating decimal]]
*[[Fermat's little theorem]]
*[[Cyclic permutation of integer]]
*[[Parasitic number]]

== References ==
{{Reflist}}

==Further reading==
*Gardner, Martin. Mathematical Circus: More Puzzles, Games, Paradoxes and Other Mathematical Entertainments From Scientific American. New York: The Mathematical Association of America, 1979. pp.&nbsp;111–122.
*Kalman, Dan; 'Fractions with Cycling Digit Patterns'  The College Mathematics Journal, Vol. 27, No. 2. (Mar., 1996), pp.&nbsp;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}}
*[[David G. Wells|Wells, David]]; ''"[[The Penguin Dictionary of Curious and Interesting Numbers]]"'',  Penguin Press.  {{ISBN|0-14-008029-5}}

==External links==
* {{MathWorld | urlname=CyclicNumber | title=Cyclic Number}}
* {{Cite AV media |url=https://www.youtube.com/watch?v=WUlaUalgxqI |title=Cyclic Numbers - Numberphile |date=2013-10-27 |last=Numberphile |access-date=2024-11-05 |via=YouTube}}

{{Classes of natural numbers}}
[[Category:Number theory]]
[[Category:Permutations]]