login
A variation on the sieve of Eratosthenes (A000040): Start with the primes; the first term is 2, which is a(1) and we cross off every second prime starting with 2; the next prime not crossed off is 3, which is a(2) and we cross off every third prime starting with 3; the next prime not crossed off is 7, which is a(3) and we cross off every 7th prime starting with 7; and so on.
6

%I #24 Jul 01 2020 22:49:48

%S 2,3,7,13,29,37,53,79,89,107,113,139,151,173,181,223,239,251,311,317,

%T 349,359,383,397,421,463,491,503,541,577,593,613,619,647,659,683,743,

%U 787,821,857,863,887,911,983,997,1033,1061,1151,1163,1193,1213,1249

%N A variation on the sieve of Eratosthenes (A000040): Start with the primes; the first term is 2, which is a(1) and we cross off every second prime starting with 2; the next prime not crossed off is 3, which is a(2) and we cross off every third prime starting with 3; the next prime not crossed off is 7, which is a(3) and we cross off every 7th prime starting with 7; and so on.

%C In contrast to Flavius's sieve (A000960), primes are not erased when they are crossed off; that is, primes get crossed off multiple times (see A099362).

%H T. D. Noe, <a href="/A099361/b099361.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>

%H <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>

%e The first few sieving stages are as follows (X or XX indicates a prime that has been crossed off one or more times):

%e 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 ...

%e 2 3 X 7 XX 13 XX 19 XX 29 XX 37 XX 43 XX 53 XX 61 XX 71 XX 79 XX 89 XX ...

%e 2 3 X 7 XX 13 XX XX XX 29 XX 37 XX XX XX 53 XX 61 XX XX XX 79 XX 89 XX ...

%e 2 3 X 7 XX 13 XX XX XX 29 XX 37 XX XX XX 53 XX XX XX XX XX 79 XX 89 XX ...

%e .... Continue forever and the numbers not crossed off give the sequence.

%t nn=300; a=Prime[Range[nn]]; Do[p=a[[i]]; If[p>0, Do[a[[j]]=0, {j, i+p, nn, p}]], {i, nn}]; Rest[Union[a]] (* _T. D. Noe_, Nov 18 2004 *)

%Y Cf. A000040, A000960, A099204, A099207, A099243, A099362.

%Y Cf. A100424.

%K nonn,easy,nice

%O 1,1

%A _N. J. A. Sloane_, Nov 18 2004

%E More terms from _T. D. Noe_ and _Ray Chandler_, Nov 18 2004