A102549 -id:A102549 - cp's OEIS frontend

A033622 Good sequence of increments for Shell sort (best on big values).

1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929, 16001, 36289, 64769, 146305, 260609, 587521, 1045505, 2354689, 4188161, 9427969, 16764929, 37730305, 67084289, 150958081, 268386305, 603906049, 1073643521, 2415771649, 4294770689, 9663381505, 17179475969

Offset: 0

Jud McCranie

One of the best sequences of gaps' lengths for Shell sort. Giving asymptotic O(N^(4/3)), therefore it is efficient in case of big N. On small values (approx. < 4000), it is better to use A108870 or A102549. - Roman Dovgopol, May 08 2011

J. Incerpi, R. Sedgewick, "Improved Upper Bounds for Shellsort", J. Computer and System Sciences 31, 2, 1985. - Roman Dovgopol, May 08 2011
D. E. Knuth, The Art of Computer Programming, Vol. 3, Sorting and Searching, 2nd ed, section 5.2. 1.
R. Sedgewick, J. Algorithms 7 (1986), 159-173 Addison-Wesley. ISBN 0-201-06672-6. - Roman Dovgopol, May 08 2011

Nathaniel Johnston, Table of n, a(n) for n = 0..1000
Frank Ellermann, Comparison of Shell sorts based on EIS sequences. [broken link]
Wikipedia, Shellsort
Index entries for sequences related to sorting
Index entries for linear recurrences with constant coefficients, signature (1, 6, -6, -8, 8).

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

int sedg(int i){ return (i%2) ? (9*(2<Roman Dovgopol, May 08 2011 */

A033622 := proc(n) return (9-(n mod 2))*2^n-(9-3*(n mod 2))*2^ceil(n/2)+1: end: seq(A033622(n),n=0..29); # Nathaniel Johnston, May 08 2011

Table[If[EvenQ[n],9*2^n-9*2^(n/2)+1,8*2^n-6*2^((n+1)/2)+1],{n,0,30}] (* or *) LinearRecurrence[{1,6,-6,-8,8},{1,5,19,41,109},30] (* Harvey P. Dale, Mar 02 2015 *)

a(n) = 9*2^n - 9*2^(n/2) + 1 if n is even;
a(n) = 8*2^n - 6*2^((n+1)/2) + 1 if n is odd.
G.f.: (8*x^4 + 2*x^3 - 8*x^2 - 4*x - 1)/((x-1)*(2*x+1)*(2*x-1)*(2*x^2-1)). - Maksym Voznyy (voznyy(AT)mail.ru), Aug 11 2009
a(0)=1, a(1)=5, a(2)=19, a(3)=41, a(4)=109, a(n)=a(n-1)+6*a(n-2)- 6*a(n-3)- 8*a(n-4)+8*a(n-5). - Harvey P. Dale, Mar 02 2015

A036567 Basic numbers used in Sedgewick-Incerpi upper bound for shell sort.

Original entry on oeis.org

1, 3, 7, 16, 41, 101, 247, 613, 1529, 3821, 9539, 23843, 59611, 149015, 372539, 931327, 2328307, 5820767, 14551919, 36379789, 90949471, 227373677, 568434193, 1421085473, 3552713687, 8881784201, 22204460497, 55511151233, 138777878081, 346944695197, 867361737989

Offset: 0

N. J. A. Sloane

			2.5^4 = 39.0625, and 41 is the next integer that is relatively prime to 1, 3, 7 and 16.

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

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Janet Incerpi and Robert Sedgewick, Improved upper bounds on shellsort, Journal of Computer and System Sciences, Volume 31, Issue 2, October 1985, Pages 210-224
Robert Sedgewick, Analysis of shellsort and related algorithms, Fourth European Symposium on Algorithms, Barcelona, September, 1996.
Index entries for sequences related to sorting

Cf. A003462, A033622, A036561, A036562, A036564, A036566, A036567, A036569, A055875, A055876, A102549, A108870, A112262, A112263, A154393, A204772, A205669, A205670, A361506, A361507.

a:= proc(n) option remember; local l, m;
      l:= [seq(a(i), i=1..n-1)];
      for m from ceil((5/2)^n) while ormap(x-> igcd(m, x)>1, l) do od; m
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Jan 06 2022

A036567[1] = 3;
A036567[q_] :=
With[{prev = A036567 /@ Range[q - 1]},
  Block[{n = Ceiling[(5/2)^q]},
   While[Nand @@ ((# == 1 &) /@ GCD[prev, n]), n++];
   n]]; (* Morgan Owens, Oct 08 2020 *)
Array[A036567, 10]

a036567(m)={my(v=vector(m)); for(n=1,m,my(b=ceil((5/2)^n));for(j=b,oo,my(g=1); for(k=1,n-1,if(gcd(j,v[k])>1,g=0;break));if(g,v[n]=j;break)));v};
a036567(28) \\ Hugo Pfoertner, Oct 15 2020

a(n) is the smallest number >= 2.5^n that is relatively prime to all previous terms in the sequence.

Better description and more terms from Jud McCranie, Jan 05 2001

a(0)=1 prepended by Alois P. Heinz, Dec 04 2023

A112262 A good sequence of gaps for Shellsort, found by genetic programming.

Original entry on oeis.org

1, 4, 9, 24, 58, 171, 340, 1097, 2673, 5467, 13353, 35957, 128823, 451488, 494198, 499871

Offset: 1

Jud McCranie, Aug 30 2005

The gaps were determined for a maximum length of the test arrays of 500000. - Hugo Pfoertner, Nov 04 2024

Gene Michael Stover, Improving Shellsort Through Evolution, 2002-2006. See Figure 2.

Cf. A033622, A102549, A108870, A112263.

A112263 A good sequence of gaps for Shellsort, found by genetic programming.

Original entry on oeis.org

1, 4, 13, 23, 61, 177, 444, 1325, 3716, 8186, 18168, 62025, 275360, 461299, 498201

Offset: 1

Jud McCranie, Aug 30 2005

The gaps were determined for a maximum length of the test arrays of 500000. - Hugo Pfoertner, Nov 04 2024

Gene Michael Stover, Improving Shellsort Through Evolution, 2002-2006. See Figure 2.

Cf. A033622, A102549, A108870.

Cf. A112262.

cp's OEIS Frontend

A033622 Good sequence of increments for Shell sort (best on big values).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

C

Maple

Mathematica

Formula

A036567 Basic numbers used in Sedgewick-Incerpi upper bound for shell sort.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A112262 A good sequence of gaps for Shellsort, found by genetic programming.

Views

Author

Keywords

Comments

Links

Crossrefs

A112263 A good sequence of gaps for Shellsort, found by genetic programming.

Views

Author

Keywords

Comments

Links

Crossrefs