A002960 The square sieve. (Formerly M1346)

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,1

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

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

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

Example

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 elements, 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 is the first element in the sequence and remove it
  3,5,6,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,...
Remove the 1,4,9,16th,... elements
  5,6,8,10,11,12,14,15,17,18,19,20,22,23,...
Return 5 as the next element in the sequence and remove it
  6,8,10,11,12,14,15,17,18,19,20,22,23,...
Remove the 1,4,9,16th,... elements
  8,10,12,14,15,17,19,20,22,23,...
Return 8 as the next element in the sequence and remove it
  10,12,14,15,17,19,20,22,23,...
Remove the 1,4,9,16th,... elements
  12,14,15,19,20,22,23,...
etc. - Sean A. Irvine, Dec 10 2014

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

Crossrefs

Cf A274089.

Sequence in context: A330188 A214047 A241566 * A022942 A183861 A024534

Adjacent sequences: A002957 A002958 A002959 * A002961 A002962 A002963

Keyword

nonn

Author

N. J. A. Sloane

Status

approved