cp's OEIS Frontend

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.

%I A282166 #24 Jun 02 2025 16:19:23
%S A282166 1,3,4,7,8,12,13,17,18,22,24,28,30,35,37,42,44,49,51,56,59,64,67,72,
%T A282166 75,81,84,90,93,99,102,108,111,117,121,127,131,137,141,147,151,158,
%U A282166 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
%N 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.
%C A282166 For example, [1,1] is not a valid sequence because 1 is self-adjacent; [1,2,3,1,2] is not valid because the substring [1,2] appears twice.
%F A282166 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
%e A282166 a(1)  = 1  via [1];
%e A282166 a(2)  = 3  via [1,2];
%e A282166 a(3)  = 4  via [1,2,1];
%e A282166 a(4)  = 7  via [1,2,1,3];
%e A282166 a(5)  = 8  via [1,2,1,3,1];
%e A282166 a(6)  = 12 via [1,2,1,3,1,4];
%e A282166 a(7)  = 13 via [1,2,1,3,1,4,1];
%e A282166 a(8)  = 17 via [1,2,1,3,1,4,2,3];
%e A282166 a(9)  = 18 via [1,2,1,3,2,3,1,4,1];
%e A282166 a(10) = 22 via [1,2,1,3,1,4,2,3,4,1];
%e A282166 a(11) = 24 via [1,2,1,3,2,3,1,4,1,5,1].
%t A282166 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 *)
%Y A282166 Cf. A259280, A282167, A282168.
%Y A282166 Cf. A282169 is the product analog.
%K A282166 nonn
%O A282166 1,2
%A A282166 _Peter Kagey_, Feb 07 2017
%E A282166 a(12)-a(21) from _Lars Blomberg_, Jun 10 2017
%E A282166 Terms a(22) onward from _Max Alekseyev_, Feb 04 2025