A385646 a(n) is the number of distinct sums of distinct prime factors of n.

0, 1, 1, 1, 1, 3, 1, 1, 1, 3, 1, 3, 1, 3, 3, 1, 1, 3, 1, 3, 3, 3, 1, 3, 1, 3, 1, 3, 1, 6, 1, 1, 3, 3, 3, 3, 1, 3, 3, 3, 1, 7, 1, 3, 3, 3, 1, 3, 1, 3, 3, 3, 1, 3, 3, 3, 3, 3, 1, 6, 1, 3, 3, 1, 3, 7, 1, 3, 3, 6, 1, 3, 1, 3, 3, 3, 3, 7, 1, 3, 1, 3, 1, 7, 3, 3, 3, 3

Offset: 1

Author

Felix Huber, Jul 11 2025

Keywords

• nonn
• easy

Examples

			The a(18) = 3 distinct sums of distinct prime factors of 18 = 2*3^2 are 2, 3 and 2 + 3.
The a(42) = 7 distinct sums of distinct prime factors of 42 = 2*3*7 are 2, 3, 7, 2 + 3 = 5, 2 + 7 = 9, 3 + 7 = 10, 2 + 3 + 7 = 12.
The a(30) = 6 distinct sums of distinct prime factors of 30 = 2*3*5 are 2, 3, 2 + 3 = 5, 2 + 5 = 7, 3 + 5 = 8, 2 + 3 + 5 = 10.
		

Links

• Felix Huber, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000040, A001221, A119347, A385645.

Programs

Maple

A385646:=proc(n)
    local b,k,l,i,j;
    l:=[seq(i[1],i in ifactors(n)[2])]:
    b:=proc(m,i)
        option remember;
        `if`(m=0,1,`if`(i<1,0,b(m,i-1)+`if`(l[i]>m,0,b(m-l[i],i-1))))
    end;
    return nops(select(x->x>0,[seq(b(k,nops(l)),k=1..add(l))]))
    end:
seq(A385646(n),n=1..85);

Formula

a(n) < A385646(n).