Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the 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