## 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.

Pages: 1 2

### 6 Responses to “Hidden Squares”

1. James Curtis-Smith said

perl -e ‘print “@{[grep { \$ARGV=~/\$/ } map { \$*\$_ } 1..sqrt(\$ARGV) ]}\n”;’ 1625649

2. James Curtis-Smith said

Try again – this time without letting wordpress mess up the formatting…

```perl -e ‘print “@{[grep { \$ARGV=~/\$/ } map { \$*\$_ } 1..sqrt(\$ARGV) ]}\n”;’ 1625649
```
3. Daniel said

@programmingpraxis, your solution errors when there is a zero in the number, seemingly from the `isqrt` function.

4. Daniel said

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':
continue
for start in range(end + 1):
x = int(string[start:end + 1])
y = isqrt(x)
if y * y == 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:

```[1, 4, 9, 16, 25, 49, 64, 256, 625]
[0, 1, 4, 9, 16, 25, 49, 64, 625, 2500, 62500]
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 196, 225, 256, 361, 400, 484, 676, 729, 784, 841, 900, 961, 1089, 1764, 7921, 11025, 82369, 96100, 3010225]
```
5. Larry Lee said

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)
```
6. Larry Lee said
```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)
```