# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1604: From primes to squares

From New Scientist #2769, 17th July 2010 [link]

Harry has been looking for 5-digit perfect squares that can be read (in any order) as a 1-digit prime and two 2-digit primes. He knows that 1 is not a prime. 31329 (177²) qualifies in two ways, since the primes could be 3, 13, 29 or 31, 3, 29. Harry hasn’t found that example, but he has found three squares that each qualify in one way; they use nine different primes.

What are those three 5-digit squares?

[enigma1604]

### One response to “Enigma 1604: From primes to squares”

1. jimrandell 8 January 2012 at 10:04 am

The following Python program runs in 33ms.

```from itertools import combinations
from enigma import irange, is_prime, printf

# find one and two digit primes (as strings)
primes = set(str(i) for i in irange(2, 99) if is_prime(i))

# check a decomposition is composed entirely of primes
def check(n, s):
return s if primes.issuperset(s) else None

# find 5-digit squares that can only be split in one way
squares = []
for i in irange(100, 316):
n = str(i * i)
# count the number of ways
c = list(filter(None, (
check(n, [n[0], n[1:3], n[3:5]]),   # 1 2 2
check(n, [n[0:2], n[2], n[3:5]]),   # 2 1 2
check(n, [n[0:2], n[2:4], n[4]])))) # 2 2 1
if len(c) != 1: continue
print(n, c[0])
squares.append((n, c[0])) # (square, decomposition)

# find three of the squares that use 9 different primes
for (i, j, k) in combinations(squares, 3):
ps = set(i[1]).union(j[1], k[1])
if len(ps) != 9: continue
printf("{i[0]} {j[0]} {k[0]} -> {ps} #{l}", l=len(ps))
```

Solution: The three squares are: 53361, 71289, 76729.