Enigmatic Code

Programming Enigma Puzzles

Enigma 1155: Ending up with numbers

From New Scientist #2311, 6th October 2001 [link]

To test my nephew’s arithmetic I get him to write down a three-figure number and then to write down the next twenty consecutive numbers as well. Then he has to “reverse” each of the numbers (so that 237 would become 732, and 540 would become 45, and so on). So, for example, if his starting number was 185 then the twenty-one numbers he would get would be: 581, 681, 781, 881, 981, 91, 191, 291, 391, 491, 591, 691, 791, 891, 991, 2, 102, 202, 302, 402 and 502.

I then ask him to cross out all those numbers which are divisible by 2, then from what’s left to cross out all those numbers divisible by 3, then from what’s left to cross out all those numbers divisible by 5, then from what’s left to cross out all those numbers divisible by 7, and finally from what’s left to cross out all those numbers divisible by 11. So, for example, if he started with 185 (as above) then he would end up with just the six numbers 881, 191, 391, 491, 691 and 991.

On one occasion recently he chose his three-figure starting number, carried out the above process and when he had finished he was left with 14 numbers. By some neat logic you can work out what the starting number was.

What was it?

[enigma1155]

Advertisements

9 responses to “Enigma 1155: Ending up with numbers

  1. Jim Randell 8 August 2016 at 8:42 am

    Instead of neat logic, this Python program uses an exhaustive search, and finds the solution in 44ms.

    from enigma import irange, nreverse, printf
    
    # a queue for 21 items
    q = []
    # count of true flags in the queue
    t = 0
    
    for i in irange(100, 1019):
      # reverse the number
      r = nreverse(i)
      # is r indivisible by 2, 3, 5, 7, 11
      f = all(r % n > 0 for n in (2, 3, 5, 7, 11))
      q.append((r, f))
      if f: t += 1
      # is the queue full?
      if len(q) == 21:
        # a solution has 14 flagged items in the queue
        if t == 14:
          printf("start={n}, q={q}", n=i - 20, q=list(r for (r, f) in q if f))
        # remove the front of the queue
        (r, f) = q.pop(0)
        if f: t -= 1
    

    Solution: The starting number was 749.

  2. Brian Gladman 8 August 2016 at 10:51 am
    from collections import deque
    
    # the 21 consecutive numbers (when reversed)
    nbrs = deque([], 21)
    # true if the related number in nbrs will be left
    # after the elimination step
    left = deque([], 21)
    
    # try all sequences starting with three digit values
    for nbr in range(100, 1020):
      # add the next nunber
      nbrs.append(int(str(nbr)[::-1]))
      # and whether it will be left after the elimination step
      left.append(all(nbrs[-1] % p for p in (2, 3, 5, 7, 11)))
      
      # find a sequence in which fourteen values will be left 
      if left.count(True) == 14:
        t = tuple(x for x, y in zip(nbrs, left) if y)
        print('Start: {} {}.'.format(nbr - 20, t))
    
  3. Hugh Casement 8 August 2016 at 1:13 pm

    Do any of you clever people have an idea what the neat logic could be?
    Clearly the procedure has the makings of a prime-number sieve, but he’s also going to be left with any multiples of 13, 17, 19, 23, 29, and 31.

    • Hugh Casement 8 August 2016 at 1:57 pm

      I meant, of course, that he’s going to be left with semi-primes whose factors are 13 or more.
      I got part of the way there.  Of the original 21 numbers, seven are multiples of 3.  Each digit-reverse has the same digit sum so is also a multiple of 3.  Therefore he can have crossed out no other numbers.  The original numbers must all have started with 1, 3, 7, or 9.  Any multiples of 7 or 11 in the reversed list must also be multiples of 3, so have been crossed out already.  The multiples of 11 correspond to the multiples of 11 in the original list; 7 is harder.

    • Jim Randell 9 August 2016 at 10:45 pm

      My thoughts about the neat logic were that when the 21 consecutive numbers are written out then every third number will be a multiple of 3. If a number is divisible by 3, then the sum of its digits is divisible by 3, and so of the 21 reversed numbers, the 7 that correspond to those consecutive multiples of 3 will also be divisible by 3, and the 14 numbers that aren’t multiples of 3 won’t be multiples of 3 when reversed either, so we need these numbers not to be multiples of 2, 5, 7 or 11 either.

      The final digit of the reversed numbers is the leading digit of the original numbers, so it has to be odd (otherwise the reversed numbers will be even), and remain odd for the entire sequence. Also, it cannot be 5, as the reversed numbers would all by divisible by 5, and if it is odd and not 5, then none of the reversed numbers will be divisible by 2 or 5.

      A divisibility test for 11 is to check to see if the alternating sum of the digits is divisible by 11. For a 3-digit number, abc, this is (a − b + c), which is the same for the reversed number. So the central number in the consecutive sequence must be a multiple of 3 and of 11, so that the next smallest and next largest multiples of 11 will fall outside the sequence.

      So the central number in the consecutive sequence is (33 × n). And the sequence runs from (33n − 10) to (33n + 10).

      This only leaves us with multiples of 7 to consider. But I haven’t yet got such a neat analysis for divisibility by 7.

      But we have narrowed the initial sequence down to being centred on eight possible values. Maybe that is enough.

      • Jim Randell 10 August 2016 at 8:33 am

        Here’s a Python program that uses the above analysis to examine the possibilities:

        from enigma import irange, nreverse, printf
        
        # consider n, the middle number of the consecutive sequence
        # it is a multiple of 33 and the sequence is [n - 10, n + 10]
        for n in irange(33, 1009, step=33):
          # it must be 3 digits, and the first is 1, 3, 7, 9
          (a, bc) = divmod(n, 100)
          if a not in (1, 3, 7, 9): continue
          # all numbers in the sequence must have the same first digit
          if not(9 < bc < 90): continue
          # any number in the sequence that is not divisible by 3 it's reverse is not divisible by 7
          if any(nreverse(x) % 7 == 0 for x in irange(n - 10, n + 10) if x % 3 > 0): continue
          printf("sequence = [{x}, ..., {y}]", x=n - 10, y=n + 10)
        
      • Jim Randell 10 August 2016 at 12:26 pm

        For the 7’s we can look at the reversed sequence, which will be a concatenation of 3 arithmetic progressions with a common difference of 100. One (or two) of them will be complete (with 10 elements) and two (or one) of them will be truncated.

        No complete sequence can have an element 0xy, 1xy, 2xy divisible by 7, as the entry 7xy, 8xy, 9xy would differ by 700 and so be also be divisible by 7, and they can’t both be divisible by 3.

        This method eliminates 5 of the possible 8 sequences. For the remaining three we examine all multiples of 7 in the reversed sequence to ensure they are also divisible by 3.

        So examining the possible sequences, centred on the eight candidate (forward) numbers:

        (1) 132, maps to 231 when reversed. So the reversed sequence includes the complete progression (31, …, 931). But both 231 and 931 are divisible by 7.

        (2) 165, maps to 561 when reversed. So the reversed sequence includes the complete progression (61, …, 961). But both 161 and 861 are divisible by 7.

        (3) 330, maps to 33 when reversed. So the reversed sequence includes the complete progression (33, …, 933). But both 133 and 833 are divisible by 7.

        (4) 363, maps to 363 when reversed. So the reversed sequence includes the complete progression (63, …, 963). But both 63 and 763 are divisible by 7.

        (5) 726, cannot be eliminated this way. The reversed sequence is (617, …, 917) (27, …, 927) (37, …, 637). And this includes 917, 427, 637, which are all divisible by 7, and none of them are also divisible by 3.

        (6) 759. The reversed sequence is (947) (57, …, 957) (67, …, 967). This includes 357 and 567 which are divisible by 7, but are both also divisible by 3. This candidate is not eliminated.

        (7) 924. The reversed sequence (419, …, 919) (29, …, 929) (39, …, 439) includes 819 and 329 as multiples of 7. 329 is not also a multiple of 3.

        (8) 957. The reversed sequence includes (59, …, 959), which includes 259 and 959, both divisible by 7.

        So (6), the sequence centred of 759, is the solution.

        I don’t know if this is the method the setter had in mind. It doesn’t seem that neat to me, but it is enough to permit a manual solution.

  4. geoffrounce 9 August 2016 at 9:24 am
    nlist, rlist = [], []
    
    for num in range(101,1020,2):
        del(nlist)
        del(rlist)
        revnum = int(str(num)[::-1])
        nlist, rlist = [], []
        if all(revnum % a != 0 for a in(2,3,5,7,11)):
            nlist.append(num)
            rlist. append(revnum)
            for n in range(1,21):
                nlist.append(num + n)
                revnum = int(str(num + n)[::-1])
                if all(revnum % a != 0 for a in(2,3,5,7,11)):
                    rlist.append(revnum)
                    if len(rlist) == 14:
                        print('Starting number was:', nlist[0])
                        print('Reverse number list:', rlist)
                        print('Number list:',nlist)
    
    # Output (16 msec)                   
    # Starting number was: 749
    # Reverse number list: [947, 157, 257, 457, 557, 757, 857,
    # 67, 167, 367, 467, 667, 767, 967]
    # Number list: [749, 750, 751, 752, 753, 754, 755, 756, 757,
    # 758, 759, 760, 761, 762, 763, 764, 765, 766, 767, 768, 769]
    
  5. geoffrounce 10 August 2016 at 9:35 am

    Here is an update to the code in my original posting:

    for num in range(101, 1000, 2):
        revnum = int(str(num)[::-1])
        nlist, rlist = [], []
        if all(revnum % a != 0 for a in (3, 5, 7, 11)):
            # add 20 numbers to the starting number
            for n in range(21):
                nlist.append(num + n)
                revnum = int(str(num + n)[::-1])
                if all(revnum % a != 0 for a in (3, 5, 7, 11)):
                    rlist.append(revnum)
            if len(rlist) == 14:
                print('Starting number was:', num)
                print('Reverse number list:', rlist)
                print('Number list:',nlist)
    

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: