Chemistry - Cyclic number

If leading zeros are not permitted on numerals, then 142857 is the only cyclic number in decimal. Allowing leading zeros, the sequence of cyclic numbers begins:

142857

0588235294117647

052631578947368421

0434782608695652173913

0344827586206896551724137931

0212765957446808510638297872340425531914893617

0169491525423728813559322033898305084745762711864406779661

016393442622950819672131147540983606557377049180327868852459

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

This restriction also excludes such trivial cases as:

repeated digits, e.g.: 555
repeated cyclic numbers, e.g.: 142857142857
single digits preceeded by zeros, e.g.: "005"

Single digits may be considered degenerate or trivial cases of cyclic numbers.

Relation to recurring decimals

The Cyclic numbers are related to the repeating digital representations of unit fractions. In general, for a cyclic number of length L, the digital representation of

1/(L + 1)

has a period of L, and repeats the cyclic number.

For example:

1/7 = 0.142857142857…

Multiples of these fractions also exhibit cyclic permutation:

1/7 = 0.142857142857…

2/7 = 0.285714285714…

3/7 = 0.428571428571…

4/7 = 0.571428571428…

5/7 = 0.714285714285…

6/7 = 0.857142857142…

Conversely, if the digital period of 1 /p is

p − 1,

then the digits repeat a cyclic number.

Form of cyclic numbers

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.

For example, the case b = 10, p = 7 gives the cyclic number 142857.

Not all values of p will yield a cyclic number using this formula; for example p=13 gives 076923076923. These failed cases will always contain a repetition of digits (possibly several).

The values of p for which this formula produces cyclic numbers in decimal are:

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 …

The known pattern to this sequence comes from algebraic number theory. A conjecture of Emil Artin [1] is that this sequence contains 37.395..% of the primes.

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 outputted 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 remaning digits.

Other numeric Bases

Using the above technique, cyclic numbers can be found in other numeric bases. In binary, the sequence of cyclic numbers begins:

0011

0001011101

000100111011

000011010111100101

In ternary:

0121

010212

0011202122110201

001102100221120122

0002210102011122200121202111

In octal:

1463

0564272135

0215173454106475626043236713

0115220717545336140465103476625570602324416373126743

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.

References

Wells, David; The Penguin Dictionary of Curious and Interesting Numbers. Penguin Press. ISBN 0-14-008029-5

External link

Wolfram Research (http://mathworld.wolfram.com/CyclicNumber.html) Retrieved Mar 30, 2005.

Categories: Number theory