|
| |
|
|
A338517
|
|
Smallest positive number not in a random Fibonacci sequence of length n.
|
|
1
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
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.)
|
|
|
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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,more
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
