A090701 - OEIS

%I #10 Jan 25 2018 17:45:38

%S 1,2,2,2,2,3,3,4,4,4,5,5,5,6,6,6,6,7,7,8,8,8,8,9,9,10,10,10,10,11,11,

%T 12,12,12,12,13,13,14,14,14,14,15,15,16,16,16,16,17,17,18,18,18,18,19,

%U 19,20,20,20,20,21,21,22,22,22,22,23,23,24,24,24,24,25,25,26,26,26,26,27,27,28,28,28,28,29,29,30,30

%N a(n) is the minimal number k such that every binary word of length n can be divided into k palindromes.

%C A word l_0...l_n is called a palindrome if l_i=l_{n-i} for all i<=n.

%H Michael De Vlieger, <a href="/A090701/b090701.txt">Table of n, a(n) for n = 1..16384</a>

%H A. Baababov, <a href="http://kvant.mccme.ru/pdf/1999/04/kv0499baababov.pdf">A "Pentium" is good but a mind is better</a>, Kvant 4-5 (1999), 38-42. (in Russian)

%H O. V. Ravsky, <a href="https://arxiv.org/abs/1004.1278">On the palindromic decomposition of binary words</a>, arXiv:1004.1278 [math.CO], 2010; Journal of Automata, Languages and Combinatorics, 8, #1 (2003), p. 71-74.

%F a(n) = floor(n/6) + floor((n+4)/6) + 1 for n<>11 and a(11)=5.

%t Array[Boole[# == 11] + Floor[#/6] + Floor[(# + 4)/6] + 1 &, 87] (* _Michael De Vlieger_, Jan 23 2018 *)

%o (PARI) a(n)=if(n==11,5,floor(n/6)+floor((n+4)/6)+1); \\ _Joerg Arndt_, Jan 21 2018

%Y Cf. A090702.

%K easy,nonn

%O 1,2

%A Sasha Ravsky (oravsky(AT)mail.ru), Jan 12 2004

%E More terms from _Joerg Arndt_, Jan 21 2018