login
Irregular triangle read by rows: lexicographically earliest, minimum size sets, S_n, such that {1, 2, ... n} is a subset of the union of S_n with the sums of distinct pairs in S_n and the differences of pairs in S_n.
1

%I #20 Oct 28 2021 07:10:29

%S 1,1,2,1,2,1,3,1,2,3,1,2,4,1,2,5,1,2,6,1,2,3,6,1,2,3,7,1,2,3,8,1,2,3,

%T 9,1,2,6,11,1,2,3,4,10,1,2,3,4,11,1,2,3,4,12,1,2,3,7,14,1,2,3,8,15,1,

%U 2,3,9,16,1,2,7,13,17,1,2,3,4,8,17

%N Irregular triangle read by rows: lexicographically earliest, minimum size sets, S_n, such that {1, 2, ... n} is a subset of the union of S_n with the sums of distinct pairs in S_n and the differences of pairs in S_n.

%C Each row is weakly longer than the preceding row, and weakly lexicographically later if the preceding row is the same length.

%C Conjecture: A225687 gives the row lengths.

%H Peter Kagey, <a href="/A292997/b292997.txt">Table of n, a(n) for n = 1..265</a> (first 47 rows, flattened)

%H Reddit user uoaei, <a href="https://www.reddit.com/r/math/comments/72m1d8">For a given maximum integer N, what is the set of integers with minimal cardinality that can give me any integer between 1 and N by only one addition or subtraction between any two elements in that set?</a>

%e For n = 7, S_7 = {1, 2, 5}. Because {1, 2, ..., 7} can be represented as {1, 2, 1 + 2, 5 - 1, 5, 5 + 1, 5 + 2}, where each term is in S_7 or is the sum or difference of two distinct terms in S_7.

%e There is no set of fewer than three elements with this property, and S_7 is the lexicographically earliest set of three elements with this property.

%e Table begins:

%e 1;

%e 1, 2;

%e 1, 2;

%e 1, 3;

%e 1, 2, 3;

%e 1, 2, 4;

%e 1, 2, 5;

%e 1, 2, 6;

%e 1, 2, 3, 6;

%e 1, 2, 3, 7.

%Y Cf. A005228, A225687.

%K nonn,tabf

%O 1,3

%A _Peter Kagey_, Sep 27 2017