A283528 The number of phi-partitions of n.

0, 0, 1, 1, 2, 0, 3, 4, 8, 2, 4, 1, 5, 8, 24, 24, 6, 2, 7, 15, 107, 46, 8, 4, 135, 101, 347, 83, 9, 0, 10, 460, 1019, 431, 1308, 13, 11, 842, 2760, 214, 12, 2, 13, 1418, 5124, 2977, 14, 42, 2021, 720, 17355, 4997, 15, 70, 21108, 3674, 40702, 16907, 16, 1, 17

Offset

1,5

Comments

The number of partitions n = a1+a2+...+ak which have at least two parts and obey phi(n) = phi(a1)+phi(a2)+...+phi(ak). phi(.) = A000010(.) is Euler's totient. The trivial result with one part, n=a1, is not counted; that would induce another sequence with terms a(n)+1.

Links

Alois P. Heinz, Table of n, a(n) for n = 1..1000 (first 100 terms from Giovanni Resta)

P. Jones, Phi-partitions, Fib. Quart. 29 (4) (1991) 347-350.

C. Powell, On the uniqueness of reduced phi-partitions, Fib. Quart. 34 (3) (1996) 194-199.

J. Wang, Reduced phi-partitions of positive integers, Fib. Quart. 31 (4) (1993) 365-369.

Example

a(7) = 3 counts the partitions 1+1+1+1+1+2 = 1+1+1+1+3 = 1+1+5.
a(8) = 4 counts the partitions 2+2+2+2 = 2+2+4 = 4+4 = 1+1+6.

Maple

A283528 := proc(n)
    local a, k, phip ;
    a := 0 ;
    for k in combinat[partition](n) do
        if nops(k) > 1 then
            phip := add( numtheory[phi](p), p =k) ;
            if phip = numtheory[phi](n) then
                a := a+1 ;
            end if;
        end if;
    end do:
    a ;
end proc:
# second Maple program:
with(numtheory):
b:= proc(n, m, i) option remember; `if`(n=0,
      `if`(m=0, 1, 0), `if`(i<1 or m<0, 0, b(n, m, i-1)+
      `if`(i>n, 0, b(n-i, m-phi(i), i))))
    end:
a:= n-> b(n, phi(n), n)-1:
seq(a(n), n=1..70);  # Alois P. Heinz, Mar 10 2017

Mathematica

Table[ Length@ IntegerPartitions[n 10^7 + EulerPhi[n], {2, Infinity},
EulerPhi@ Range[n-1] + 10^7 Range[n-1]], {n, 60}] (* Giovanni Resta, Mar 10 2017 *)
b[n_, m_, i_] := b[n, m, i] = If[n == 0,
     If[m == 0, 1, 0], If[i < 1 || m < 0, 0, b[n, m, i - 1] +
     If[i > n, 0, b[n - i, m - EulerPhi[i], i]]]];
a[n_] := b[n, EulerPhi[n], n]-1;
Array[a, 70] (* Jean-François Alcover, Jun 01 2021, after Alois P. Heinz *)

Crossrefs

Cf. A000010, A271384, A283530.

Sequence in context: A257136 A344059 A258871 * A336972 A110990 A254213

Adjacent sequences: A283525 A283526 A283527 * A283529 A283530 A283531

Keyword

nonn

Author

R. J. Mathar, Mar 10 2017

Extensions

a(56)-a(61) from Giovanni Resta, Mar 10 2017

Status

approved