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:
Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Back
Top