|
| |
|
|
A217099
|
|
Binary palindromes (cf. A006995) such that the number of contiguous palindromic bit patterns is minimal (for a given number of places).
|
|
5
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
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).
|
|
|
LINKS
|
|
|
|
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))))).
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<m)), m = 1..4-2*floor(j/5).
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).
|
|
|
EXAMPLE
|
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.
|
|
|
PROG
|
(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 |
s := p * (2 raisedToInteger: d // 2).
q := p // (2 - (j // 5)) reverse: 2.
s A206925 = min ifTrue: [answer add: (s + q)]].
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,base
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
