Transposable integer

The digits of some specific integers permute or shift cyclically when they are multiplied by a number n. Examples are:

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. 1143 = 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.

For example,

   gcd(091575, 999999) = gcd(32×52×11×37, 33×7×11×13×37)
                       = 3663
                       = gcd(915750, 999999)
                       = gcd(157509, 999999)
                       = gcd(575091, 999999)
                       = gcd(750915, 999999)
                       = gcd(509157, 999999)

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 10m1. For examples the related fractions to the above cyclic permutations are thus:

Reduced to their lowest terms using the common gcd, they are:

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:

  1. An integer X shift right cyclically by k positions when it is multiplied by an integer n. X is then the repeating digits of 1F, whereby F is F0 = n 10k − 1 (F0 is coprime to 10), or a factor of F0; excluding any values of F which are not more than n.
  2. An integer X shift left cyclically by k positions when it is multiplied by an integer n. X is then the repeating digits of 1F, 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 1F 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. (j X) are also solutions provided that the integer i satisfies the condition n jF < 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 1F; 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 jF > 110, i.e. j > F10.

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 ns. X is then the repeating digits of sF, whereby F is F0 = s 10k - n, or a factor of F0; and F must be coprime to 10.

For this third case, multiples of X, i.e. (j X) are again solutions but the condition to be satisfied for integer j is that n jF < 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 j sF > 110, i.e. j > F10s.

Again if j sF > 1, there is no solution.

Direct representation

The direct algebra approach to the above cases integral multiplier lead to the following formula:

  1. 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 n X, satisfies D < 10k.
    If the numbers are not to have leading zeros, then n 10k  1D.
  2. 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 n X, satisfies:
    1. 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  1D.

Cyclic permutation by multiplication

A long division of 1 by 7 gives:

        0.142857...
    7 ) 1.000000
         .7
          3
          28
           2
           14
            6
            56
             4
             35
              5
              49
               1

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:

    Dividend/Remainders    1 3 2 6 4 5
    Quotients              1 4 2 8 5 7

and also note that:

By observing the remainders at each step, we can thus perform a desired cyclic permutation by multiplication. E.g.,

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:

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 n X then will have the following relationship:

  1. The integer X is the repeating digits of the fraction 1F, say dpdp-1...d3d2d1, where dp, dp-1, ..., d3, d2 and d1 each represents a digit and p is the number of digits.
  2. The multiple n X is thus the repeating digits of the fraction nF, say dkdk-1...d3d2d1dpdp-1...dk+2dk+1, representing the results after right cyclical shift of k positions.
  3. F must be coprime to 10 so that when 1F is expressed in decimal there is no preceding non-repeating digits otherwise the repeating decimal does not possesses cyclic behavior in multiplication.
  4. If the first remainder is taken to be n then 1 shall be the (k + 1)th remainder in the long division for nF in order for this cyclic permutation to take place.
  5. 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 n X then will have the following relationship:

  1. The integer X is the repeating digits of the fraction 1F, say dpdp-1...d3d2d1 .
  2. The multiple n X is thus the repeating digits of the fraction nF, say dp-kdp-k-1...d3d2d1dpdp-1...dp-k+1,

which represents the results after left cyclical shift of k positions.

  1. F must be coprime to 10 so that 1F has no preceding non-repeating digits otherwise the repeating decimal does not possesses cyclic behavior in multiplication.
  2. If the first remainder is taken to be 1 then n shall be the (k + 1)th remainder in the long division for 1F in order for this cyclic permutation to take place.
  3. 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 ns can be derived in a similar way and is not documented here.

Shifting an integer cyclically

The permutations can be:

Parasitic numbers

Main article: parasitic number

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 439 and 410256 the repeating digits of 1639.

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 1F, whereby F = n × 102 - 1; or a factor of it; but excluding values for which 1F 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:

Multiplier n Solution Represented by Other Solutions
2 0050251256 2814070351 7587939698 4924623115 5778894472 3618090452 2613065326 6331658291 4572864321 608040201 1199 x 2 = 2199

period = 99 i.e. 99 repeating digits.

2199, 3199, ..., 99199
3 0033444816 0535117056 8561872909 6989966555 1839464882 9431438127 090301 1299 x 3 = 3299

period = 66

299 = 13×23

2299, 3299, ..., 99299

some special cases are illustrated below

3 076923 113 x 3 = 313

period = 6

213, 313, 413
3 0434782608 6956521739 13 123 x 3 = 323

period = 22

223, 323, ..., 723
4 0025062656 64160401 1399 x 4 = 4399

period = 18

399 = 3×7×19

2399, 3399, ..., 99399

some special cases are illustrated below

4 142857 17 x 4 = 47

period = 6

-
4 0526315789 47368421 119 x 4 = 419

period = 18

219, 319, 419
5 (a cyclic number with a period of 498) 1499 x 5 = 5499

499 is a full reptend prime

2499, 3499, ..., 99499

Note that:

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:

This yields the results that:

X = the repeating digits of 17
=142857, and
the multiple = 142857 × 3 = 428571, the repeating digits of 37

The other solution is represented by 27 x 3 = 67:

There are no other solutions [1] because:

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 32, then 3 shall be the next remainder after 2 in a long division of a fraction 2F. This deduces that F = 2 x 10 - 3 = 17, giving X as the repeating digits of 217, i.e. 1176470588235294, and its multiple is 1764705882352941.

The following summarizes some of the results found in this manner:

Multiplier ns Solution Represented by Other Solutions
12 105263157894736842 219 × 12 = 119

A 2-parasitic number

Other 2-parasitic numbers:

419, 619, 819, 1019, 1219, 1419, 1619, 1819

32 1176470588235294 217 × 32 = 317 417, 617, 817, 1017
72 153846 213 × 72 = 713 -
92 18 211 × 92 = 911 -
73 1304347826086956521739 323 × 73 = 723 623, 923, 1223, 1523, 1823, 2123
194 190476 421 × 194 = 1921 -

Shifting left cyclically by double positions

An integer X shift left cyclically by double positions when it is multiplied by an integer n. X is then the repeating digits of 1F, whereby F is R = 102 - n, or a factor of R; excluding values of F for which 1F 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:

Multiplier n Solution Represented by Other Solutions
2 142857 17 × 2 = 27 27, 37
3 0103092783 5051546391 7525773195 8762886597 9381443298 9690721649 4845360824 7422680412 3711340206 185567 197 x 3 = 397 297, 397, 497, 597, ...., 3197, 3297
4 No solution - -
5 0526315789 47368421 119 x 5 = 519 219, 319
6 0212765957 4468085106 3829787234 0425531914 893617 147 x 6 = 647 247, 347, 447, 547, 647, 747
7 0322580645 16129 131 x 7 = 731 231, 331, 431

193, 293, 493, 593, 793, 893, 1093, 1193, 1393

8 0434782608 6956521739 13 123 x 8 = 823 223
9 076923 113 x 9 = 913 191, 291, 391, 491, 591, 691, 891, 991, 1091
10 No solution - -
11 0112359550 5617977528 0898876404 4943820224 7191 189 x 11 = 1189 289, 389, 489, 589, 689, 789, 889
12 No solution - -
13 0344827586 2068965517 24137931 129 x 13 = 1329 229

187, 287, 487, 587, 687

14 0232558139 5348837209 3 143 x 14 = 1443 243, 343
15 0588235294 117647 117 x 15 = 1517 -

Other bases

In duodecimal system, the transposable integers are: (using inverted two and three for ten and eleven, respectively)

Multiplier n Smallest solution such that the multiplication moves the last digit to left Digits Represented by Smallest solution such that the multiplication moves the first digit to right Digits Represented by
2 06316948421 Ɛ 1 x 2 = 2 2497 4 15 x 2 = 25
3 2497 4 15 x 3 = 35 no solution
4 0309236ᘔ8820 61647195441 1 x 4 = 4 no solution
5 025355ᘔ94330 73ᘔ458409919 Ɛ7151 25 1 x 5 = 5 186ᘔ35 6 17 x 5 = 57
6 020408142854 ᘔ997732650ᘔ1 83469163061 1 x 6 = 6 no solution
7 01899Ɛ864406 Ɛ33ᘔᘔ1542391 374594930525 5Ɛ171 35 1 x 7 = 7 no solution
8 076Ɛ45 6 117 x 8 = 817 no solution
9 014196486344 59Ɛ9384Ɛ26Ɛ5 33040547216ᘔ 1155Ɛ3Ɛ12978 ᘔ3991 45 1 x 9 = 9 no solution
08579214Ɛ364 29ᘔ7 14 115 x ᘔ = 15 no solution
Ɛ 011235930336 ᘔ53909ᘔ873Ɛ3 25819Ɛ997505 5Ɛ54ᘔ3145ᘔ42 694157078404 491Ɛ1 55 1ᘔƐ x Ɛ = ƐᘔƐ no solution

Notes

  1. P. Yiu, k-right-transposable integers, Chap.18.1 'Recreational Mathematics'

References

This article is issued from Wikipedia - version of the 4/22/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.