OFFSET
0,2
COMMENTS
Random Fibonacci numbers are defined by f(1) = f(2) = 1, and f(n) = f(n-1) +/- f(n-2) where the sign is chosen at random.
LINKS
John D. Cook, Is every integer a random Fibonacci number?, Blog, 31 October 2020.
H. Furstenberg and H. Kesten, Products of random matrices, Annals of Mathematical Statistics, volume 31, number 2, 1960, pages 457-469. (Asymptotic properties of random Fibonacci numbers.)
Rémy Sigrist, C program for A338517
EXAMPLE
The following is the union of all random Fibonacci sequences of length 8: [-5, -3, -2, -1, 0, 1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 21]. The largest negative number not included is -4, and the smallest positive number not included is 6.
PROG
(PARI) a(n)={if(n==0, 1, my(F=Set([[1, 1]]), T=Set(1)); for(k=3, n, F=setunion(Set(vector(#F, i, my([a, b]=F[i]); [a+b, a])), Set(vector(#F, i, my([a, b]=F[i]); [a-b, a]))); T=setunion(T, Set(vector(#F, i, F[i][1])))); my(v=select(t->t>0, T), k=1); while(k<=#v&&v[k]==k, k++); k)} \\ Andrew Howroyd, Nov 07 2020
(C) See Links section.
(Python)
def aupto(n, v=False):
Xall, Xnm2Xnm1, alst, leastnot = {1}, {(1, 1)}, [1, 2, 2], 2
if v: print(*[ak for k, ak in enumerate(alst) if k<=n], sep=", ", end=", ")
for n in range(3, n+1):
Xnm1Xn = set()
for x, y in Xnm2Xnm1:
Xnm1Xn.update([(y, y-x), (y, y+x)])
Xall.update([y-x, y+x])
Xnm2Xnm1 = Xnm1Xn
for i in range(leastnot, max(Xall)+2):
if i not in Xall: leastnot = i; break
alst.append(leastnot)
if v: print(leastnot, end=", ")
return alst
aupto(40, v=True) # Michael S. Branicky, Jan 02 2021
CROSSREFS
KEYWORD
nonn,more
AUTHOR
John D. Cook, Oct 31 2020
EXTENSIONS
a(28)-a(35) from Jinyuan Wang, Nov 07 2020
a(36)-a(41) from Rémy Sigrist, Nov 09 2020
STATUS
approved