# Enigmatic Code

Programming Enigma Puzzles

## Enigma 642: Fibonacciesque

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]

### 8 responses to “Enigma 642: Fibonacciesque”

1. Jim Randell 8 October 2021 at 8:30 am

If the second term is a, and the third term is b, then the start of the sequence looks like:

(b – a), (a), (b), (a + b), …

We are looking for sequences where (b – a) is negative (i.e. a > b).

And b = 3.

And (a + b) < 100.

So, we have:

b = 3
3 < a < 97

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 ]

```from enigma import irange, fib, first, printf

# candidate sequences by the first 2 terms
ss = dict()
b = 3
for a in irange(4, 96):
k = (b - a, a)
ss[k] = fib(*k)

# consider terms in the sequences, until we only have 2 candidate remaining
while len(ss.keys()) > 2:
# remove any sequence with a term divisible by 5, 11, 13
ks = list()
for (k, v) in ss.items():
n = next(v)
if any(n % d == 0 for d in (5, 11, 13)):
ks.append(k)
for k in ks: del ss[k]

# output the first 4 terms of each remaining sequence
for k in ss.keys():
ts = first(fib(*k), 4)
printf("{ts} ...")
```

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).

• Frits 8 October 2021 at 1:18 pm

@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.

• Jim Randell 8 October 2021 at 1:43 pm

@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).

• Jim Randell 8 October 2021 at 2:29 pm

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):

mod 5: [2, 1, 3, 4] …
mod 11: [4, 10, 3, 2, 5, 7, 1, 8, 9, 6] …
mod 13: [5, 11, 3, 1, 4, 5, 9, 1, 10, 11, 8, 6, 1, 7, 8, 2, 10, 12, 9, 8, 4, 12, 3, 2, 5, 7, 12, 6] …

And for (–28, 31):

mod 5: [2, 1, 3, 4] …
mod 11: [5, 9, 3, 1, 4] …
mod 13: [11, 5, 3, 8, 11, 6, 4, 10, 1, 11, 12, 10, 9, 6, 2, 8, 10, 5, 2, 7, 9, 3, 12, 2, 1, 3, 4, 7]…

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.

• Frits 8 October 2021 at 3:12 pm

@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).

2. Frits 8 October 2021 at 5:44 pm

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)

```
from enigma import SubstitutedExpression

# check the first <n> numbers of <s> and see if a sequence repeats itself
def repseq(s, n=1000, m=1):
if not type(s) is tuple:
s = tuple(s)
rep = dict()
n = min(n, len(s))
i = 2
while i < n:
fh = s[:i//2]
sh = s[i//2:i]
# both halves same?
if fh == sh:
for k, v in rep.items():
r = len(fh) // len(k)
# sequence repeats itself <r> times?
if k * r == fh:
rep[k] = r * 2
break
else: # no break
# new sequence which repeats itself?
if fh not in rep:
rep[fh] = 2
i += 2

# check if sequence repeats itself at least <m> times
for k, v in rep.items():
if v < m: return dict()

return rep

# the alphametic puzzle
p = SubstitutedExpression(
[ # (b – a), (a), (b), (a + b), ..   with b = 3, 3 - a < 0 and a + b < 100
# 3 - a, a, 3, a + 3 with 4 <= a <= 96
"4 <= AB <= 96",
"not any(x % j == 0 for x in [3 - AB, AB, AB + 3] for j in [5, 11, 13])",
],
answer="AB, (3 - AB, AB, 3, AB + 3)",
verbose=0,
d2i="",
reorder=0,
)

firstnum = 1000
for (_, ans) in p.solve():
# check if candidate answers have repeated modulo sequences
for d in (5, 11, 13):
li = ans[:2]
cum = [x % d for x in li]
# first <firstnum> entries
for _ in range(firstnum - 2):
new = li[-1] + li[-2]
if new % d == 0: break

li = [li[-1], new]
cum.append(new % d)
else: # no break
# check the first <firstnum> numbers of cumulative modulos
if not repseq(cum, firstnum, 10): break

continue  # next d

# break occurred in previous loop
break
else: # no break
print(f"{ans}")
```
3. Jim Randell 9 October 2021 at 9:39 am

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 (mod k) 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 k in 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 ]

```from enigma import irange, fib, unpack, tuples, first, printf

# make a mod sequence
fibmod = lambda a, b, k: fib(a % k, b % k, fn=unpack(lambda x, y: (x + y) % k))

# are there zeros in mod sequence s?
def zero(s):
# look for repeated pairs
seen = set()
for p in tuples(s, 2):
if 0 in p: return True
if p in seen: return False

# examine candidate sequences
b = 3
for a in irange(4, 96):
# look for mod-sequences that contain no zeros
if not any(zero(fibmod(b - a, a, k)) for k in (5, 11, 13)):
printf("{ts} ...", ts=first(fib(b - a, a), 4))
```

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.

This site uses Akismet to reduce spam. Learn how your comment data is processed.