Enigmatic Code

Programming Enigma Puzzles

Enigma 1527: Square from primes

From New Scientist #2690, 10th January 2009 [link]

Harry, Tom and I were looking to find 5-digit perfect squares that consisted of a 2-digit prime followed by a 3-digit prime, neither prime starting with a zero.

We each found a different example. My 2-digit prime was the same as Harry’s and my 3-digit prime was the same as Tom’s.

Which square was found by (a) Harry, (b) Tom?

[enigma1527]

Advertisements

3 responses to “Enigma 1527: Square from primes

  1. Jim Randell 17 July 2012 at 8:46 pm

    Here’s my original Perl program, although it isn’t a full solution. I obviously inspected the results to determine the final solution. It runs in 22ms.

    use strict;
    
    use Enigma qw/prime/;
    
    my (%SQUARES, %PRIME2, %PRIME3);
    
    for (sqrt(10_000)..sqrt(99_999)) {
      $SQUARES{$_ * $_} = 1;
    }
    
    for (10..99) {
      $PRIME2{$_} = 1 if prime($_);
    }
    
    for (100..999) {
      $PRIME3{$_} = 1 if prime($_);
    }
    
    printf "%d squares, %d 2-digit primes, %d 3-digit primes\n",
      scalar(keys %SQUARES), scalar(keys %PRIME2), scalar(keys %PRIME3);
    
    my ($p2, $p3);
    for (sort keys %SQUARES) {
      next unless ($p2, $p3) = /^(..)(...)$/;
      next unless $PRIME2{$p2} and $PRIME3{$p3};
      print "[$p2,$p3]\n";
    }
    

    Solution: (a) Harry’s square is 11449, (b) Tom’s square is 19881.

    • Jim Randell 17 July 2012 at 8:47 pm

      And here’s a full solution in Python. It runs in 45ms.

      from collections import defaultdict
      from itertools import product
      from enigma import Primes, irange, printf
      
      # we need to check for 2 and 3 digit primes
      primes = set(str(x) for x in Primes(1000) if x > 9)
      
      squares = []
      p2s = defaultdict(set)
      p3s = defaultdict(set)
      
      # consider 5-digit squares
      for i in irange(100, 316):
        s = str(i * i)
        # split the square into 2-digits + 3-digits
        (p2, p3) = (s[:2], s[2:])
        if not(p2 in primes and p3 in primes): continue
        squares.append(s)
        p2s[p2].add(s)
        p3s[p3].add(s)
      
      # now go through the squares to see if we can find a suitable D, T, H triple
      for D in squares:
        Ds = set((D,))
        (p2, p3) = (D[:2], D[2:])
        for (H, T) in product(p2s[p2].difference(Ds), p3s[p3].difference(Ds)):
          printf("D={D} H={H} T={T}")
      
  2. Geoff Rounce 18 July 2012 at 2:38 pm

    My program below gives the following squares, split into 2 digit and 3 digit primes:
    (11449, 11, 449)
    (11881, 11, 881)
    (19881, 19, 881)
    (23409, 23, 409)
    (29241, 29, 241)
    (29929, 29, 929)
    (47089, 47, 89) – fails due to leading zero
    (83521, 83, 521)
    (89401, 89, 401)

    Therefore:
    My square = 11881
    Harry’s square = 11449
    Tom’s square = 19881

      
    def isprime(n): 
        for x in range(2, int(n**0.5)+1): 
            if n % x == 0: 
                return False 
        return True
    
    sq5 = [x*x for x in range(100,316)]
    list1 = []
    
    for n in sq5:
        ns = str(n)
        n1 = int(ns[0] + ns[1])
        n2 = int(ns[2]+ns[3]+ns[4])
        if isprime(n1) and isprime(n2):
            list1.append((n,n1,n2))
            
    for a in list1:
        print(a)
     

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: