Enigmatic Code

Programming Enigma Puzzles

Enigma 1531: The year in question

From New Scientist #2694, 7th February 2009 [link]

I have written down three 3-figure numbers which, overall, use no digit more than once. One of the numbers is a perfect square and the two other numbers are primes. Their total is 2009.

With a little logic it is possible to calculate the three numbers very quickly.

What (in increasing order) are they?

[enigma1531]

Advertisements

5 responses to “Enigma 1531: The year in question

  1. Jim Randell 3 July 2012 at 6:50 pm

    Here’s my original Perl solution. It runs in 19ms.

    use strict;
    
    use Enigma qw/prime/;
    
    my ($n);
    
    # find 3-digit squares
    my @SQUARES = ();
    for (10..31) {
      $n = $_ * $_;
      next if $n =~ /(.).*\1/; # no repeated digits
      push @SQUARES, $n;
    }
    
    # find 3 digit primes
    my @PRIMES = ();
    my %PRIMES = ();
    for (123..987) {
      next if /(.).*\1/; # no repeated digits
      next unless prime($_);
      push @PRIMES, $_;
      $PRIMES{$_}++;
    }
    
    # now find a square and 2 primes that sum 2009
    my ($A, $B, $C);
    for $A (@SQUARES) {
      for $B (@PRIMES) {
        $C = 2009 - $A - $B;
        last unless $B < $C;
        next unless $PRIMES{$C};
        next if "$A$B$C" =~ /(.).*\1/; # no shared digits
        print join(' + ', sort $A, $B, $C), " = 2009\n";
      }
    }
    

    Solution: The numbers are 401, 625 and 983.

    • Jim Randell 3 July 2012 at 6:52 pm

      And here’s a similar Python solution. It runs in 44ms.

      from itertools import product
      from enigma import irange, is_duplicate, Primes, concat, printf
      
      # 3-digit squares, with no repeated digits
      squares = list(x for x in (i * i for i in irange(10, 31)) if not is_duplicate(x))
      
      # 3-digit primes, with no repeated digits
      primes = list(x for x in Primes(1000) if x > 99 and not is_duplicate(x))
      
      for (s, p) in product(squares, primes):
        # calculate the third number
        n = 2009 - (s + p)
        # it should be a prime (greater than p, for uniqueness)
        if not(n in primes and p < n): continue
        # there should be no repeated digits across the numbers
        if is_duplicate(concat(s, p, n)): continue
        
        printf("sum({l}) = 2009", l=sorted((s, p, n)))
      
  2. arthurvause 3 July 2012 at 9:53 pm

    I couldn’t resist having a go at this one as well:

    import primes
    pr=[x for x in primes.primeList(999) if len(set(str(x)))==3]
    # the square must be odd to give prime1+prime2+square=2009
    for s in [n*n for n in range(11,32,2) if len(set(str(n*n)))==3]:
      for p in pr:
        q=2009-s-p 
        if q in pr and len(set(str(s)+str(p)+str(q)))==9 and q>p:
          print s,p,q
    
    • Hugh Casement 2 February 2016 at 7:31 am

      I think I’ve worked out the little logic:
      The digital root of 2009 is 2. The digits 0 to 9 sum to 45,
      so we must omit 7 to leave a total 38 with digital root 2.

      The primes are necessarily odd, so the square must be too, to give an odd total.
      Odd 3-digit squares with no repeated digit are 169, 289, 361, 529, 625, 841, 961
      (omitting 729).
      If the square were to end in 1, the primes would have to end in 1 and 7, but that repeats the 1;
      so 361, 841, and 961 are excluded.
      If the square were to end in 9, the primes would have to end in 1 and 9 (duplication!) or 3 and 7, but we’ve excluded 7 from the start.

      Therefore the square is 625 and the primes end in 1 and 3.
      They have to sum to 1384, and must not start with 3, so 401 is the smallest possible.
      By chance we’ve hit on the solution: 401 and 983.

      • geoffrounce 2 February 2016 at 2:00 pm
        include "globals.mzn";
        solve satisfy;
        
        var 0..9 : a;  var 0..9 : b;  var 0..9 : c;
        var 0..9 : d;  var 0..9 : e;  var 0..9 : f;
        var 0..9 : g;  var 0..9 : h;  var 0..9 : i;
        
        constraint all_different ([a,b,c,d,e,f,g,h,i]);
        
        var 100..999 : sq1; var 100..999 : pr1; var 100..999 : pr2;
        
        constraint sq1 = 100*a + 10*b + c;
        constraint pr1 = 100*d + 10*e + f;
        constraint pr2 = 100*g + 10*h + i;
        
        predicate is_square(var int: c) =
           let {
              var 0..ceil(pow(int2float(ub(c)),(1/2.0))): z
           } in z * z = c ;
        
        predicate is_prime(var int: x) = x > 1 /\
           forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) ( 
                (i < x) -> (x mod i > 0));
        
        constraint is_square(sq1) /\ is_prime(pr1) /\ is_prime(pr2);
        constraint sq1 + pr1 + pr2 = 2009;
        
        output[show(pr2),show(" "), show(sq1),show(" "), show(pr1)];
        
        % Running Enigma 1531 The year in question.mzn
        % 401 625 983
        %
        

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: