Enigmatic Code

Programming Enigma Puzzles

Enigma 1107: Factory work

From New Scientist #2263, 4th November 2000

When it comes to factor problems it is often quicker to use a bit of cunning logic than to resort to a computer or even a calculator, and here is one such puzzle.

Write down a four-figure number ending in 1 and then write down the next eight consecutive numbers, and then write down the nine numbers obtained by reversing the first nine. For example:

3721    1273
3722    2273
3723    3273
3724    4273
3725    5273
3726    6273
3727    7273
3728    8273
3729    9273

You could then count how many of all those numbers have a factor greater than 1 but less than 14: in this example there are actually eleven of them.

Your task now is to find a four-figure number ending in 1 so that, when you carry out this process, fewer than half the numbers have a factor greater than 1 but less than 14.

What is that four-figure number?

[enigma1107]

Advertisements

5 responses to “Enigma 1107: Factory work

  1. Jim Randell 10 July 2017 at 8:37 am

    Of course I used a computer program, rather than cunning logic.

    This Python program performs an exhaustive search of the solution space in 67ms.

    from enigma import irange, nreverse, printf
    
    # divisors to consider
    divisors = (2, 3, 5, 7, 11, 13)
    
    # is the number divisible by one of the divisors
    def check(n, ds=divisors):
      return any(n % d == 0 for d in ds)
    
    # consider possible initial numbers
    for n in irange(1001, 9991, step=10):
    
      # reverse it
      r = nreverse(n)
    
      # how many of the 18 numbers have divisors
      t = sum(check(n + i) + check(1000 * i + r) for i in irange(0, 8))
    
      # output solutions
      if t < 9:
        printf("n={n}, t={t}")
    

    Solution: The four-figure number is 9461.

  2. arthurvause 10 July 2017 at 9:57 am

    Using a sieve to find candidate numbers with no small factors, and some up-front analysis to eliminate obvious multiples of 2 and 5:

    nosmallprimes = set(range(1001,10000,2)) 
    for p in (3,5,7,11,13) :
      nosmallprimes -= set(range(1000-1000%p,10000,p))
    
    for n in range(1001,10000,10):
      if n//1000 in (1,3,7,9):
     
        rev = int(str(n)[::-1])
      
        # output solutions
        if len( (set(range(n,n+10,2)) | set(range(rev,rev+10000,1000))) & nosmallprimes) > 9:
          print "n=",n
    
    • arthurvause 10 July 2017 at 11:26 am

      A minor improvement, observing that at most 4 of the consecutive numbers can’t have a small factor (numbers ending in 2,4,5,6,8 will), and 3 of the reversed numbers are multiples of 3, so at most 6 of the reversed numbers don’t have a small factor:

      nosmallprimes = set(range(1001,10000,2)) 
      for p in (3,5,7,11,13) :
        nosmallprimes -= set(range(1000-1000%p,10000,p))
      
      for n in range(1001,10000,10):
        if n//1000 in (1,3,7,9):
          if len( (set(range(n,n+10,2)) & nosmallprimes)) == 4:
            rev = int(str(n)[::-1])
            if len ( set(range(rev,rev+10000,1000)) & nosmallprimes)==6:
              print "n=",n
      
  3. Brian Gladman 10 July 2017 at 1:45 pm
    # the possible prime factors 
    pf = (2, 3, 5, 7, 11, 13)
    
    # consider the leftmost digit (which cannot be even
    # since there would then be too many factors)
    for d1 in range(1, 10, 2):
      
      # ... and the number formed by digits 2 and 3
      for d23 in range(100):
    
        # form the leftmost three digit number and its reverse 
        d3, r3 = 100 * d1 + d23, int(str(100 * d1 + d23)[::-1])
        
        # consider the nine four digit numbers and their reverses,
        # collecting the number of values with a specified factor 
        nbr = 0
        for d in range(1, 10):
          n1, n2 = 10 * d3 + d, 1000 * d + r3
    
          # count any number with a specified factor
          if any(n1 % f == 0 for f in pf):
            nbr += 1
          # ... and any reverse with a specified factor
          if any(n2 % f == 0 for f in pf):
            nbr += 1
    
        # output base numbers with less than nine specified factors
        if nbr < 9:
          print(f'The number is {10 * d3 + 1}.')
    
  4. Hugh Casement 10 July 2017 at 4:32 pm

    The ‘start’ number takes the form abc1.  As Brian says, a cannot be even; nor can it be 5, or all the reversed numbers would be multiples of 5.
    Inevitably three numbers in each set are multiples of 3.
    a – b + c must be 0, -1, 10, or 11, so that none of the nine in either set is a multiple of 11.
    I think the condition that only one in each set is a multiple of 7 is that neither (100b + 10c – a) mod 7 nor (100c + 10b + a) mod 7 may be 5 or 6, but that probably doesn’t help us much.
    At that point, logic (cunning or otherwise) deserted me.

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: