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

Author

Peter Kagey, Nov 30 2015

Keywords

• nonn

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).

Examples

			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]
		

Links

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

Programs

Ruby

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

Formula

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