Cyclic number
Encyclopedia
A cyclic number is an integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

 in which cyclic permutation
Cyclic permutation
A cyclic permutation or circular permutation is a permutation built from one or more sets of elements in cyclic order.The notion "cyclic permutation" is used in different, but related ways:- Definition 1 :right|mapping of permutation...

s of the digits are successive multiples of the number. The most widely known is 142857
142857 (number)
142857 is the six repeating digits of 1/7, 0., and is the best-known cyclic number in base 10. If it is multiplied by 2, 3, 4, 5, or 6, the answer will be a cyclic permutation of itself, and will correspond to the repeating digits of 2/7, 3/7, 4/7, 5/7, or 6/7, respectively.- Calculations :- 22/7...

:
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 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
Decimal
The decimal numeral system has ten as its base. It is the numerical base most widely used by modern civilizations....

. Allowing leading zeros, the sequence of cyclic numbers begins:
142857 (6 digits)
0588235294117647 (16 digits)
052631578947368421 (18 digits)
0434782608695652173913 (22 digits)
0344827586206896551724137931 (28 digits)
0212765957446808510638297872340425531914893617 (46 digits)
0169491525423728813559322033898305084745762711864406779661 (58 digits)
016393442622950819672131147540983606557377049180327868852459 (60 digits)

Relation to repeating decimals

Cyclic numbers are related to the recurring digital representations
Repeating decimal
In arithmetic, a decimal representation of a real number is called a repeating decimal if at some point it becomes periodic, that is, if there is some finite sequence of digits that is repeated indefinitely...

 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


where b is the number base
Radix
In mathematical numeral systems, the base or radix for the simplest case is the number of unique digits, including zero, that a positional numeral system uses to represent numbers. For example, for the decimal system the radix is ten, because it uses the ten digits from 0 through 9.In any numeral...

 (10 for decimal
Decimal
The decimal numeral system has ten as its base. It is the numerical base most widely used by modern civilizations....

), and p is a prime
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...

 that does not divide
Divisor
In mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...

 b. (Primes p that give cyclic numbers are called full reptend primes or long primes).

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 first values of p for which this formula produces cyclic numbers in decimal are (sequence A001913 in OEIS
On-Line Encyclopedia of Integer Sequences
The On-Line Encyclopedia of Integer Sequences , also cited simply as Sloane's, is an online database of integer sequences, created and maintained by N. J. A. Sloane, a researcher at AT&T Labs...

):
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
Algebraic number theory
Algebraic number theory is a major branch of number theory which studies algebraic structures related to algebraic integers. This is generally accomplished by considering a ring of algebraic integers O in an algebraic number field K/Q, and studying their algebraic properties such as factorization,...

, specifically, this sequence is the set of primes p such that 10 is a primitive root modulo p
Primitive root modulo n
In modular arithmetic, a branch of number theory, a primitive root modulo n is any number g with the property that any number coprime to n is congruent to a power of g modulo n. In other words, g is a generator of the multiplicative group of integers modulo n...

. A conjecture of Emil Artin
Artin's conjecture on primitive roots
In number theory, Artin's conjecture on primitive roots states that a given integer a which is not a perfect square and not −1 is a primitive root modulo infinitely many primes p. The conjecture also ascribes an asymptotic density to these primes...

  is that this sequence contains 37.395..% of the primes.

Construction of cyclic numbers

Cyclic numbers can be constructed by the following procedure
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

:

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
Floor function
In mathematics and computer science, the floor and ceiling functions map a real number to the largest previous or the smallest following integer, respectively...

(x / p)
Let r = x mod
Modulo operation
In computing, the modulo operation finds the remainder of division of one number by another.Given two positive numbers, and , a modulo n can be thought of as the remainder, on division of a by n...

 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
Long division
In arithmetic, long division is a standard procedure suitable for dividing simple or complex multidigit numbers. It breaks down a division problem into a series of easier steps. As in all division problems, one number, called the dividend, is divided by another, called the divisor, producing a...

. r is the remainder
Remainder
In arithmetic, the remainder is the amount "left over" after the division of two integers which cannot be expressed with an integer quotient....

 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 remaining digits.

Properties of cyclic numbers

  • When multiplied by their generating prime, results in a sequence of 9's. 142857 × 7 = 999999
  • When split in half by its digits and added the result is a sequence of 9's. 142 + 857 = 999 (This is a special case of Midy's Theorem
    Midy's theorem
    In mathematics, Midy's theorem, named after French mathematician E. Midy, is a statement about the decimal expansion of fractions a/p where p is a prime and a/p has a repeating decimal expansion with an even period...

    .)
  • All cyclic numbers are divisible by 9. (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 binary
Binary numeral system
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...

, the sequence of cyclic numbers begins:
01
0011
0001011101
000100111011
000011010111100101


In ternary
Ternary numeral system
Ternary is the base- numeral system. Analogous to a bit, a ternary digit is a trit . One trit contains \log_2 3 bits of information...

:
0121
010212
0011202122110201
001102100221120122
0002210102011122200121202111


In octal
Octal
The octal numeral system, or oct for short, is the base-8 number system, and uses the digits 0 to 7. Numerals can be made from binary numerals by grouping consecutive binary digits into groups of three...

:
25
1463
0564272135
0215173454106475626043236713
0115220717545336140465103476625570602324416373126743


In duodecimal
Duodecimal
The duodecimal system is a positional notation numeral system using twelve as its base. In this system, the number ten may be written as 'A', 'T' or 'X', and the number eleven as 'B' or 'E'...

:
2497
186A35
08579214B36429A7


In Base 24
Base 24
The base- system is a numeral system with 24 as its base.There are 24 hours in a nychthemeron , so solar time includes a base-24 component.See also base 12. Decimal Equivalent...

:
3A6LDH
248HAMKF6D
1L795CN3GEJB
19M45FCGNE2KJ8B7


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
Square number
In mathematics, a square number, sometimes also called a perfect square, is an integer that is the square of an integer; in other words, it is the product of some integer with itself...

; thus there are no cyclic numbers in hexadecimal
Hexadecimal
In mathematics and computer science, hexadecimal is a positional numeral system with a radix, or base, of 16. It uses sixteen distinct symbols, most often the symbols 0–9 to represent values zero to nine, and A, B, C, D, E, F to represent values ten to fifteen...

.

See also

  • Repeating decimal
    Repeating decimal
    In arithmetic, a decimal representation of a real number is called a repeating decimal if at some point it becomes periodic, that is, if there is some finite sequence of digits that is repeated indefinitely...

  • Fermat's little theorem
    Fermat's little theorem
    Fermat's little theorem states that if p is a prime number, then for any integer a, a p − a will be evenly divisible by p...

  • Cyclic permutation of integer
  • Parasitic number
    Parasitic number
    An n-parasitic number is a positive natural number which can be multiplied by n by moving the rightmost digit of its decimal representation to the front. Here n is itself a single-digit positive natural number. In other words, the decimal representation undergoes a right circular shift by one...

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK