A154393 Empirically good sequence of increments for shell sort algorithm.

1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713, 4895689348, 23233383508, 110258103799, 523249458736, 2483172990911, 11784338112247, 55924666344750, 265400424550505, 1259504788813791, 5977203382848010

Offset: 1

Author

Niels Pardons (nielspardons(AT)hotmail.com), Jan 08 2009

Keywords

• nonn

Comments

This sequence was made by taking the Fibonacci numbers, leaving out one of the starting 1's, raising them to the power of 2 * the golden ratio. Fractions are removed with the floor function. It works particularly well as a gap sequence for the shell sort algorithm on large arrays.

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..1000
• Wikipedia, Shell sort

Programs

Mathematica

Table[Floor[Fibonacci[n + 1]^(1 + Sqrt[5])], {n, 1, 10}] (* G. C. Greubel, Sep 16 2016 *)

Formula

a(n) = floor(fibonacci(n+1)^(1+sqrt(5))).

Extensions

More terms from Alois P. Heinz, May 31 2016