# Solutions for Problem 206

Find the unique positive integer n with n2 = 1_2_3_4_5_6_7_8_9_0 where _ may be any digit.

Runtime: 8.104 seconds

```{- Function to test the digits, note the last four (?9?0) are already accounted for! -}
okDigs :: Integer -> Bool
okDigs n = inner (div n 100) [8,7,6,5,4,3,2]
where
inner :: Integer -> [Integer] -> Bool
inner i [] = i == 1
inner i (d:ds) = mod i 10 == d && inner (div i 100) ds

{- Print the number with the last digit added... find the rest by taking the head of
- the filter of the check of the digits. Start with the square root (sort of) and
- increment up testing the two numbers that will have a 9 as the last digit (i.e.
- ending in 3 or 7 - noted by Althalus). -}
main = print (10 * (head (filter (\x -> okDigs (x * x))
[101010100 + r + k | r <- [0,10..], k <- [3,7]])))
```

and because one line solutions have been mentioned, you can inline the "okDigs" as a fold left function and create this horrible line of code:

```main=print(10*(head(filter(\x->fst(foldl(\(b,n)y->(\z->(b&&mod z 10==y,z))(div n 100))(True,x*x)[8,7..1]))[101010100+r+k|r<-[0,10..],k<-[3,7]])))
```

Thanks to Althalus for the optimisation to ensure the "9" in the right place, makes iteration much faster (reduce by a factor of 5 the number of numbers to check). Also used a simpler comparison function to save some computation there as well. Now down to well below the 1 minute mark!

Original code, left for posterity.

Runtime: 88.57 seconds (with aglaope)

```{- Function to test the digits, note the last two are already accounted for! -}
okDigs :: Integer -> Bool
okDigs n = inner 9 n
where
inner :: Integer -> Integer -> Bool
inner 9 n = mod n 10 == 9 && inner 8 (div n 100)
inner 8 n = mod n 10 == 8 && inner 7 (div n 100)
inner 7 n = mod n 10 == 7 && inner 6 (div n 100)
inner 6 n = mod n 10 == 6 && inner 5 (div n 100)
inner 5 n = mod n 10 == 5 && inner 4 (div n 100)
inner 4 n = mod n 10 == 4 && inner 3 (div n 100)
inner 3 n = mod n 10 == 3 && inner 2 (div n 100)
inner 2 n = mod n 10 == 2 && inner 1 (div n 100)
inner 1 1 = True
inner d n = False

{- There is an optimisation in recognising that for any number to end in a zero
- it must be divisble by 10. Thus we can reduce the numbers we are exploring by
- a factor of 10 and search the reduced numbers. Just multiply the answer by 10
- to find the integer we were looking for in the problem.
- Start at the square root of 10203040506070809 and go upwards. -}
main = print (10 * (head (filter (\x -> okDigs (x * x)) [101010101..])))
```

## Python by Althalus

Optimised a little. Runtime: 58 seconds.

```from time import time

#The number has to end in 0. Which means it has to be a multiple of 10.
#Any square that's a multiple of 10 is going to be a multiple of 100.
#This simplifies what we have to test somewhat, knowing that the number will
#be 1_2_3_4_5_6_7_8_900, we don't need to test that last section.
#ie just test 1_2_3_4_5_6_7_8_9
def test(n):
for i in range(9,-1,-1):
if n%10!=i: return False
n/=100
return True

start_time = time()
#Sqrt of smallest number to match our pattern (10203040506070809) is 101010101.
#An interesting observation: A square that ends in 9 has a square root ending in either 3 or 7.
#Interestingly, it appears you can accurately guess the last digit, and know whether the second
#digit is odd or even for the square of any number based on the last digit...
n=101010103
while True:
if test(n**2):
print n*10
print time() - start_time
break
if n%10==3:
n+=4
else:
n+=6
```

Original Solution below. Figure I might as well leave it here:

```#The number has to end in 0. Which means it has to be a multiple of 10.
#Any square that's a multiple of 10 is going to be a multiple of 100.
#This simplifies what we have to test somewhat, knowing that the number will
#be 1_2_3_4_5_6_7_8_900, we don't need to test that last section.
def test(n):
for i in range(9,-1,-1):
if n%10!=i: return False
n/=100
return True

#After deciding I wanted to be able to make an infinite(ish) list, and having
#discovered generators, I decided to play around.
#Then I saw a mention somewhere of itertools.count() which looks like it would have
#done this for me, more or less. Oh well.
def irange(start=0,step=1):
cur = start
while True:
cur+=step
yield cur

for n in irange(101010101):
#101010101 is the square root of the smallest number that matches our pattern.
#(10203040506070809)
if test(n**2):
print n*10
#Since we decided to ignore the last digit, let's put it back.
break
```