cp's OEIS Frontend

A283528 The number of phi-partitions of n.

%I A283528 #26 Jan 05 2025 19:51:41
%S A283528 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,
%T A283528 9,0,10,460,1019,431,1308,13,11,842,2760,214,12,2,13,1418,5124,2977,
%U A283528 14,42,2021,720,17355,4997,15,70,21108,3674,40702,16907,16,1,17
%N A283528 The number of phi-partitions of n.
%C A283528 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.
%H A283528 Alois P. Heinz, <a href="/A283528/b283528.txt">Table of n, a(n) for n = 1..1000</a> (first 100 terms from Giovanni Resta)
%H A283528 P. Jones, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/29-4/jones.pdf">Phi-partitions</a>, Fib. Quart. 29 (4) (1991) 347-350.
%H A283528 C. Powell, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/34-3/powell.pdf">On the uniqueness of reduced phi-partitions</a>, Fib. Quart. 34 (3) (1996) 194-199.
%H A283528 J. Wang, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/31-4/wang.pdf">Reduced phi-partitions of positive integers</a>, Fib. Quart. 31 (4) (1993) 365-369.
%e A283528 a(7) = 3 counts the partitions 1+1+1+1+1+2 = 1+1+1+1+3 = 1+1+5.
%e A283528 a(8) = 4 counts the partitions 2+2+2+2 = 2+2+4 = 4+4 = 1+1+6.
%p A283528 A283528 := proc(n)
%p A283528     local a,k,phip ;
%p A283528     a := 0 ;
%p A283528     for k in combinat[partition](n) do
%p A283528         if nops(k) > 1 then
%p A283528             phip := add( numtheory[phi](p),p =k) ;
%p A283528             if phip = numtheory[phi](n) then
%p A283528                 a := a+1 ;
%p A283528             end if;
%p A283528         end if;
%p A283528     end do:
%p A283528     a ;
%p A283528 end proc:
%p A283528 # second Maple program:
%p A283528 with(numtheory):
%p A283528 b:= proc(n, m, i) option remember; `if`(n=0,
%p A283528       `if`(m=0, 1, 0), `if`(i<1 or m<0, 0, b(n, m, i-1)+
%p A283528       `if`(i>n, 0, b(n-i, m-phi(i), i))))
%p A283528     end:
%p A283528 a:= n-> b(n, phi(n), n)-1:
%p A283528 seq(a(n), n=1..70);  # _Alois P. Heinz_, Mar 10 2017
%t A283528 Table[ Length@ IntegerPartitions[n 10^7 + EulerPhi[n], {2, Infinity},
%t A283528 EulerPhi@ Range[n-1] + 10^7 Range[n-1]], {n, 60}] (* _Giovanni Resta_, Mar 10 2017 *)
%t A283528 b[n_, m_, i_] := b[n, m, i] = If[n == 0,
%t A283528      If[m == 0, 1, 0], If[i < 1 || m < 0, 0, b[n, m, i - 1] +
%t A283528      If[i > n, 0, b[n - i, m - EulerPhi[i], i]]]];
%t A283528 a[n_] := b[n, EulerPhi[n], n]-1;
%t A283528 Array[a, 70] (* _Jean-François Alcover_, Jun 01 2021, after _Alois P. Heinz_ *)
%Y A283528 Cf. A000010, A271384, A283530.
%K A283528 nonn
%O A283528 1,5
%A A283528 _R. J. Mathar_, Mar 10 2017
%E A283528 a(56)-a(61) from _Giovanni Resta_, Mar 10 2017