A347403 Step at which n is removed by the sieve of Eratosthenes or 0 if n is prime.

1, 0, 0, 2, 0, 2, 0, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 4, 2, 3, 2, 0, 2, 0, 2, 3, 2, 4, 2, 0, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 2, 4, 2, 3, 2, 0, 2, 0, 2, 3, 2, 4, 2, 0, 2, 3, 2, 0, 2, 0, 2, 3, 2, 5, 2, 0, 2, 3, 2, 0, 2, 4, 2, 3, 2, 0, 2, 5, 2, 3, 2, 4, 2, 0, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 4, 2, 3, 2, 5, 2, 6, 2, 3, 2, 4, 2, 0

Offset: 1

Author

Nicola De Mitri, Aug 30 2021

Keywords

• nonn

Comments

Here, 1 is removed by the sieve at step 1 (a(1) = 1); all even numbers greater than 2 are removed at step 2 (a(2*n) = 2 for n>1); all multiples of 3 greater than 3, that have not been already removed (i.e., all odd multiples of 3), are removed at step 3; and so on (each time removing multiples of the next number not yet removed). Prime numbers are never removed and are assigned the default value of 0.

For all primes p, and k > 1: a(p^k) = PrimePi(p)+1 and a(i) < PrimePi(p)+1 for i < p^2.

Links

• Nicola De Mitri, Table of n, a(n) for n = 1..15000

Crossrefs

Cf. A036234, A063918, A055396.

Programs

Mathematica

{1}~Join~Array[If[PrimeQ[#], 0, PrimePi@ FactorInteger[#][[-1, 1]]] &, 104, 2] (* Michael De Vlieger, Sep 01 2021 *)

Python

UPPER = 1000
number_to_step = [float("NaN"), 1] + [0 for _ in range(2, UPPER+1)]
curstep = 1
for sieve_val in range(2, int(UPPER**.5) + 1):
    if number_to_step[sieve_val]:
        continue
    curstep += 1
    for j in range(2*sieve_val, UPPER + 1, sieve_val):
        if not number_to_step[j]:
            number_to_step[j] = curstep
def A347403(n):
    return number_to_step[n]

Python

from sympy import isprime, primepi, primefactors
def a(n):
    return 0 if isprime(n) else primepi(min(primefactors(n), default=0)) + 1
print([a(n) for n in range(1, 128)]) # Michael S. Branicky, Aug 31 2021

Formula

a(n) = f(A063918(n)) where f(0) = 0 and f(m) = A036234(m) for m > 0.

a(n) = 0 if n is prime, else A000720(A020639(n))+1. - Michael S. Branicky, Aug 31 2021