### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,525)
- enigma-book-1982 (71)
- misc (5)
- project euler (2)
- puzzle (90)
- puzzle# (129)
- site news (70)
- tantalizer (170)
- teaser (7)
- today (1)

### Site Stats

- 287,425 hits

Programming Enigma Puzzles

8 October 2021

Posted by on **From New Scientist #1796, 23rd November 1991** [link]

My children had been practising addition, forming additive sequences of numbers, and when the numbers got too large for them, extending the sequence the other way using subtraction and getting some negative numbers. Eventually, they noticed that one of their sequences had numbers in it divisible by 2, 3, 5 and 7 but none divisible by 11. Part of that sequence was:

… –2 3 1 4 …

the rule going from left to right being, of course, that one term plus the following one gives the next.

The children soon saw too that every sequence they wrote down had terms divisible by 2 and 3, and probably 7 also.

What I want you to find is the two sequences like this, each having no terms divisible by 5, 11 or 13. In each sequence the four consecutive terms we want should have:

just the first term negative;

the third term 3;

and the fourth term less than 100.(In fact, one of the sequences will have terms divisible by 17 and none divisible by 19, while the other will have terms divisible by 19 and none divisible by 17, but you don’t need these facts to find them).

Find the four terms of the two sequences.

[enigma642]

%d bloggers like this:

If the second term is

a, and the third term isb, then the start of the sequence looks like:We are looking for sequences where

(b – a)is negative (i.e.a > b).And

b= 3.And

(a + b)< 100.So, we have:

This Python program examines terms of candidate sequences, removing those that have terms divisible by 5, 11, or 13, until there are only 2 sequences remaining. It runs in 55ms.

Run:[ @replit ]Solution:The two sequences start: (–28, 31, 3, 34) and (–73, 76, 3, 79).(The published solution gives 6 as the third term in the second sequence, but this must be an error in the solution, as the third term is required to be 3).

@Jim, the problem for me is a bit ambiguous.

If I have problems adding numbers bigger than fi 400 then there are probably more solutions (like -48, 51, 3, 54). So the solution depends on this limit (and if you swap back to adding again?).

You only say “if there are two such sequences it must be A and B”. There is no check whether if the sequence is continued (up to infinity?) for A and B no divisibility by 5, 11 or 13 may arise.

@Frits: As I can’t test all terms in a sequence programmatically, I treated the statement that there are exactly two sequences as described that have no terms divisible by 5, 11 or 13, as a fact.

So all I need to do is eliminate all the other sequences, and the two that remain must be the two I’m looking for. And that is what my program does.

It is easy to check that first 50,000 terms or so of these sequences programmatically, but to show all terms are not divisible would require a mathematical proof. (Like

Teaser 683).I had a look at the behaviour of these sequences mod 5, 11, 13 and we get patterns that repeat as follows. For (–73, 76):

And for (–28, 31):

And we can show that these sequences repeat indefinitely, and as none of them contain 0, it demonstrates the two sequences have the required property.

@Jim, instead of proving these sequences repeat indefinitely you might use (or add to enigma.py) a function which checks a list of numbers on repeating sequences (and with a minimum number of such sequences to occur before True is returned).

Function repseq is not totally accurate for certain odd m’s (example: if input contains 11 repetitions and m is set to 11 False is returned)

Pingback: New Scientist Enigma 642 – Fibonacciesque | PuzzlingInPython

Here is a program that examines each possible sequence and reports those that have no terms divisible by 5, 11, or 13.

If we consider one of the sequences, each term is the sum of the previous two terms.

So looking at the “mod sequence”, where each term is taken modulo

k, we see that each term is also the sum (modk) of the previous two terms.So, if we see two adjacent terms that we have seen before, we know the sequence must repeat.

And there are only a finite number of pairs (mod

k), so every mod sequence must eventually repeat.So we can look for zeros in the mod sequence, until we come across a pair of values we have seen before, and then we know for sure that there are no zeros in the entire sequence, and hence no terms divisible by

kin the parent sequence.This Python program examines each sequence, and outputs those that with no terms divisible by 5, 11, or 13. It doesn’t need to know that there are exactly two sequences with this property. It runs in 55ms.

Run:[ @replit ]And it confirms that exactly 2 of the sequences have this property.

We can use the same idea to show:

(–28, 31, 3, …) has elements that are divisible by 17, but none that are divisible by 19.

(–73, 76, 3, …) has no elements that are divisible by 17, but does have elements divisible by 19.