cp's OEIS Frontend

A161510 Number of primes formed as the sum of distinct divisors of n, counted with repetition.

%I A161510 #9 Jul 24 2025 10:53:18
%S A161510 0,2,1,4,1,6,1,6,2,7,1,20,1,5,4,11,1,16,1,19,5,5,1,66,2,5,4,17,1,64,1,
%T A161510 18,4,6,6,120,1,5,5,63,1,62,1,18,11,5,1,237,1,15,3,18,1,47,6,60,5,7,1,
%U A161510 863,1,3,20,31,6,58,1,16,3,62,1,808,1,4,13,16,4,56,1,216,5,5,1,839,5,5
%N A161510 Number of primes formed as the sum of distinct divisors of n, counted with repetition.
%C A161510 That is, if a number has d divisors, then we compute all 2^d sums of distinct divisors and count how many primes are formed. Sequence A093893 lists the n that produce no primes except for the primes that divide n. The Mathematica code works well for numbers up to about 221760, which has 168 divisors and creates a polynomial of degree 950976. The coefficients of the prime powers of that polynomial sum to 28719307224839120896278355000770621322645671888269, the number of primes formed by the divisors of 221760. Records appear to occur at n=10 and n in A002182, the highly composite numbers.
%H A161510 Felix Huber, <a href="/A161510/b161510.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from T. D. Noe)
%e A161510 a(4) = 4 because the divisors (1,2,4) produce 4 primes (2,1+2,1+4,1+2+4).
%p A161510 with(NumberTheory):
%p A161510 A161510:=proc(n)
%p A161510     local b,l,j;
%p A161510     l:=[(Divisors(n))[]]:
%p A161510     b:=proc(m,i)
%p A161510         option remember;
%p A161510         `if`(m=0,1,`if`(i<1,0,b(m,i-1)+`if`(l[i]>m,0,b(m-l[i],i-1))))
%p A161510     end;
%p A161510     add(b(ithprime(j),nops(l)),j=1..pi(sigma(n)));
%p A161510 end:
%p A161510 seq(A161510(n),n=1..77); # _Felix Huber_, Jul 24 2025
%t A161510 CountPrimes[n_] := Module[{d=Divisors[n],t,lim,x}, t=CoefficientList[Product[1+x^d[[i]], {i,Length[d]}], x]; lim=PrimePi[Length[t]-1]; Plus@@t[[1+Prime[Range[lim]]]]]; Table[CountPrimes[n], {n,100}]
%o A161510 (PARI) a(n) = my(nb=0, d=divisors(n)); forsubset(#d, s, nb+=isprime(sum(i=1, #s, d[s[i]]))); nb; \\ _Michel Marcus_, Jul 24 2025
%K A161510 nonn
%O A161510 1,2
%A A161510 _T. D. Noe_, Jun 17 2009