A395082 - OEIS

A395082

a(n) is the number of partitions of n into distinct parts with sum of phi values equals phi(n).

1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 3, 6, 3, 1, 2, 1, 4, 10, 6, 1, 2, 10, 13, 13, 10, 1, 1, 1, 39, 36, 37, 44, 4, 1, 60, 61, 20, 1, 2, 1, 85, 133, 131, 1, 8, 40, 50, 242, 195, 1, 14, 223, 159, 417, 383, 1, 1, 1, 533, 758, 686, 495, 7, 1, 786, 1150, 41, 1

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

COMMENTS

Any valid partition of n has at most n - phi(n) + 1 parts (with equality only possible if 1 is a part). If we exclude 1 as a part, then at most n - phi(n) parts.

Equivalently, valid partitions S satisfy Sum_{k in S} A051953(k) = A051953(n).

We define A000010(0) = 0.

LINKS

Felix Huber, Table of n, a(n) for n = 0..500

FORMULA

Any valid partition of n has at most n - phi(n) + 1 parts (with equality only possible if 1 is a part).

Equivalently, valid partitions S satisfy Sum_{k in S} A051953(k) = A051953(n).

We define A000010(0) = 0.

EXAMPLE

a(3) = 2: [3], [1,2], since phi(3) = 2 and phi(1) + phi(2) = 1 + 1 = 2.

a(16) = 3: [16], [1,2,3,10], [1,2,3,4,6], since phi(16) = 8 and each listed partition has phi sum 8.

MAPLE

A395082 := proc(n)

local h, g, f;

h := proc(k) option remember; `if`(k <= 0, 0, NumberTheory:-phi(k)) end proc:

g := proc(k) option remember; `if`(k <= 0, 0, g(k - 1) + h(k)) end proc:

f := proc(i, j, k) option remember;

`if`(i = 0 and j = 0, 1, `if`(i < 0 or j < 0 or k = 0 or j > g(k), 0,

f(i, j, k - 1) + f(i - k, j - h(k), k - 1)))

end proc:

`if`(n = 0, 1, f(n, h(n), n))

end proc:

seq(A395082(n), n = 0 .. 71);

MATHEMATICA

a[n_]:=Count[Total/@EulerPhi[Select[IntegerPartitions[n], DuplicateFreeQ]], EulerPhi[n]]; a[0]=1; Array[a, 70, 0] (* James C. McMahon, May 05 2026 *)

CROSSREFS

Cf. A000009, A000010, A051953, A394248, A395091, A395096, A395097, A395111.

Sequence in context: A327168 A329037 A279794 * A025900 A118383 A115766

Adjacent sequences: A395079 A395080 A395081 * A395083 A395084 A395085

KEYWORD

nonn

AUTHOR

Felix Huber, Apr 27 2026

STATUS

approved