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

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.

Mathematica

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

Crossrefs

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

Sequence in context: A144685 A109110 A366726 * A331942 A111587 A161221

Adjacent sequences: A108867 A108868 A108869 * A108871 A108872 A108873

Keyword

easy,nonn

Author

Jud McCranie, Jul 13 2005

Extensions

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

Status

approved