Enigmatic Code

Programming Enigma Puzzles

Enigma 1168: Thrice unfactorised

From New Scientist #2324, 5th January 2002 [link]

I have found a four-digit number such that it is impossible to factorise the numbers formed by its first digit or last digit or first two digits or middle two digits or last two digits or first three digits or last three digits or all four digits. In other words all those eight numbers are prime except that either or both of the single-digit numbers may be unity.

Harry and Tom have also each found such a four-digit number. The four-digit numbers that we have found are all different; but Harry’s number uses the same digits as Tom’s number, though in a different order.

Which four digit number have I found?

This completes the archive of puzzles from 2002.

[enigma1168]

Advertisements

3 responses to “Enigma 1168: Thrice unfactorised

  1. Jim Randell 10 May 2016 at 12:36 am

    This Python program runs in 33ms.

    from itertools import product
    from collections import defaultdict
    from enigma import Primes, join, printf
    
    # primes up to 4-digits
    primes = Primes(9999)
    
    # 2-digit primes as strings
    p2s = list(str(p) for p in primes.range(10, 99))
    
    # record results by the digits used
    rs = defaultdict(list)
    
    # stick together two 2-digits primes
    for (ab, cd) in product(p2s, repeat=2):
      (a, b) = ab
      (c, d) = cd
      # check the following are prime (or unity): a, d, bc, abc, bcd, abcd
      abcd = ab + cd
      if all(n == '1' or int(n) in primes for n in (a, d, b + c, ab + c, b + cd, abcd)):
        rs[join(sorted(abcd))].append(abcd)
    
    # output the results
    for (k, vs) in rs.items():
      printf("{k} -> {vs}", vs=join(vs, sep=', '))
    

    Solution: Your number is 3797.

    Harry and Tom’s numbers are 1373 and 3137, although we can’t be sure who found which number.

    These are the only 4-digit numbers that satisfy the conditions of the puzzle.

    • Brian Gladman 10 May 2016 at 12:26 pm
      from itertools import product
      from functools import reduce
      from collections import defaultdict
      from number_theory import Primes, is_prime
      
      # function to convert a sequence of digits to an integer
      fn = lambda seq: reduce(lambda x, y: 10 * x + y, seq)
      
      # for saving four digit values that are solutions
      dgts_to_values = defaultdict(list)
      
      # try all values of the first and last digits
      for a, d in product((1, 2, 3, 5, 7), repeat=2):
        
        # and all prime values for the middle two digits
        for bc in Primes().range(10, 100):
          
          # the list of digits    
          dgts = (a, *divmod(bc, 10), d)
          
          # create a list of the six values with two or more digits
          nbrs = [fn(dgts[s : s + l]) for l in range(2, 5) 
                                       for s in range(0, 5 - l)]
          
          # and check that they are all prime
          if all(is_prime(x) for x in nbrs):
      
            # if so, store them associated with their sets of digits
            dgts_to_values[frozenset(dgts)].append(nbrs[-1])
      
      for k, lv in dgts_to_values.items():
        # find the result that has a unique set of digits
        if len(lv) == 1:
          print('The number is {}.'.format(lv[0]))
      
  2. geoffrounce 13 May 2016 at 7:27 am
    % A MiniZinc solution
    include "globals.mzn";
    solve satisfy;
    
    var 1..9:E; 
    var 1..9:F; 
    var 1..9:G; 
    var 1..9:H; 
    var 1000..9999: EFGH;
    
    % ex Hakank
    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 EFGH = 1000*E + 100*F + 10*G + H;
    
    constraint (E == 1 \/ is_prime(E)) /\ (H == 1 \/ is_prime(H));
    
    constraint is_prime(10*E + F) /\ is_prime(10*F + G)
    /\ is_prime(10*G + H) /\ is_prime(100*E + 10*F + G)
    /\ is_prime(100*F + 10*G + H) /\ is_prime(EFGH);
    
    output ["Four Digit Number = " ++ show(EFGH)];
    
    % N.B. necessary to set configuration for multiple outputs
    % Four Digit Number = 1373 
    % ----------
    % Four Digit Number = 3137 
    % ----------
    % Four Digit Number = 3797 <<< Number I found
    % ----------
    % Finished in 152msec
    %
    

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: