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

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

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Examples

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

References

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

Links

• 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

Crossrefs

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

Programs

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]

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

Formula

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

Extensions

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

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