Pour Le Science and the anti-Sum-Product Problem

In March 2021, I got an out-of-the-blue email from OEIS editor Michel Marcus which totally delighted me. He wrote:

This afternoon I went to the library.
And I was browsing “Pour La Science” the French version of the Scientific American.
And here is what I saw.

I like the mysterious tone.

He included this photo of an excerpt of an article, which on the first line mentioned an OEIS sequence of mine (with my name slightly misspelled):

The article, translated

Michel had sent me a snippet of the article “Addition et multiplication, des tables qui intriguent” by French Computer Science professor Jean-Paul Delahaye. I read French quite clumsily, so I sent it to my friend Alec, and he volunteered a translation.

Sloane [verb not pictured] of my sequence A337655, Peter Kagey, who must have been informed of changes to the encyclopedia, proposed this second way of accounting for addition and multiplication. This has yielded a new entry in the encyclopedia, the following A337946:

1, 3, 7, 12, 22, 30, 47, 61, 85, 113, 126, 177, 193, 246, 279, 321, 341, 428, 499, 571, 616, 686, 754, 854, 975, 1052, 1150, 1317, 1376, 1457, …

Impossible Little Tables

Let’s consider the fourth question. The response is negative this time: no, it’s not possible that the tables of addition and multiplication have simultaneously only a few distinct values. This is a result of Paul Erdős and Endre Szemerédi from 1983, which we state precisely here:

“There exist two constants \(C>0\) and \(e > 0\) such that, for the set \(E\) of real numbers of […]

Translation by Alec Jones

A Sum-Product Problem

The article—or at least the part that I could make sense of—is about the opposite of Erdos’s Sum-Product Problem. This article explores questions about the greatest number of different values in the corresponding addition and multiplication tables for different sequences of positive integers.

Jean-Paul’s sequence, A337655, is the lexicographically earliest (greedy) sequence such that for all \(n\) both the addition and multiplication tables of the first \(n\) terms have \(\binom{n+1}{2}\) distinct terms (the greatest number).

The addition and multiplication tables share some values. For example, they both have a \(2\), a \(4\), a \(7\), a \(10\), and so on. My sequence, A337946, is similar to Jean-Paul’s but with the additional restriction that the addition and multiplication tables cannot have any values in common.

Some related sequences

I’ve recently added some new sequences to the OEIS related to these sequences.

One way of thinking of A066720 is that it’s the lexicographically earliest infinite sequence \(S = \(a_i\)_{i=1}^{\infty}\) such that for all \(n\) the set \(S_n = \{a_i\}_{i=1}^{n}\) consisting of the first \(n\) terms of \(S\) has the property that \(S_n \times S_n = \{xy \mid x, y \in S_n\}\) has exactly \(\binom{n+1}{2}\) elements—the most possible.

A347498: minimize the largest term

If instead of minimizing the lexicographic order, we instead minimize the size of the largest element, we get OEIS sequence A347498: for each \(n\), find the least \(m\) such that there exists a subset \(T_n \subseteq \{1, 2, \dots, m\}\) with \(n\) elements such that \(|T_n \times T_n| = \binom{n+1}{2}\). \(A347498(n)\) records the value of the \(m\)s.

For example, \(A347498(8) = 11\) as illustrated by the table below.

A347499: Examples with minimized largest element

We wish to record examples of the sequences described in the above section. There are \(A348481(n)\) subsets of \(\{1,2,…,A347499(n)\}\) with the distinct product property, but we record the lexicographically earliest one in OEIS sequence A347499.

 n | Distinct product subset of {1,2,...,A347499(n)}
---+-------------------------------------------------------
 1 | {1}
 2 | {1, 2}
 3 | {1, 2, 3}
 4 | {1, 2, 3, 5}
 5 | {1, 3, 4, 5,  6}
 6 | {1, 3, 4, 5,  6,  7}
 7 | {1, 2, 5, 6,  7,  8,  9}
 8 | {1, 2, 5, 6,  7,  8,  9, 11}
 9 | {1, 2, 5, 6,  7,  8,  9, 11, 13}
10 | {1, 2, 5, 7,  8,  9, 11, 12, 13, 15}
11 | {1, 2, 5, 7,  8,  9, 11, 12, 13, 15, 17}
12 | {1, 2, 5, 7,  8,  9, 11, 12, 13, 15, 17, 19}
13 | {1, 5, 6, 7,  9, 11, 13, 14, 15, 16, 17, 19, 20}
14 | {1, 2, 5, 7, 11, 12, 13, 16, 17, 18, 19, 20, 21, 23} 

For all of the known values, the lexicographically earliest subset begins with \(1\). Is this true in general?

A347570: Sums with more terms

Perhaps instead of asking when all sums \(x + y\) are distinct for \(x \leq y\), we want to know when all sums \(x_1 + x_2 + \dots + x_n\) are distinct for \(x_1 \leq x_2\leq \dots \leq x_n\). This family of sequences are sometimes called \(B_n\) sequences and have been studied by the likes of Richard Guy.

I’ve recorded the lexicographically earliest \(B_n\) sequences in OEIS sequence A347570.

n\k | 1  2   3   4    5     6     7      8
----+------------------------------------------
  1 | 1, 2,  3,  4,   5,    6,    7,     8, ...
  2 | 1, 2,  4,  8,  13,   21,   31,    45, ...
  3 | 1, 2,  5, 14,  33,   72,  125,   219, ...
  4 | 1, 2,  6, 22,  56,  154,  369,   857, ...
  5 | 1, 2,  7, 32, 109,  367,  927,  2287, ...
  6 | 1, 2,  8, 44, 155,  669, 2215,  6877, ...
  7 | 1, 2,  9, 58, 257, 1154, 4182, 14181, ...
  8 | 1, 2, 10, 74, 334, 1823, 8044, 28297, ... 

I ask about this family of sequences in a recent question on Code Golf Stack Exchange.

Other ideas?

Did this post spark any related ideas? Let me know about them on Twitter @PeterKagey—I’d love to hear about them!