cp's OEIS Frontend

A082650 Number of primes < n of form 1+k*spf(n), where spf(n) is the smallest prime factor of n (A020639).

%I A082650 #18 Jan 13 2023 10:36:05
%S A082650 0,0,0,1,0,2,0,3,1,3,0,4,0,5,2,5,0,6,0,7,3,7,0,8,1,8,3,8,0,9,0,10,4,
%T A082650 10,2,10,0,11,5,11,0,12,0,13,6,13,0,14,2,14,6,14,0,15,3,15,6,15,0,16,
%U A082650 0,17,7,17,4,17,0,18,8,18,0,19,0,20,9,20,3,20,0,21,10,21,0,22,5,22,10,22,0
%N A082650 Number of primes < n of form 1+k*spf(n), where spf(n) is the smallest prime factor of n (A020639).
%H A082650 Antti Karttunen, <a href="/A082650/b082650.txt">Table of n, a(n) for n = 1..16384</a>
%H A082650 Antti Karttunen, <a href="/A082650/a082650.txt">Data supplement: n, a(n) computed for n = 1..65537</a>
%H A082650 <a href="/index/Pri#primes_AP">Index entries for sequences related to primes in arithmetic progressions</a>
%F A082650 a(2*n) = A000720(2*n)-1; a(n)=0 iff n=1 or n prime, i.e., a(A008578(n)) = 0. - _Reinhard Zumkeller_, Sep 11 2003, typo corrected by _Antti Karttunen_, Apr 03 2022
%e A082650 For n=20, spf(20) = 2, and there are 8 primes of form 1+k*2: 1+1*2=3, 1+2*2=5,
%e A082650 1+3*2=7, 1+5*2=11, 1+6*2=13, 1+8*2=17, 1+9*2=19, therefore a(20) = 8.
%e A082650 For n=21, spf(21) = 3, and there are 3 primes of form 1+k*3: 1+2*3=7, 1+4*3=13, 1+6*3=19, therefore a(21) = 3.
%t A082650 a[n_] := With[{spfn = FactorInteger[n][[1, 1]]}, Select[Range[n-1], PrimeQ[#] && IntegerQ[(#-1)/spfn]&] // Length];
%t A082650 Table[a[n], {n, 1, 100}] (* _Jean-François Alcover_, Jan 13 2023 *)
%o A082650 (PARI)
%o A082650 A020639(n) = if(1==n,n,vecmin(factor(n)[, 1]));
%o A082650 A082650(n) = { my(spf=A020639(n), s=0); forprime(p=(1+spf),n-1,if(!((p-1)%spf),s++)); (s); }; \\ _Antti Karttunen_, Apr 03 2022
%Y A082650 Cf. A000720, A008578 (positions of 0's), A020639, A035096.
%K A082650 nonn
%O A082650 1,6
%A A082650 _Reinhard Zumkeller_, May 16 2003