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

%I #44 Dec 04 2023 19:04:27

%S 1,3,7,16,41,101,247,613,1529,3821,9539,23843,59611,149015,372539,

%T 931327,2328307,5820767,14551919,36379789,90949471,227373677,

%U 568434193,1421085473,3552713687,8881784201,22204460497,55511151233,138777878081,346944695197,867361737989

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

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

%H Alois P. Heinz, <a href="/A036567/b036567.txt">Table of n, a(n) for n = 0..1000</a>

%H Janet Incerpi and Robert Sedgewick, <a href="https://doi.org/10.1016/0022-0000(85)90042-X">Improved upper bounds on shellsort</a>, Journal of Computer and System Sciences, Volume 31, Issue 2, October 1985, Pages 210-224

%H Robert Sedgewick, <a href="http://www.cs.princeton.edu/~rs/shell/paperF.pdf">Analysis of shellsort and related algorithms</a>, Fourth European Symposium on Algorithms, Barcelona, September, 1996.

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

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

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

%p a:= proc(n) option remember; local l, m;

%p l:= [seq(a(i), i=1..n-1)];

%p for m from ceil((5/2)^n) while ormap(x-> igcd(m, x)>1, l) do od; m

%p end:

%p seq(a(n), n=0..30); # _Alois P. Heinz_, Jan 06 2022

%t A036567[1] = 3;

%t A036567[q_] :=

%t With[{prev = A036567 /@ Range[q - 1]},

%t Block[{n = Ceiling[(5/2)^q]},

%t While[Nand @@ ((# == 1 &) /@ GCD[prev, n]), n++];

%t n]]; (* _Morgan Owens_, Oct 08 2020 *)

%t Array[A036567, 10]

%o (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};

%o a036567(28) \\ _Hugo Pfoertner_, Oct 15 2020

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

%K nonn,easy

%O 0,2

%A _N. J. A. Sloane_

%E Better description and more terms from _Jud McCranie_, Jan 05 2001

%E a(0)=1 prepended by _Alois P. Heinz_, Dec 04 2023