### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,183)
- misc (2)
- project euler (2)
- puzzle (46)
- site news (46)
- tantalizer (49)
- teaser (3)

### Site Stats

- 184,818 hits

Advertisements

Programming Enigma Puzzles

8 August 2016

Posted by on **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

%d bloggers like this:

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

Solution:The starting number was 749.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.

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.

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.

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

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,2xydivisible by 7, as the entry7xy,8xy,9xywould 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:

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.

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