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: 1 2 3 8 ⟶ 8 1 2 3 .
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.
Very nice solution
That was a short multiplication when I went to school.
Can anyone clear it please with a solution??
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.
I did that but gave up at 4210526, cuz i had no paper and was doing it in my head.
The answer is wrong. The question never stated "positive integer." The answer might be -421052631578947368, something more negative, or it may be unknown.
If the original number is 1 0 x + 8 , then twice that number is 8 ⋅ 1 0 n + x , where n is the number of digits of x . This leads to the equation 8 ( 1 0 n − 2 ) = 1 9 x . The smallest solution will use the smallest positive n such that 1 0 n ≡ 2 mod 1 9 . Looking at powers of 1 0 mod 1 9 , we see that 1 0 is a primitive root , and the smallest n such that 1 0 n ≡ 2 mod 1 9 is n = 1 7 . Checking x = 1 9 8 ( 1 0 1 7 − 2 ) , we see that it does indeed have 1 7 digits, so the answer is 1 0 x + 8 = 4 2 1 0 5 2 6 3 1 5 7 8 9 4 7 3 6 8 .
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.
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.
To phrase the problem mathematically, 1 0 x − 8 + 8 × 1 0 n = 2 x , where x is our original number, and n is the amount of digits in our original number. x − 8 + 8 × 1 0 n + 1 = 2 0 x
8 ( 1 0 n + 1 − 1 ) = 1 9 x
1 0 n + 1 − 1 = 8 1 9 x (1)
The left-hand side of this equation evaluates to 9 × 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.
1 9 × 5 8 4 7 9 5 3 2 1 6 3 7 4 2 6 9 = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 , a repunit with 18 digits
This tells us that 1 0 n + 1 − 1 = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 × 9
1 0 n + 1 = 1 0 1 9
n = 1 8
Sub into (1)
( 1 0 1 9 − 1 ) 1 9 8 = x
x = 4 2 1 0 5 2 6 3 1 5 7 8 9 4 7 3 6 8
And indeed, 2 8 4 2 1 0 5 2 6 3 1 5 7 8 9 4 7 3 6 = 4 2 1 0 5 2 6 3 1 5 7 8 9 4 7 3 6 8
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
I could only follow up to "The left-hand side.." etc. How can you evaluate that?
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.
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
Let n be the desired integer. We will use ∥ to represent concatenation. We have n = x ∥ 8 and 2 n = 8 ∥ x for some integer x . We can rewrite these expressions as n = 1 0 x + 8 and 2 n = 8 ∗ 1 0 a + x for some integer a . We perform some basic algebra: 2 n = 8 ∗ 1 0 a + x 2 ( 1 0 x + 8 ) = 8 ∗ 1 0 a + x 2 0 x + 1 6 = 8 ∗ 1 0 a + x 1 9 x = 8 ∗ 1 0 a − 1 6 1 9 x = 8 ∗ ( 1 0 a − 2 ) 8 1 9 x = 1 0 a − 2 . Since 1 0 a − 2 is an integer, 8 1 9 x is also an integer. Since 8 and 1 9 are relatively prime, b = 8 x is an integer. So we have 1 9 b = 1 0 a − 2 , or equivalently, 1 0 a ≡ 2 ( m o d 1 9 ) . Multiplying by 1 0 , we get 1 0 a + 1 ≡ 1 ( m o d 1 9 ) . Since 1 9 is prime, we can use Fermat's Little Theorem to find the smallest such a that satisfies this congruence. Then, a + 1 = 1 8 , so a = 1 7 . (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 , . . . .)
From here, it is a simple matter of solving for n : n = 1 0 x + 8 n = 1 0 ( 8 b ) + 8 n = 1 0 ( 8 ∗ 1 9 1 0 a − 2 ) + 8 n = 1 0 ( 8 ∗ 1 9 1 0 1 7 − 2 ) + 8 n = 4 2 1 0 5 2 6 3 1 5 7 8 9 4 7 3 6 8 .
The following code solves the problem more generally for the question a b c … X × F = X a b c … , for any factor F and any digit 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 |
|
Output:
1 |
|
Well , how did you come to know that the number is of atmost 30 digits?
Log in to reply
Each pair ( d i , c i ) uniquely determines the remainder of the sequence. Since there are only 1 0 × 2 = 2 0 possible values for the combination ( d i , c i ) , the sequence must either reach ( 8 , 0 ) within 20 steps or end up in a loop with period less than 20 steps.
A general approach can be as follows: Let the n digit number be 1 0 r + d ---------------------- (1) After the last digit is moved to the first , the number looks like 1 0 n + 1 d + r ---------------------- (2) . By Question, 2 × ( 1 0 r + d ) = 1 0 n + 1 d + r Solving for d = 8 in the abobe expression we get r = 1 9 8 . 1 0 n + 1 − 1 6 Since 1 9 is prime so we have the following set of congruences: 8 . 1 0 n + 1 ≡ 1 6 m o d 1 9 1 0 n + 1 ≡ 2 m o d 1 9 5 . 1 0 n ≡ 1 m o d 1 9 1 0 n ≡ 4 m o d 1 9 2 5 . 1 0 n − 2 ≡ 1 m o d 1 9 1 0 n − 2 ≡ 1 6 m o d 1 9 2 5 . 1 0 n − 4 ≡ 4 m o d 1 9 6 2 5 . 1 0 n − 6 ≡ 1 m o d 1 9 1 0 n − 6 ≡ 9 m o d 1 9 1 0 n − 7 ≡ 1 8 m o d 1 9
Now starting with p = 2 and repeatedly applying the congruences modulo 19 i.e, 1 0 p m o d 1 9 with increasing p . We see that 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 we get n = 1 6 which is indeed the solution. Substitute this n in 2 to get r and in 1 substitute r to get the original number
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).
Problem Loading...
Note Loading...
Set Loading...
Just approach this problem like long multiplication.
× □ 8 2 □ 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.