A069918 -id:A069918 - cp's OEIS frontend

A025591 Maximal coefficient of Product_{k<=n} (1 + x^k). Number of solutions to +- 1 +- 2 +- 3 +- ... +- n = 0 or 1.

1, 1, 1, 2, 2, 3, 5, 8, 14, 23, 40, 70, 124, 221, 397, 722, 1314, 2410, 4441, 8220, 15272, 28460, 53222, 99820, 187692, 353743, 668273, 1265204, 2399784, 4559828, 8679280, 16547220, 31592878, 60400688, 115633260, 221653776, 425363952, 817175698

Offset: 0

David W. Wilson

If k is allowed to approach infinity, this gives the partition numbers A000009.

a(n) is the maximal number of subsets of {1,2,...,n} that share the same sum.

T. D. Noe, Alois P. Heinz and Ray Chandler, Table of n, a(n) for n = 0..3339 (terms < 10^1000, first 201 terms from T. D. Noe, next 200 terms from Alois P. Heinz)
Dorin Andrica and Ioan Tomescu, On an Integer Sequence Related to a Product of Trigonometric Functions, and Its Combinatorial Relevance , Journal of Integer Sequences, Vol. 5 (2002), Article 02.2.4.
Vlad-Florin Dragoi and Valeriu Beiu, Fast Reliability Ranking of Matchstick Minimal Networks, arXiv:1911.01153 [cs.DM], 2019.
Steven R. Finch, Signum equations and extremal coefficients, February 7, 2009. [Cached copy, with permission of the author]
Erich Friedman and Mike Keith, Magic Carpets, J. Int Sequences, 3 (2000), Article 00.2.5.
Susumu Kubo, Partially Ordered Sets Corresponding to the Partition Problem, arXiv:2405.05544 [cs.DM], 2024. See pp. 2, 16.
Marco Mondelli, S. Hamed Hassani, and Rüdiger Urbanke, Construction of Polar Codes with Sublinear Complexity, arXiv preprint arXiv:1612.05295 [cs.IT], 2016-2017. See Sect. I.
Robert A. Proctor, Solution of two difficult combinatorial problems with linear algebra, American Mathematical Monthly 89, 721-734.
Blair D. Sullivan, On a conjecture of Adrica and Tomescu, J. Int. Sequences 16 (2013), Article 13.3.1.

Cf. A039828, A063865, A069918, A063866, A063867, A083309, A083527, A086376.

Cf. A053632, A160235, A359319, A359320.

b:= proc(n, i) option remember; `if`(n>i*(i+1)/2, 0,
      `if`(i=0, 1, b(n+i, i-1)+b(abs(n-i), i-1)))
    end:
a:=n-> b(0, n)+b(1, n):
seq(a(n), n=0..40);  # Alois P. Heinz, Mar 10 2014

f[n_, s_] := f[n, s]=Which[n==0, If[s==0, 1, 0], Abs[s]>(n*(n+1))/2, 0, True, f[n-1, s-n]+f[n-1, s+n]]; Table[Which[Mod[n, 4]==0||Mod[n, 4]==3, f[n, 0], Mod[n, 4]==1||Mod[n, 4]==2, f[n, 1]], {n, 0, 40}]
(* Second program: *)
p = 1; Flatten[{1, Table[p = Expand[p*(1 + x^n)]; Max[CoefficientList[p, x]], {n, 1, 50}]}] (* Vaclav Kotesovec, May 04 2018 *)
b[n_, i_] := b[n, i] = If[n > i(i+1)/2, 0, If[i == 0, 1, b[n+i, i-1] + b[Abs[n-i], i-1]]];
a[n_] := b[0, n] + b[1, n]; a /@ Range[0, 40] (* Jean-François Alcover, Feb 17 2020, after Alois P. Heinz *)

a(n)=if(n<0,0,polcoeff(prod(k=1,n,1+x^k),n*(n+1)\4))

from collections import Counter
def A025591(n):
    c = {0:1,1:1}
    for i in range(2,n+1):
        d = Counter(c)
        for k in c:
            d[k+i] += c[k]
        c = d
    return max(c.values()) # Chai Wah Wu, Jan 31 2024

a(n) = A063865(n) + A063866(n).
a(n) ~ sqrt(6/Pi) * 2^n / n^(3/2) [conjectured by Andrica and Tomescu (2002) and proved by Sullivan (2013)]. - Vaclav Kotesovec, Mar 17 2020
More precise asymptotics: a(n) ~ sqrt(6/Pi) * 2^n / n^(3/2) * (1 - 6/(5*n) + 589/(560*n^2) - 39/(50*n^3) + ...). - Vaclav Kotesovec, Dec 30 2022
a(n) = max_{k>=0} A053632(n,k). - Alois P. Heinz, Jan 20 2023

A058377 Number of solutions to 1 +- 2 +- 3 +- ... +- n = 0.

Original entry on oeis.org

0, 0, 1, 1, 0, 0, 4, 7, 0, 0, 35, 62, 0, 0, 361, 657, 0, 0, 4110, 7636, 0, 0, 49910, 93846, 0, 0, 632602, 1199892, 0, 0, 8273610, 15796439, 0, 0, 110826888, 212681976, 0, 0, 1512776590, 2915017360, 0, 0, 20965992017, 40536016030, 0, 0, 294245741167

Offset: 1

Naohiro Nomoto, Dec 19 2000

nonn

Consider the set { 1,2,3,...,n }. Sequence gives number of ways this set can be partitioned into 2 subsets with equal sums. For example, when n = 7, { 1,2,3,4,5,6,7} can be partitioned in 4 ways: {1,6,7} {2,3,4,5}; {2,5,7} {1,3,4,6}; {3,4,7} {1,2,5,6} and {1,2,4,7} {3,5,6}. - sorin (yamba_ro(AT)yahoo.com), Mar 24 2007
The "equal sums" of Sorin's comment are the positive terms of A074378 (Even triangular numbers halved). In the current sequence a(n) <> 0 iff n is the positive index (A014601) of an even triangular number (A014494). - Rick L. Shepherd, Feb 09 2010
a(n) is the number of partitions of n(n-3)/4 into distinct parts not exceeding n-1. - Alon Amit, Oct 18 2017
a(n) is the coefficient of x^(n*(n+1)/4-1) of Product_{k=2..n} (1+x^k). - Jianing Song, Nov 19 2021

			1+2-3=0, so a(3)=1;
1-2-3+4=0, so a(4)=1;
1+2-3+4-5-6+7=0, 1+2-3-4+5+6-7=0, 1-2+3+4-5+6-7=0, 1-2-3-4-5+6+7=0, so a(7)=4.

Alois P. Heinz and Ray Chandler, Table of n, a(n) for n = 1..3342 (terms < 10^1000, first 1000 terms from Alois P. Heinz)
Larry Glasser, A formula for A058377, Jul 29 2019

Cf. A000217, A014601, A014494, A025591, A063865, A063866, A063867, A069918, A074378, A111133, A161943, A348639.

Column k=2 of A275714.

b:= proc(n, i) option remember; local m; m:= i*(i+1)/2;
      `if`(n>m, 0, `if`(n=m, 1, b(abs(n-i), i-1) +b(n+i, i-1)))
    end:
a:= n-> `if`(irem(n-1, 4)<2, 0, b(n, n-1)):
seq(a(n), n=1..60);  # Alois P. Heinz, Oct 30 2011

f[n_, s_] := f[n, s] = Which[n == 0, If[s == 0, 1, 0], Abs[s] > (n*(n + 1))/2, 0, True, f[n - 1, s - n] + f[n - 1, s + n]]; Table[ f[n, 0]/2, {n, 1, 50}]

list(n) = my(poly=vector(n), v=vector(n)); poly[1]=1; for(k=2, n, poly[k]=poly[k-1]*(1+'x^k)); for(k=1, n, if(k%4==1||k%4==2, v[k]=0, v[k]=polcoeff(poly[k], k*(k+1)/4-1))); v \\ Jianing Song, Nov 19 2021

a(n) is half the coefficient of q^0 in product('(q^(-k)+q^k)', 'k'=1..n) for n >= 1. - Floor van Lamoen, Oct 10 2005
a(4n+1) = a(4n+2) = 0. - Michael Somos, Apr 15 2007
a(n) = [x^n] Product_{k=1..n-1} (x^k + 1/x^k). - Ilya Gutkovskiy, Feb 01 2024

More terms from Sascha Kurz, Mar 25 2002

Edited and extended by Robert G. Wilson v, Oct 24 2002

A160089 The maximum of the absolute value of the coefficients of Pn = (1-x)(1-x^2)(1-x^3)...(1-x^n).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 3, 2, 4, 3, 3, 4, 6, 5, 6, 7, 8, 8, 10, 11, 16, 16, 19, 21, 28, 29, 34, 41, 50, 56, 68, 80, 100, 114, 135, 158, 196, 225, 269, 320, 388, 455, 544, 644, 786, 921, 1111, 1321, 1600, 1891, 2274, 2711, 3280, 3895, 4694, 5591, 6780, 8051, 9729, 11624

Offset: 0

Theodore Kolokolnikov, May 01 2009

nonn

If n is even then a(n) is the absolute value of the coefficient of z^(n(n+1)/4). If n is odd, it is an open question as to which coefficient is a(n).

For odd n values, the Berkovich/Uncu reference provides explicit conjectural formulas for a(n). - Ali Uncu, Jul 19 2020

Vaclav Kotesovec, Table of n, a(n) for n = 0..5000 (terms n = 1..100 from Theodore Kolokolnikov, terms n = 101..1000 from Alois P. Heinz)
Alexander Berkovich, and Ali K. Uncu, Where do the maximum absolute q-series coefficients of (1-q)(1-q^2)(1-q^3)...(1-q^(n-1))(1-q^n) occur?, arXiv:1911.03707 [math.NT], 2019.
Steven R. Finch, Signum equations and extremal coefficients, February 7, 2009. [Cached copy, with permission of the author]

Cf. A025591, A063866, A069918, A133871.

A160089 := proc(n)
        g := expand(mul( 1-x^k,k=1..n) );
        convert(PolynomialTools[CoefficientVector](g, x), list):
        max(op(map(abs, %)));
end proc:

p = 1; Flatten[{1, Table[p = Expand[p*(1 - x^n)]; Max[Abs[CoefficientList[p, x]]], {n, 1, 100}]}] (* Vaclav Kotesovec, May 03 2018 *)

a(n) >= A086376(n). - R. J. Mathar, Jun 01 2011
From Vaclav Kotesovec, May 04 2018: (Start)
a(n)^(1/n) tends to 1.2197...
Conjecture: a(n)^(1/n) ~ sqrt(A133871(n)^(1/n)) ~ 1.21971547612163368901359933...
(End)

a(0)=1 prepended by Alois P. Heinz, Apr 12 2017

A306443 Number of ways of partitioning the set of the first n primes into two subsets whose sums differ at most by 1.

Original entry on oeis.org

1, 0, 1, 1, 1, 1, 3, 2, 6, 5, 16, 13, 45, 39, 138, 122, 439, 392, 1417, 1286, 4698, 4341, 16021, 14860, 55146, 51085, 190274, 178402, 671224, 634511, 2404289, 2260918, 8535117, 8067237, 30635869, 29031202, 110496946, 105250449, 401422210, 383579285, 1467402238

Offset: 0

Alois P. Heinz, May 31 2019

nonn

			a(8) = 6: 2,17,19/3,5,7,11,13; 3,5,11,19/2,7,13,17; 3,5,13,17/2,7,11,19; 3,7,11,17/2,5,13,19; 2,3,5,11,17/7,13,19; 2,5,7,11,13/3,17,19.
a(9) = 5: 2,3,5,17,23/7,11,13,19; 2,5,7,13,23/3,11,17,19; 2,5,7,17,19/3,11,13,23; 2,5,11,13,19/3,7,17,23; 2,7,11,13,17/3,5,19,23.

Alois P. Heinz, Table of n, a(n) for n = 0..2000
Wikipedia, Partition problem

Bisections give: A022894 (odd part), A113040 (even part).

Cf. A000040, A069918, A307877.

s:= proc(n) s(n):= `if`(n=0, 1, ithprime(n)+s(n-1)) end:
b:= proc(n, i) option remember; `if`(i=0, `if`(n<=1, 1, 0),
     `if`(n>s(i), 0, (p->b(n+p, i-1)+b(abs(n-p), i-1))(ithprime(i))))
    end:
a:= n-> ceil(b(0, n)/2):
seq(a(n), n=0..45);

s[n_] := s[n] = If[n == 0, 1, Prime[n] + s[n - 1]];
b[n_, i_] := b[n, i] = If[i==0, If[n <= 1, 1, 0], If[n > s[i], 0, Function[ p, b[n + p, i - 1] + b[Abs[n - p], i - 1]][Prime[i]]]];
a[n_] := Ceiling[b[0, n]/2];
a /@ Range[0, 45] (* Jean-François Alcover, Apr 30 2020, after Alois P. Heinz *)

A307877 Number of ways of partitioning the set of the first n positive squares into two subsets whose sums differ at most by 1.

Original entry on oeis.org

1, 1, 0, 0, 0, 0, 2, 1, 1, 5, 2, 1, 5, 13, 43, 43, 57, 193, 274, 239, 430, 1552, 3245, 2904, 5419, 18628, 31048, 27813, 50213, 188536, 372710, 348082, 649300, 2376996, 4197425, 3913496, 7287183, 27465147, 53072709, 50030553, 93696497, 351329160, 650125358

Offset: 0

Alois P. Heinz, Jun 04 2019

nonn

			a(6) = 2: 1,9,36/4,16,25; 1,4,16,25/9,36.
a(7) = 1: 1,4,16,49/9,25,36.

Alois P. Heinz, Table of n, a(n) for n = 0..200
Wikipedia, Partition problem

Cf. A000290, A069918, A083527, A158092, A306443, A308682.

s:= proc(n) s(n):= `if`(n=0, 1, n^2+s(n-1)) end:
b:= proc(n, i) option remember; `if`(i=0, `if`(n<=1, 1, 0),
      `if`(n>s(i), 0, (p-> b(n+p, i-1)+b(abs(n-p), i-1))(i^2)))
    end:
a:= n-> ceil(b(0, n)/2):
seq(a(n), n=0..45);

s[n_] := s[n] = If[n == 0, 1, n^2 + s[n - 1]];
b[n_, i_] := b[n, i] = If[i == 0, If[n <= 1, 1, 0], If[n > s[i], 0, Function[p, b[n + p, i - 1] + b[Abs[n - p], i - 1]][i^2]]];
a[n_] := Ceiling[b[0, n]/2];
a /@ Range[0, 45] (* Jean-François Alcover, Dec 07 2020, after Alois P. Heinz *)

a(n) = A083527(n) if n == 0 or 3 (mod 4).

A290889 Number of partitions of the set of odd numbers {1, 3, ..., 2*n-1} into two subsets such that the absolute difference of the sums of the two subsets is minimized.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 5, 4, 13, 10, 38, 34, 118, 103, 380, 346, 1262, 1153, 4277, 3965, 14745, 13746, 51541, 48396, 182182, 171835, 650095, 615966, 2338706, 2223755, 8472697, 8082457, 30884150, 29543309, 113189168, 108545916, 416839177, 400623807, 1541726967

Offset: 1

Hugo Pfoertner, Aug 13 2017

nonn

Partitioning in equal sums is only possible for n = 4*k-1, k > 1, and the number of such partitions is given by A156700. For the set {1,3} and the other values of n, i.e., for the sets {1,3,5}, {1,3,5,7,9}, {1,3,5,7,9,11,13}, one can use the criterion to split the sets "as well as possible" by choosing those partitions for which the absolute value of the difference of the respective sums of the subset members achieves its minimum.

			a(1) = 1: {}U{1} with difference 1.
a(2) = 1: {1}U{3} with difference 2.
a(3) = 1: {1,3}U{5} with difference 1.
a(4) = 1 = A156700(2): {1,7}U{3,5} with difference 0.
a(5) = 2: {1,3,9}U{5,7} and {1,5,7}U{3,9} with |difference|=1.
a(6) = 1 = A156700(3): {1,3,5,9}U{7,11} with difference 0.
a(7) = 5: {1,3,5,7,9}U{11,13}, {1,3,9,11}U{5,7,13}, {1,5,7,11}U{3,9,13},
          {1,11,13}U{3,5,7,9}, {1,3,7,13}U{5,9,11} with |difference|=1.

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Cf. A005408, A058377, A069918, A156700.

b:= proc(n, i) option remember; `if`(n>i^2, 0,
      `if`(n=i^2, 1, b(abs(n-2*i+1), i-1)+b(n+2*i-1, i-1)))
    end:
a:= n-> `if`(n<5, 1, (t-> b(t, n)/(2-t))(irem(n, 2))):
seq(a(n), n=1..50);  # Alois P. Heinz, Aug 14 2017

b[n_, i_] := b[n, i] = If[n > i^2, 0, If[n == i^2, 1, b[Abs[n - 2i + 1], i - 1] + b[n + 2i - 1, i - 1]]];
a[n_] := If[n < 5, 1, b[#, n]/(2-#)&[Mod[n, 2]]];
Array[a, 50] (* Jean-François Alcover, Nov 14 2020, after Alois P. Heinz *)

a(n) ~ (3 - (-1)^n) * sqrt(3) * 2^(n - 5/2) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Sep 18 2017

cp's OEIS Frontend

A025591 Maximal coefficient of Product_{k<=n} (1 + x^k). Number of solutions to +- 1 +- 2 +- 3 +- ... +- n = 0 or 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A058377 Number of solutions to 1 +- 2 +- 3 +- ... +- n = 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A160089 The maximum of the absolute value of the coefficients of Pn = (1-x)(1-x^2)(1-x^3)...(1-x^n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A306443 Number of ways of partitioning the set of the first n primes into two subsets whose sums differ at most by 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A307877 Number of ways of partitioning the set of the first n positive squares into two subsets whose sums differ at most by 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A290889 Number of partitions of the set of odd numbers {1, 3, ..., 2*n-1} into two subsets such that the absolute difference of the sums of the two subsets is minimized.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula