cp's OEIS Frontend

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

%I A383977 #25 May 17 2025 22:42:35
%S A383977 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,
%T A383977 26,30,31,33,32,29,21,35,36,38,37,40,41,39,43,44,46,45,42,48,49,51,50,
%U A383977 53,54,52,47,34,56,57,59,58,61,62,60,64,65,67,66,63,69,70,72,71,74,75
%N A383977 Sequence of successive merge positions when Fibonacci-sorting an infinite list.
%C A383977 Arises naturally from the Fibonacci sort algorithm (see links).
%C A383977 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.
%C A383977 The entire sequence is a permutation of the positive integers (every positive integer occurs exactly once).
%C A383977 Differs from A194030 starting at n=10 with a(10) = 12 whereas A194030(10) = 11. Despite their similar starts, the two sequences are unrelated.
%H A383977 Lucilla Blessing, <a href="/A383977/b383977.txt">Table of n, a(n) for n = 1..10000</a>
%H A383977 Lucilla Blessing, <a href="https://thepoweroffive.me/writing/pdf/fibonacci_sort.pdf">Fibonacci Sort</a>
%F A383977 a(F(n+1) - 1) = F(n).
%F A383977 a(F(n) + k - 1) = F(n) + a(k), for 0 < k < F(n-1).
%e A383977 The first 7 merges when sorting a list of >= 8 values with Fibonacci sort are as follows:
%e A383977   (8|7)6 5 4 3 2 1 ...
%e A383977   (7 8|6)5 4 3 2 1 ...
%e A383977    6 7 8(5|4)3 2 1 ...
%e A383977   (6 7 8|4 5)3 2 1 ...
%e A383977    4 5 6 7 8(3|2)1 ...
%e A383977    4 5 6 7 8(2 3|1)...
%e A383977   (4 5 6 7 8|1 2 3)...
%e A383977    1 2 3 4 5 6 7 8 ...
%e A383977 The offsets of the "splitting positions" (marked by | characters) in the array are: 1, 2, 4, 3, 6, 7, 5...
%e A383977 These are a(1) through a(7).
%o A383977 (Python)
%o A383977 def fib(n):
%o A383977   return n if n < 2 else fib(n - 1) + fib(n - 2)
%o A383977 def a_first(n):
%o A383977   # returns an array of the first n terms
%o A383977   if n == 0: return []
%o A383977   f = []
%o A383977   i = 1
%o A383977   while True:
%o A383977     for j in range(fib(i) - 1):
%o A383977       f.append(f[j] + fib(i + 1))
%o A383977       if len(f) == n: return f
%o A383977     f.append(fib(i + 1))
%o A383977     if len(f) == n: return f
%o A383977     i += 1
%o A383977 (Haskell)
%o A383977 -- "a" is a list of all sequence values
%o A383977 -- e.g. "take 7 a" evaluates to [1, 2, 4, 3, 6, 7, 5]
%o A383977 import Data.List
%o A383977 fibs :: [Int]
%o A383977 fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
%o A383977 fib :: Int -> Int
%o A383977 fib n = fibs !! n
%o A383977 a :: [Int]
%o A383977 a = concat $ map (\i -> let
%o A383977   f = fib (i + 1)
%o A383977   fPrev = fib i
%o A383977   in (map (+ f) (take (fPrev - 1) a)) ++ [f]) [1..]
%Y A383977 Cf. A000045.
%K A383977 easy,nonn
%O A383977 1,2
%A A383977 _Lucilla Blessing_, May 16 2025