MHB Find x and y values that satisfy the given conditions

  • Thread starter Thread starter Albert1
  • Start date Start date
  • Tags Tags
    Value
AI Thread Summary
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.
Albert1
Messages
1,221
Reaction score
0
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
 
Mathematics news on Phys.org
Re: find the value of x and y

$$x^2 \equiv x \pmod{1000} \tag{1}$$
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.​
 
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

y=141376=$376^2$ , and 390625=$625^2$
 
Last edited:
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.
Thread 'Imaginary Pythagoras'
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...
Back
Top