A036569 Increments used in Sedgewick-Incerpi upper bound for shell sort.

1, 3, 7, 21, 48, 112, 336, 861, 1968, 4592, 13776, 33936, 86961, 198768, 463792, 1391376, 3402672, 8382192, 21479367, 49095696, 114556624, 343669872, 852913488, 2085837936, 5138283696, 13166851971, 30095661648, 70223210512

Offset

0,2

References

D. E. Knuth, The Art of Computer Programming, Vol. 3, Sorting and Searching, 2nd ed, section 5.2.1, pp. 91-92.

Links

Table of n, a(n) for n=0..27.

Robert Sedgewick, Analysis of shellsort and related algorithms, Fourth European Symposium on Algorithms, Barcelona, September, 1996.

Index entries for sequences related to sorting

Formula

a(0)=1, then a(s)=a(s-r)*b(r) for r such that C(r, 2)<s<=C(r+1, 2), where b() is A036567.

Mathematica

A036569[k_] :=
With[{r = Floor[Sqrt[2 k + Sqrt[2 k]]]},
  With[{b = r (r + 1)/2 - k + 1},
   Times @@ (A036567 /@
      Select[Range[r], # != b &])]]; (* Morgan Owens, Oct 08 2020 *)
Array[A036569, 10]

Crossrefs

Sequences used for Shell sort: A003462, A033622, A036562, A036564, A036569, A055875.

Sequence in context: A018760 A050614 A181393 * A018303 A098545 A161707

Adjacent sequences: A036566 A036567 A036568 * A036570 A036571 A036572

Keyword

nonn

Author

N. J. A. Sloane

Status

approved