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

Author

R. J. Mathar, Mar 10 2017

Keywords

• nonn

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.

Examples

			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.
		

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.

Crossrefs

Cf. A000010, A271384, A283530.

Programs

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

Extensions

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