A338517 Smallest positive number not in a random Fibonacci sequence of length n.

1, 2, 2, 3, 4, 4, 6, 6, 6, 15, 20, 20, 33, 38, 38, 85, 90, 90, 229, 252, 252, 483, 638, 638, 1395, 1864, 1864, 3705, 4830, 4830, 10395, 13772, 13772, 31995, 40950, 40950, 89595, 97490, 97490, 272235, 314490, 314490

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

Table of n, a(n) for n=0..41.

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

Cf. A336717.

Sequence in context: A224979 A211317 A126246 * A173633 A138369 A173332

Adjacent sequences: A338514 A338515 A338516 * A338518 A338519 A338520

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