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

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

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

Mathematica

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

Prog

(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

Crossrefs

Cf. A036234, A063918, A055396.

Sequence in context: A338271 A176866 A294614 * A063918 A271419 A278922

Adjacent sequences: A347400 A347401 A347402 * A347404 A347405 A347406

Keyword

nonn

Author

Nicola De Mitri, Aug 30 2021

Status

approved