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