It's like you're my mirror, my mirror staring back at me

What is the sum of all six-digit positive integer(s) such that they satisfy the property that the number equals to the last six (rightmost) digits of its own square?


The answer is 1000001.

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.

2 solutions

Pi Han Goh
Apr 16, 2015

Let 1 0 5 x < 1 0 6 10^5 \leqslant x < 10^6 be the integer(s) satisfying the given constraints.

We have x 2 x ( m o d 1 0 6 ) x ( x 1 ) 0 ( m o d 1 0 6 ) x^2 \equiv x \pmod{10^6} \Rightarrow x(x-1) \equiv 0 \pmod{10^6} . Because x x and x 1 x-1 are coprime and 1 0 6 10^6 factors to 2 6 × 5 6 2^6 \times 5^6 , then one of x , x 1 x,x-1 divides 2 6 2^6 and the other divides 5 6 5^6 . This will be a simple case of Chinese Remainder Theorem.

Case 1: x m o d 2 6 = 0 , x m o d 5 6 = 1 x = 109376 x \bmod {2^6} = 0 , x \bmod {5^6} = 1 \Rightarrow x = 109376

Case 2: x m o d 2 6 = 1 , x m o d 5 6 = 0 x = 890625 x \bmod {2^6} = 1 , x \bmod {5^6} = 0 \Rightarrow x = 890625

Add them up gives 1 0 6 + 1 \boxed{10^6 + 1} .

Great solution!

Phạm Hoàng - 3 years, 1 month ago

This is brilliant - I totally forgot about factoring and derived a non-linear recursive relation for the digits, starting with the least significant digit d 0 d_0 on the right. Using m o d 10 \mod 10 on both sides, you get d 0 2 d 0 m o d 10 d 0 { 0 ; 1 ; 5 ; 6 } d_0^2\equiv d_0\mod 10\quad\Rightarrow\quad d_0\in\{0;\:1;\: 5;\:6\} and can work from there to find the recursive relation, it will involve a convolution of the digits already found. The first two cases lead to x = 0 , x = 1 x=0,\: x=1 and can be ignored for 6-digit solutions. You conveniently ignored them too, I see...

Carsten Meyer - 1 year, 1 month ago

Log in to reply

Well, I consider 0 and 1 to be 1-digit integers....

Pi Han Goh - 1 year, 1 month ago

Log in to reply

They are, but they are also solutions to x ( x 1 ) 0 m o d 1 0 6 x(x-1)\equiv 0 \mod 10^6 . I know it's nitpicking (and I'm sorry if I'm being too pedantic here), but wouldn't it be clearer to list them, too, and discard them later for not having enough digits?

Carsten Meyer - 1 year, 1 month ago

Log in to reply

@Carsten Meyer Oh, I immediately make the constraint that x x is a 6-digit number, so I didn't bother writing x = 0 , 1 x=0,1 should be a solution. I'm going to add that in.

Pi Han Goh - 1 year, 1 month ago

Log in to reply

@Pi Han Goh Thank you, that's great!

Carsten Meyer - 1 year, 1 month ago
Brian Furtado
May 4, 2015

total <- 0
for(k in 10^5:(10^6-1)){
if(k == (k^2 %% 10^6)){
total <- total + k
}
}
print(total)



0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...