A108870 -id:A108870 - 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

A361506 a(n) = floor( (4/5)*( (9/4)^(n+1)-1 ) ).

Original entry on oeis.org

1, 3, 8, 19, 45, 102, 232, 524, 1181, 2659, 5984, 13466, 30300, 68177, 153400, 345151, 776590, 1747330, 3931495, 8845865, 19903197, 44782195, 100759939, 226709865, 510097199, 1147718699, 2582367075, 5810325919, 13073233320, 29414774972, 66183243689, 148912298302

Offset: 0

N. J. A. Sloane, Mar 20 2023, at the suggestion of Don Knuth

nonn

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

Marcin Ciura, Best Increments for the Average Case of Shellsort, 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.

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

A361506[n_]:=Floor[4/5((9/4)^(n+1)-1)];Array[A361506,50,0] (* Paolo Xausa, Dec 02 2023 *)

Some terms corrected by Paolo Xausa, Dec 02 2023

A361507 a(0) = 1; thereafter a(n) = floor((9/4)*a(n-1)) + 1.

Original entry on oeis.org

1, 3, 7, 16, 37, 84, 190, 428, 964, 2170, 4883, 10987, 24721, 55623, 125152, 281593, 633585, 1425567, 3207526, 7216934, 16238102, 36535730, 82205393, 184962135, 416164804, 936370810, 2106834323, 4740377227, 10665848761, 23998159713, 53995859355, 121490683549, 273354037986, 615046585469, 1383854817306, 3113673338939

Offset: 0

N. J. A. Sloane, Mar 20 2023, following a suggestion from Don Knuth

nonn

N. Tokuda, An efficient Shell's method of sorting by generalized scheme, Department of Computer Science, Utunomiya University, 1989; 10 pages plus 9 unnumbered pages of tables and charts.

Paolo Xausa, Table of n, a(n) for n = 0..1000

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

NestList[Floor[9/4#]+1&,1,50] (* Paolo Xausa, Dec 02 2023 *)

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.

A366726 Lee's empirically improved Tokuda gaps for shellsort.

Original entry on oeis.org

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

Stephen J. Chick, Oct 17 2023

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...

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

Cf. A108870.

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

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

A361506 a(n) = floor( (4/5)*( (9/4)^(n+1)-1 ) ).

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Extensions

A361507 a(0) = 1; thereafter a(n) = floor((9/4)*a(n-1)) + 1.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

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

A366726 Lee's empirically improved Tokuda gaps for shellsort.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula