A383977 Sequence of successive merge positions when Fibonacci-sorting an infinite list.

1, 2, 4, 3, 6, 7, 5, 9, 10, 12, 11, 8, 14, 15, 17, 16, 19, 20, 18, 13, 22, 23, 25, 24, 27, 28, 26, 30, 31, 33, 32, 29, 21, 35, 36, 38, 37, 40, 41, 39, 43, 44, 46, 45, 42, 48, 49, 51, 50, 53, 54, 52, 47, 34, 56, 57, 59, 58, 61, 62, 60, 64, 65, 67, 66, 63, 69, 70, 72, 71, 74, 75

Offset: 1

Author

Lucilla Blessing, May 16 2025

Keywords

• easy
• nonn

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.

Examples

			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).
		

Links

• Lucilla Blessing, Table of n, a(n) for n = 1..10000
• Lucilla Blessing, Fibonacci Sort

Crossrefs

Cf. A000045.

Programs

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..]

Python

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

Formula

a(F(n+1) - 1) = F(n).

a(F(n) + k - 1) = F(n) + a(k), for 0 < k < F(n-1).