This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A033622 Good sequence of increments for Shell sort (best on big values). 9
 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,2 COMMENTS 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 REFERENCES 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 LINKS 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 linear recurrences with constant coefficients, signature (1, 6, -6, -8, 8). FORMULA 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 MAPLE 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 MATHEMATICA 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 *) PROG (C) int sedg(int i){ return (i%2) ? (9*(2<

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 20 12:43 EDT 2019. Contains 327238 sequences. (Running on oeis4.)