A259280 a(n) is the minimal sum of a positive integer sequence of length n with no duplicate substrings of length greater than 1.

1, 2, 4, 5, 7, 9, 11, 14, 16, 19, 21, 24, 27, 30, 33, 36, 40, 43, 47, 50, 54, 57, 61, 65, 69, 73, 77, 81, 85, 90, 94, 99, 103, 108, 112, 117, 121, 126, 131, 136, 141, 146, 151, 156, 161, 166, 172, 177, 183, 188, 194, 199, 205, 210, 216, 221, 227, 233, 239, 245

Offset

1,2

Comments

The lexicographically earliest positive integer sequence with no duplicate substrings is [1, 1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, ...].

Note: Trivial substring of length 1 are allowed to recur, i.e., duplicate terms are permitted.

Non-examples of positive integer sequences with no duplicate substrings are

[1, 1, 1] (the substring [1, 1] occurs twice) and [1, 2, 3, 1, 2] (the substring [1, 2] occurs twice).

Links

Peter Kagey, Table of n, a(n) for n = 1..10000

Formula

a(1) = 1, a(n) = ceiling((n + 1 + A060432(n - 1))/2) for n > 1.

Example

Lexicographically earliest examples:
a(1) = 1 via [1]
a(2) = 2 via [1, 1]
a(3) = 4 via [1, 1, 2]
a(4) = 5 via [1, 1, 2, 1]
a(5) = 7 via [1, 1, 2, 2, 1]
a(6) = 9 via [1, 1, 2, 1, 3, 1]
a(7) = 11 via [1, 1, 2, 2, 1, 3, 1]
a(8) = 14 via [1, 1, 2, 1, 3, 1, 4, 1]
a(9) = 16 via [1, 1, 2, 1, 3, 2, 2, 3, 1]
a(10) = 19 via [1, 1, 2, 1, 3, 2, 2, 3, 3, 1]
a(11) = 21 via [1, 1, 2, 1, 3, 2, 2, 3, 1, 4, 1]
a(12) = 24 via [1, 1, 2, 1, 3, 2, 2, 3, 3, 1, 4, 1]
a(13) = 27 via [1, 1, 2, 1, 3, 1, 4, 2, 2, 3, 2, 4, 1]

Prog

(Ruby)
def a259280(n)
  lower_bound = 0.5 * (a060432(n - 1) + n + 1)
  lower_bound.ceil
end

Crossrefs

Sequence in context: A258049 A057352 A156625 * A186388 A058577 A356075

Adjacent sequences: A259277 A259278 A259279 * A259281 A259282 A259283

Keyword

nonn

Author

Peter Kagey, Nov 30 2015

Status

approved