## Hidden Squares

### June 2, 2020

We have a simple task today:

A number n may have squares hidden among its digits. For instance, in the number 1625649, the consecutive digits 1, 4, 9, 16, 25, 49, 64, 256 and 625 are all squares.

Your task is to write a program that takes a positive integer n and finds all of its hidden squares. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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;
}
```