%I #42 Mar 20 2024 15:44:55

%S 1,5,19,41,109,209,505,929,2161,3905,8929,16001,36289,64769,146305,

%T 260609,587521,1045505,2354689,4188161,9427969,16764929,37730305,

%U 67084289,150958081,268386305,603906049,1073643521,2415771649,4294770689,9663381505,17179475969

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

%C 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

%D J. Incerpi, R. Sedgewick, "Improved Upper Bounds for Shellsort", J. Computer and System Sciences 31, 2, 1985. - _Roman Dovgopol_, May 08 2011

%D D. E. Knuth, The Art of Computer Programming, Vol. 3, Sorting and Searching, 2nd ed, section 5.2. 1.

%D R. Sedgewick, J. Algorithms 7 (1986), 159-173 Addison-Wesley. ISBN 0-201-06672-6. - _Roman Dovgopol_, May 08 2011

%H Nathaniel Johnston, <a href="/A033622/b033622.txt">Table of n, a(n) for n = 0..1000</a>

%H Frank Ellermann, <a href="http://www.xyzzy.claranet.de/rexxsort.htm#TESTS">Comparison of Shell sorts based on EIS sequences</a>. [broken link]

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Shellsort">Shellsort</a>

%H <a href="/index/So#sorting">Index entries for sequences related to sorting</a>

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (1, 6, -6, -8, 8).

%F a(n) = 9*2^n - 9*2^(n/2) + 1 if n is even;

%F a(n) = 8*2^n - 6*2^((n+1)/2) + 1 if n is odd.

%F 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

%F 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

%p 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

%t 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 *)

%o (C) int sedg(int i){ return (i%2) ? (9*(2<<i)-9*(2<<(i/2))+1) : (8*(2<<i)-6*(2<<((i+1)/2))+1); } /* _Roman Dovgopol_, May 08 2011 */

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

%K nonn,easy

%O 0,2

%A _Jud McCranie_