A382397 - OEIS

A382397

Minimum size of a maximal subset of {1..n} such that every pair of distinct elements has a different difference.

0, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6

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

OFFSET

0,3

COMMENTS

Also the minimum size of a maximal subset of {1..n} such that every pair of (not necessarily distinct) elements has a different sum.

a(n) is the minimum size of a set enumerated by A325879(n).

Number of occurrences of k: 1, 1, 3, 6, 12, 20, ...

Maximum n having a(n) = k: 0, 1, 4, 10, 22, 42, ...

There are insufficient known terms in either of the above to distinguish from other sequences.

LINKS

Table of n, a(n) for n=0..65.

Thomas Bloom, Problem 156, Erdős Problems.

Erdős problems database contributors, Erdős problem database, see no. 156.

Wikipedia, Sidon sequence.

Index entries for sequences related to Golomb rulers.

PROG

(PARI)

a(n)={

my(ismaxl(b, w)=for(k=1, n, if(!bittest(b, k) && !bitand(w, bitor(b, 1<<k)<<k), return(0))); 1);

my(recurse(k, b, w)=

if(k > n, if(ismaxl(b, w), 0, n+1),

my(s=self()(k+1, b, w));

b+=1<<k; if(!bitand(w, b<<k), s=min(s, 1+self()(k+1, b, w + (b<<k))));

s);

);

recurse(1, 0, 0);

}

CROSSREFS

Cf. A143824 (maximum size of set), A325879, A377419 (minimum sum), A382396.

Sequence in context: A227923 A346425 A029836 * A004257 A360010 A276611

Adjacent sequences: A382394 A382395 A382396 * A382398 A382399 A382400

KEYWORD

nonn,more

AUTHOR

Andrew Howroyd, Mar 23 2025

STATUS

approved