A051533 -id:A051533 - cp's OEIS frontend

A007294 Number of partitions of n into nonzero triangular numbers.

1, 1, 1, 2, 2, 2, 4, 4, 4, 6, 7, 7, 10, 11, 11, 15, 17, 17, 22, 24, 25, 32, 35, 36, 44, 48, 50, 60, 66, 68, 81, 89, 92, 107, 117, 121, 141, 153, 159, 181, 197, 205, 233, 252, 262, 295, 320, 332, 372, 401, 417, 465, 501, 520, 575, 619, 645, 710, 763

Offset: 0

N. J. A. Sloane, Mira Bernstein

nonn

Also number of decreasing integer sequences l(1) >= l(2) >= l(3) >= .. 0 such that sum('i*l(i)','i'=1..infinity)=n.
a(n) is also the number of partitions of n such that #{parts equal to i} >= #{parts equal to j} if i <= j.
Also the number of partitions of n (necessarily into distinct parts) where the part sizes are monotonically decreasing (including the last part, which is the difference between the last part and a "part" of size 0). These partitions are the conjugates of the partitions with number of parts of size i increasing. - Franklin T. Adams-Watters, Apr 08 2008
Also partitions with condition as in A179255, and additionally, if more than one part, first difference >= first part: for example, a(10)=7 as there are 7 such partitions of 10:  1+2+3+4 = 1+2+7 = 1+3+6 = 1+9 = 2+8 = 3+7 = 10. - Joerg Arndt, Mar 22 2011
Number of members of A181818 with a bigomega value of n (cf. A001222). - Matthew Vandermast, May 19 2012

			6 = 3+3 = 3+1+1+1 = 1+1+1+1+1+1 so a(6) = 4.
a(7)=4: Four sequences as above are (7,0,..), (5,1,0,..), (3,2,0,..),(2,1,1,0,..). They correspond to the partitions 1^7, 2 1^5, 2^2 1^3, 3 2 1^2 of seven or in the main description to the partitions 1^7, 3 1^4, 3^2 1, 6 1.
From _Gus Wiseman_, May 03 2019: (Start)
The a(1) = 1 through a(9) = 6 partitions using nonzero triangular numbers are the following. The Heinz numbers of these partitions are given by A325363.
  1   11   3     31     311     6        61        611        63
           111   1111   11111   33       331       3311       333
                                3111     31111     311111     6111
                                111111   1111111   11111111   33111
                                                              3111111
                                                              111111111
The a(1) = 1 through a(10) = 7 partitions with weakly decreasing multiplicities are the following. Equivalent to Matthew Vandermast's comment, the Heinz numbers of these partitions are given by A025487 (products of primorial numbers).
  1  11  21   211   2111   321     3211     32111     32211      4321
         111  1111  11111  2211    22111    221111    222111     322111
                           21111   211111   2111111   321111     2221111
                           111111  1111111  11111111  2211111    3211111
                                                      21111111   22111111
                                                      111111111  211111111
                                                                 1111111111
The a(1) = 1 through a(11) = 7 partitions with weakly increasing differences (where the last part is taken to be zero) are the following. The Heinz numbers of these partitions are given by A325362 (A = 10, B = 11).
  (1)  (2)  (3)   (4)   (5)   (6)    (7)    (8)    (9)    (A)     (B)
            (21)  (31)  (41)  (42)   (52)   (62)   (63)   (73)    (83)
                              (51)   (61)   (71)   (72)   (82)    (92)
                              (321)  (421)  (521)  (81)   (91)    (A1)
                                                   (531)  (631)   (731)
                                                   (621)  (721)   (821)
                                                          (4321)  (5321)
(End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe and Vaclav Kotesovec, Table of n, a(n) for n = 0..10000 (terms 0..1000 from T. D. Noe)
Gert Almkvist, Asymptotics of various partitions, arXiv:math/0612446 [math.NT], 2006.
G. E. Andrews, MacMahon's Partition Analysis II: Fundamental Theorems, Annals Combinatorics, 4 (2000), 327-338.
N. A. Brigham, A General Asymptotic Formula for Partition Functions, Proc. Amer. Math. Soc., vol. 1 (1950), p. 191.
Jorge A. Campos-Gonzalez-Angulo, Raphael F. Ribeiro, and Joel Yuen-Zhou, Generalization of the Tavis-Cummings model for multi-level anharmonic systems, arXiv:2101.09475 [physics.optics], 2021.
Zhicheng Gao, Andrew MacFie and Daniel Panario, Counting words by number of occurrences of some patterns, The Electronic Journal of Combinatorics, 18 (2011), #P143.
Igor Pak, Complexity problems in enumerative combinatorics, arXiv:1803.06636 [math.CO], 2018.
James A. Sellers, Partitions Excluding Specific Polygonal Numbers As Parts, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.4.
Jan Snellman and Michael Paulsen, Enumeration of Concave Integer Partitions, Journal of Integer Sequences, Vol. 7, 2004.
Gus Wiseman, Sequences counting and ranking integer partitions by the differences of their successive parts.

Cf. A000217, A051533, A000294.
Cf. A102462.
Row sums of array A176723 and triangle A176724. - Wolfdieter Lang, Jul 19 2010
Cf. A179255 (condition only on differences), A179269 (parts strictly increasing instead of nondecreasing). - Joerg Arndt, Mar 22 2011
Cf. A024940, A280366.
Row sums of A319797.
Cf. A007862, A025487, A240026, A320509, A325324, A325354, A325356, A325362, A325363.

a007294 = p $ tail a000217_list where
   p _      0 = 1
   p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m
-- Reinhard Zumkeller, Jun 28 2013

b:= proc(n,i) option remember;
      if n<0 then 0
    elif n=0 then 1
    elif i=0 then 0
    else b(n, i-1) +b(n-i*(i+1)/2, i)
      fi
    end:
a:= n-> b(n, floor(sqrt(2*n))):
seq(a(n), n=0..100);  # Alois P. Heinz, Mar 22 2011
isNondecrP :=proc(L) slp := DIFF(DIFF(L)) ; min(op(%)) >= 0 ; end proc:
A007294 := proc(n) local a, p; a := 0 ; if n = 0 then return 1 ; end if; for p in combinat[partition](n) do if nops(p) = nops(convert(p, set)) then if isNondecrP(p) then if nops(p) =1 then a := a+1 ; elif op(2, p) >= 2*op(1, p) then a := a+1; end if; end if; end if; end do; a ; end proc:
seq(A007294(n), n=0..30) ; # R. J. Mathar, Jan 07 2011

CoefficientList[ Series[ 1/Product[1 - x^(i(i + 1)/2), {i, 1, 50}], {x, 0, 70}], x]
(* also *)
t = Table[n (n + 1)/2, {n, 1, 200}] ; p[n_] := IntegerPartitions[n, All, t]; Table[p[n], {n, 0, 12}] (*shows partitions*)
a[n_] := Length@p@n; a /@Range[0, 80]
(* Clark Kimberling, Mar 09 2014 *)
b[n_, i_] := b[n, i] = Which[n < 0, 0, n == 0, 1, i == 0, 0, True, b[n, i-1]+b[n-i*(i+1)/2, i]]; a[n_] := b[n, Floor[Sqrt[2*n]]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Apr 09 2014, after Alois P. Heinz *)
Table[Length[Select[IntegerPartitions[n],OrderedQ[Differences[Append[#,0]]]&]],{n,0,30}] (* Gus Wiseman, May 03 2019 *)
nmax = 58; t = Table[PolygonalNumber[n], {n, nmax}];
Table[Count[IntegerPartitions@n, x_ /; SubsetQ[t, x]], {n, 0, nmax}] (* Robert Price, Aug 02 2020 *)

N=66; Vec(1/prod(k=1,N,1-x^(k*(k+1)\2))+O(x^N)) \\ Joerg Arndt, Apr 14 2013

from functools import lru_cache
from sympy import divisors
from sympy.ntheory.primetest import is_square
@lru_cache(maxsize=None)
def A007294(n):
    @lru_cache(maxsize=None)
    def a(n): return is_square((n<<3)+1)
    @lru_cache(maxsize=None)
    def c(n): return sum(d for d in divisors(n,generator=True) if a(d))
    return (c(n)+sum(c(k)*A007294(n-k) for k in range(1,n)))//n if n else 1 # Chai Wah Wu, Jul 15 2024

def A007294(n):
    has_nondecreasing_diffs = lambda x: min(differences(x, 2)) >= 0
    special = lambda x: (x[1]-x[0]) >= x[0]
    allowed = lambda x: (len(x) < 2 or special(x)) and (len(x) < 3 or has_nondecreasing_diffs(x))
    return len([1 for x in Partitions(n, max_slope=-1) if allowed(x[::-1])]) # D. S. McNeil, Jan 06 2011

G.f.: 1/Product_{k>=2} (1-z^binomial(k, 2)).
For n>0: a(n) = b(n, 1) where b(n, k) = if n>k*(k+1)/2 then b(n-k*(k+1)/2, k) + b(n, k+1) else (if n=k*(k+1)/2 then 1 else 0). - Reinhard Zumkeller, Aug 26 2003
For n>0, a(n) is Euler Transform of [1,0,1,0,0,1,0,0,0,1,0,0,0,0,1,...], i.e A010054, n>0. - Benedict W. J. Irwin, Jul 29 2016
a(n) ~ exp(3*Pi^(1/3) * Zeta(3/2)^(2/3) * n^(1/3) / 2) * Zeta(3/2) / (2^(7/2) * sqrt(3) * Pi * n^(3/2)) [Brigham 1950 (exponential part), Almkvist 2006]. - Vaclav Kotesovec, Dec 31 2016
G.f.: Sum_{i>=0} x^(i*(i+1)/2) / Product_{j=1..i} (1 - x^(j*(j+1)/2)). - Ilya Gutkovskiy, May 07 2017

Additional comments from Roland Bacher, Jun 17 2001

A020756 Numbers that are the sum of two triangular numbers.

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 7, 9, 10, 11, 12, 13, 15, 16, 18, 20, 21, 22, 24, 25, 27, 28, 29, 30, 31, 34, 36, 37, 38, 39, 42, 43, 45, 46, 48, 49, 51, 55, 56, 57, 58, 60, 61, 64, 65, 66, 67, 69, 70, 72, 73, 76, 78, 79, 81, 83, 84, 87, 88, 90, 91, 92, 93, 94, 97, 99, 100, 101, 102, 105, 106, 108

Offset: 1

David W. Wilson

The possible sums of a square and a promic, i.e., x^2+n(n+1), e.g., 3^2 + 2*3 = 9 + 6 = 15 is present. - Jon Perry, May 28 2003
A052343(a(n)) > 0; union of A118139 and A119345. - Reinhard Zumkeller, May 15 2006
Also union of A051533 and A000217. - Ant King, Nov 29 2010

T. D. Noe, Table of n, a(n) for n = 1..10000
John A. Ewell, On Sums of Triangular Numbers and Sums of Squares, The American Mathematical Monthly, 99:8 (October 1992), pp. 752-757.
T. Khovanova, K. Knop, and A. Radul, Baron Munchhausen's Sequence, J. Int. Seq. 13 (2010) # 10.8.7.
L. K. Mork, Keith Sullivan, Trenton Vogt, and Darin J. Ulness, A group theoretical approach to the partitioning of integers: Application to triangular numbers, squares, and centered polygonal numbers, Australasian J. Comb. (2021) Vol. 80, No. 3, 305-321.

Complement of A020757.
Cf. A051533 (sums of two positive triangular numbers), A001481 (sums of two squares), A002378, A000217.
Cf. A052343.

a020756 n = a020756_list !! (n-1)
a020756_list = filter ((> 0) . a052343) [0..]
-- Reinhard Zumkeller, Jul 25 2014

q[k_] := If[! Head[Reduce[m (m + 1) + n (n + 1) == 2 k && 0 <= m && 0 <= n, {m, n}, Integers]] === Symbol, k, {}]; DeleteCases[Table[q[i], {i, 0, 108}], {}] (* Ant King, Nov 29 2010 *)
Take[Union[Total/@Tuples[Accumulate[Range[0,20]],2]],80] (* Harvey P. Dale, May 02 2012 *)

v=vector(200); vc=0; for (x=0,10, for (y=0,10,v[vc++ ]=x^2+y*(y+1))); v=vecsort(v); v

is(n)=my(f=factor(4*n+1));for(i=1,#f~,if(f[i,1]%4==3 && f[i,2]%2, return(0))); 1 \\ Charles R Greathouse IV, Jul 05 2013

Numbers n such that 4n+1 is the sum of two squares, i.e. such that 4n+1 is in A001481. Hence n is a member if and only if 4n+1 = odd square * product of distinct primes of form 4k+1. (Fred Helenius and others, Dec 18 2004)
Equivalently, we may say that a positive integer n can be partitioned into a sum of two triangular numbers if and only if every 4 k + 3 prime factor in the canonical form of 4 n + 1 occurs with an even exponent. - Ant King, Nov 29 2010
Also, the values of n for which 8n+2 can be partitioned into a sum of two squares of natural numbers. - Ant King, Nov 29 2010
Closed under the operation f(x, y) = 4*x*y + x + y.

Entry revised by N. J. A. Sloane, Dec 20 2004

A053614 Numbers that are not the sum of distinct triangular numbers.

Original entry on oeis.org

2, 5, 8, 12, 23, 33

Offset: 1

Jud McCranie, Mar 19 2000

The Mathematica program first computes A024940, the number of partitions of n into distinct triangular numbers. Then it finds those n having zero such partitions. It appears that A024940 grows exponentially, which would preclude additional terms in this sequence. - T. D. Noe, Jul 24 2006, Jan 05 2009

			a(2) = 5: the 7 partitions of 5 are 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1. Among those the distinct ones are 5, 4+1, 3+2. None contains all distinct triangular numbers.
12 is a term as it is not a sum of 1, 3, 6 or 10 taken at most once.

Joe Roberts, Lure of the Integers, The Mathematical Association of America, 1992, page 184, entry 33.
David Wells in "The Penguin Dictionary of Curious and Interesting Numbers, Revised Edition, page 94, states that "33 is the largest number that is not the sum of distinct triangular numbers".

Shyam Sunder Gupta, Triangular Numbers, Exploring the Beauty of Fascinating Numbers, Springer (2025) Ch. 3, 83-125.

Cf. A025524 (number of numbers not the sum of distinct n-th-order polygonal numbers)
Cf. A007419 (largest number not the sum of distinct n-th-order polygonal numbers)
Cf. A001422, A121405 (corresponding sequences for square and pentagonal numbers)
Cf. A000217, A002243, A002244, A014134, A014156, A014158, A020757, A050941, A050942, A051611, A007294, A051533, A060773.

nn=100; t=Rest[CoefficientList[Series[Product[(1+x^(k*(k+1)/2)), {k,nn}], {x,0,nn(nn+1)/2}], x]]; Flatten[Position[t,0]] (* T. D. Noe, Jul 24 2006 *)

Complement of A061208.

Entry revised by N. J. A. Sloane, Jul 23 2006

A061336 Smallest number of triangular numbers which sum to n.

Original entry on oeis.org

0, 1, 2, 1, 2, 3, 1, 2, 3, 2, 1, 2, 2, 2, 3, 1, 2, 3, 2, 3, 2, 1, 2, 3, 2, 2, 3, 2, 1, 2, 2, 2, 3, 3, 2, 3, 1, 2, 2, 2, 3, 3, 2, 2, 3, 1, 2, 3, 2, 2, 3, 2, 3, 3, 3, 1, 2, 2, 2, 3, 2, 2, 3, 3, 2, 2, 1, 2, 3, 2, 2, 3, 2, 2, 3, 3, 2, 3, 1, 2, 3, 2, 3, 2, 2, 3, 3, 2, 2, 3, 2, 1, 2, 2, 2, 3, 3, 2, 3, 2, 2, 2, 2, 3, 3

Offset: 0

Henry Bottomley, Apr 25 2001

nonn

a(n)=3 if n=5 or 8 mod 9, since triangular numbers are {0,1,3,6} mod 9.
From Bernard Schott, Jul 16 2022: (Start)
In September 1636, Fermat, in a letter to Mersenne, made the statement that every number is a sum of at most three triangular numbers. This was proved by Gauss, who noted this event in his diary on July 10 1796 with the notation:
EYPHKA! num = DELTA + DELTA + DELTA (where Y is in fact the Greek letter Upsilon and DELTA is the Greek letter of that name).
This proof was published in his book Disquisitiones Arithmeticae, Leipzig, 1801. (End)

			a(3)=1 since 3=3, a(4)=2 since 4=1+3, a(5)=3 since 5=1+1+3, with 1 and 3 being triangular.

Elena Deza and Michel Marie Deza, Fermat's polygonal number theorem, Figurate numbers, World Scientific Publishing (2012), Chapter 5, pp. 313-377.
C. F. Gauss, Disquisitiones Arithmeticae, Yale University Press, 1966, New Haven and London, p. 342, art. 293.

Giovanni Resta, Table of n, a(n) for n = 0..10000
George E. Andrews, EYPHKA! num = Delta + Delta + Delta, J. Number Theory 23 (1986), 285-293.
Eric Weisstein's World of Mathematics, Fermat's Polygonal Number Theorem.

Cf. A000217, A007294, A057945, A061337, A051533, A020757.

Cf. A100878 (analog for A000326), A104246 (analog for A000292), A283365 (analog for A000332), A283370 (analog for A000389).

t[n_]:=n*(n+1)/2; a[0]=0; a[n_]:=Block[ {k=1, tt= t/@ Range[Sqrt[2*n]]}, Off[IntegerPartitions::take]; While[{} == IntegerPartitions[n, {k}, tt, 1], k++]; k]; a/@ Range[0, 104] (* Giovanni Resta, Jun 09 2015 *)

\\ see A283370 for generic code, working but not optimized for this case of triangular numbers. - M. F. Hasler, Mar 06 2017

a(n)=my(m=n%9,f); if(m==5 || m==8, return(3)); f=factor(4*n+1); for(i=1,#f~, if(f[i,2]%2 && f[i,1]%4==3, return(3))); if(ispolygonal(n,3), n>0, 2) \\ Charles R Greathouse IV, Mar 17 2022

a(n) = 0 if n=0, otherwise 1 if n is in A000217, otherwise 2 if n is in A051533, otherwise 3 in which case n is in A020757.

a(n) <= 3 (proposed by Fermat and proved by Gauss). - Bernard Schott, Jul 16 2022

A053604 Number of ways to write n as an ordered sum of 3 nonzero triangular numbers.

Original entry on oeis.org

0, 0, 0, 1, 0, 3, 0, 3, 3, 1, 6, 0, 6, 3, 6, 3, 3, 9, 1, 12, 0, 6, 9, 6, 6, 6, 9, 6, 12, 0, 10, 9, 12, 6, 9, 9, 3, 18, 3, 12, 12, 9, 9, 9, 12, 10, 12, 9, 9, 18, 6, 6, 27, 6, 12, 6, 9, 18, 15, 15, 6, 21, 9, 13, 12, 9, 18, 21, 9, 6, 21, 15, 15, 15, 12, 15, 18, 15, 9

Offset: 0

N. J. A. Sloane, Jan 20 2000

nonn

Fermat asserted that every number is the sum of three triangular numbers. This was proved by Gauss, who recorded in his Tagebuch entry for Jul 10 1796 that: EYPHEKA! num = DELTA + DELTA + DELTA.

Mel Nathanson, Additive Number Theory: The Classical Bases, Graduate Texts in Mathematics, Volume 165, Springer-Verlag, 1996. See Chapter 1.

T. D. Noe, Table of n, a(n) for n=0..5050

Cf. A000217, A007294, A051611, A051533, A053603, A008443, A002636.

nmax = 100; m0 = 10; A053604 :=
Table[a[n], {n, 0, nmax}]; Clear[counts];
counts[m_] :=
counts[m] = (Clear[a]; a[_] = 0;
   Do[s = i*(i + 1)/2 + j*(j + 1)/2 + k*(k + 1)/2;
    a[s] = a[s] + 1, {i, 1, m}, {j, 1, m}, {k, 1, m}];
   A053603); counts[m = m0]; counts[m = 2*m]; While[
counts[m] != counts[m/2], m = 2*m]; A053604  (* G. C. Greubel, Dec 24 2016 *)

G.f.: ( Sum_{k>=1} x^(k*(k+1)/2) )^3. - Ilya Gutkovskiy, Dec 24 2016

A053603 Number of ways to write n as an ordered sum of two nonzero triangular numbers.

Original entry on oeis.org

0, 0, 1, 0, 2, 0, 1, 2, 0, 2, 0, 2, 1, 2, 0, 0, 4, 0, 2, 0, 1, 2, 2, 0, 2, 2, 0, 2, 0, 2, 1, 4, 0, 0, 2, 0, 2, 2, 2, 2, 0, 0, 3, 2, 0, 0, 4, 0, 2, 2, 0, 4, 0, 0, 0, 2, 3, 2, 2, 0, 2, 2, 0, 0, 2, 2, 2, 2, 0, 2, 2, 0, 3, 2, 0, 0, 4, 0, 0, 2, 0, 6, 0, 2, 2, 0, 0, 2, 2, 0, 1, 2, 2

Offset: 0

N. J. A. Sloane, Jan 20 2000

nonn

a(A051611(n)) = 0; A051533(a(n)) > 0. - Reinhard Zumkeller, Jun 27 2013

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Cf. A000217, A007294, A051611, A051533, A052343-A052348, A053604.

Cf. A010054.

a053603 n = sum $ map (a010054 . (n -)) $
                  takeWhile (< n) $ tail a000217_list
-- Reinhard Zumkeller, Jun 27 2013

nmax = 100; m0 = 10; A053603 := Table[a[n], {n, 0, nmax}]; Clear[counts]; counts[m_] := counts[m] = (Clear[a]; a[A053603);%20counts%5Bm%20=%20m0%5D;%20counts%5Bm%20=%202*m%5D;%20While%5B%20counts%5Bm%5D%20!=%20counts%5Bm/2%5D,%20m%20=%202*m%5D;%20A053603%20(*%20_Jean-Fran%C3%A7ois%20Alcover">] = 0; Do[k = i*(i+1)/2 + j*(j+1)/2; a[k] = a[k]+1, {i, 1, m}, {j, 1, m}]; A053603); counts[m = m0]; counts[m = 2*m]; While[ counts[m] != counts[m/2], m = 2*m]; A053603 (* _Jean-François Alcover, Sep 05 2013 *)

istriang(n)={n>0 && issquare(8*n+1);}
a(n) = { my(t=1, ct=0, j=1); while (tJoerg Arndt, Sep 05 2013

G.f.: ( Sum_{k>=1} x^(k*(k+1)/2) )^2. - Ilya Gutkovskiy, Dec 24 2016

a(n) = Sum_{k=1..n-1} c(k) * c(n-k), where c(n) = A010054(n). - Wesley Ivan Hurt, Jan 06 2024

cp's OEIS Frontend

A007294 Number of partitions of n into nonzero triangular numbers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Sage

Formula

Extensions

A020756 Numbers that are the sum of two triangular numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Formula

Extensions

A053614 Numbers that are not the sum of distinct triangular numbers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A061336 Smallest number of triangular numbers which sum to n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A053604 Number of ways to write n as an ordered sum of 3 nonzero triangular numbers.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

A053603 Number of ways to write n as an ordered sum of two nonzero triangular numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell