Cyclic number

From Wikipedia, the free encyclopedia
Jump to: navigation, search
This article is about numbers where permutations of their digits (in some base) yield related numbers. For the number theoretic concept, see cyclic number (group theory).

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:

142857 × 1 = 142857
142857 × 2 = 285714
142857 × 3 = 428571
142857 × 4 = 571428
142857 × 5 = 714285
142857 × 6 = 857142

Details[edit]

To qualify as a cyclic number, it is required that successive multiples be cyclic permutations. Thus, the number 076923 would not be considered a cyclic number, even though all cyclic permutations are 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:

(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)

Relation to repeating decimals[edit]

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[edit]

From the relation to unit fractions, it can be shown that cyclic numbers are of the form

\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 076Ɛ45076Ɛ45076Ɛ45. 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 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 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 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 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 [1] is that this sequence contains 37.395..% of the primes.

Construction of cyclic numbers[edit]

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[edit]

  • 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[edit]

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 binary, the sequence of cyclic numbers begins:

11 (3) → 01
101 (5) → 0011
1011 (11) → 0001011101
1101 (13) → 000100111011
10011 (19) → 000011010111100101

In ternary:

12 (5) → 0121
21 (7) → 010212
122 (17) → 0011202122110201
201 (19) → 001102100221120122
1002 (29) → 0002210102011122200121202111

In quaternary:

none

In quinary:

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

In senary:

15 (11) → 0313452421
21 (13) → 024340531215
25 (17) → 0204122453514331
31 (19) → 015211325015211325
105 (41) → 0051335412440330234455042201431152253211

In septenary:

5 (5) → 1254
14 (11) → 0431162355
16 (13) → 035245631421
23 (17) → 0261143464055232
32 (23) → 0206251134364604155323

In octal:

3 (3) → 25
5 (5) → 1463
13 (11) → 0564272135
35 (29) → 0215173454106475626043236713
65 (53) → 0115220717545336140465103476625570602324416373126743

In nonary:

none

In Base 11:

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

In duodecimal:

5 (5) → 2497
7 (7) → 186A35
15 (17) → 08579214B36429A7
27 (31) → 0478AA093598166B74311B28623A55
35 (41) → 036190A653277397A9B4B85A2B15689448241207

In Base 13:

5 (5) → 27A5
B (11) → 12495BA837
16 (19) → 08B82976AC414A3562
25 (31) → 055B42692C21347C7718A63A0AB985

In Base 14:

3 (3) → 49
13 (17) → 0B75A9C4D2683419
15 (19) → 0A45C7522D398168BB

In Base 15:

D (13) → 124936DCA5B8
14 (19) → 0BC9718A3E3257D64B
18 (23) → 09BB1487291E533DA67C5D

In hexadecimal:

none

In Base 17:

3 (3) → 5B
5 (5) → 36DA
7 (7) → 274E9C
B (11) → 194ADF7C63

In Base 18:

B (11) → 1B834H69ED
1B (29) → 0B31F95A9GDAE4H6EG28C781463D
21 (37) → 08DB37565F184FA3G0H946EACBC2G9D27E1H

In Base 19:

7 (7) → 2DAG58
B (11) → 1DFA6H538C
D (13) → 18EBD2HA475G

In Base 20:

3 (3) → 6D
D (13) → 1AF7DGI94C63
H (17) → 13ABF5HCIG984E27

In Base 21:

J (19) → 1248HE7F9JIGC36D5B
12 (23) → 0J3DECG92FAK1H7684BI5A
18 (29) → 0F475198EA2IH7K5GDFJBC6AI23D

In Base 22:

5 (5) → 48HD
H (17) → 16A7GI2CKFBE53J9
J (19) → 13A95H826KIBCG4DJF

In Base 23:

3 (3) → 7F
5 (5) → 4DI9
H (17) → 182G59AILEK6HDC4

In Base 24:

7 (7) → 3A6KDH
B (11) → 248HALJF6D
D (13) → 1L795CM3GEIB
H (17) → 19L45FCGME2JI8B7

Smallest prime which gives a cyclic number in base n are

2, 3, 2, 0, 2, 11, 2, 3, 2, 7, 2, 5, 2, 3, 2, 0, 2, 5, 2, 3, 2, 5, 2, 7, 2, 3, 2, 5, 2, 11, 2, 3, 2, 19, 2, 0, 2, 3, 2, 7, 2, 5, 2, 3, 2, 11, 2, 5, 2, 3, 2, 5, 2, 7, 2, 3, 2, 5, 2, 19, 2, 3, 2, 0, 2, 7, 2, 3, 2, 19, 2, 5, ... (sequence A056619 in OEIS)

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; thus there are no cyclic numbers in hexadecimal, base 4, or nonary.

See also[edit]

References[edit]

Further reading[edit]

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

External links[edit]