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

Links

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

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

Example

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.

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

Crossrefs

Cf. A000040, A000961, A119347, A385646.

Sequence in context: A249382 A386543 A317929 * A285387 A100803 A036840

Adjacent sequences: A385642 A385643 A385644 * A385646 A385647 A385648

Keyword

nonn,easy

Author

Felix Huber, Jul 11 2025

Status

approved