A002960 - OEIS

%I M1346 #67 May 03 2024 10:32:02

%S 2,5,8,12,17,22,28,34,41,48,56,65,74,84,94,105,116,128,140,153,166,

%T 180,194,209,224,240,257,274,292,310,329,348,368,388,409,430,452,474,

%U 497,520,544,568,593,618,644,670,697,724,752,780,809,838,868,898,929,960,992,1025,1058,1092,1126,1161,1196

%N The square sieve.

%C See example for the construction used.

%C Conjecture: The first differences are given by A274089 (omitting the first two terms 1 and 2). - _Alisa Ediger_, Jun 04 2016

%D David L. Silverman, Problem #116, The Square Sieve, J. Rec. Math., 4 (1971), 288-289.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Sean A. Irvine, <a href="/A002960/b002960.txt">Table of n, a(n) for n = 1..1000</a>

%H <a href="/index/Si#sieve">Index entries for sequences generated by sieves</a>

%F Conjecture: a(n) = a(n-1) + 1 + floor(sqrt(a(n-1) + 1 + floor(sqrt(a(n-1))))); a(1) = 2. - _Gionata Neri_, Jun 22 2015

%F Conjecture: a(n) = 2^(x-1)*(2^(x-1)+y-1) + floor((y+1)^2/4), where y = n+1+x-2^x and x = floor(log_2(n+1+floor(log_2(n)))). - _Gionata Neri_, Jul 05 2015

%e Start with

%e   1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,...

%e Remove all square-th terms, 1,4,9,16,... to get

%e   2,3,5,6,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,...

%e Return 2 as the first term in the sequence and remove it to get

%e   3,5,6,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,...

%e Remove the 1st,4th,9th,16th,... terms to get

%e   5,6,8,10,11,12,14,15,17,18,19,20,22,23,...

%e Return 5 as the next term in the sequence and remove it to get

%e   6,8,10,11,12,14,15,17,18,19,20,22,23,...

%e Remove the 1st,4th,9th,16th,... terms to get

%e   8,10,12,14,15,17,19,20,22,23,...

%e Return 8 as the next term in the sequence and remove it to get

%e   10,12,14,15,17,19,20,22,23,...

%e Remove the 1st,4th,9th,16th,... terms to get

%e   12,14,15,19,20,22,23,...

%e etc. - _Sean A. Irvine_, Dec 10 2014

%p sieve:= L -> subsop(seq(i^2=NULL, i=1..floor(sqrt(nops(L)))),L):

%p A:= [$1..10^5]:

%p for n from 1 do

%p   A:= sieve(A);

%p   if nops(A) = 0 then break fi;

%p   R[n]:= A[1];

%p   A:= subsop(1=NULL,A);

%p od:

%p seq(R[i],i=1..n-1); # _Robert Israel_, Dec 11 2014

%t First /@ NestWhileList[Function[w, {First@ #, Rest@ #} &@ Delete[Last@ w, #] &@ Map[{#} &, Reverse@ Range[Floor@ Sqrt@ Length[Last@ w]]^2]], {0, Range@ 1200}, Length@ Last@ # > 1 &] (* _Michael De Vlieger_, Jun 05 2016 *)

%Y Cf A274089.

%K nonn

%O 1,1

%A _N. J. A. Sloane_