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=""
    --answer="ABCDE"
    
    "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 
    

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: