A217099 Binary palindromes (cf. A006995) such that the number of contiguous palindromic bit patterns is minimal (for a given number of places).

0, 1, 3, 5, 9, 17, 21, 27, 45, 51, 73, 93, 99, 107, 153, 165, 297, 313, 325, 403, 717, 843, 1241, 1421, 1619, 1675, 2409, 2661, 4841, 4953, 5349, 5709, 13011, 13515, 21349, 22861, 26067, 27083, 38505, 39513, 76905, 78937, 85349, 108235, 183117, 208083, 307817, 366413, 415955, 432843, 632409

Offset: 1

Author

Hieronymus Fischer, Jan 23 2013

Keywords

• nonn
• base

Comments

For a given number of places m a binary palindrome has at least 2*(m-1) + floor((m-3)/2) palindromic substrings. To a certain extent, this number indicates the minimal possible grade of symmetry.

a(n) is the least binary palindrome > a(n-1) which have the same number of palindromic substrings than a(n-1). If such a palindrome doesn't exist, a(n) is the least binary palindrome with one additional digit which meets the minimal possible number of palindromic substrings for such increased number of digits.

b_left(n) := floor(a(n)/2^log_2(a(n))) is a term of A206926, if n > 3. More precise, the bit pattern of b_left(n) is contained in the concatenation of the bit patterns of 37 or of 41, provided n > 16.

b_right(n) := a(n) mod (2^(1+log_2(a(n))) is a term of A206926, if n > 6. More precise, the bit pattern of b_right(n) is contained in the concatenation of the bit patterns of 37 or of 41, provided n > 16.

Provided n > 16: The bit pattern of b_left(n) is contained in the continued concatenation of the bit pattern of 37 (or 41, respectively) if and only if the bit pattern of b_ right(n) is contained in the continued concatenation of the bit pattern of 41 (or 37, respectively).

Examples

			a(1) = 0, since 0 is a binary palindrome with 1 palindromic substring (=0) which is the minimum for binary palindromes with 1 place.
a(2) = 1, since 1 is a binary palindrome with 1 palindromic substring (=1) which is the minimum for binary palindromes with 1 place.
a(8) = 27, since 27=11011_2 is a binary palindrome with 9 palindromic substrings which is the minimum for binary palindromes with 5 places.
a(9) = 45, since 45=101101_2 is a binary palindrome with 11 palindromic substrings which is the minimum for binary palindromes with 6 places.
		

Links

• Hieronymus Fischer, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A006995, A206923, A206924, A206925, A206926, A070939.

Programs

Smalltalk

"Calculates a(n) - not optimized.
If the complete array 'answer' is answered instead of a separate term, the next 2 (if d is even) or 4 (if d is odd) terms are calculated simultaneously"
| n min d B k j p q answer |
answer := OrderedCollection new.
n := self.
B := #(0 1 3 5 9 17 21 27 45 51 73 93 99 107 153 165).
n <= 16 ifTrue: [^s := B at: n].
k := (n - 5) // 6 - 1.
j := (n - 5) \\ 6 + 1.
d := 2 * k + 7 + (j // 5).
min := (d - 1) * 2 + ((d - 3) // 2).
0 to: 5
  do:
   [:i |
   p := (6 * k + 4 + i) A206926.
   s := p * (2 raisedToInteger: d // 2).
   q := p // (2 - (j // 5)) reverse: 2.
   s A206925 = min ifTrue: [answer add: (s + q)]].
^answer at: j - (j // 5 * 4) [by Hieronymus Fischer]

Formula

a(n) = min(p > a(n-1) | p is binary palindrome and A206925(p) = A206925(a(n-1))), if this minimum exists, else a(n) = min(p > 2*2^floor(log(a(n-1))) | p is binary palindrome and A206925(p) = min(A206925(q) | q is binary palindrome and q > 2*2^floor(log(a(n-1))))).

a(n) = A006995(j), where j := j(n) = min(k > A206915(a(n-1)) | A206924(k) = A206925(a(n-1)), if this minimum exists, else j(n) = min(k > A206915(2*2^floor(log(a(n-1)))) | A206924(k) = min(a206925(A006995(i)) | i > A206915(2*2^floor(log(a(n-1)))))).

With k := k(n) = floor((n - 5)/6) - 1, j := j(n) = (n - 5) mod 6 + 1, d = 2k+7+floor(j/5),

c = 2*(d-1) + floor((d-3)/2), f(i) = A206926(6k + 4 + i)*2^floor(d/2) + Reversal(floor((A206926(6k + 4 + i))/(2 - floor(j/5)))), for i=0..5, we have

a(n) = b(j - 4*floor(j/5)), where b(m) = f(min(m-1<=i<=5 | A206925(f(i)) = c and f(i) <> b(l) for 1<=l

With m = 1+floor(log_2(a(n)), n > 3:

A206924(k) = 2(m-1) + floor((m-3)/2), where k is that uniquely determined number for which A006995(k) = a(n).

A206924(A206915(a(n))) = 2(m-1) + floor((m-3)/2).

A206924(A206915(a(n))) = 3*floor(log_2(A206915(a(n)))) + 2*floor(log_2(A206915(a(n))/3)) - 2, n > 3.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.