## Euler 206- Concealed Square

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.

First thought was brute force by replacing blanks with numbers, and checking for a square root. This comes to a mere 10^9 possibilities, with a lot of parsing longs from string. After a bit of analysis though, you realize the last digit of the number we are looking for has to be 0. (0 being the only a*a to result in a 0 digit at the end). This also means the first blank is a 0, giving a mere 10^8 possibilities. Next is to realize that 9 can only be formed by a 3, or a 7 in the number. (Try not to forget the 7, as I did the first time through). So, we now know the target square ends in either 70 or 30.

We can move away a lot of parsing longs from strings, and sqrt’s, by just iterating over the possible answers, rather then the possible answers^2. This basically means iterating from 10^9+30 to something less then 10^10 (sqrt of 1929394959697989900; though I’m far too boring to plug that into a calculator). As already stated, we’re looking for something ending in 30 or 70, so we could start with 10^9+30 and increment by 100, then switch to +70, or alternatively alter increments of 40 and 60.

Probably the most complex thing is checking whether or not a square is of the desired format. For that I get the string representation of the square, and then in a for loop check that every other character is incrementing; with a special check for the 0 case. I envision there are better ways, but this was good enough for this problem.

Code:

static void Main(string[] args) { long start = 1000000000; //add 100 to long on the off chance that there's a terrible loss // of precision in the constant double long end = (long)(Math.Sqrt(1929394959697989900))+100; Test(start + 30, end, 100); Test(start + 70, end, 100); } static void Test(long start, long end, long incr) { for (long current = start; current < end; current += incr) { string squareString = (current * current).ToString(); bool isValid = true; for (int i = 1; i <= 9 && isValid; i++) if (squareString[2 * (i - 1)] != '0' + i) isValid = false; if (squareString[2 * (10 - 1)] != '0') isValid = false; if (isValid) Console.WriteLine("Solution: " + current); } } |

Tags: project euler