Enigmatic Code

Programming Enigma Puzzles

Enigma 1538: Six factors

From New Scientist #2701, 28th March 2009 [link]

Harry chose two 2-digit numbers and added them together to create a third 2-digit number. Each of the three numbers was the product of two primes; the six primes were all different.

He then transposed the unit digits of his first two numbers to create two new numbers, which he added together to create the same third number as before. Once again each of the three numbers was the product of two primes, the six primes all being different.

What was the ‘third number’ common to both sums?

Hint: The phrase “transposing the unit digits of the first two numbers” means going from AB & CD to AD & CB.

[enigma1538]

Advertisements

2 responses to “Enigma 1538: Six factors

  1. Jim Randell 17 April 2012 at 9:32 pm

    Here’s my original Perl code. It runs in 14ms.

    use Enigma qw/distinct/;
    
    # use a sieve to find primes less than 50
    
    my $MAX = 100;
    
    my @NON_PRIME = (1, 1); # 0, 1 are non-prime
    
    my ($i, $j);
    
    for ($i = 2; $i < $MAX; $i++) {
      next if $NON_PRIME[$i];
      for ($j = 2 * $i; $j < $MAX; $j += $i) {
        $NON_PRIME[$j] ||= 1;
      }
    }
    
    # find 2 digit numbers that are products of these primes
    
    my ($P1, $P2, $N);
    
    my %PRIME = ();
    for $P1 (2..$MAX) {
      next if $NON_PRIME[$P1];
    
      for $P2 ($P1+1..$MAX) {
        next if $NON_PRIME[$P2];
        next unless distinct($P2, $P1);
    
        $N = $P1 * $P2;
        next unless length($N) == 2;
    
        $PRIME{$N} = [ $P1, $P2 ];
      }
    }
    
    # find 2 of these numbers that sum to a third
    
    # distinct: 6 way distinct test
    sub distinct6 {
      my ($A, $B, $C, $D, $E, $F) = @_;
      return 0 unless distinct($A, $B, $C, $D, $E, $F);
      return 0 unless distinct($B, $C, $D, $E, $F);
      return 0 unless distinct($C, $D, $E, $F);
      return 0 unless distinct($D, $E, $F);
      return 0 unless distinct($E, $F);
      return 1;
    }
    
    my ($N1, $N2, $N3);
    my ($R1, $R2);
    my ($P3, $P4, $P5, $P6);
    
    for $N1 (keys %PRIME) {
      for $N2 (keys %PRIME) {
        next unless distinct($N1, $N2);
        next unless $N1 < $N2;
        $N3 = $N1 + $N2;
        next unless $PRIME{$N3};
        next unless distinct6(@{$PRIME{$N1}}, @{$PRIME{$N2}}, @{$PRIME{$N3}});
    
        # apparently they are looking for: AB + CD and AD + BC _not_ AB + CD and BA + DC
        $R1 = "$N1$N2"; substr($R1, 1, 2) = '';
        $R2 = substr("$N1$N2", 1, 2);
    
        next unless $PRIME{$R1};
        next unless $PRIME{$R2};
        next unless distinct6(@{$PRIME{$R1}}, @{$PRIME{$R2}}, @{$PRIME{$N3}});
    
        printf "%d [%d x %d] + %d [%d x %d] = %d [%d x %d] / %d [%d x %d] + %d [%d x %d] = %d\n",
          $N1, @{$PRIME{$N1}},
          $N2, @{$PRIME{$N2}},
          $N3, @{$PRIME{$N3}},
          $R1, @{$PRIME{$R1}},
          $R2, @{$PRIME{$R2}},
          $R1 + $R2;
      }
    }
    

    Solution: The common number in both sums is 93.

    • Jim Randell 17 April 2012 at 9:34 pm

      And here’s a Python solution. It uses the prime sieve in the enigma.py library. It runs in 36ms.

      from itertools import combinations
      from enigma import Primes, printf
      
      # primes up to 50
      primes = Primes(50)
      
      # 2-digit products of primes
      products = {}
      for (a, b) in combinations(primes, 2):
        p = a * b
        if not(9 < p < 100): continue
        products[p] = (a, b)
      
      # choose two 2-digit products that sum to a 2-digit product
      for (ab, cd) in combinations(products.keys(), 2):
        xy = ab + cd
        if not(xy in products): continue
        # check the primes used are distinct
        s = set(products[ab]).union(products[cd]).union(products[xy])
        if len(s) < 6: continue
      
        # swap the units digits
        (a, b) = divmod(ab, 10)
        (c, d) = divmod(cd, 10)
        ad = 10 * a + d
        cb = 10 * c + b
        # check the numbers are different
        if len(set((ab, cd, ad, cb))) != 4: continue
        if not(ab < ad): continue # for uniqueness
        # and are 2-digit products
        if not(ad in products and cb in products): continue
        # and the primes are distinct
        s = set(products[ad]).union(products[cb]).union(products[xy])
        if len(s) < 6: continue
        
        printf("{xy} {pxy} = {ab} {pab} + {cd} {pcd} = {ad} {pad} + {cb} {pcb}", pxy=products[xy], pab=products[ab], pcd=products[cd], pad=products[ad], pcb=products[cb])
      

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: