A385645 a(n) is the number of distinct sums of distinct prime powers dividing n.

1, 3, 3, 7, 3, 6, 3, 15, 7, 7, 3, 10, 3, 7, 7, 31, 3, 13, 3, 12, 7, 7, 3, 18, 7, 7, 15, 14, 3, 11, 3, 63, 7, 7, 7, 19, 3, 7, 7, 20, 3, 13, 3, 15, 14, 7, 3, 34, 7, 15, 7, 15, 3, 27, 7, 22, 7, 7, 3, 15, 3, 7, 14, 127, 7, 13, 3, 15, 7, 13, 3, 27, 3, 7, 15, 15, 7, 13

Offset: 1

Author

Felix Huber, Jul 11 2025

Keywords

• nonn
• easy

Examples

			The a(4) = 7 distinct sums of distinct prime powers dividing 4 are 1, 2, 4, 1 + 2, 1 + 4, 2 + 4 and 1 + 2 + 4.
		

Links

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

Crossrefs

Cf. A000040, A000961, A119347, A385646.

Programs

Maple

A385645:=proc(n)
    local b,k,l,i,j;
    l:=[1,seq(seq(i[1]^j,j=1..i[2]),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(A385645(n),n=1..78);

Formula

a(p) = 3 for prime p.

a(p^k) = A119347(p^k) for prime p and nonnegative integer k.

A385646(n) < a(n) <= A119347(n).