A282166 a(n) is the minimal sum of a positive integer sequence of length n with no duplicate substrings of length greater than 1, and every number different from its neighbors.
1, 3, 4, 7, 8, 12, 13, 17, 18, 22, 24, 28, 30, 35, 37, 42, 44, 49, 51, 56, 59, 64, 67, 72, 75, 81, 84, 90, 93, 99, 102, 108, 111, 117, 121, 127, 131, 137, 141, 147, 151, 158, 162, 169, 173, 180, 184, 191, 195, 202, 206, 213, 218, 225, 230, 237, 242, 249, 254, 261, 266, 274, 279, 287, 292, 300, 305, 313, 318, 326, 331, 339, 344, 352, 358, 366, 372, 380, 386, 394
Offset: 1
Keywords
Examples
a(1) = 1 via [1]; a(2) = 3 via [1,2]; a(3) = 4 via [1,2,1]; a(4) = 7 via [1,2,1,3]; a(5) = 8 via [1,2,1,3,1]; a(6) = 12 via [1,2,1,3,1,4]; a(7) = 13 via [1,2,1,3,1,4,1]; a(8) = 17 via [1,2,1,3,1,4,2,3]; a(9) = 18 via [1,2,1,3,2,3,1,4,1]; a(10) = 22 via [1,2,1,3,1,4,2,3,4,1]; a(11) = 24 via [1,2,1,3,2,3,1,4,1,5,1].
Programs
-
Mathematica
Table[Module[{s = Select[Permutations[Range@ n - 1, n], Length@ # > 1 &]}, Total@ First@ MinimalBy[#, Total] &@ DeleteCases[#, w_ /; Apply[Times, If[Length@ # > 0, Rest@ #, #] &@ Union@ Map[SequenceCount[w, #] &, s]] > 1] &@ Apply[Join, Map[MinimalBy[#, Total] &, Table[Select[Tuples[Range@ k, n], Function[w, Times @@ Boole@ {Length@ Union@ w == k, First@ #, If[n > 2, Xor @@ Rest@ #, True]} == 1 &@ Map[Length@ Split@ # == Length@ # &, {w, w[[1 ;; -1 ;; 2]], Rest[w][[1 ;; -1 ;; 2]]}]]], {k, n}]]]], {n, 7}] (* Michael De Vlieger, Mar 27 2017, Version 10 *)
Formula
For n>=4, we seem to have a(n) = a(n-1) + a(n-2) - a(n-3) + d(n), where d(n) is either 0 or 1 (with a clear formula). This observation leads to the conjecture: for n>=4, a(n) = -3/2 + 2*n + n*m/2 - m*(2*m^2+15*m+46)/24 + (-1)^n*(m%2+2)/4 + (m%2)*3/8, where m is the largest integer such that (2*m^2 + 8*m + 1 + 3*(-1)^m)/4 <= n. - Max Alekseyev, May 28 2025
Extensions
a(12)-a(21) from Lars Blomberg, Jun 10 2017
Terms a(22) onward from Max Alekseyev, Feb 04 2025
Comments