A393584 - OEIS

A393584

a(n) is the minimum, over all partitions {X, Y} of {1..2n} with |X| = |Y|, of the maximum number of pairs (x, y) with the same difference x - y for x in X and y in Y.

1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 8, 8, 8, 9, 9, 10, 10, 10, 11, 11, 11, 12, 12, 13, 13, 13

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

a(n) is floor(5*n/13) for small n but a(n) ~ (c - o(1))*n for some 0.379005 < c < 0.380876. - Sharvil Kesarwani, Mar 04 2026

From Bert Dobbelaere, Mar 02 2026: (Start)

a(k*n) <= k*a(n) can be shown by constructing a set X' containing all elements in range [k*(x-1)+1...k*x] for each element x of X (similar for Y).

a(n+1) <= a(n) + 1 can be shown by extending X with element 2n+1 and Y with element 2n+2.

It follows that a(n)/n >= the lower bound for c, otherwise it would be violated for arbitrary large k. (End)

LINKS

Table of n, a(n) for n=1..33.

Thomas F. Bloom, Erdős Problem #36

FORMULA

a(2n) <= n.

a(k*n) <= k * a(n) for positive integer k. - Bert Dobbelaere, Mar 02 2026

a(n+1) <= a(n) + 1. - Bert Dobbelaere, Mar 02 2026

EXAMPLE

For n = 2, the equal partitions of {1,2,3,4} are:

- {1,2} and {3,4}: the differences are 2, 1, 3, 2: max repetition is 2.

- {1,3} and {2,4}: the differences are 1, -1, 3, 1, max repetition is 2.

- {1,4} and {2,3}: the differences are 1, -2, 2, -1, max repetition is 1.

Hence a(2) = 1.

For n = 3, the partition {1,2,4} and {3,5,6} has at most two pairs with the same difference, so a(3) <= 2. Exhaustive checking shows that no partition has lower repetition.

PROG

(Python)

from itertools import combinations

from collections import Counter

def a(n): return min(max(Counter(a-b for a in A for b in range(1, 2 * n + 1) if b not in A).values()) for A in combinations(range(1, 2*n + 1), n))

CROSSREFS

Sequence in context: A143796 A245473 A306904 * A371627 A057362 A214046

Adjacent sequences: A393581 A393582 A393583 * A393585 A393586 A393587

KEYWORD

nonn,more

AUTHOR

Touch Sungkawichai, Feb 22 2026