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

Author

Stephen J. Chick, Oct 17 2023

Keywords

• easy
• nonn

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

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

Crossrefs

Cf. A108870.

Formula

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