Teaser 2607: Tribonacci
From The Sunday Times, 9th September 2012 [link] [link]
In the Fibonacci sequence 1, 2, 3, 5, 8, 13, … each number after the second is the sum of the previous two. Pat has experimented with some “Tribonacci” sequences of positive whole numbers where each number after the third is the sum of the previous three.
He chooses the first three numbers to be different and in increasing order and then generates the sequence. He has shown us one where just the first five numbers are less than a hundred and where a later number is ten thousand.
What are the first three numbers in this sequence?
[teaser2607]
Frits, 
GeoffR, and 2 others are discussing. 
Lise Andreasen, 
Ruud, and 1 other are discussing. 
Hugo and 
S2T2 
Jim Randell 10:10 am on 17 April 2024 Permalink |
If the first 3 terms are a, b, c (where a < b < c) then the first 5 terms are:
And so the fifth term of the sequence must be at least:
We can use these to reduce the search space for the (a, b, c) values.
This Python program runs in 78ms. (Internal runtime is 12ms).
Run: [ @replit ]
from enigma import (irange, fib, first, le, printf) # suppose the sequence starts (a, b, c, a+b+c, a+2b+2c, ...) # and these terms are all < 100 for a in irange(1, 97): if not (5*a + 6 < 100): break for b in irange(a + 1, 98): if not (a + 4*b + 2 < 100): break for c in irange(b + 1, 99): if not (a + 2*b + 2*c) < 100: break if 2*a + 3*b + 4*c < 100: continue # calculate terms up to 10_000 ss = first(fib(a, b, c), le(10000)) # is the final term 10_000? if ss[-1] == 10000: # output solution sequence printf("{ss}")Solution: The first three numbers in the sequence are: 6, 11, 24.
The terms of the sequence up to 10,000 are:
LikeLike
Frits 3:17 pm on 17 April 2024 Permalink |
“just the first five numbers are less than a hundred” :
sixth term: 2a + 3b + 4c > 99
LikeLike
Jim Randell 3:29 pm on 17 April 2024 Permalink |
Good point. I’ve added a check in my program to ensure the 6th term is at least 100.
LikeLike
Frits 8:30 pm on 17 April 2024 Permalink |
I wanted to start from the back of the sequence. It has been a lot of work.
This might be automated with the sympy or z3 packages (or with Enigma’s Matrix.linear_solve).
from math import ceil # round r = lambda n, k=0: int(round(n, k)) if k == 0 else round(n, k) # suppose the sequence ends like the following list s = [ "18*y+27*z-200000", "-20*y-2*z+70000", "7*y-13*z+50000", "5*y+12*z-80000", "-8*y-3*z+40000", "4*y-4*z+10000", "y+5*z-30000", "-3*y-2*z+20000", "2*y-z", "2*z-10000", "-y-z+10000", "y", "z", "10000"] # the sequence must be increasing: # 7*y-13*z+50K < 5*y+12*z-80K, 2*y < 25*z-130K, y < 12.5*z - 65K # 5*y+12*z-80K < -8*y-3*z+40K, 13y < -15*z + 120K, y < -15/13*z + 120K/13 # -8*y-3*z+40K < 4*y-4*z+10K, 12y > z + 30K y > z/12 + 2500 # 4*y-4*z+10K < y+5*z-30K , 3*y < 9*z - 40K y < 3*z - 40K/3 # y+5*z-30K < -3*y-2*z+20K, 4*y < -7*z + 50K y < -7/4*z + 12500 # -3*y-2*z+20K < 2*y-z , 5*y > -z + 20K y > -z/5 + 4K # 2*y-z < 2*z-10K , y < 1.5*z - 5K # determine minimum for <z> # y < 12.5*z - 65K, z > y / 12.5 + 5200 and y > -z/5 + 4K # z > -z / 62.5 + 5520, 63.5/62.5*z > 5520, z > 5433.07 # determine maximum for <z> # 15/13*z < -y + 120K/13 and y > -z/5 + 4K # 15*z < 13*(z/5 - 4K) + 120K, z < 68K / 12.4 = 5483.87 # maximum looks too high (knowing the answer) so: # 15/13*z < -y + 120K/13 and y > z/12 + 2500 # 15*z < -13*(z/12 + 2500) + 120K, z < 12 * 87500 / 193 = 5440.41 for z in range(5434, 5441): # determine boundaries for <y> mx = min(1.5*z - 5000, 12.5*z - 65000, -15/13*z + 120000/13, 3*z - 40000/3, -7/4*z + 12500) mn = max(z / 12 + 2500, -z/5 + 4000) for y in range(int(mn) + 1, ceil(mx)): # calculate the sequence numbers ns = [eval(x) for x in s] # determine the 5 numbers below 100 b100 = [n for n in ns if n < 100] if len(b100) < 5: continue f5 = b100[-5:] # five numbers must be increasing and without a valid previous number if sorted(f5) == f5 and f5[0] > 0 and \ not (0 < f5[2] - f5[1] - f5[0] < f5[0]): print("answer:", f5[:3], "\n") # print the sequence for i, x in enumerate(s): print(f"{i + 1:>2} {x:<20} {ns[i]:<10}")LikeLike
ruudvanderham 8:18 am on 18 April 2024 Permalink |
Instead of a very clever, fast algorithm, here’s a super simple -brute force- solution without any reasoning beforehand.
import itertools for i1, i2, i3 in itertools.combinations(range(1, 100), 3): n_min2 = i1 + i2 + i3 n_min1 = i2 + i3 + n_min2 if n_min2 < 100 and n_min1 < 100: n = i3 + n_min2 + n_min1 while n < 10000: n_min2, n_min1, n = n_min1, n, n_min2 + n_min1 + n if n == 10000: print(i1, i2, i3)LikeLike
Jim Randell 11:39 am on 18 April 2024 Permalink |
Here is a different approach, that I didn’t think would be very fast, but it turns out it has an internal runtime of 11ms. (Although it does stop when it finds the first solution).
It works by generating the coefficients of (a, b, c) in each term, i.e.
And then, when we reach sufficiently large terms, it looks for (a, b, c) values between 1 and 99 that would give the term a value of 10000. If an acceptable set of values is found we construct the sequence of terms up to 10000 and check the remaining conditions.
Run: [ @replit ]
from enigma import (unzip, express, fib, first, dot, printf) # solve the puzzle, by looking for a term = N def solve(N=10000): # a, b, c coefficients for terms 1, 2, 3 ts = [(1, 0, 0), (0, 1, 0), (0, 0, 1)] k = 3 # find the coefficients in the k'th term while True: k += 1 cs = tuple(sum(ss) for ss in unzip(ts)) if k > 5 and not (dot(cs, [97, 98, 99]) < N): # is the k'th term is N for (a, b, c) in express(N, cs, min_q=1, max_q=99): if not (a < b < c): continue # calculate the first k terms ss = first(fib(a, b, c), k) # check 5th term < 100 and 6th term >= 100 if ss[4] < 100 and not (ss[5] < 100): yield ss # move on to the next term ts.pop(0) ts.append(cs) for ss in solve(): printf("{ss}") breakA custom version of
express()that only generates quantities in ascending order would probably make this code even faster.LikeLike
Frits 5:58 pm on 18 April 2024 Permalink |
Mix of Jim’s and Ruud’s code.
# 5a + 6 < 100 for a in range(1, 19): # a + 4 * b + 2 < 100 for b in range(a + 1, (101 - a) // 4): # a + 2b + 2c < 100 and not all odd # sixth term 2 * a + 3 * b + 4 * c > 99 mn = max(b + 1, (103 - 2 * a - 3 * b) // 4) mxplus1 = (101 - a - 2 * b) // 2 for c in range(mn, mxplus1, 1 + (a % 2 and b % 2)): n_min2 = a + b + c n_min1 = a + 2 * b + 2 * c n = c + n_min2 + n_min1 while n < 10000: n_min2, n_min1, n = n_min1, n, n_min2 + n_min1 + n if n == 10000: print("answer:", a, b, c)LikeLike
Hugo 11:03 am on 17 April 2024 Permalink |
I solved this rather differently.
In a Fibonacci sequence, the ratio of successive terms tends to the positive root of the equation
x^2 = x + 1. Here it tends to the real root of x^3 = x^2 + x + 1: x = 1.839 287 approx.
I divided 10000 by that number twice, taking the nearest integer each time.
The method may lead to incorrect values when they become small,
but I continued with the relationship T(n) = T(n + 3) – T(n + 2) – T(n + 1)
for successively smaller n and got the required answer.
LikeLike
GeoffR 10:54 am on 18 April 2024 Permalink |
Not a rigorous solution – I had to use the fact that the answer is the 13th term, in order to get a solution in MiniZinc.
LikeLike
Frits 2:06 pm on 18 April 2024 Permalink |
An implementation with the z3 solver (of my previous program).
Downside is that I had to fix the sequence length to 13. I tried to loop over sequence lengths but for some reason the program got really slow after one or 2 runs.
from z3 import Solver, Int, simplify, sat s = Solver() M = 13 # length of final sequence # variables y, z = Int('y'), Int('z') # start from the back of the sequence a, b, c = "y", "z", "10000" seq = [a, b, c] eqs = ["y < z", "z < 10000"] # add <M - 3> previous numbers for _ in range(M - 3): a, b, c = c + " - (" + a + ") - (" + b + ")", a, b, # simplify and prettify the new equation a_ = str(eval(f"simplify({a})")) seq = [a_.replace("+ -", "-").replace("-", "- ").replace(" 1*", " ")] + seq eval(f"s.add({a} < {b})") # first sequence number must be positive (otherwise y = 2957 is a solution) eval(f"s.add({seq[0]} > 0)") # run z3 solver if(s.check() == sat): m = s.model() # convert y and z to integers y = int(str(m[y])) z = int(str(m[z])) # calculate the sequence numbers ns = [eval(x) for x in seq] # determine the 5 numbers below 100 b100 = [n for n in ns if n < 100] if len(b100) >= 5: f5 = b100[-5:] # five numbers must be increasing if sorted(f5) == f5 and f5[0] > 0: print("answer:", f5[:3], "\n") # print the sequence for i, x in enumerate(seq): print(f"{i + 1:>2} {x:<22} {ns[i]:<10}")LikeLike