Enigmatic Code

Programming Enigma Puzzles

Enigma 1016: Semi(pr)imes

From New Scientist #2172, 6th February 1999 [link]

A semi-prime is the product of two prime numbers. Sometimes when the digits of a semi-prime are reversed, the resulting number is also a semi-prime: 326 and 623 (2 × 163 and 7 × 89 respectively) are both semi-primes. More rarely the sum of these two semi-primes is itself a semi-prime, as with 326 + 623 = 949 = 13 × 73.

In fact, 949 is the largest of very few three-digit semi-primes that have these characteristics; but two of the three-digit semi-primes that can be the sum of two semi-primes, of which one is the reverse of the other, are consecutive numbers.

Identify these two consecutive three-digit numbers and the sums that lead to them. (Give your answer in the form a = b + c and d = e + f, where d = a + 1).

[enigma1016]

One response to “Enigma 1016: Semi(pr)imes

  1. Jim Randell 5 April 2019 at 7:38 am

    This Python program runs in 100ms.

    Run: [ @repl.it ]

    from collections import defaultdict
    from enigma import irange, factor, nreverse, printf
    
    # find 3-digit semi-primes
    semis = list(n for n in irange(100, 999) if len(factor(n)) == 2)
    
    # record the sum semi-primes
    d = defaultdict(list)
    
    # find n where the reverse is a (higher) semi-prime
    # and the sum of n and its reverse is also a semi-prime
    for n in semis:
      r = nreverse(n)
      if r < n: continue
      s = n + r
      if not(r in semis and s in semis): continue
      printf("[{n} + {r} = {s}]")
      d[s].append((n, r))
    
    # look for consecutive sums
    for s in sorted(d.keys()):
      if s + 1 in d:
        printf("{s} -> {ds}, {s1} -> {ds1}", ds=d[s], s1=s + 1, ds1=d[s + 1])
    

    Solution: The consecutive numbers are 706 (= 155 + 551) and 707 (=205 + 502).

    The prime factorisations of these numbers are:

    155 = 5 × 31
    205 = 5 × 41
    502 = 2 × 251
    551 = 19 × 29
    706 = 2 × 353
    707 = 7 × 101

    The full list of semi-prime sums are:

    505 = 203 + 302
    626 = 115 + 511
    706 = 155 + 551
    707 = 205 + 502
    766 = 185 + 581
    949 = 326 + 623

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: