Hidden Squares
June 2, 2020
This is easy:
(define (square? n)
(let ((s (isqrt n)))
(= n (* s s))))
(define (k-squares k ds)
(if (< (length ds) k) (list)
(let ((n (undigits (take k ds))))
(if (square? n)
(cons n (k-squares k (cdr ds)))
(k-squares k (cdr ds))))))
(define (hidden-squares n)
(let* ((ds (digits n)) (len (length ds)))
(let loop ((k 1) (hs (list)))
(if (< len k) (unique = (sort < hs))
(loop (+ k 1) (append (k-squares k ds) hs))))))
And here is the example:
> (hidden-squares 1625649) (1 4 9 16 25 49 64 256 625)
You can run the program at https://ideone.com/9Q3suE.
perl -e ‘print “@{[grep { $ARGV[0]=~/$/ } map { $*$_ } 1..sqrt($ARGV[0]) ]}\n”;’ 1625649
Try again – this time without letting wordpress mess up the formatting…
perl -e ‘print “@{[grep { $ARGV[0]=~/$/ } map { $*$_ } 1..sqrt($ARGV[0]) ]}\n”;’ 1625649@programmingpraxis, your solution errors when there is a zero in the number, seemingly from the
isqrtfunction.Here’s a solution in Python. The program skips the nested loop in some cases where a candidate cannot possibly be square. An online search suggests additional properties of squares in base 10 that can be utilized to narrow the search further (not implemented in my solution).
def isqrt(n): assert n >= 0 if n == 0: return 0 x = n while True: y = (x + (n // x)) // 2 if y - x in (0, 1): return x x = y def hidden_squares(n): result = set() string = str(n) for end in range(len(string) - 1, -1, -1): if string[end] in ('2', '3', '7', '8'): continue if end > 0 and string[end] == '5' and string[end - 1] != '2': continue if end > 0 and string[end] == '0' and string[end - 1] != '0': result.add(0) continue for start in range(end + 1): x = int(string[start:end + 1]) y = isqrt(x) if y * y == x: result.add(x) return sorted(list(result)) print(hidden_squares(1625649)) print(hidden_squares(162500649)) import random random.seed(0) digits = 600 x = int(''.join([str(random.randint(0, 10)) for _ in range(digits)])) print(hidden_squares(x))Output:
A naive implementation in Haskell in which I generate a list of candidate squares and then filter them based on the digits given in the argument:
hiddenSqrs :: Int -> [Int] hiddenSqrs n = filterSqrs n $ getSqrs 0 where getSqrs :: Int -> [(Int, Int)] getSqrs m | m^2 <= n = (m^2, m^2):(getSqrs $ m + 1) | otherwise = [] filterSqrs :: Int -> [(Int, Int)] -> [Int] filterSqrs _ [] = [] filterSqrs m pending | m == 0 = [] | otherwise = let (cleared, pendingNext) = foldl (\(cleared, pendingNext) (x, y) -> let digit = mod m 10 in if y == digit then (x:cleared, pendingNext) else (cleared, (if mod y 10 == digit then (x, div y 10) else (x, y)):pendingNext)) ([], []) pending in cleared ++ (filterSqrs (div m 10) pendingNext)hiddenSqrs :: Int -> [Int] hiddenSqrs n = filterSqrs n $ getSqrs 0 where getSqrs :: Int -> [(Int, Int)] getSqrs m | m^2 <= n = (m^2, m^2):(getSqrs $ m + 1) | otherwise = [] filterSqrs :: Int -> [(Int, Int)] -> [Int] filterSqrs _ [] = [] filterSqrs m pending | m == 0 = [] | otherwise = let (cleared, pendingNext) = foldl (\(cleared, pendingNext) (x, y) -> let digit = mod m 10 in if y == digit then (x:cleared, pendingNext) else (cleared, (if mod y 10 == digit then (x, div y 10) else (x, y)):pendingNext)) ([], []) pending in cleared ++ (filterSqrs (div m 10) pendingNext)