A222807 -id:A222807 - cp's OEIS frontend

A118544 Number of subsets A of {1,2,...,n} with |A+A| = |A-A|.

2, 4, 8, 14, 24, 40, 66, 106, 174, 286, 480, 814, 1412, 2480, 4476, 8184, 15230, 28652, 54488, 104262, 201266, 390090, 760234, 1486030, 2914492, 5728506, 11289420, 22279222, 44046072, 87181188, 172777354, 342724456, 680524908, 1352154964, 2688763324

Offset: 1

Kevin O'Bryant, May 07 2006

nonn

Keywords: sum-dominant sets, MSTD sets.

Some authors work with subsets of [0..n-1], others with subsets of [1..n].

			a(4)=14: two of the sixteen subsets of {1,2,3,4} have |A+A|<|A-A| (specifically, {1,3,4} and {1,2,4}).

James Wilcox and Giovanni Resta, Table of n, a(n) for n = 1..40 (first 35 terms from James Wilcox)

Cf. A222807, A222808, A140794.

a(21)-a(29) from Robert Gerbicz, Nov 19 2010

a(30)-a(35) from James Wilcox, Jul 22 2013

A222808 Number of subsets A of {0,1,...,n-1} with |A+A| < |A-A|.

Original entry on oeis.org

0, 0, 0, 2, 8, 24, 62, 150, 338, 738, 1568, 3282, 6780, 13904, 28288, 57342, 115812, 233426, 469656, 944000, 1895194, 3802762, 7625328, 15284798, 30626642, 61353084, 122872144, 246042562, 492592948, 986089652, 1973756116, 3950330140, 7905541650, 15819942048, 31655323370

Offset: 1

N. J. A. Sloane, Mar 10 2013

nonn

Some authors work with subsets of [0..n-1], others with subsets of [1..n].
Keywords: sum-dominant sets, MSTD sets.
a(1)-a(21) were computed by Daniel C. R. Scheinerman, Mar 10 2013; although a(1)-a(27) had been found by Kevin O'Bryant some time earlier.

James Wilcox and Giovanni Resta, Table of n, a(n) for n = 1..40 (first 35 terms from James Wilcox)
Greg Martin and Kevin O'Bryant, Many sets have more sums than differences, arXiv:math/0608131 [math.NT], 2006.

Cf. A118544, A140794, A222807.

a(28)-a(35) from James Wilcox, Jul 22 2013

A140794 One of the four smallest counterexamples to the conjecture that the cardinality of the sumset is less than or equal to the cardinality of the difference set of every finite set of integers.

Original entry on oeis.org

0, 2, 3, 7, 10, 11, 12, 14

Offset: 1

Jonathan Vos Post, Jul 15 2008

This sequence is the reflection of A102282: a(n) = 14 - A102282(9-n).
Keywords: sum-dominant sets, MSTD sets.
A set with more sums than differences is called an MSTD set. Hegarty has constructed many such examples.
Comment from N. J. A. Sloane, Mar 10 2013: Out of the 2^n subsets S of [0..n-1], let
AG(n) = number of S with |S+S|>|S-S|,
AE(n) = number of S with |S+S|=|S-S|,
AL(n) = number of S with |S+S|<|S-S|.
A140794 says AG(n) = 0 for n <= 14. These three sequences are respectively A222807, A118544, A222808.

			Let A = {0, 2, 3, 7, 10, 11, 12, 14}. Then the cardinality of the sumset, |A + A| = 26, while the cardinality of the difference set, |A - A| = 25.

P. V. Hegarty, Some explicit constructions of sets with more sums than differences, Acta Arith., 130 (2007), 61-77.
Greg Martin and Kevin O'Bryant, Many sets have more sums than differences, arXiv:math/0608131 [math.NT], 2006.
Melvyn B. Nathanson, Problems in Additive Number Theory, III: Thematic Seminars at the Centre de Recerca Matematica, arXiv:0807.2073 [math.NT], 2008.

Cf. A222807, A118544, A222808.

Corrected by James Wilcox, Jul 24 2013

A102282 Smallest possible example of an MSTD ("More sums than differences") set.

Original entry on oeis.org

0, 2, 3, 4, 7, 11, 12, 14

Offset: 1

N. J. A. Sloane, Sep 08 2008

Reflection of A140794: a(n) = 14 - A140794(9-n). - James Wilcox, Jul 24 2013

Hegarty, who attributes the set to Conway, proves its minimality. - Charles R Greathouse IV, Sep 26 2019

B. Hayes, Calculemus!, American Scientist, 96 (Sep-Oct 2008), 362-366.

Peter Hegarty, Some explicit constructions of sets with more sums than differences (2007)

Cf. A222807, A118544, A222808.

A224893 Number of subsets A of {0,...,n-1} such that A contains 0 and n-1, and |A+A| > |A-A|.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 2, 14, 16, 42, 92, 208, 382, 834, 1748, 3568, 7066, 14914, 28618, 60712, 120872, 240102, 483328, 992812, 1948804, 3975364, 7933368, 15876692, 31759760, 64035868, 126968066, 255821994

Offset: 1

James Wilcox, Jul 24 2013

nonn

A222807(n) = Sum_{i=1..n} (n-i+1)*a(i).

Cf. A222807.

A305503 Largest cardinality of subsets A of {0,1,...,n-1} with |A + A| > |A - A|.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40

Offset: 1

Tanuj Mathur, Jun 03 2018

All the possible 'A's are explicitly generated and sorted according to their cardinality.

			For n = 15, the subsets A of {0,1,...,n-1} with |A + A| > |A - A| are (0, 2, 3, 4, 7, 11, 12, 14); (0, 2, 3, 7, 10, 11, 12, 14); (0, 1, 2, 4, 5, 9, 12, 13, 14) and (0, 1, 2, 5, 9, 10, 12, 13, 14). So, the largest cardinality is 9.

P. V. Hegarty, Some explicit constructions of sets with more sums than differences, Acta Arith., 130 (2007), 61-77.
Greg Martin and Kevin O'Bryant, Many sets have more sums than differences, arXiv:math/0608131 [math.NT], 2006-2007.

Cf. A118544, A222807, A222808, A291514.

import numpy as np
import itertools
def findsubsets(S, m):
    return itertools.combinations(S, m)
def mstd(a):
    a1 = set()
    a2 = set()
    for i in a:
        for j in a:
            a1.add(i + j)
            a2.add(i - j)
    return len(a1) > len(a2)
def a(n):
    ans = 0
    Nn = list(range(n))
    for k in range(1, n):
        if any(mstd(i) for i in findsubsets(Nn, k)):
            ans = k
    return ans

a(n) = n - 7 (conjectured) for all n > 15.
Conjectures from Colin Barker, Jun 01 2020: (Start)
G.f.: x^14*(9 - 9*x + x^2) / (1 - x)^2.
a(n) = 2*a(n-1) - a(n-2) for n>17.
(End)

A327819 Elements of the unique smallest MSTD set of primes.

Original entry on oeis.org

3, 5, 7, 13, 17, 19, 23, 43, 47, 53, 59, 61, 67, 71, 73

Offset: 1

Charles R Greathouse IV, Sep 26 2019

This set is smallest in terms of minimizing the maximum element.

Chu, McNew, Miller, Xu, & Zhang show that, as a consequence of the Green-Tao theorem, there are infinitely many MSTD sets of primes, and give an example. Chu finds this set and proves minimality, answering a question of the former authors.

Hung Chu, Nathan McNew, Steven J. Miller, Victor Xu, and Sean Zhang, When sets can and cannot have MSTD subsets (2016) arXiv:1608.03256 [math.NT]
Hung Viet Chum, Sets of cardinality 6 are not sum-dominant, arXiv:1906.00470 [math.NT], 2019.

Cf. A102282, A222807, A000040.

cp's OEIS Frontend

A118544 Number of subsets A of {1,2,...,n} with |A+A| = |A-A|.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A222808 Number of subsets A of {0,1,...,n-1} with |A+A| < |A-A|.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A140794 One of the four smallest counterexamples to the conjecture that the cardinality of the sumset is less than or equal to the cardinality of the difference set of every finite set of integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A102282 Smallest possible example of an MSTD ("More sums than differences") set.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A224893 Number of subsets A of {0,...,n-1} such that A contains 0 and n-1, and |A+A| > |A-A|.

Views

Author

Keywords

Comments

Crossrefs

A305503 Largest cardinality of subsets A of {0,1,...,n-1} with |A + A| > |A - A|.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

A327819 Elements of the unique smallest MSTD set of primes.

Views

Author

Keywords

Comments

Links

Crossrefs