|
%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
|
