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
KEYWORD
nonn
AUTHOR
R. J. Mathar, Mar 10 2017
EXTENSIONS
a(56)-a(61) from Giovanni Resta, Mar 10 2017
STATUS
approved