cp's OEIS Frontend

A206926 Numbers such that the number of contiguous palindromic bit patterns in their binary representation is minimal (for a given number of places).

%I A206926 #19 Jan 03 2016 04:03:05
%S A206926 2,4,5,6,9,10,11,12,13,18,19,20,22,25,26,37,38,41,44,50,52,75,77,83,
%T A206926 89,101,105,150,154,166,178,203,211,300,308,333,357,406,422,601,617,
%U A206926 666,715,812,845,1202,1235,1332,1430,1625,1690,2405,2470,2665,2860,3250
%N A206926 Numbers such that the number of contiguous palindromic bit patterns in their binary representation is minimal (for a given number of places).
%C A206926 The only binary palindromes in the sequence are 5 and 9.
%C A206926 The sequence is infinite, since A206927 is an infinite subsequence.
%C A206926 a(n) is the least number > a(n-1) which have the same number of palindromic substrings than a(n-1). If such a number doesn't exist, a(n) is the least number with one additional digit which meets the minimal possible number of palindromic substrings for such increased number of digits.
%C A206926 The concatenation of the bit patterns of a(n) and the reversal of a(n) form a term of A217099. Same is true for the concatenation of the bit patterns of a(n) and the reversal of floor(a(n)/2).
%C A206926 For a given number of places m there are at least 2*(m-1) palindromic substrings in the binary representation (cf. A206925). According to the definition the sequence terms are those with minimal possible symmetry. In other words: numbers not in the sequence have a significantly 'higher grade of symmetry'.
%C A206926 The terms have characteristic bit patterns and can be subdivided into 6 different classes of minimal symmetry. There are the following basic bit patterns: '100101', '100110', '101001', '101100', '110010' and '110100' representing the numbers 37, 38, 41, 44, 50 and 52. Numbers which are not a concatenation of one of these basic bit patterns do not meet the minimality condition. Evidently, 37, 44 and 50 (=Set_1) are equivalent patterns, since they can be derived from each other by rotation of digits (bit rotation). Same is true for 38, 41 and 52 (=Set_2). These two sets reflect reverse (mirror inverted) patterns. Each of those numbers from these sets can be viewed as a substitute to represent minimal symmetry.
%C A206926 For a given number b>3 the number of contiguous palindromic bit patterns in its binary representation is minimal if and only if there exists a number c from Set_1 or Set_2 such that the bit pattern of b is contained in concatenated c bit patterns, or, what is equivalent, if and only if b is contained in the concatenated bit patterns of 37 or 41.
%C A206926 If b is a number with more than 4 binary digits such that the number of contiguous palindromic bit patterns in its binary representation is minimal, then b is contained in the concatenated bit patterns either of 37 or 41, but not in both.
%H A206926 Hieronymus Fischer, <a href="/A206926/b206926.txt">Table of n, a(n) for n = 1..2000</a>
%F A206926 a(n) = min(k > a(n-1) | A206925(k) = A206925(a(n-1))), if this minimum exists, else a(n) = min(k >= 2*2^floor(log(a(n-1))) | A206925(k) = min(A206925(j) | j >= 2*2^floor(log(a(n-1)))).
%F A206926 A206925(a(n)) = 2*floor(log_2(a(n))).
%F A206926 A070939(a(n)) = 4 + floor((n-4)/6), for n>4.
%F A206926 A206925(a(n)) = 6 + 2*floor((n-4)/6), for n>4.
%F A206926 Iteration formulas for k>0:
%F A206926 a(6(k+1)+4) = 2a(6k+4) + floor(37*2^(k+5)/63) mod 2.
%F A206926 a(6(k+1)+5) = 2a(6k+5) + floor(41*2^(k+1)/63) mod 2.
%F A206926 a(6(k+1)+6) = 2a(6k+6) + floor(41*2^(k+5)/63) mod 2.
%F A206926 a(6(k+1)+7) = 2a(6k+7) + floor(37*2^(k+2)/63) mod 2.
%F A206926 a(6(k+1)+8) = 2a(6k+8) + floor(37*2^(k+4)/63) mod 2.
%F A206926 a(6(k+1)+9) = 2a(6k+9) + floor(41*2^(k+4)/63) mod 2.
%F A206926 Calculation formulas for k>0:
%F A206926 a(6k+4) = floor((37*2^(k+4)/63) mod 2^(k+4).
%F A206926 a(6k+5) = floor((41*2^(k+6)/63) mod 2^(k+4).
%F A206926 a(6k+6) = floor((41*2^(k+4)/63) mod 2^(k+4).
%F A206926 a(6k+7) = floor((37*2^(k+7)/63) mod 2^(k+4).
%F A206926 a(6k+8) = floor((37*2^(k+9)/63) mod 2^(k+4).
%F A206926 a(6k+9) = floor((41*2^(k+9)/63) mod 2^(k+4).
%F A206926 With q(i) = 1 - 2*(floor((i+5)/6) - floor((i+4)/6) + floor((i+2)/6) + floor(i/6)),
%F A206926 this means q(i) = -1, 1, 1, -1, -1, 1, for i = 1..6,
%F A206926 p(i) = - 4 + 9*floor((i+5)/6) - 4*floor((i+4)/6) + 4*floor((i+3)/6) - 3*floor((i+2)/6)) + 2*floor((i+1)/6)),
%F A206926 this means p(i) = 5, 1, 5, 2, 4, 4, for i = 1..6,
%F A206926 k := k(n) = floor((n-4)/6),
%F A206926 j := j(n) = 1 + (n-4) mod 6,
%F A206926 we get the following formulas:
%F A206926 a(n+6) = 2*a(n) + floor((39+2*q(j))*2^(k+p(j))/63) mod 2, for n>9.
%F A206926 a(n+6) = 2*a(n) + b(k(n),j(n)), for n>9,
%F A206926 where b(k,j) is the 6x6-matrix:
%F A206926   (1 0 1 0 0 0)
%F A206926   (1 1 1 1 1 1)
%F A206926   (0 0 0 0 1 1)
%F A206926   (0 0 1 1 0 0)
%F A206926   (1 1 0 0 1 0)
%F A206926   (1 0 1 0 0 0).
%F A206926 a(n) = floor((39+2*q(j(n)))*2^(k(n)+p(j(n))+5)/63) mod 2^(k(n)+4), for n>4.
%F A206926 a(n) = (floor((39+2*q(j))*2^(6+p(j))/63) mod 32) * 2^(k-1) + (floor((39+2*q(j))*2^(6+p(j))/63) mod 64) * 2^(k mod 6 -1)*(2^(6*floor(k/6)) - 1)/63 + sum_{i=1..(k mod 6 - 1)} 2^(k mod 6 - 1 - i)*(floor((39+2*q(j))*2^(p(j)+i)/63) mod 2), for n>9.
%F A206926 a(n) = floor((39+2*q(j(n)))*2^(p(j(n))+floor((n+26)/6))/63) mod 2^floor((n+20)/6)), for n>4.
%F A206926 With: b(i) = floor((39+2*q(i))*2^(6+p(i))/63) mod 32, this means b(i) = 18, 19, 20, 22, 25, 26, for i = 1..6,
%F A206926 c(i) = (floor((39+2*q(i))*2^(6+p(i))/63) mod 64. This means c(i) = 50, 19, 52, 22, 25, 26, for i = 1..6:
%F A206926 a(n) = b(j)* 2^(k-1) + c(j)*2^(k mod 6 -1)*(2^(6*floor(k/6)) - 1)/63 + sum_{i=1..(k mod 6 - 1)} 2^(k mod 6 - 1 - i)*(floor(c(j)*2^i/63) mod 2), for n>9.
%F A206926 a(n) = floor(16*c(j)*2^floor((n+2)/6)/63) mod (8*2^floor((n+2)/6))), for n>4.
%F A206926 Asymptotic behavior:
%F A206926 a(n) = O(2^(n/6)).
%F A206926 lim inf a(n)/2^floor((n+2)/6) = 8*37/63 = 4.698412….
%F A206926 lim sup a(n)/2^floor((n+2)/6) = 8*52/63 = 6.603174….
%F A206926 lim inf a(n)/2^(n/6) = sqrt(2)*4*52/63 = 4.66914953….
%F A206926 lim sup a(n)/2^(n/6) = 2^(1/3)*8*37/63 = 5.91962906….
%F A206926 G.f. g(x) = x*(2 + 4x + 5x^2 + 6x^3 + 9x^4 + 10x^5 + 7x^6 + 3x^8 + 6x^9 + x^10 + x^13)/(1-2x^6) + (x^16*(1+x^2)(1+x^27) + x^22*(1-x^6)/(1-x) + x^32*(1-x^12)/((1-x^2)(1-x)) + x^47*(1+x^3)/(1-x))/(1-x^36).
%F A206926 Also: g(x) = x*(2 + 5x*(1-x^40) + 4x^2*(1+x^2+x^3-x^6-x^36-x^38-x^42)+ 2x^3*(1-x^3+x^6-x^7+x^39+x^43) - 6x^7*(1+x^4+x^38-x^40) - x^12*(1-x+x^7-x^8-x^10+x^15+x^16+x^18-x^20-x^23-x^24) - 3x^37*(1-x^6))/((1-x)(1+x^2)(1-x^9)(1+x^9)(1+x^18)).
%e A206926 a(2)=4=100_2 has 4 [=A206925(4)] contiguous palindromic bit patterns, this is the minimum value for binary numbers with 3 places. The other numbers with 3 places which meet that minimum value of 4 are 5 and 6.
%e A206926 a(7)=11=1011_2 has 6 [=A206925(11)] contiguous palindromic bit patterns, this is the minimum value for binary numbers with 4 places. The other numbers with 4 places which meet that minimum value of 6 are 9, 10, 12 and 13.
%e A206926 Examples to demonstrate the concatenation rule:
%e A206926 a(4) = 6 = 110_2 = (110010_2 truncated to 3 digits) = (50 truncated to 3 binary digits).
%e A206926 a(35) = 308 = 100110100_2 = (concatenation(100110, 100110) truncated to 9 digits) = (concatenation(38, 38) truncated to 9 binary digits).
%e A206926 a(94) = 307915 = 1001011001011001011_2 = (concatenation(101001, 101001, 101001, 101001) truncated to 19 digits) = (concatenation(41, 41, 41, 41) truncated to 19 binary digits).
%o A206926 (Smalltalk)
%o A206926 A206926
%o A206926 "Calculates a(n)"
%o A206926 | k j p q pArray qArray B n s |
%o A206926 n := self.
%o A206926 pArray := #(5 1 5 2 4 4).
%o A206926 qArray := #(-1 1 1 -1 -1 1).
%o A206926 B := #(2 4 5 6 9 10 11 12 13 18 19 20 22 25 26).
%o A206926 n < 10 ifTrue: [^s := B at: n].
%o A206926 k := (n - 4) // 6.
%o A206926 j := (n - 4) \\ 6 + 1.
%o A206926 p := pArray at: j.
%o A206926 q := qArray at: j.
%o A206926 s := (2 * q + 39) * (2 raisedToInteger: k + p + 5) // 63 \\ (2 raisedToInteger: k + 4).
%o A206926 ^s [by _Hieronymus Fischer_]
%Y A206926 Cf. A006995, A206923, A206924, A206925, A206927, A070939.
%Y A206926 Cf. A217100, A217101.
%K A206926 nonn,base
%O A206926 1,1
%A A206926 _Hieronymus Fischer_, Mar 24 2012; additional comments and formulas Jan 23 2013