cp's OEIS Frontend

A079124 Number of ways to partition n into distinct positive integers <= phi(n), where phi is Euler's totient function (A000010).

%I A079124 #23 May 20 2023 12:11:30
%S A079124 1,1,0,1,0,2,0,4,1,5,1,11,0,17,4,13,13,37,2,53,13,51,35,103,10,135,78,
%T A079124 167,89,255,4,339,253,378,306,542,121,759,558,872,498,1259,121,1609,
%U A079124 1180,1677,1665,2589,808,3250,1969,3844,3325,5119,1850,6268,4758,7546,7070
%N A079124 Number of ways to partition n into distinct positive integers <= phi(n), where phi is Euler's totient function (A000010).
%D A079124 Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem, Mathematics and Computer Education, Vol. 31, No. 1, pp. 24-28, Winter 1997.  MathEduc Database (Zentralblatt MATH, 1997c.01891).
%H A079124 Alois P. Heinz, <a href="/A079124/b079124.txt">Table of n, a(n) for n = 0..10000</a>
%H A079124 Mohammad K. Azarian, <a href="https://web.archive.org/web/20100727063142/http://www.math-cs.ucmo.edu/~mjms/2004.1/azar6.pdf">A Generalization of the Climbing Stairs Problem II</a>, Missouri Journal of Mathematical Sciences, Vol. 16, No. 1, Winter 2004, pp. 12-17. Zentralblatt MATH, Zbl 1071.05501.
%F A079124 a(n) = b(0, n), b(m, n) = 1 + sum(b(i, j): m<i<j<phi(n) & i+j=n).
%p A079124 with(numtheory):
%p A079124 b:= proc(n, i) option remember; `if`(n=0, 1,
%p A079124       `if`(i<1, 0, b(n, i-1)+`if`(i>n, 0, b(n-i, i-1))))
%p A079124     end:
%p A079124 a:= n-> b(n, phi(n)):
%p A079124 seq(a(n), n=0..100);  # _Alois P. Heinz_, May 11 2015
%t A079124 b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, b[n, i-1] + If[i>n, 0, b[n-i, i-1]]]]; a[n_] := b[n, EulerPhi[n]]; Table[a[n], {n, 0, 100}] (* _Jean-François Alcover_, Jun 30 2015, after _Alois P. Heinz_ *)
%o A079124 (Haskell)
%o A079124 a079124 n = p [1 .. a000010 n] n where
%o A079124    p _      0 = 1
%o A079124    p []     _ = 0
%o A079124    p (k:ks) m = if m < k then 0 else p ks (m - k) + p ks m
%o A079124 -- _Reinhard Zumkeller_, Jul 05 2013
%Y A079124 Cf. A079126, A000009, A079122, A079125, A067953.
%Y A079124 Cf. A227296, A036998.
%K A079124 nonn
%O A079124 0,6
%A A079124 _Reinhard Zumkeller_, Dec 27 2002
%E A079124 a(0)=1 prepended by _Alois P. Heinz_, May 11 2015