142857 × 3 = 428571 (shifts cyclically one place left)
142857 × 5 = 714285 (shifts cyclically one place right)
128205 × 4 = 512820 (shifts cyclically one place right)
076923 × 9 = 692307 (shifts cyclically two places left)
These specific integers, known as transposable integers, can be but are not always cyclic numbers. The characterization of such numbers can be done using repeating decimals (and thus the related fractions), or directly.
General
For any integer coprime to 10, its reciprocal is a repeating decimal without any non-recurring digits. E.g. 1⁄143 = 0.006993006993006993...
While the expression of a single series with vinculum on top is adequate, the intention of the above expression is to show that the six cyclic permutations of 006993 can be obtained from this repeating decimal if we select six consecutive digits from the repeating decimal starting from different digits.
This illustrates that cyclic permutations are somehow related to repeating decimals and the corresponding fractions.
The greatest common divisor (gcd) between any cyclic permutation of an m-digit integer and 10m−1 is constant. Expressed as a formula,
where N is an m-digit integer; and Nc is any cyclic permutation of N.
If N is an m-digit integer, the number Nc, obtained by shifting N to the left cyclically, can be obtained from:
where d is the first digit of N and m is the number of digits.
This explains the above common gcd and the phenomenon is true in any base if 10 is replaced by b, the base.
The cyclic permutations are thus related to repeating decimals, the corresponding fractions, and divisors of 10m−1. For examples the related fractions to the above cyclic permutations are thus:
091575⁄999999, 915750⁄999999, 157509⁄999999, 575091⁄999999, 750915⁄999999, and 509157⁄999999.
Reduced to their lowest terms using the common gcd, they are:
25⁄273, 250⁄273, 43⁄273, 157⁄273, 205⁄273, and 139⁄273.
That is, these fractions when expressed in lowest terms, have the same denominator. This is true for cyclic permutations of any integer.
Fraction method
Integral multiplier
An integral multiplier refers to the multiplier n being an integer:
An integer X shift right cyclically by k positions when it is multiplied by an integer n. X is then the repeating digits of 1⁄F, whereby F is F0 = n10k − 1 (F0 is coprime to 10), or a factor of F0; excluding any values of F which are not more than n.
An integer X shift left cyclically by k positions when it is multiplied by an integer n. X is then the repeating digits of 1⁄F, whereby F is F0 = 10k - n, or a factor of F0; excluding any values of F which are not more than n and which are not coprime to 10.
It is necessary for F to be coprime to 10 in order that 1⁄F is a repeating decimal without any preceding non-repeating digits (see multiple sections of Repeating decimal). If there are digits not in a period, then there is no corresponding solution.
For these two cases, multiples of X, i.e. (jX) are also solutions provided that the integer i satisfies the condition nj⁄F < 1. Most often it is convenient to choose the smallest F that fits the above. The solutions can be expressed by the formula:
where p is a period length of 1⁄F; and F is a factor of F0 coprime to 10.
E.g, F0 = 1260 = 22× 32× 5 × 7. The factors excluding 2 and 5 recompose to F = 32× 7 = 63. Alternatively, strike off all the ending zeros from 1260 to become 126, then divide it by 2 (or 5) iteratively until the quotient is no more divisible by 2 (or 5). The result is also F = 63.
To exclude integers that begin with zeros from the solutions, select an integer j such that j⁄F > 1⁄10, i.e. j > F⁄10.
There is no solution when n > F.
Fractional multiplier
An integer X shift left cyclically by k positions when it is multiplied by a fraction n⁄s. X is then the repeating digits of s⁄F, whereby F is F0 = s10k - n, or a factor of F0; and F must be coprime to 10.
For this third case, multiples of X, i.e. (jX) are again solutions but the condition to be satisfied for integer j is that nj⁄F < 1. Again it is convenient to choose the smallest F that fits the above.
The solutions can be expressed by the formula:
where p is defined likewise; and F is made coprime to 10 by the same process as before.
To exclude integers that begin with zeros from the solutions, select an integer j such that js⁄F > 1⁄10, i.e. j > F⁄10s.
Again if js⁄F > 1, there is no solution.
Direct representation
The direct algebra approach to the above cases integral multiplier lead to the following formula:
where m is the number of digits of X, and D, the k-digit number shifted from the low end of X to the high end of nX, satisfies D < 10k.
If the numbers are not to have leading zeros, then n10k−1 ≤ D.
where m is the number of digits of X, and D, the k-digit number shifted from the high end of X to the low end of nX, satisfies:
and the 10-part (the product of the terms corresponding to the primes 2 and 5 of the factorization) of 10k−n divides D.
The 10-part of an integer t is often abbreviated
If the numbers are not to have leading zeros, then 10k−1 ≤ D.
At the last step, 1 reappears as the remainder. The cyclic remainders are {1, 3, 2, 6, 4, 5}. We rewrite the quotients with the corresponding dividend/remainders above them at all the steps:
By observing the remainders at each step, we can thus perform a desired cyclic permutation by multiplication. E.g.,
The integer 142857, corresponding to remainder 1, permutes to 428571 when multiplied by 3, the corresponding remainder of the latter.
The integer 142857, corresponding to remainder 1, permutes to 857142 when multiplied by 6, the corresponding remainder of the latter.
The integer 857142, corresponding to remainder 6, permutes to 571428 when multiplied by 5⁄6; i.e. divided by 6 and multiplied by 5, the corresponding remainder of the latter.
In this manner, cyclical left or right shift of any number of positions can be performed.
Less importantly, this technique can be applied to any integer to shift cyclically right or left by any given number of places for the following reason:
Every repeating decimal can be expressed as a rational number (fraction).
Every integer, when added with a decimal point in front and concatenated with itself infinite times, can be converted to a fraction, e.g. we can transform 123456 in this manner to 0.123456123456..., which can thus be converted to fraction 123456⁄999999. This fraction can be further simplified but it will not be done here.
To permute the integer 123456 to 234561, all one needs to do is to multiply 123456 by 234561⁄123456. This looks like cheating but if 234561⁄123456 is a whole number (in this case it is not), the mission is completed.
Proof of formula for cyclical right shift operation
An integer X shift cyclically right by k positions when it is multiplied by an integer n. Prove its formula.
Proof
First recognize that X is the repeating digits of a repeating decimal, which always possesses cyclic behavior in multiplication. The integer X and its multiple nX then will have the following relationship:
The integer X is the repeating digits of the fraction 1⁄F, say dpdp-1...d3d2d1, where dp, dp-1, ..., d3, d2 and d1 each represents a digit and p is the number of digits.
The multiple nX is thus the repeating digits of the fraction n⁄F, say dkdk-1...d3d2d1dpdp-1...dk+2dk+1, representing the results after right cyclical shift of k positions.
F must be coprime to 10 so that when 1⁄F is expressed in decimal there is no preceding non-repeating digits otherwise the repeating decimal does not possess cyclic behavior in multiplication.
If the first remainder is taken to be n then 1 shall be the (k + 1)st remainder in the long division for n⁄F in order for this cyclic permutation to take place.
In order that n× 10k = 1 (mod F) then F shall be either F0 = (n× 10k - 1), or a factor of F0; but excluding any values not more than n and any value having a nontrivial common factor with 10, as deduced above.
This completes the proof.
Proof of formula for cyclical left shift operation
An integer X shift cyclically left by k positions when it is multiplied by an integer n. Prove its formula.
Proof
First recognize that X is the repeating digits of a repeating decimal, which always possesses a cyclic behavior in multiplication. The integer X and its multiple nX then will have the following relationship:
The integer X is the repeating digits of the fraction 1⁄F, say dpdp-1...d3d2d1 .
The multiple nX is thus the repeating digits of the fraction n⁄F, say dp-kdp-k-1...d3d2d1dpdp-1...dp-k+1,
which represents the results after left cyclical shift of k positions.
F must be coprime to 10 so that 1⁄F has no preceding non-repeating digits otherwise the repeating decimal does not possesses cyclic behavior in multiplication.
If the first remainder is taken to be 1 then n shall be the (k + 1)st remainder in the long division for 1⁄F in order for this cyclic permutation to take place.
In order that 1 × 10k = n (mode F) then F shall be either F0 = (10k -n), or a factor of F0; but excluding any value not more than n, and any value having a nontrivial common factor with 10, as deduced above.
This completes the proof. The proof for non-integral multiplier such as n⁄s can be derived in a similar way and is not documented here.
When a parasitic number is multiplied by n, not only it exhibits the cyclic behavior but the permutation is such that the last digit of the parasitic number now becomes the first digit of the multiple. For example, 102564 x 4 = 410256. Note that 102564 is the repeating digits of 4⁄39 and 410256 the repeating digits of 16⁄39.
Shifting right cyclically by double positions
An integer X shift right cyclically by double positions when it is multiplied by an integer n. X is then the repeating digits of 1⁄F, whereby F = n× 102 - 1; or a factor of it; but excluding values for which 1⁄F has a period length dividing 2 (or, equivalently, less than 3); and F must be coprime to 10.
Most often it is convenient to choose the smallest F that fits the above.
Summary of results
The following multiplication moves the last two digits of each original integer to the first two digits and shift every other digits to the right:
299 = 13 x 23, and the period of 1⁄299 is accurately determined by the formula, LCM(6, 22) = 66, according to Repeating decimal#Generalization.
399 = 3 x 7 x 19, and the period of 1⁄399 is accurately determined by the formula, LCM(1, 6, 18) = 18.
There are many other possibilities.
Shifting left cyclically by single position
Problem: An integer X shift left cyclically by single position when it is multiplied by 3. Find X.
Solution: First recognize that X is the repeating digits of a repeating decimal, which always possesses some interesting cyclic behavior in multiplications. The integer X and its multiple then will have the following relationship:
The integer X is the repeating digits of the fraction 1⁄F, say ab***.
The multiple is thus the repeating digits of the fraction 3⁄F, say b***a.
In order for this cyclic permutation to take place, then 3 shall be the next remainder in the long division for 1⁄F. Thus F shall be 7 as 1 × 10 ÷ 7 gives remainder 3.
This yields the results that:
X = the repeating digits of 1⁄7
=142857, and
the multiple = 142857 × 3 = 428571, the repeating digits of 3⁄7
The other solution is represented by 2⁄7 x 3 = 6⁄7:
Integer n must be the subsequent remainder in a long division of a fraction 1⁄F. Given that n = 10 - F, and F is coprime to 10 in order for 1⁄F to be a repeating decimal, then n shall be less than 10.
For n = 2, F must be 10 - 2 = 8. However 1⁄8 does not generate a repeating decimal, similarly for n = 5.
For n = 7, F must be 10 - 7 = 3. However 7 > 3 and 7⁄3 = 2.333 > 1 and does not fit the purpose.
Similarly there is no solution for any other integer of n less than 10 except n = 3.
However, if the multiplier is not restricted to be an integer (though ugly), there are many other solutions from this method. E.g., if an integer X shift right cyclically by single position when it is multiplied by 3⁄2, then 3 shall be the next remainder after 2 in a long division of a fraction 2⁄F. This deduces that F = 2 x 10 - 3 = 17, giving X as the repeating digits of 2⁄17, i.e. 1176470588235294, and its multiple is 1764705882352941.
The following summarizes some of the results found in this manner:
An integer X shift left cyclically by double positions when it is multiplied by an integer n. X is then the repeating digits of 1⁄F, whereby F is R = 102 - n, or a factor of R; excluding values of F for which 1⁄F has a period length dividing 2 (or, equivalently, less than 3); and F must be coprime to 10.
Most often it is convenient to choose the smallest F that fits the above.
Summary of results
The following summarizes some of the results obtained in this manner, where the white spaces between the digits divide the digits into 10-digit groups:
Note that the “Shifting left cyclically by single position” problem has no solution for the multiplier less than 12 except 2 and 5, the same problem in decimal system has no solution for the multiplier less than 10 except 3.
Notes
↑ P. Yiu, k-right-transposable integers, Chap.18.1 'Recreational Mathematics'
Related Research Articles
In number theory, two integers a and b are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides a does not divide b, and vice versa. This is equivalent to their greatest common divisor (GCD) being 1. One says also ais prime tob or ais coprime withb.
In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.
The decimal numeral system is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers of the Hindu–Arabic numeral system. The way of denoting numbers in the decimal system is often referred to as decimal notation.
In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements . It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.
In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers x, y, the greatest common divisor of x and y is denoted . For example, the GCD of 8 and 12 is 4, that is, .
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.
In number theory, Euler's totient function counts the positive integers up to a given integer n that are relatively prime to n. It is written using the Greek letter phi as or , and may also be called Euler's phi function. In other words, it is the number of integers k in the range 1 ≤ k ≤ n for which the greatest common divisor gcd(n, k) is equal to 1. The integers k of this form are sometimes referred to as totatives of n.
In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers a and b, also the coefficients of Bézout's identity, which are integers x and y such that
A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" (zero) and "1" (one).
In arithmetic, long division is a standard division algorithm suitable for dividing multi-digit Hindu-Arabic numerals that is simple enough to perform by hand. It breaks down a division problem into a series of easier steps.
Balanced ternary is a ternary numeral system that uses a balanced signed-digit representation of the integers in which the digits have the values −1, 0, and 1. This stands in contrast to the standard (unbalanced) ternary system, in which digits have values 0, 1 and 2. The balanced ternary system can represent all integers without using a separate minus sign; the value of the leading non-zero digit of a number has the sign of the number itself. The balanced ternary system is an example of a non-standard positional numeral system. It was used in some early computers and also in some solutions of balance puzzles.
49 (forty-nine) is the natural number following 48 and preceding 50.
Positional notation usually denotes the extension to any base of the Hindu–Arabic numeral system. More generally, a positional system is a numeral system in which the contribution of a digit to the value of a number is the value of the digit multiplied by a factor determined by the position of the digit. In early numeral systems, such as Roman numerals, a digit has only one value: I means one, X means ten and C a hundred. In modern positional systems, such as the decimal system, the position of the digit means that its value must be multiplied by some value: in 555, the three identical symbols represent five hundreds, five tens, and five units, respectively, due to their different positions in the digit string.
The number 142,857 is a Kaprekar number.
A divisibility rule is a shorthand and useful way of determining whether a given integer is divisible by a fixed divisor without performing the division, usually by examining its digits. Although there are divisibility tests for numbers in any radix, or base, and they are all different, this article presents rules and examples only for decimal, or base 10, numbers. Martin Gardner explained and popularized these rules in his September 1962 "Mathematical Games" column in Scientific American.
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
A fraction represents a part of a whole or, more generally, any number of equal parts. When spoken in everyday English, a fraction describes how many parts of a certain size there are, for example, one-half, eight-fifths, three-quarters. A common, vulgar, or simple fraction consists of an integer numerator, displayed above a line, and a non-zero integer denominator, displayed below that line. If these integers are positive, then the numerator represents a number of equal parts, and the denominator indicates how many of those parts make up a unit or a whole. For example, in the fraction 3/4, the numerator 3 indicates that the fraction represents 3 equal parts, and the denominator 4 indicates that 4 parts make up a whole. The picture to the right illustrates 3/4 of a cake.
A decimal representation of a non-negative real number r is its expression as a sequence of symbols consisting of decimal digits traditionally written with a single separator:
An n-parasitic number is a positive natural number which, when multiplied by n, results in movement of the last digit of its decimal representation to its front. Here n is itself a single-digit positive natural number. In other words, the decimal representation undergoes a right circular shift by one place. For example:
A repeating decimal or recurring decimal is decimal representation of a number whose digits are periodic and the infinitely repeated portion is not zero. It can be shown that a number is rational if and only if its decimal representation is repeating or terminating. For example, the decimal representation of 1/3 becomes periodic just after the decimal point, repeating the single digit "3" forever, i.e. 0.333.... A more complicated example is 3227/555, whose decimal becomes periodic at the second digit following the decimal point and then repeats the sequence "144" forever, i.e. 5.8144144144.... At present, there is no single universally accepted notation or phrasing for repeating decimals. Another example of this is 593/53, which becomes periodic after the decimal point, repeating the 13-digit pattern "1886792452830" forever, i.e. 11.18867924528301886792452830....
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, ISBN1-4020-1546-1
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
