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,2

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

Formula

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

Mathematica

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

Crossrefs

Sequence in context: A264678 A050478 A204426 * A119389 A197273 A067960

Adjacent sequences: A154390 A154391 A154392 * A154394 A154395 A154396

Keyword

nonn

Author

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

Extensions

More terms from Alois P. Heinz, May 31 2016

Status

approved