# Euler Solution 206

### From ProgSoc Wiki

# Solutions for Problem 206

Find the unique positive integer *n* with *n ^{2}* = 1_2_3_4_5_6_7_8_9_0 where _ may be any digit.

## Haskell by SanguineV

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