Project Euler 206: Find the unique positive integer for a concealed square
Problem Description
Find the unique positive integer whose square has the form 1_2_3_4_5_6_7_8_9_0,
where each “_” is a single digit.
Analysis
The square of any number, n, will end in 00 if the last digit of n is zero. So, our square root ends in a zero and the square has the form 1_2_3_4_5_6_7_8_900.
We can reduce our search to 1_2_3_4_5_6_7_8_9 and multiply the square root (when we find it) by 10. Now, the only way to end a square with 9 is to square a number ending with 3 or 7. OK, so our square root ends with 3 or 7, an odd number, and we can skip even-numbered n from consideration.
Let’s begin our search with the maximum possible number, 19293949596979899 and take its square root. Starting with an odd number we count down by 2 until the square fits our pattern.
Project Euler 206 Solution
Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 206 Solution Python 2.7 source.
Afterthoughts
- The square root can only be a 9 digit integer that starts with 1 and ends with 0.
Project Euler 206 Solution last updated
it shows the wrong answer as i think It provide the Square of no. than the Square Root.
Posted by pado Likho | December 29, 2021, 3:41 AMI do like your approach to matching. I came here because I couldn’t see what was wrong with my solution. As it happens, I was offering the square rather than the square root. 🙁
Posted by Bill | March 19, 2016, 10:26 AMThanks, Bill. Glad it helped.
Posted by Mike Molony | March 23, 2016, 11:40 PMThe assumption made is incompletely justified for the problem statement
The question asks for the number whose square is 1_2_3…_9_0
There is no explicit guarantee that n ends in 0, only that n^2 ends in 0.
A better rationale is that there is no value other than a multiple of 10, that when multiplied by itself which gives x0, thus n must be divisible by 10
Posted by Philip Whitehouse | December 8, 2012, 6:01 PMPhil, if someone planted an explosive device under your chair and told you that to disarm it all you had to do was type in any integer ending with a zero that, when squared, would not end with a zero would you be blown left or right from the concussion?
Posted by Mike | February 3, 2014, 11:25 PMPHIL GOT PWNT!!!!
Posted by George | August 24, 2015, 7:29 PMIf a proper square ends in 0, then its square root ends in a zero.
Proof:
0x0=[0]
1×1=[1]
2×2=[4]
3×3=[9]
4×4=1[6]
5×5=2[5]
6×6=3[6]
7×7=4[9]
8×8=6[4]
9×9=8[1]
Occurances of a square ending in a zero: 1; 0x0.
So, the square root ends in a zero.
Posted by Anonymous | July 28, 2017, 12:59 PMI forgot the =0 in 0x0=0. whoops
Posted by Anonymous | July 28, 2017, 1:00 PM