

A108870


Tokuda's good set of increments for Shell sort.


2



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Empirically better for the average running time than currently known sequences of increments, except A102549 (and only a few terms of that sequence are known).


REFERENCES

Marcin Ciura, Best Increments for the Average Case of Shellsort, 13th International Symposium on Fundamentals of Computation Theory, Riga, Latvia, Aug 22 2001; Lecture Notes in Computer Science 2001; 2138: 106117.
N. Tokuda, An Improved Shellsort, IFIP Transactions, A12 (1992) 449457.


LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Marcin Ciura, Best Increments for the Average Case of Shellsort


FORMULA

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


CROSSREFS

Other sequences used for Shell sort: A003462, A033622, A036562, A036564, A036569, A055875, A055876.
Sequence in context: A144686 A144685 A109110 * A111587 A161221 A130045
Adjacent sequences: A108867 A108868 A108869 * A108871 A108872 A108873


KEYWORD

easy,nonn


AUTHOR

Jud McCranie, Jul 13 2005


STATUS

approved



