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

2, 3, 7, 11, 17, 19, 31, 41, 43, 53, 67, 79, 83, 97, 101, 107, 131, 139, 163, 173, 191, 193, 199, 211, 227, 229, 241, 257, 271, 277, 313, 331, 337, 349, 353, 389, 401, 409, 421, 439, 457, 461, 479, 521, 541, 547, 563, 577, 587, 599, 601, 641, 653, 661, 673, 683, 709, 739, 757, 773, 797

Offset

1,1

Comments

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.

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.

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.

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.

Links

Table of n, a(n) for n=1..61.

Example

Starting with primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, ...
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, ...
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, ...
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.

Mathematica

luckySieveOnSeq[seq_] := Module[{s = seq, i = 2},
  While[i <= Length[s] && s[[i]] <= Length[s],
    s = Delete[s, Table[{j}, {j, s[[i]], Length[s], s[[i]]}]];
    i++];
  s];
luckySieveOnSeq[Prime[Range[200]]]

Prog

(Python)
from sympy import primerange
def lucky_sieve_on_primes(limit):
    s = list(primerange(limit+1))
    i = 1
    while i < len(s) and s[i] <= len(s):
        step = s[i]
        s = [s[j] for j in range(len(s)) if (j+1) % step != 0]
        i += 1
    return s
print(lucky_sieve_on_primes(1000))

Crossrefs

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

Sequence in context: A045323 A161185 A226993 * A235482 A375818 A155141

Adjacent sequences: A394447 A394448 A394449 * A394451 A394452 A394453

Keyword

nonn

Author

Nova Spivack, Mar 20 2026

Status

approved