login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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: 106-117.

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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 27 08:27 EDT 2017. Contains 284146 sequences.