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]

Advertisements

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.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: