Fastest way to find a number in an unknown range?

user_15461189 0
Viewed 136

Sorry for the horrible title - I'm new to python and I'm not sure how to describe my question. So the question asks:

x plus 100 is a perfect square number, plus another 168 is also a perfect square number. Find x.

And here's my answer:

from math import sqrt
for x in range(-100,10000):
    a=int(sqrt(x+100))
    b=int(sqrt(x+100+168))
    if (a*a!=x+100) or (b*b!=x+100+168):
        continue
    else:
        print(x)

The problem is, I don't actually know the range. I only know that the number can't be smaller than -100, but the 10000 is only a random large number that I put in there. Is there a way for me to figure out a smaller range first? Or a way that I could make this faster?

python-3.x python
3 Answers

If you want every solution in the range, this is a faster solution

for x in range(-100,10000):
    if ((x+100)**.5).is_integer():       
        if ((x+268)**.5).is_integer():
            print(x)

If only the first solution is required, you can add a break after the print statement.

user_108830940

There is an easily ascertainable upper bound to your problem: after a couple of numbers, the difference between perfect squares is much larger than 168. (Take a look at 100^2 and 101^2. The results are perfect squares about 200 apart. With this your number will be no larger than 10,000).

If you would like to speed up your problem, rather than checking if a number is square, you can check if by squaring numbers you can achieve a solution.

for x in range(0,100):
    y=x
    while y**2 - x**2 < 169 and y < 100:
        y+=1
        if y**2 - x**2 == 168:
            print("Your number is: " + str(x**2 - 100))

Edit: code was broken, fixed. Running this gives you -99 (-99 + 100 is 1, is a perfect square, 1 + 168 is 169, which is 13^2), 21, 261, and 1581

user_153403940

Since the prompt assumes only one correct value of x, then there is no need to use a for loop, as we can just loop indefinitely using a while and no upper bound is known.

To check if the result of an operation is a whole number, we can check if the float and integer representation of the number are equal, i.e. int(num) == num.

>>> i = 1
>>> while True:
        a, b = (i+100)**0.5, (i+268)**0.5
        if int(a) == a and int(b) == b:
            break
        i += 1

        
>>> i
21

And if we check the quality of the result obtained, both results are whole numbers:

>>> (i+100)**0.5
11.0
>>> (i+268)**0.5
17.0
user_137463890
Related