How long could it be?

Number Theory Level 4

A rather long number ends with an 8. If this digit, i.e. the 8, is shifted to the front position, we obtain a number which is twice the original number. Find the smallest positive integer that satisfies.

The answer is 421052631578947368.

2 solutions

Vincent Miller Moral
Sep 18, 2015

n = 8
carry = 0
n_str = ""

while True:
    temp = n*2 + carry
    n = temp % 10
    carry = temp / 10
    n_str += str(n)
    if n == 8 and carry == 0:
        print n_str[-2::-1] + "8"
        break

Jesse Nieminen
Sep 17, 2015

We know that the number ends with 8.

Therefore we know that the first digit is 4, second is 2 and third is 1. (divide by 2) (There is no other way to get a number starting with 8, 84 or 842)

We also know that the second last digit is 6 (2 * 8 = 16). (Here also is no other way because 8 must be the last digit)

Now we know that the number ends with 68.

From this we can calculate the third last digit which is 3 (2 * 68 = 136).

Using this method we continue until we hit 052631578947368

Now we cannot continue, but we know the first 3 digits.

Now we have 421052631578947368 which is the number we are trying to find, because 2 * 421052631578947368 = 842105263157894736.

Moderator note:

Good initial approach to figuring out what the answer has to be like.

There is a pretty short Number theoretic approach. Hint: What is the equation represented by the problem?

@Sharky Kesa It's too tedious. Don't you think the problem should be tagged as Computer Science ?

Satyajit Mohanty - 5 years, 8 months ago

I solved it WITHOUT any computer science.

Hint hint: 8/19 decimal expansion.

Paul Paul - 5 years, 8 months ago

Great! man, but, could you explain me, why 8 divided by 19?

Victor Rodriguez - 5 years, 7 months ago

@Victor Rodriguez – When a number happens to be a multiple of its own rotation, I immediately think about 142857. 1/7 has decimal expansion "0.(142857)". That is one thing to know. I need to find such a number myself.

Then, I need to find a number which obeys 2(10x+k) = pk + x (where p is the lowest power of 10 larger than x) which gives 19x = (p-2)k. That hints that it's 19.

So I try 1/19. Well, I try to look after the digit 8. It's in 2 places, I try both cases (only the one where it is followed by 4 in the loop works) and I get the number.

I conjecture this trick, while non-rigorous, works for any problem of this kind.

Paul Paul - 5 years, 7 months ago

@Paul Paul – Thanks, it's clear now. (:

Victor Rodriguez - 5 years, 7 months ago

Perhaps, that might be best.

Sharky Kesa - 5 years, 8 months ago

Good initial approach to figuring out what the answer has to be like.

There is a pretty short Number theoretic approach. Hint: What is the equation represented by the problem?

Calvin Lin Staff - 5 years, 8 months ago

8*(10^k) + (x - 8)/10 = 2x, where k and x are non-negative integers

8*(10^(k+1) - 1) = 19x

10^(k+1) = 1 (mod 19)

Using Fermat's little theorem we know that k + 1 = 18n, where n is a positive integer

We want to find the smallest solution so k = 17.

Therefore x = 421052631578947368

Jesse Nieminen - 5 years, 8 months ago

Yes, that's the idea! Note that Fermat's Little Theorem only tells you that $10^{18} \equiv 1 \pmod{19}$ . It doesn't tell you that 18 is the smallest solution to $10 ^ n \equiv 1 \pmod{19}$ , which is known as the Order of 10 mod 18. So, we still have to check that 1, 2, 3, .... do not work.

Of course, we need to check that $x > 10 ^ k$ in order for that equation to be valid, but it also follows from the setup.

Calvin Lin Staff - 5 years, 8 months ago

How long could it be?

The answer is 421052631578947368.

2 solutions

Moderator note:

0 pending reports