Euler Solution 206

From ProgSoc Wiki

Jump to: navigation, search

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.

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
Personal tools