cp's OEIS Frontend

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

%I A036567 #44 Dec 04 2023 19:04:27
%S A036567 1,3,7,16,41,101,247,613,1529,3821,9539,23843,59611,149015,372539,
%T A036567 931327,2328307,5820767,14551919,36379789,90949471,227373677,
%U A036567 568434193,1421085473,3552713687,8881784201,22204460497,55511151233,138777878081,346944695197,867361737989
%N A036567 Basic numbers used in Sedgewick-Incerpi upper bound for shell sort.
%D A036567 D. E. Knuth, The Art of Computer Programming, Vol. 3, Sorting and Searching, 2nd ed, section 5.2.1, p. 91.
%H A036567 Alois P. Heinz, <a href="/A036567/b036567.txt">Table of n, a(n) for n = 0..1000</a>
%H A036567 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 A036567 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 A036567 <a href="/index/So#sorting">Index entries for sequences related to sorting</a>
%F A036567 a(n) is the smallest number >= 2.5^n that is relatively prime to all previous terms in the sequence.
%e A036567 2.5^4 = 39.0625, and 41 is the next integer that is relatively prime to 1, 3, 7 and 16.
%p A036567 a:= proc(n) option remember; local l, m;
%p A036567       l:= [seq(a(i), i=1..n-1)];
%p A036567       for m from ceil((5/2)^n) while ormap(x-> igcd(m, x)>1, l) do od; m
%p A036567     end:
%p A036567 seq(a(n), n=0..30);  # _Alois P. Heinz_, Jan 06 2022
%t A036567 A036567[1] = 3;
%t A036567 A036567[q_] :=
%t A036567 With[{prev = A036567 /@ Range[q - 1]},
%t A036567   Block[{n = Ceiling[(5/2)^q]},
%t A036567    While[Nand @@ ((# == 1 &) /@ GCD[prev, n]), n++];
%t A036567    n]]; (* _Morgan Owens_, Oct 08 2020 *)
%t A036567 Array[A036567, 10]
%o A036567 (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 a036567(28) \\ _Hugo Pfoertner_, Oct 15 2020
%Y A036567 Cf. A003462, A033622, A036561, A036562, A036564, A036566, A036567, A036569, A055875, A055876, A102549, A108870, A112262, A112263, A154393, A204772, A205669, A205670, A361506, A361507.
%K A036567 nonn,easy
%O A036567 0,2
%A A036567 _N. J. A. Sloane_
%E A036567 Better description and more terms from _Jud McCranie_, Jan 05 2001
%E A036567 a(0)=1 prepended by _Alois P. Heinz_, Dec 04 2023