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

### 7 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)
```
7. Antonio Leonti said

Hello everybody. Here’s my solution which is implemented in C. I feel like it could be a naive approach, but at the same time I only test each “sub-integer” (like a substring) once, so I don’t think it’s too bad. I’m actually unsure how I could make it better if I’m being honest. Obviously my way of determining if a number is a square is risky (“if(rt == (int)rt)”), but I can’t think of a safe way to do this– and in everything I’ve tried so far it works.

```// returns length followed by each hidden square.
int* hiddenSquares(int x){
int count = 0;
int digits = 0;

for(int i = x; i > 0; i /= 10) digits++; // count digits in x
int tmp[digits*(digits+1)/2]; // set up temp array for values
// digits*(digits+1)/2 is the max number of hidden squares there could be!

for(int i = digits; i > 0; i--){
x %= (int)(pow(10, i)+0.5); // remove leftmost digits of x

for(int j = x; j > 0; j /= 10){ // remove rightmost digits
float rt = sqrt(j); // take sqrt

if(rt == (int)rt){ // if it's a perfect square...
int exists = 0; // is j already in tmp? ...
for(int k = 0; k < count && !exists; k++) exists = tmp[k]==j;
if(!exists) tmp[count++] = j; // if not, add it!
}
}
}
// set up the return array
int* ret = malloc((count+1) * sizeof(int)); // allocate return array
for (int i = 1; i < count+1; i++) ret[i] = tmp[i-1]; // copy over values
ret = count; // count is the first number.

return ret;
}
```