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

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

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

Example

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.

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 *)

Prog

(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

Crossrefs

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

Sequence in context: A199470 A098006 A336916 * A054875 A375111 A324115

Adjacent sequences: A082647 A082648 A082649 * A082651 A082652 A082653

Keyword

nonn

Author

Reinhard Zumkeller, May 16 2003

Status

approved