On 04/08/17 15:51, Steve D'Aprano wrote:
Another hint: if you run this code:
for i in range(53, 1024):
n = 2**i
if isqrt_newton(n) != isqrt_float(n):
print(n)
break
you can find a much better upper bound for M:
2**53 < M <= 2**105
which is considerable smaller that the earlier upper bound of 2**1024. But even
so, that's still 40564819207303331840695247831040 values to be tested.
On the assumption that we want a solution before the return of Halley's Comet,
how would you go about finding M?
I tried a variation of what you used to cut down the search space further:
for j in range(0, 53):
for i in range(53, 105):
n = 2**i + 2**j
if isqrt_newton(n) != isqrt_float(n):
print(n, i, j)
sys.exit(1)
which gave me a new upper bound of 2**54+2**28. Reversing the order of
the loops would probably have been more sensible, but what the heck.
That's only (!) 9007199523176448 values to test, which my machine seemed
to be quite happy with, but you could repeat the exercise with more
layers if you really wanted to.
--
Rhodri James *-* Kynesim Ltd
--
https://mail.python.org/mailman/listinfo/python-list
