Programming Enigma Puzzles
From New Scientist #2118, 24th January 1998 [link]
In the interest of a healthier lifestyle, George has decided to buy some fruit every week — but he is starting gradually.
The first week, when he gets his pay-packet, he buys and eats an apple. The second week, he buys and eats an orange. The third week, he buys and eats a banana.
In every subsequent week he buys and eats the same items of fruit as he consumed in the previous three weeks combined, and in the same order. Thus the first six weeks, in order, are:
A
O
B
AOB
OBAOB
BAOBOBAOBYou will quickly discover that this story is quite incredible, but if it could be believed, what would be the one-millionth piece of fruit consumed, and in which week?
[enigma963]
 | Frits on Enigma 773: Duodecimal |
 | Jim Randell on Enigma 773: Duodecimal |
 | Brian Gladman on Enigma 773: Duodecimal |
| Frits on Enigma 773: Duodecimal |
| Frits on Enigma 773: Duodecimal |
| Frits on Enigma 773: Duodecimal |
| Frits on Enigma 773: Duodecimal |
| Jim Randell on Enigma 773: Duodecimal |
Enigmatic Code 
This Python program constructs the sequence for each week. It runs in 96ms.
Run: [ @repl.it ]
from enigma import join, arg, printf # term we are interested in k = arg(1000000, 0, int) # generate the list for successive weeks def generate(s): while True: s.append(join(s[-3:])) yield s.pop(0) # consider weeks (numbered from 1) t = 0 for (w, x) in enumerate(generate(['A', 'O', 'B']), start=1): n = len(x) t += n printf("week {w}: n={n}; t={t}") if not(t < k): i = x[k - t - 1] printf("-> {k}th item = {i}") breakSolution: The one millionth piece of fruit consumed is a banana. It is consumed during the 24th week.
The n sequence (number of pieces of fruit eaten each week) is a Tribonacci sequence with (1, 1, 1) as the the first 3 terms [ see A000213 ].
The t sequence (total number of pieces of fruit eaten) is a Tribonacci sequence with (1, 2, 3) as the first 3 terms [ see A001590 ].