A108870 a(n) = ceiling((9*(9/4)^n - 4) / 5).

1, 4, 9, 20, 46, 103, 233, 525, 1182, 2660, 5985, 13467, 30301, 68178, 153401, 345152, 776591, 1747331, 3931496, 8845866, 19903198, 44782196, 100759940, 226709866, 510097200, 1147718700, 2582367076, 5810325920, 13073233321, 29414774973

Offset: 0

Author

Jud McCranie, Jul 13 2005

Keywords

• easy
• nonn

Comments

The old definition was "Tokuda's good set of increments for Shell sort", but that seems to be false.

Adding 0, -1, -1, -1, ... to the terms gives A361506. For another version see A361507.

References

• N. Tokuda, An Improved Shellsort, IFIP Transactions, A-12 (1992) 449-457.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Marcin Ciura, Best Increments for the Average Case of Shellsort, in R. Freivalds, (ed.), Fundamentals of Computation Theory: 13th International Symposium, FCT 2001, Riga, Latvia, August 2001, Lecture Notes in Computer Science, vol. 2138, Springer, pp. 106-117.

Crossrefs

Other sequences used for Shell sort: A003462, A033622, A036562, A036564, A036569, A055875, A055876, A361506, A361507.

Programs

Mathematica

A108870[n_]:=Ceiling[(9(9/4)^n-4)/5];Array[A108870,50,0] (* Paolo Xausa, Dec 02 2023 *)

Extensions

Edited by N. J. A. Sloane, Mar 20 2023 at the suggestion of Don Knuth.