# Cyclic number

A cyclic number is an integer for which cyclic permutations of the digits are successive integer multiples of the number. The most widely known is the six-digit number 142857, whose first six integer multiples are
    142857 × 1 = 142857
    142857 × 2 = 285714
    142857 × 3 = 428571
    142857 × 4 = 571428
    142857 × 5 = 714285
    142857 × 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 × 1 = 076923
    076923 × 3 = 230769
    076923 × 4 = 307692
    076923 × 9 = 692307
    076923 × 10 = 769230
    076923 × 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$^6$ − 1) / 7 = 142857 (6 digits)
    (10$^{16}$ − 1) / 17 = 0588235294117647 (16 digits)
    (10$^{18}$ − 1) / 19 = 052631578947368421 (18 digits)
    (10$^{22}$ − 1) / 23 = 0434782608695652173913 (22 digits)
    (10$^{28}$ − 1) / 29 = 0344827586206896551724137931 (28 digits)
    (10$^{46}$ − 1) / 47 = 0212765957446808510638297872340425531914893617 (46 digits)
    (10$^{58}$ − 1) / 59 = 0169491525423728813559322033898305084745762711864406779661 (58 digits)
    (10$^{60}$ − 1) / 61 = 016393442622950819672131147540983606557377049180327868852459 (60 digits)
    (10$^{96}$ − 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
    ${\frac {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 OEIS: 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.
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, 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
In ternary: (sequence A019334 in the OEIS)
    2 (2) → 1
    12 (5) → 0121
    21 (7) → 010212
    122 (17) → 0011202122110201
    201 (19) → 001102100221120122
In quaternary, there are 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
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
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
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
In nonary, the unique cyclic number is
    2 (2) → 4
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
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
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 perfect square, that is, base 4, 9, 16, 25, etc.