A394450 - OEIS

%I #10 Mar 28 2026 20:35:34

%S 2,3,7,11,17,19,31,41,43,53,67,79,83,97,101,107,131,139,163,173,191,

%T 193,199,211,227,229,241,257,271,277,313,331,337,349,353,389,401,409,

%U 421,439,457,461,479,521,541,547,563,577,587,599,601,641,653,661,673,683,709,739,757,773,797

%N Primes that survive the lucky number sieve when applied to the sequence of primes.

%C Apply the lucky number sieve to the sequence of primes (rather than to the positive integers). Start with the full prime sequence [2, 3, 5, 7, 11, 13, ...]. At each step k >= 1, let s_k be the current second element of the surviving sequence; remove every s_k-th term. The sequence consists of the primes that survive all steps.

%C This sequence is NOT the same as A031157 (numbers that are both lucky and prime). The lucky sieve applied to the primes uses the positional structure of the prime sequence, not the value structure of the integers, so different primes survive. For example, 11 is in this sequence (it survives the lucky sieve on primes) but 11 is not a lucky number. Conversely, 13 is a lucky prime (A031157) but does not survive the lucky sieve on primes.

%C The survival fraction among primes up to N decreases slowly: 73/168 = 43.5% for N=1000, 452/1229 = 36.8% for N=10000, 3129/9592 = 32.6% for N=100000. The asymptotic density among primes is an open question.

%C The sequence is a bridge between the prime sequence (A000040) and the lucky numbers (A000959): every term is prime (by construction), and the sieve rule is exactly the lucky number sieve.

%e Starting with primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, ...

%e Step 1: second element is 3; remove every 3rd prime (positions 3, 6, 9, ...): removes 5, 13, 23, 37, 47, ... Survivors: 2, 3, 7, 11, 17, 19, 29, 31, 41, 43, 53, 59, 67, ...

%e Step 2: second element is still 3; remove every 3rd survivor: removes 7, 19, 41, 59, ... Survivors: 2, 3, 11, 17, 29, 31, 43, 53, 67, 71, 83, 97, 107, ...

%e Step 3: second element is now 11; remove every 11th survivor: removes 83, 211, ... The process continues until the step size exceeds the sequence length.

%t luckySieveOnSeq[seq_] := Module[{s = seq, i = 2},

%t   While[i <= Length[s] && s[[i]] <= Length[s],

%t     s = Delete[s, Table[{j}, {j, s[[i]], Length[s], s[[i]]}]];

%t     i++];

%t   s];

%t luckySieveOnSeq[Prime[Range[200]]]

%o (Python)

%o from sympy import primerange

%o def lucky_sieve_on_primes(limit):

%o     s = list(primerange(limit+1))

%o     i = 1

%o     while i < len(s) and s[i] <= len(s):

%o         step = s[i]

%o         s = [s[j] for j in range(len(s)) if (j+1) % step != 0]

%o         i += 1

%o     return s

%o print(lucky_sieve_on_primes(1000))

%Y Cf. A000040 (primes), A000959 (lucky numbers), A031157 (lucky primes).

%K nonn

%O 1,1

%A _Nova Spivack_, Mar 20 2026