A356852 Minimum over all order two bases for the interval [1, n] of the maximum number of ways some number in the interval [1, n] can be written as a sum of at most two elements of the basis.

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

Offset: 1

Author

Javier Múgica, Aug 31 2022

Keywords

• nonn

Comments

a(n) >= a(n-1). Hence this sequence is defined by its jumps: "Maximum k such that there exists an order two basis for the interval [1, k] with no multiplicity greater than n". This sequence has still too few known terms to have its own entry. It starts: 5, 55, 323. The next term is >= 1006 (in all likelihood it is greater).

a(n) is the minimum over all branches of length n in A265262 of the maximum number in each branch.

If the number 0 is allowed to be part of the basis then the "sum of at most two" from the definition should be changed to "sum of two".

It is believed that a(n) tends to infinity. Erdős and Turán conjectured in 1941 that any basis of order two for all the natural numbers cannot avoid large multiplicities. The two conjectures can easily be proved to be equivalent.

The bases yielding the highest n with given a(n) = k for each k are:

1: 1 3 5 (n <= 5)

2: 1 2 4 5 7 11 16 19 24 32 40 45 52 53 (n <= 55)

3: 1 2 3 5 6 8 9 17 20 22 28 29 40 47 53 57 69 83 90 99 107 117 131 141 152 162 172 182 193 203 217 227 237 248 258 268 279 289 303 313 (n <= 324)

For k = 4 the following basis serves for n <= 1006:

1 2 3 4 5 7 8 9 12 13 17 23 33 39 49 55 64 66 80 86 95 97 111 113 126 134 140 153 162 178 181 192 203 210 231 242 254 275 281 299 303 311 325 335 346 386 405 423 435 446 469 486 504 521 538 556 590 602 620 639 656 673 690 739 772 805 822 840 855 873 890 907 940 957 974 987 996

Examples

			The basis 1, 3, 5 can serve to express every number in the interval [1, 5] in a unique way: 1 = 1, 2 = 1+1, 3 = 2+1, 4 = 2+2, 5 = 5. Hence a(1) = ... = a(5) = 1. This is the only basis with this property and cannot be extended further since 6 = 3+3 = 5+1. Therefore a(n) >= 2 for n >= 6.
The basis 1, 3, 4, 9, 11, 16, 21, 23, 28 allows one to express every number in the interval [1, 31] as a sum of one or two elements from it, hence a(6) = ... = a(31) = 2.
		

Links

• Javier Múgica, Table of n, a(n) for n = 1..1000
• P. Erdős and P. Turán, On a problem of Sidon in additive number theory, and on some related problems, J. Lond. Math. Soc. 16 (1941), 212-215.

Crossrefs

Cf. A265262, A001212.