OFFSET
1,2
COMMENTS
Arises naturally from the Fibonacci sort algorithm (see links).
The restriction of this sequence to the first F(k) - 1 entries, where k >= 2 and F is the Fibonacci sequence (A000045), is a permutation.
The entire sequence is a permutation of the positive integers (every positive integer occurs exactly once).
Differs from A194030 starting at n=10 with a(10) = 12 whereas A194030(10) = 11. Despite their similar starts, the two sequences are unrelated.
Conjecture: a(n) is obtained by reading the binary number on the right column of page 10 in the Arndt reference, interpreted as Fibonacci base, reading from bottom to top; see example. - Joerg Arndt, Jan 31 2026
LINKS
Lucilla Blessing, Table of n, a(n) for n = 1..10000
Joerg Arndt, Subset-lex: did we miss an order?, arXiv:1405.6503 [math.CO], 2014-2024, pp. 11-12 (subset-lex order for binary non-adjacent forms).
Lucilla Blessing, Fibonacci Sort.
FORMULA
a(F(n+1) - 1) = F(n).
a(F(n) + k - 1) = F(n) + a(k), for 0 < k < F(n-1).
EXAMPLE
The first 7 merges when sorting a list of >= 8 values with Fibonacci sort are as follows:
(8|7)6 5 4 3 2 1 ...
(7 8|6)5 4 3 2 1 ...
6 7 8(5|4)3 2 1 ...
(6 7 8|4 5)3 2 1 ...
4 5 6 7 8(3|2)1 ...
4 5 6 7 8(2 3|1)...
(4 5 6 7 8|1 2 3)...
1 2 3 4 5 6 7 8 ...
The offsets of the "splitting positions" (marked by | characters) in the array are: 1, 2, 4, 3, 6, 7, 5...
These are a(1) through a(7).
From Joerg Arndt, Jan 31 2026: (Start)
n: subset-lex a(n)
(dots for zeros)
1: .......1 1
2: ......1. 2
3: .....1.1 4
4: .....1.. 3
5: ....1..1 6
6: ....1.1. 7
7: ....1... 5
8: ...1...1 9
9: ...1..1. 10
10: ...1.1.1 12
11: ...1.1.. 11
12: ...1.... 8
13: ..1....1 14
14: ..1...1. 15
15: ..1..1.1 17
16: ..1..1.. 16
17: ..1.1..1 19
18: ..1.1.1. 20
19: ..1.1... 18
20: ..1..... 13
21: .1.....1 22
22: .1....1. 23
(End)
MAPLE
PROG
(Python)
from functools import cache
@cache
def fib(n):
return n if n < 2 else fib(n - 1) + fib(n - 2)
def a_first(n):
# returns an array of the first n terms
if n == 0: return []
f = []
i = 1
while True:
for j in range(fib(i) - 1):
f.append(f[j] + fib(i + 1))
if len(f) == n: return f
f.append(fib(i + 1))
if len(f) == n: return f
i += 1
(Haskell)
-- "a" is a list of all sequence values
-- e.g. "take 7 a" evaluates to [1, 2, 4, 3, 6, 7, 5]
import Data.List
fibs :: [Int]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
fib :: Int -> Int
fib n = fibs !! n
a :: [Int]
a = concat $ map (\i -> let
f = fib (i + 1)
fPrev = fib i
in (map (+ f) (take (fPrev - 1) a)) ++ [f]) [1..]
(PARI) A383977_first(n)={my(L=[], F=1, G=1); while(#L<n && L=concat(L, F), F=G+G=F; L=concat(L, [x+F | x<-L[1..min(G-1, n-#L)]])); L} \\ M. F. Hasler, Feb 02 2026
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Lucilla Blessing, May 16 2025
STATUS
approved
