Parasitic number

From Wikipedia, the free encyclopedia
  (Redirected from Parasitic numbers)
Jump to navigation Jump to search

An n-parasitic number (in base 10) 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 place. For example, 4•128205=512820, so 128205 is 4-parasitic. Most authors do not allow leading zeros to be used, and this article follows that convention. So even though 4•025641=102564, the number 025641 is not 4-parasitic.

Derivation[edit]

An n-parasitic number can be derived by starting with a digit k (which should be equal to n or greater) in the rightmost (units) place, and working up one digit at a time. For example, for n = 4 and k = 7

4•7=28
4•87=348
4•487=1948
4•9487=37948
4•79487=317948
4•179487=717948.

So 179487 is a 4-parasitic number with units digit 7. Others are 179487179487, 179487179487179487, etc.

Notice that the repeating decimal

Thus

In general, an n-parasitic number can be found as follows. Pick a one digit integer k such that kn, and take the period of the repeating decimal k/(10n−1). This will be where m is the length of the period; i.e. the multiplicative order of 10 modulo (10n − 1).

For another example, if n = 2, then 10n − 1 = 19 and the repeating decimal for 1/19 is

So that for 2/19 is double that:

The length m of this period is 18, the same as the order of 10 modulo 19, so 2 × (1018 − 1)/19 = 105263157894736842.

105263157894736842 × 2 = 210526315789473684, which is the result of moving the last digit of 105263157894736842 to the front.

Additional Information[edit]

The step-by-step derivation algorithm depicted above is a great core technique but will not find all n-parasitic numbers. It literally gets stuck in an infinite loop with the derived number equaling the derivation source. An example of this where n = 5 and k = 5. The 42-digit n-parasitic number to be derived is 102040816326530612244897959183673469387755. Check the steps in Table One below. The algorithm begins building from right to left until it reaches step 15—then the infinite loop occurs. Lines 16 and 17 are pictured to show that nothing changes. There is a fix for this problem, and when applied, the algorithm will not only find all n-parasitic numbers in base ten, it will find them in base 8 and base 16 as well. Look at line 15 in Table Two. The fix, when this condition is identified and the n-parasitic number has not been found, is simply to not shift the product from the multiplication, but use it as is, and append n (in this case 5) to the end. After 42 steps, the proper parasitic number will be found.

Table One[edit]

1. 5 * 5 = 25 - Shift = 55
2. 5 * 55 = 275 - Shift = 755
3. 5 * 755 = 3775 - Shift = 7755
4. 5 * 7755 = 38775 - Shift = 87755
5. 5 * 87755 = 438775 - Shift = 387755
6. 5 * 387755 = 1938775 - Shift = 9387755
7. 5 * 9387755 = 46938775 - Shift = 69387755
8. 5 * 69387755 = 346938775 - Shift = 469387755
9. 5 * 469387755 = 2346938775 - Shift = 3469387755
10. 5 * 3469387755 = 17346938775 - Shift = 73469387755
11. 5 * 73469387755 = 367346938775 - Shift = 673469387755
12. 5 * 673469387755 = 3367346938775 - Shift = 3673469387755
13. 5 * 3673469387755 = 18367346938775 - Shift = 83673469387755
14. 5 * 83673469387755 = 418367346938775 - Shift = 183673469387755
15. 5 * 183673469387755 = 918367346938775 - Shift = 183673469387755
16. 5 * 183673469387755 = 918367346938775 - Shift = 183673469387755
17. 5 * 183673469387755 = 918367346938775 - Shift = 183673469387755

Table Two[edit]

1. 5 * 5 = 25 - Shift = 55
2. 5 * 55 = 275 - Shift = 755
3. 5 * 755 = 3775 - Shift = 7755
4. 5 * 7755 = 38775 - Shift = 87755
5. 5 * 87755 = 438775 - Shift = 387755
6. 5 * 387755 = 1938775 - Shift = 9387755
7. 5 * 9387755 = 46938775 - Shift = 69387755
8. 5 * 69387755 = 346938775 - Shift = 469387755
9. 5 * 469387755 = 2346938775 - Shift = 3469387755
10. 5 * 3469387755 = 17346938775 - Shift = 73469387755
11. 5 * 73469387755 = 367346938775 - Shift = 673469387755
12. 5 * 673469387755 = 3367346938775 - Shift = 3673469387755
13. 5 * 3673469387755 = 18367346938775 - Shift = 83673469387755
14. 5 * 83673469387755 = 418367346938775 - Shift = 183673469387755
15. 5 * 183673469387755 = 918367346938775 - Shift = 9183673469387755
16. 5 * 9183673469387755 = 45918367346938775 - Shift = 59183673469387755
17. 5 * 59183673469387755 = 295918367346938775 - Shift = 959183673469387755

There is one more condition to be aware of when working with this algorithm, leading zeros must not be lost. When the shift number is created it may contain a leading zero which is positionally important and must be carried into and through the next step. Calculators and computer math methods will remove leading zeros. Look at Table Three below displaying the derivation steps for n=4 and k=4. The Shift number created in step 4, 02564, has a leading zero which is fed into step 5 creating a leading zero product. The resulting Shift is fed into Step 6 which displays a product proving the 4-parasitic number ending in 4 is 102564.

Table Three[edit]

1. 4 * 4 = 16 - Shift = 64
2. 4 * 64 = 256 - Shift = 564
3. 4 * 564 = 2256 - Shift = 2564
4. 4 * 2564 = 10256 - Shift = 02564
5. 4 * 02564 = 010256 - Shift = 102564
6. 4 * 102564 = 410256 - Shift = 102564

Smallest n-parasitic numbers[edit]

The smallest n-parasitic numbers are also known as Dyson numbers, after a puzzle concerning these numbers posed by Freeman Dyson.[1][2][3] They are: (leading zeros are not allowed) (sequence A092697 in the OEIS)

n Smallest n-parasitic number Digits Period of
1 1 1 1/9
2 105263157894736842 18 2/19
3 1034482758620689655172413793 28 3/29
4 102564 6 4/39
5 102040816326530612244897959183673469387755 42 5/49
6 1016949152542372881355932203389830508474576271186440677966 58 6/59
7 1014492753623188405797 22 7/69
8 1012658227848 13 8/79
9 10112359550561797752808988764044943820224719 44 9/89

General note[edit]

In general, if we relax the rules to allow a leading zero, then there are 9 n-parasitic numbers for each n. Otherwise only if kn then the numbers do not start with zero and hence fit the actual definition.

Other n-parasitic integers can be built by concatenation. For example, since 179487 is a 4-parasitic number, so are 179487179487, 179487179487179487 etc.

Other bases[edit]

In duodecimal system, the smallest n-parasitic numbers are: (using inverted two and three for ten and eleven, respectively) (leading zeros are not allowed)

n Smallest n-parasitic number Digits Period of
1 1 1 1/Ɛ
2 10631694842 Ɛ 2/1Ɛ
3 2497 4 7/2Ɛ = 1/5
4 10309236ᘔ88206164719544 4/3Ɛ
5 1025355ᘔ9433073ᘔ458409919Ɛ715 25 5/4Ɛ
6 1020408142854ᘔ997732650ᘔ18346916306 6/5Ɛ
7 101899Ɛ864406Ɛ33ᘔᘔ15423913745949305255Ɛ17 35 7/6Ɛ
8 131ᘔ8ᘔ 6 /7Ɛ = 2/17
9 101419648634459Ɛ9384Ɛ26Ɛ533040547216ᘔ1155Ɛ3Ɛ12978ᘔ399 45 9/8Ɛ
14Ɛ36429ᘔ7085792 14 12/9Ɛ = 2/15
Ɛ 1011235930336ᘔ53909ᘔ873Ɛ325819Ɛ9975055Ɛ54ᘔ3145ᘔ42694157078404491Ɛ 55 Ɛ/ᘔƐ

Strict definition[edit]

In strict definition, least number m beginning with 1 such that the quotient m/n is obtained merely by shifting the leftmost digit 1 of m to the right end are

1, 105263157894736842, 1034482758620689655172413793, 102564, 102040816326530612244897959183673469387755, 1016949152542372881355932203389830508474576271186440677966, 1014492753623188405797, 1012658227848, 10112359550561797752808988764044943820224719, 10, 100917431192660550458715596330275229357798165137614678899082568807339449541284403669724770642201834862385321, 100840336134453781512605042016806722689075630252, ... (sequence A128857 in the OEIS)

They are the period of n/(10n - 1), also the period of the decadic integer -n/(10n - 1).

Number of digits of them are

1, 18, 28, 6, 42, 58, 22, 13, 44, 2, 108, 48, 21, 46, 148, 13, 78, 178, 6, 99, 18, 8, 228, 7, 41, 6, 268, 15, 272, 66, 34, 28, 138, 112, 116, 179, 5, 378, 388, 18, 204, 418, 6, 219, 32, 48, 66, 239, 81, 498, ... (sequence A128858 in the OEIS)

See also[edit]

Notes[edit]

  1. ^ Dawidoff, Nicholas (March 25, 2009), "The Civil Heretic", New York Times Magazine.
  2. ^ Tierney, John (April 6, 2009), "Freeman Dyson's 4th-Grade Math Puzzle", New York Times.
  3. ^ Tierney, John (April 13, 2009), "Prize for Dyson Puzzle", New York Times.

References[edit]