A366726 Lee's empirically improved Tokuda gaps for shellsort.

1, 4, 9, 20, 45, 102, 230, 516, 1158, 2599, 5831, 13082, 29351, 65853, 147748, 331490, 743735, 1668650, 3743800, 8399623, 18845471, 42281871, 94863989, 212837706, 477524607, 1071378536, 2403754591, 5393085583, 12099975682, 27147615084, 60908635199, 136655165852

Offset

1,2

Comments

The gaps were found empirically using a generalization of the formula which generates Tokuda's good gaps (A108870). These are a noticeable improvement over Tokuda's sequence when sorting random data, especially where N is in the millions.

The specific gamma = 2.243609061420001 is used to generate the present sequence. If one were to continue the search for a better gamma, the next best value lies within the range: 2.243609055217999... < gamma <= 2.243609061420001...

Links

Table of n, a(n) for n=1..32.

Ying Wai Lee, Empirically Improved Tokuda Gap Sequence in Shellsort, arXiv:2112.11112 [cs.DS], 2021.

Formula

a(n) = ceiling((gamma^n - 1)/(gamma - 1)), where gamma = 2.243609061420001

Crossrefs

Cf. A108870.

Sequence in context: A345192 A144685 A109110 * A108870 A331942 A111587

Adjacent sequences: A366723 A366724 A366725 * A366727 A366728 A366729

Keyword

easy,nonn

Author

Stephen J. Chick, Oct 17 2023

Status

approved