A002960 The square sieve.

2, 5, 8, 12, 17, 22, 28, 34, 41, 48, 56, 65, 74, 84, 94, 105, 116, 128, 140, 153, 166, 180, 194, 209, 224, 240, 257, 274, 292, 310, 329, 348, 368, 388, 409, 430, 452, 474, 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

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

Comments

See example for the construction used.

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

Examples

			Start with
  1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,...
Remove all square-th terms, 1,4,9,16,... to get
  2,3,5,6,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,...
Return 2 as the first term in the sequence and remove it to get
  3,5,6,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,...
Remove the 1st,4th,9th,16th,... terms to get
  5,6,8,10,11,12,14,15,17,18,19,20,22,23,...
Return 5 as the next term in the sequence and remove it to get
  6,8,10,11,12,14,15,17,18,19,20,22,23,...
Remove the 1st,4th,9th,16th,... terms to get
  8,10,12,14,15,17,19,20,22,23,...
Return 8 as the next term in the sequence and remove it to get
  10,12,14,15,17,19,20,22,23,...
Remove the 1st,4th,9th,16th,... terms to get
  12,14,15,19,20,22,23,...
etc. - _Sean A. Irvine_, Dec 10 2014
		

References

• David L. Silverman, Problem #116, The Square Sieve, J. Rec. Math., 4 (1971), 288-289.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Sean A. Irvine, Table of n, a(n) for n = 1..1000
• Index entries for sequences generated by sieves

Crossrefs

Cf A274089.

Programs

Maple

sieve:= L -> subsop(seq(i^2=NULL, i=1..floor(sqrt(nops(L)))),L):
A:= [$1..10^5]:
for n from 1 do
  A:= sieve(A);
  if nops(A) = 0 then break fi;
  R[n]:= A[1];
  A:= subsop(1=NULL,A);
od:
seq(R[i],i=1..n-1); # Robert Israel, Dec 11 2014

Mathematica

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 *)

Formula

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

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