# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1075: No factors

From New Scientist #2231, 25th March 2000 [link]

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

Identify the five-digit number.

[enigma1075]

### 9 responses to “Enigma 1075: No factors”

1. Jim Randell 12 February 2018 at 7:35 am

We can feed this problem directly to the [[ `SubstitutedExpression()` ]] solver in the enigma.py library.

This run file executes in 130ms.

Run: [ @repl.it ]

```#!/usr/bin/env python -m enigma -r

SubstitutedExpression

--distinct=""

"A == 1 or is_prime(A)"
"E == 1 or is_prime(E)"
"is_prime(AB)"
"is_prime(DE)"
"is_prime(ABC)"
"is_prime(CDE)"
"is_prime(ABCD)"
"is_prime(BCDE)"
"is_prime(ABCDE)"
```

Solution: The number is 73331.

• Jim Randell 12 February 2018 at 10:27 am

And here’s a simple Python program that uses the [[ `Primes()` ]] class from enigma.py. It runs in 121ms.

```from enigma import Primes

# up to 5 digit primes
primes = Primes(100000)

# check for "indivisible" numbers
is_indivisible = lambda n: n == 1 or n in primes

# check prefixes and suffixes are indivisible
def check(n):
for m in (10, 100, 1000, 10000):
(p, s) = divmod(n, m)
if not(is_indivisible(p) and is_indivisible(s)): return False
return True

# consider 5 digit primes
for p in primes.range(10000, 100000):
if check(p):
print(p)
```
2. geoffrounce 12 February 2018 at 9:57 am
```% A Solution in MiniZinc
include "globals.mzn";

var 1..9:A;  var 1..9:B;  var 1..9:C;  var 1..9:D;  var 1..9:E;

var 10..99: AB = 10*A  + B;
var 10..99: DE = 10*D + E;
var 100..999: ABC = 100*A + 10*B + C;
var 100..999: CDE = 100*C + 10*D + E;
var 1000..9999: ABCD = 1000*A + 100*B + 10*C + D;
var 1000..9999: BCDE = 1000*B+ 100*C + 10*D + E;
var 10000..99999: ABCDE = 10000*A + 1000*B + 100*C + 10*D + E;

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 (A == 1 \/ is_prime(A) ) /\  (E == 1 \/ is_prime(E) );

constraint sum ( [ is_prime(AB), is_prime(DE), is_prime(ABC), is_prime(CDE),
is_prime(ABCD), is_prime(BCDE), is_prime(ABCDE) ] ) == 7;

solve satisfy;

output [ "Five digit number  = " ++ show(ABCDE) ];

% Five digit number  = 73331
% ----------
% Finished in 130msec
```
• geoffrounce 12 February 2018 at 12:04 pm
```def is_prime(n):
for x in range(2, int(n**0.5) + 1):
if n % x == 0:
return False
return True

for a in range(1,10):
if a == 1 or is_prime(a):
for b in range(1,10,2):
ab = 10*a + b
if not is_prime(ab): continue
for c in range (1,10,2):
abc = 100*a + 10*b + c
if not is_prime(abc): continue
for d in range(1,10,2):
abcd = 1000*a + 100*b + 10*c + d
if not is_prime(abcd): continue
for e in range(1,10,2):
if e == 1 or is_prime(e):
abcde = 10000*a + 1000*b + 100*c + 10*d + e
if not is_prime(abcde): continue
de, cde, bcde = 10*d + e, 100*c+ 10*d + e, \
1000*b + 100*c + 10*d  + e
if is_prime(de) and is_prime(cde) and is_prime(bcde):
print("Five digit number = ", abcde)

# Five digit number =  73331
```
3. Brian Gladman 12 February 2018 at 7:19 pm
```from number_theory import is_prime

# build the five digit number from left to right
def form(nbr=0, nd=0):
# do we have five digits?
if nd == 5:
# check that the 4, 3 and 2 digit suffix numbers are prime
if all(is_prime(int(str(nbr)[i:])) for i in range(1, 4)):
yield nbr
else:
# add another digit to the right
for x in {1, 2, 3, 5, 7}:
# only the first and last digits added can be 1
if (nd in {0, 4} or x != 1) and is_prime(10 * nbr + x):
yield from form(10 * nbr + x, nd + 1)

for nbr in form():
print(nbr)
```
4. arthurvause 12 February 2018 at 10:23 pm

Constructing the number from the right hand side:

```primes = set([2]+range(3,100000,2))
for n in xrange(3,317,2) :
if n in primes: primes-= set(range(n*n,100000,n*2))

ends = (1,3,7,9)
candidates = set(ends)
for i in xrange(1,4):
candidates = set( x + e*10**i for x in candidates for e in ends) & primes

candidates = set( x + s*10000 for x in candidates for s in (1,2,3,5,7) ) & primes

for c in candidates:
if c//10 in primes and c//100 in primes and c//1000 in primes :
print c
```
5. paul2cleary 13 February 2018 at 5:22 pm

Extending this puzzle to 6 digits also has one solution, both single digit numbers are also prime. No solutions with 7 digits.

6. arthurvause 15 February 2018 at 11:48 am

I couldn’t resist calculating the left-truncatable primes for myself. (Here is a link to factors.py )

Coincidentally, the left truncatable prime pencil was mentioned recently in the Radio 4 series Two thousand years of puzzling

```from factors import millerRabin

def isprime(n):
return millerRabin(n)

ltps = (1,3,7,9)
i=1
while len(ltps):
ltps = [x + e*10**i for x in ltps for e in xrange(1,10)]
ltps = [x for x in ltps if isprime(x)]
print len(ltps),"left truncatable primes with",i+1,"digits, e.g.", ltps[:2]
i+=1
```

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