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

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

Offset: 1

Author

Reinhard Zumkeller, May 16 2003

Keywords

• nonn

Examples

			For n=20, spf(20) = 2, and there are 8 primes of form 1+k*2: 1+1*2=3, 1+2*2=5,
1+3*2=7, 1+5*2=11, 1+6*2=13, 1+8*2=17, 1+9*2=19, therefore a(20) = 8.
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.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..16384
• Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537
• Index entries for sequences related to primes in arithmetic progressions

Crossrefs

Cf. A000720, A008578 (positions of 0's), A020639, A035096.

Programs

Mathematica

a[n_] := With[{spfn = FactorInteger[n][[1, 1]]}, Select[Range[n-1], PrimeQ[#] && IntegerQ[(#-1)/spfn]&] // Length];
Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Jan 13 2023 *)

PARI

A020639(n) = if(1==n,n,vecmin(factor(n)[, 1]));
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

Formula

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