Enigmatic Code

Programming Enigma Puzzles

Enigma 1688: Eight prime factors

From New Scientist #2855, 10th March 2012 [link]

The numbers 38 and 77 are each the product of two primes; furthermore their difference (39) and their sum (115) are also each the product of two primes, and the eight primes involved are all different.

There is one other pair of two-digit positive integers for which all this is true. What are those two integers?

[enigma1688]

8 responses to “Enigma 1688: Eight prime factors

  1. Jim Randell 7 March 2012 at 7:06 pm

    The following Python program runs in 38ms.

    from itertools import combinations
    from enigma import is_prime, factor, printf
    
    # primes less than 50
    primes = set(n for n in range(2, 50) if is_prime(n))
    
    # make 2-digit integers that are the product of pairs of the primes
    numbers = {}
    for (a, b) in combinations(primes, 2):
      c = a * b
      if not(9 < c < 100): continue
      numbers[c] = set((a, b))
    
    # check if a number is the product of two different primes
    def check(n):
      f = factor(n)
      if len(f) != 2: return
      if f[0] == f[1]: return
      return f
    
    # find pairs of the numbers
    for (a, b) in combinations(numbers.keys(), 2):
      fd = check(abs(a - b))
      if not fd: continue
      fs = check(a + b)
      if not fs: continue
      if len(numbers[a].union(numbers[b], fd, fs)) < 8: continue
      printf("{a} {fa}, {b} {fb}, diff={d} {fd}, sum={s} {fs}", s=a+b, d=abs(a-b), fa=list(numbers[a]), fb=list(numbers[b]))
    

    Solution: The other pair of 2-digit integers is 39 and 94.

    • Jim Randell 24 March 2012 at 10:18 am

      Here’s a solution using the Prime Sieve, that I’ve recently added to the enigma.py module:

      from itertools import combinations
      from enigma import Primes, printf
      
      # a, b are both two digit products of primes (9 < a, b < 100)
      # so their sum must be 20 < a+b < 199
      # the sum (and difference) are also the products of two primes,
      # so we need to consider primes up to 100
      
      # accumulate the following...
      factors = {} # map a product to its two prime factors
      primes = [] # primes (up to 100)
      numbers = [] # 2 digit products
      
      sieve = Primes(100)
      for n in sieve.generate():
        for m in primes:
          p = n * m
          if p > 199: break
          factors[p] = set((n, m))
          if 9 < p < 100: numbers.append(p)
        primes.append(n)
      
      # search the 2 digit products for solutions
      for (a, b) in combinations(numbers, 2):
        if b < a: (a, b) = (b, a)
        (s, d) = (a + b, b - a)
        if not(s in factors and d in factors): continue
        if len(factors[a].union(factors[b], factors[s], factors[d])) != 8: continue
      
        f = lambda x: 'x'.join(str(n) for n in sorted(list(factors[x])))
        printf("a={a} ({fa}) b={b} ({fb}) sum={s} ({fs}) diff={d} ({fd})", fa=f(a), fb=f(b), fs=f(s), fd=f(d))
      
  2. Brian Gladman 8 March 2012 at 9:02 am

    Here is my version:

    
    from itertools import combinations
    # create a tuple of primes up to 100
    p0 = (2, 3, 5, 7)
    pr = p0 + tuple(x for x in range(11, 100, 2) if all(x % p for p in p0))
    
    # create a dictionaary of numbers that are the product of two primes
    # d[p * q] = (p, q) for p * q < 200
    d = dict((p * q, (p, q)) for p in pr for q in pr if p < q and p * q < 200)
          
    for n1, n2 in combinations(d, 2):
      # for each pair of numbers
      if 10 <= n1 < n2 < 100:
        n3, n4 =  n1 + n2, n2 - n1
        if n3 in d and n4 in d and len(set(d[n1] + d[n2] + d[n3] + d[n4])) == 8:
          print('{0:2d} {1:s}, {2:2d} {3:s}, {4:2d} {5:s}, {6:2d} {7:s}'
                    .format(n1, d[n1], n2, d[n2], n3, d[n3], n4, d[n4]))
    
  3. Peter 2 April 2012 at 7:11 pm

    Wow, how compact these Python codes are.
    I tackled the problem using Microsoft Visual C# which I am learning.
    Here is a link to my own comparitvely amateurish coding of the solution to Enigma 1688 written for Visual C# 2008 Express (& C# 2010 Express):
    http://homepage.ntlworld.com/p.caine1/1688.html

    • Jim Randell 4 April 2012 at 8:38 am

      One of the things I like about Python is its compactness. Of course my solution uses routines from my own enigma.py library for generating primes, so that makes it a bit smaller (although Brian fitted a 2 line prime sieve into his solution). Python also has a nice standard library that includes lots of useful stuff for solving these puzzles.

      My algorithm is also a bit less complicated than yours (for example, I didn’t look for products of different parity), but my code ran in 38ms, so I didn’t bother tweaking the algorithm further.

      • Peter 4 April 2012 at 9:57 pm

        When I was asked to help to solve the Enigma 1688 puzzle I didn’t know where to begin, hence the use of Excel.Looking at the distribution of products of the primes in the cells I saw the different parities.
        Now Odd+(or-)Odd both give Even numbers, so there would be a repeat of the prime factor 2. Therefore just one of the numbers must be even. I thought then that any “algorithm” would include parity

        Even so the number of cases to examine still seemed daunting. Thats when I decided to code the problem and naturally included the parity aspect.I learned a lot about Visual C# during the coding process.

        I checked (extending my knowledge of C# again!) and my code ran in 8 ms to 14 ms (more with printing)
        I only tried the timing on four occasions {8,9,14 & 9ms}. I employed the Microsoft StopWatch function
        .
        Here is a sample of the new code ouput:
        ********************************************************************
        Operations timed using the system’s high-resolution performance counter.
        Timer frequency in ticks per second = 14318180
        Timer is accurate within 69 nanoseconds

        39,38,77,115
        //Other solution

        Time in milliseconds =9
        ********************************************************************.

        The Timer accuracy was a huge surprise to me.
        The run time however is not of particular interest to me, after all the code results are immediate.
        At this time I have no idea of how to improve my code (other than tidy it).
        My main interest is in learning C# and it was a bonus getting the solution to this puzzle.

        Timings for different codes (Python,C# etc) must, at least, be processor dependent.

        • Jim Randell 6 April 2012 at 6:41 pm

          Here’s my Python code with the list of numbers split into even and odd candidates, and then the candidate pairs are constructed by choosing one number from each list. It cuts down the candidate pairs considered by around half, from 406 (= C(13 + 16, 2)) to 208 (= 13 x 16). Although this has a negligible effect on the runtime of the program for this particular puzzle, if there were a much larger set of candidate numbers it would run noticeably faster.

          from itertools import product
          from enigma import Primes, printf
          
          # accumulate the following...
          factors = {} # map a product to it's two prime factors
          primes = [] # primes (up to 100)
          numbers = ([], []) # 2 digit products (by parity)
          
          for n in Primes(100):
            for m in primes:
              p = n * m
              if p > 199: break
              factors[p] = set((n, m))
              if 9 < p < 100: numbers[p % 2].append(p)
            primes.append(n)
          
          # search the 2 digit products for solutions
          for a, b in product(numbers[0], numbers[1]):
            if b < a: (a, b) = (b, a)
            (s, d) = (a + b, b - a)
            if not(s in factors and d in factors): continue
            if len(factors[a].union(factors[b], factors[s], factors[d])) != 8: continue
          
            f = lambda x: 'x'.join(str(n) for n in sorted(list(factors[x])))
            printf("a={a} ({fa}) b={b} ({fb}) sum={s} ({fs}) diff={d} ({fd})", fa=f(a), fb=f(b), fs=f(s), fd=f(d))
          
  4. Peter 7 April 2012 at 11:17 am

    I edited my code to remove the use of parity as part of the algorithm.
    My new code 1s now 198 lines long, poor in comparison with your Python code
    I moved the code to my notebook(circa 2006). Here is the result
    ********************************
    Operations timed using the system’s high-resolution performance counter.
    Timer frequency in ticks per second = 3579545
    Timer is accurate within 279 nanoseconds
    39,38,77,115
    //Other solution
    //Other solution with reorder of items 2 and 3.
    39,77,38,115

    Time in milliseconds =43
    ********************************
    This result is now comparible with your run time of 38 milliseconds.
    One thing is sure, after teaching myself C#, I’ll be learning Python!

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: