A093890 Number of primes arising as the sum of one or more divisors of n.

0, 2, 1, 4, 1, 5, 1, 6, 2, 7, 1, 9, 1, 5, 4, 11, 1, 12, 1, 13, 5, 5, 1, 17, 2, 5, 4, 16, 1, 20, 1, 18, 4, 6, 6, 24, 1, 5, 5, 24, 1, 24, 1, 18, 11, 5, 1, 30, 1, 15, 3, 18, 1, 30, 6, 30, 5, 7, 1, 39, 1, 3, 18, 31, 6, 34, 1, 16, 3, 34, 1, 44, 1, 4, 13, 16, 4, 39, 1, 42, 5, 5, 1, 48, 5, 5, 2, 41, 1, 51, 2

Offset: 1

Author

Amarnath Murthy, Apr 23 2004

Keywords

• nonn

Comments

a(2^n) = pi(2^(n+1)-1).

Except for n=3 and n=42, it appears that the records occur at the highly abundant numbers A002093. The record values appear to be pi(sigma(n)) for n in A002093, which means that these n are members of A093891. [T. D. Noe, Mar 19 2010]

Examples

			a(4) = 4, the divisors of 4 are 1, 2 and 4.
Primes arising are 2, 3 = 1 + 2, 5 = 1 + 4 and 7 = 1 + 2 + 4.
		

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A093891, A093892.

Cf. A161510 (primes counted with repetition). [T. D. Noe, Mar 19 2010]

Programs

Mathematica

Do[l = Subsets[Divisors[n]]; l = Union[Map[Plus @@ #&, l]]; Print[Length[Select[l, PrimeQ]]], {n, 100}] (* Ryan Propper, Jun 04 2006 *)
CountPrimes[n_] := Module[{d=Divisors[n],t,lim,x}, t=CoefficientList[Product[1+x^i, {i,d}], x]; lim=PrimePi[Length[t]-1]; Count[t[[1+Prime[Range[lim]]]], ?(#>0 &)]]; Table[CountPrimes[n], {n,100}] (* _T. D. Noe, Mar 19 2010 *)

Extensions

Corrected and extended by Ryan Propper, Jun 04 2006