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

Author

N. J. A. Sloane

Keywords

• nonn

References

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

Links

• Robert Sedgewick, Analysis of shellsort and related algorithms, Fourth European Symposium on Algorithms, Barcelona, September, 1996.
• Index entries for sequences related to sorting

Crossrefs

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

Programs

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]

Formula

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