About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
February 2013
When preparing the challenge this month, I made a small mistake that made the question much easier than intended.
Here is the solution, as I derived it:
Let y^2 be a k-digits-long number, giving us 10^k x^2 + y^2 = z^2.
Write z=10^k a + b and we get
10^k x^2 + y^2 = (10^k a + b)^2 = 10^k a(10^k a+ 2b) + b^2.
So, b^2=y^2 (mod 10^k). Here I made the mistake of concluding that b=y.
Those who want to try to solve a more difficult version of the question, can stop here and ponder a little on solving this version.
My mistake was, of course, that b can be -y mod(10^k), which lends itself to several trivial solutions like
x = 5 * 10^(k-1) - 1; y = 10^k -1; and z = 5 * 10^(2 * k-1) - 10^k + 1.
If we continue with the assumption that b=y, we get
x^2 = a^2 10^k + 2ya
so y = (x^2-a^2 10^k) / 2a.
For every k and a, we can compute x as ceil(a*sqrt(10^k)) and check whether the resulting y is divisible by 2a.
The fact that sqrt(10^37) is surprisingly close to an integer (~3162277660168379331.99889) gives us, for k=37, many possible solutions. Choosing a=463 gives us the intended solution of
x=1464134556657959630716
y=1619999831463380856
z=4630000000000000000001619999831463380856
J�nos Kram�r and Andreas Stiller sent us a solution with y=1, where one can solve Pell's equation: 10*x^2 + 1 = z^2 and get:
x=44101535838578367767701517414261786147419230399948898912033566977281348406767427039616458154500555609301871792239537197062035119616191426015391050131988492071587920645046734772112341070906349353550324660996677696009221202338336
y=1
z=139461301561451525695691667071742666259644328693387043194785898131383963733064589327602699959968509145992213260946921467365082720725567556648743873803852310099994956836260701173999664267548159260952703090632330767251579838305281
Jan Fricke also used Pell's equation to get to a solution with 60,503 digits.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com