login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A036567 Basic numbers used in Sedgewick-Incerpi upper bound for shell sort. 3
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,2
REFERENCES
D. E. Knuth, The Art of Computer Programming, Vol. 3, Sorting and Searching, 2nd ed, section 5.2.1, p. 91.
LINKS
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.
FORMULA
a(n) is the smallest number >= 2.5^n that is relatively prime to all previous terms in the sequence.
EXAMPLE
2.5^4 = 39.0625, and 41 is the next integer that is relatively prime to 1, 3, 7 and 16.
MAPLE
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
MATHEMATICA
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]
PROG
(PARI) 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
CROSSREFS
Sequence in context: A029761 A009337 A323776 * A018023 A144977 A058300
KEYWORD
nonn,easy
AUTHOR
EXTENSIONS
Better description and more terms from Jud McCranie, Jan 05 2001
a(0)=1 prepended by Alois P. Heinz, Dec 04 2023
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 03:33 EDT 2024. Contains 370952 sequences. (Running on oeis4.)