The discussion focuses on finding three-digit numbers \( x = abc \) such that \( y = x^2 \) and the last three digits of \( y \) equal \( abc \). The analysis reveals that \( x^2 \equiv x \pmod{1000} \) leads to potential solutions being narrowed down to \( x = 376 \) and \( x = 625 \). Calculations confirm that \( y = 141376 \) for \( x = 376 \) and \( y = 390625 \) for \( x = 625 \). The exploration also highlights the efficiency of the algorithm used to find these solutions, significantly reducing the number of candidates checked.
Clearly for $x$ coprime to $1000$, the only solutions are the trivial $x = 0$ and $x = 1$, so all nontrivial solutions for $x$ must be divisible by either $2$ or $5$, or both. This leaves us with about $600$ possible candidates. Now it should be clear that if a solution works for $1000$, it will also work for $100$, and for $10$. Let's try and find the solutions for $10$:
$$x^2 \equiv x \pmod{10} \tag{2}$$
We have $5$ potential solutions here, namely $2, 4, 5, 6, 8$ (modulo $10$). Let's check each of them manually, some calculations show that only $5$ and $6$ work. So the solutions must have either $5$ or $6$ as a last digit. Let's now extend our search to $100$, armed with this information (which reduces the set of possible solutions considerably):
$$x^2 \equiv x \pmod{100} \tag{3}$$
We know from the previous step that the potential solutions are $5, 6, 15, 16, \cdots$. A short exhaustive search tells us that only $25$ and $76$ work. Finally, we have narrowed down the search enough to look for the real solutions:
$$x^2 \equiv x \pmod{1000} \tag{4}$$
The only possible solutions are $25, 76, 125, 176, \cdots$. Again, trying those 20 potential solutions shows that only $376$ and $625$ work. Therefore, the solutions are $x \in \{ 0, \, 1, \, 376, \, 625 \}$. QED.
This might look like a non-answer given the amount of trial and error involved, but consider that we've only had to try $45$ potential candidates instead of the original $600$, and the cost of this algorithm is asymptotically logarithmic, for instance, finding the solutions with $m = 100000$ would only take $85$ trials, quite efficient.
Here's an Python 3 script implementing the algorithm outlined above, using recursion, for powers of $10$:
Code:
# Work count
work = 0
def Verify(x, m):
global work
work += 1
return pow(x, 2, 10**m) == x
def Solve(m):
# Solutions
found = []
if m == 1:
for x in [2, 4, 5, 6, 8]: # Precomputed
if Verify(x, m):
found.append(x)
return found
possible = Solve(m - 1)
for p in possible:
for x in range(p, 10**m, 10**(m - 1)):
if Verify(x, m):
found.append(x)
return found
def Enumerate(m):
global work
work = 0
found = Solve(m)
# Add trivial solutions
found.append(0)
found.append(1)
found.sort()
print("Solutions are {" + ', '.join(str(x) for x in found) + "}.")
print("Checked " + str(work) + " candidates.")
Which gives us (spaces added for readability):
Code:
>>> Enumerate(1) # For 10
Solutions are {0, 1, 5, 6}.
Checked 5 candidates.
>>> Enumerate(2) # For 100
Solutions are {0, 1, 25, 76}.
Checked 25 candidates.
>>> Enumerate(3) # For 1000
Solutions are {0, 1, 376, 625}.
Checked 45 candidates.
>>> Enumerate(5) # For 100000
Solutions are {0, 1, 9376, 90625}.
Checked 85 candidates.
>>> Enumerate(8) # For 100000000
Solutions are {0, 1, 12890625, 87109376}.
Checked 145 candidates.
Interestingly, there are only two nontrivial solutions for any power of $10$, and these two solutions add up to $-1$ modulo said power, suggesting that there might exist an analytic solution to this problem, though the prime factorisations of the solutions display no obvious pattern apart from a large number of powers of $2$ and $5$.
So if a better way to do this exists, I'd be interested to see it. It is worth noting that the condition $x^2 \equiv x \pmod{m}$ implies $x^n \equiv x \pmod{m}$ for all $n > 0$, but I could not find how to use this property, sadly.
#3
Albert1
1,221
0
Re: find the value of x and y
Albert said:
x=abc is a three digits number
y=$x^2$
the last 3 digits of y is also equal to abc
that is y=?abc
please find x and y
y-x =$x^2-x =x(x-1)$ must be a multiple of 1000
for 1000=$2^3 \times 5^3 =8\times 125$
further more x and (x-1) are coprime
if x is a multiple of 125 then x-1 must be a multiple of 8---------(1)
if x is a multiple of 8 then x-1 must be a multiple of 125---------(2)
so the possible solutions meet restriction of (1) and (2) will be x=376 , and x=625
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Is it possible to arrange six pencils such that each one touches the other five? If so, how? This is an adaption of a Martin Gardner puzzle only I changed it from cigarettes to pencils and left out the clues because PF folks don’t need clues. From the book “My Best Mathematical and Logic Puzzles”. Dover, 1994.
I posted this in the Lame Math thread, but it's got me thinking.
Is there any validity to this? Or is it really just a mathematical trick?
Naively, I see that i2 + plus 12 does equal zero2.
But does this have a meaning?
I know one can treat the imaginary number line as just another axis like the reals, but does that mean this does represent a triangle in the complex plane with a hypotenuse of length zero?
Ibix offered a rendering of the diagram using what I assume is matrix* notation...