# 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]

### 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=', '))
```

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
%
```

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