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

%I #28 Dec 03 2023 18:39:09

%S 1,4,9,20,46,103,233,525,1182,2660,5985,13467,30301,68178,153401,

%T 345152,776591,1747331,3931496,8845866,19903198,44782196,100759940,

%U 226709866,510097200,1147718700,2582367076,5810325920,13073233321,29414774973

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

%C The old definition was "Tokuda's good set of increments for Shell sort", but that seems to be false.

%C Adding 0, -1, -1, -1, ... to the terms gives A361506. For another version see A361507.

%D N. Tokuda, An Improved Shellsort, IFIP Transactions, A-12 (1992) 449-457.

%H Alois P. Heinz, <a href="/A108870/b108870.txt">Table of n, a(n) for n = 0..1000</a>

%H Marcin Ciura, <a href="https://doi.org/10.1007/3-540-44669-9_12">Best Increments for the Average Case of Shellsort</a>, 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.

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

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

%K easy,nonn

%O 0,2

%A _Jud McCranie_, Jul 13 2005

%E Edited by _N. J. A. Sloane_, Mar 20 2023 at the suggestion of _Don Knuth_.