cp's OEIS Frontend

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

%I A347403 #34 Nov 11 2021 09:41:12
%S A347403 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,
%T A347403 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,
%U A347403 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
%N A347403 Step at which n is removed by the sieve of Eratosthenes or 0 if n is prime.
%C A347403 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.
%C A347403 For all primes p, and k > 1: a(p^k) = PrimePi(p)+1 and a(i) < PrimePi(p)+1 for i < p^2.
%H A347403 Nicola De Mitri, <a href="/A347403/b347403.txt">Table of n, a(n) for n = 1..15000</a>
%F A347403 a(n) = f(A063918(n)) where f(0) = 0 and f(m) = A036234(m) for m > 0.
%F A347403 a(n) = 0 if n is prime, else A000720(A020639(n))+1. - _Michael S. Branicky_, Aug 31 2021
%t A347403 {1}~Join~Array[If[PrimeQ[#], 0, PrimePi@ FactorInteger[#][[-1, 1]]] &, 104, 2] (* _Michael De Vlieger_, Sep 01 2021 *)
%o A347403 (Python)
%o A347403 UPPER = 1000
%o A347403 number_to_step = [float("NaN"), 1] + [0 for _ in range(2, UPPER+1)]
%o A347403 curstep = 1
%o A347403 for sieve_val in range(2, int(UPPER**.5) + 1):
%o A347403     if number_to_step[sieve_val]:
%o A347403         continue
%o A347403     curstep += 1
%o A347403     for j in range(2*sieve_val, UPPER + 1, sieve_val):
%o A347403         if not number_to_step[j]:
%o A347403             number_to_step[j] = curstep
%o A347403 def A347403(n):
%o A347403     return number_to_step[n]
%o A347403 (Python)
%o A347403 from sympy import isprime, primepi, primefactors
%o A347403 def a(n):
%o A347403     return 0 if isprime(n) else primepi(min(primefactors(n), default=0)) + 1
%o A347403 print([a(n) for n in range(1, 128)]) # _Michael S. Branicky_, Aug 31 2021
%Y A347403 Cf. A036234, A063918, A055396.
%K A347403 nonn
%O A347403 1,4
%A A347403 _Nicola De Mitri_, Aug 30 2021