8 Shift

A particularly long integer ends with an 8. Shifting this 8 digit to the leftmost position creates a new number which is twice the original. Find the smallest possible value of the original number.

Clarification: This 8-shift procedure looks as follows: 123 8 8 123. 123{\color{#D61F06}8} \longrightarrow {\color{#D61F06}8}123.


The answer is 421052631578947368.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

7 solutions

John Ross
Apr 1, 2018

Just approach this problem like long multiplication.

8 × 2 \large{\begin{array}{ccccccc} && & & & & \square & 8\\ \times && & & & & &2\\ \hline & & & & & &&\square &\\ \end{array}} The bottom box is a 6 which we can then write in the upper box. Continue this process (don't forget to carry the 1's) until you reach an 8 (without a carrying 1). This will give you the smallest possible solution of 421052631578947368.

Very nice solution

Andre Bourque - 3 years, 2 months ago

That was a short multiplication when I went to school.

Stewart Gordon - 3 years, 2 months ago

Can anyone clear it please with a solution??

Pritesh Srivastava - 3 years, 2 months ago

Log in to reply

It's simple think this procedure as the following sequence a {n+1}=remain(2*a n,10)+quotient(2*a_{n-1), 10) With a0=0 and a1=8. The value of this sequence gives the all digit of the solution.

Davide Lombardi - 3 years, 2 months ago

I did that but gave up at 4210526, cuz i had no paper and was doing it in my head.

Little Narwhal - 3 years ago

The answer is wrong. The question never stated "positive integer." The answer might be -421052631578947368, something more negative, or it may be unknown.

Dennis Rodman - 2 years, 6 months ago
Patrick Corn
Mar 22, 2018

If the original number is 10 x + 8 , 10x+8, then twice that number is 8 1 0 n + x , 8 \cdot 10^n + x, where n n is the number of digits of x . x. This leads to the equation 8 ( 1 0 n 2 ) = 19 x . 8(10^n-2) = 19x. The smallest solution will use the smallest positive n n such that 1 0 n 2 10^n \equiv 2 mod 19. 19. Looking at powers of 10 10 mod 19 , 19, we see that 10 10 is a primitive root , and the smallest n n such that 1 0 n 2 10^n \equiv 2 mod 19 19 is n = 17. n=17. Checking x = 8 ( 1 0 17 2 ) 19 , x = \frac{8(10^{17}-2)}{19}, we see that it does indeed have 17 17 digits, so the answer is 10 x + 8 = 421052631578947368 . 10x+8 = \fbox{421052631578947368}.

I did the same and so I don't thing this problem has to be considered as an advanced. I thing it is easyer than many intermediates.

Pau Cantos - 3 years, 2 months ago

This is about what I did. Didn't know the primitive root thing, so I wrote a Ruby script to try #s and 17 hit.

Terry Smith - 3 years, 2 months ago
Red Mobbs
Mar 21, 2018

To phrase the problem mathematically, x 8 10 + 8 × 1 0 n = 2 x \frac{x-8}{10} + 8 \times 10^{n} = 2x , where x is our original number, and n is the amount of digits in our original number. x 8 + 8 × 1 0 n + 1 = 20 x x-8+8 \times 10^{n+1}=20x

8 ( 1 0 n + 1 1 ) = 19 x 8(10^{n+1}-1)=19x

1 0 n + 1 1 = 19 8 x 10^{n+1}-1=\frac{19}{8}x (1)

The left-hand side of this equation evaluates to 9 × 9 \times a repunit of 1. As x is an integer, and clearly, 19 does not divide 9, we can see that 19 must divide the repunit of 1. A quick calculator trick can yield the smallest repunit that has this property.

19 × 5847953216374269 = 111111111111111111 19 \times 5847953216374269=111111111111111111 , a repunit with 18 digits

This tells us that 1 0 n + 1 1 = 111111111111111111 × 9 10^{n+1}-1=111111111111111111 \times 9

1 0 n + 1 = 1 0 19 10^{n+1}=10^{19}

n = 18 n=18

Sub into (1)

( 1 0 19 1 ) 8 19 = x (10^{19}-1)\frac{8}{19}=x

x = 421052631578947368 x=421052631578947368

And indeed, 842105263157894736 2 = 421052631578947368 \frac{842105263157894736}{2}=421052631578947368

I would be interested to hear other solutions to this problem, preferably ones that do not require calculator tomfoolery

We diverged after 8*(10^(n+1)-1) = 19x.

x should be the smallest integer such as : x=8*(10^(n+1)-1)/19

So :

8*(10^(n+1)-1) = 0 [19]

10^(n+1) = 1 [19]

By Fermat theorem, we know that 10^18=1[19]

18=3 * 3 * 2

So the smallest value for n+1 should be 2, 3, 6, 9 or 18.

It works only for 18, so n+1=18 and n=17

denis baudouin - 3 years, 2 months ago

I could only follow up to "The left-hand side.." etc. How can you evaluate that?

Ermanno Attardo - 3 years, 2 months ago

Log in to reply

You could watch my answer below, using Fermat theorem. Otherwise I think the calculator trick is just to try to divide 11…[n time]…11 by 19, until it give a integer.

denis baudouin - 3 years, 1 month ago

To evaluete the digit of x there is a procedure without use calculator. 8 (10^19-1)=79999999999999999999(one 7 follow by ninetenn 9) The quotient of this number with 19 gives x (into the bracket the digit of x) : 79/19 =(4) 19+3 39/19=(2) 19+1 19/19=(1) 19+0 09/19=(0) 19+9 99/19=(5) 19+4 49/19=(2) 19+11 119/19=(6) 19+5 59/19=(3) 19+2 29/19=(1) 19+10 109/19=(5) 19+14 149/19=(7) 19+16 169/19=(8) 19 +17 179/19=(9) 19+8 89/19=(4) 19+13 139/19=(7) 19+6 69/19=(3) 19+12 129/19=(6) 19+15 159/19=(8)*19+7

Davide Lombardi - 3 years, 2 months ago
Matthew Lim
Apr 3, 2018

Let n n be the desired integer. We will use \Vert to represent concatenation. We have n = x 8 n=x\Vert8 and 2 n = 8 x 2n=8\Vert{x} for some integer x x . We can rewrite these expressions as n = 10 x + 8 n=10x+8 and 2 n = 8 1 0 a + x 2n=8*10^a+x for some integer a a . We perform some basic algebra: 2 n = 8 1 0 a + x 2 ( 10 x + 8 ) = 8 1 0 a + x 20 x + 16 = 8 1 0 a + x 19 x = 8 1 0 a 16 19 x = 8 ( 1 0 a 2 ) 19 8 x = 1 0 a 2. 2n=8*10^a+x\\ 2(10x+8)=8*10^a+x\\ 20x+16=8*10^a+x\\ 19x=8*10^a-16\\ 19x=8*(10^a-2)\\ \frac{19}{8}x=10^a-2. Since 1 0 a 2 10^a-2 is an integer, 19 8 x \frac{19}{8}x is also an integer. Since 8 8 and 19 19 are relatively prime, b = x 8 b=\frac{x}{8} is an integer. So we have 19 b = 1 0 a 2 19b=10^a-2 , or equivalently, 1 0 a 2 ( m o d 19 ) 10^a \equiv 2 \pmod{19} . Multiplying by 10 10 , we get 1 0 a + 1 1 ( m o d 19 ) 10^{a+1} \equiv 1 \pmod{19} . Since 19 19 is prime, we can use Fermat's Little Theorem to find the smallest such a a that satisfies this congruence. Then, a + 1 = 18 a+1=18 , so a = 17 a=17 . (Presumably, we could find some extremely large integers for which the desired shifting property holds by instead setting a = 1 8 2 1 , 1 8 3 1 , . . . a=18^2-1,18^3-1,... .)

From here, it is a simple matter of solving for n n : n = 10 x + 8 n = 10 ( 8 b ) + 8 n = 10 ( 8 1 0 a 2 19 ) + 8 n = 10 ( 8 1 0 17 2 19 ) + 8 n = 421052631578947368 . n=10x+8\\ n=10(8b)+8\\ n=10(8 * \frac{10^a-2}{19})+8\\ n=10(8 * \frac{10^{17}-2}{19})+8\\ n=\boxed{421052631578947368}.

The following code solves the problem more generally for the question a b c X × F = X a b c , \overline{abc\dots X} \times F = \overline{Xabc\dots}, for any factor F F and any digit X X . The code stops after too many digits have been generated; it does not actually check if a solution is reached, but that can easily be mended.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>

#define MAX_DIGIT 30
#define LAST_DIGIT 8
#define FACTOR 2

int main() {
    int d[MAX_DIGIT], c[MAX_DIGIT];
    int n = MAX_DIGIT;

    --n; d[n] = LAST_DIGIT; c[n] = 0;
    do {
        int nd = FACTOR*d[n] + c[n];
        --n; d[n] = nd % 10; c[n] = nd / 10;
        if (d[n] == LAST_DIGIT && c[n] == 0) break;
    } while (n > 0);

    n++;
    while (n < MAX_DIGIT) printf("%d", d[n++]);
    printf("\n");
}

Output:

1
421052631578947368

Well , how did you come to know that the number is of atmost 30 digits?

Ariijit Dey - 3 years, 2 months ago

Log in to reply

Each pair ( d i , c i ) (d_i,c_i) uniquely determines the remainder of the sequence. Since there are only 10 × 2 = 20 10 \times 2 = 20 possible values for the combination ( d i , c i ) (d_i,c_i) , the sequence must either reach ( 8 , 0 ) (8,0) within 20 steps or end up in a loop with period less than 20 steps.

Arjen Vreugdenhil - 3 years, 2 months ago

Log in to reply

:-) :-) Good observation!!!

Ariijit Dey - 3 years, 2 months ago
Ariijit Dey
Apr 3, 2018

A general approach can be as follows: Let the n n digit number be 10 r + d 10r+d ---------------------- (1) \textbf{(1)} After the last digit is moved to the first , the number looks like 1 0 n + 1 d + r 10^{n+1}d+r ---------------------- (2) \textbf{(2)} . By Question, 2 × ( 10 r + d ) = 1 0 n + 1 d + r 2\times(10r+d) = 10^{n+1}d+r Solving for d = 8 d=8 in the abobe expression we get r = 8.1 0 n + 1 16 19 r=\frac{8.10^{n+1}-16}{19} Since 19 19 is prime so we have the following set of congruences: 8.1 0 n + 1 16 m o d 19 8.10^{n+1} \equiv 16 \mod 19 1 0 n + 1 2 m o d 19 10^{n+1} \equiv 2 \mod 19 5.1 0 n 1 m o d 19 5.10^n \equiv 1\mod19 1 0 n 4 m o d 19 10^n \equiv 4\mod19 25.1 0 n 2 1 m o d 19 25.10^{n-2}\equiv 1\mod19 1 0 n 2 16 m o d 19 10^{n-2} \equiv 16 \mod19 25.1 0 n 4 4 m o d 19 25.10^{n-4} \equiv 4\mod19 625.1 0 n 6 1 m o d 19 625.10^{n-6} \equiv 1\mod19 1 0 n 6 9 m o d 19 10^{n-6} \equiv 9\mod19 1 0 n 7 18 m o d 19 10^{n-7} \equiv 18 \mod19

Now starting with p = 2 p=2 and repeatedly applying the congruences modulo 19 i.e, 1 0 p m o d 19 10^p \mod 19 with increasing p p . We see that p = 9 p=9 satisfies the last congruence in the above set of congruences(you could have satisfied any of the congruences in the above set but I chose the last one as it required the least effort) So, substituting 9 = p = n 7 9=p=n-7 we get n = 16 n=16 which is indeed the solution. Substitute this n n in 2 2 to get r r and in 1 1 substitute r r to get the original number

Mark Jones
Apr 2, 2018

This is a "Mind Your Decisions" video that shows both the long multiplication solution John Ross showed and the mod 19 solution Patrick Corn showed (by letting a in the video to equal 8).

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...