A206926 -id:A206926 - cp's OEIS frontend

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

Hieronymus Fischer, Jan 23 2013

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).

			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.

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

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

"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]

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<=lWith 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.

A206927 Minimal numbers of binary length n+1 such that the number of contiguous palindromic bit patterns in the binary representation is minimal.

Original entry on oeis.org

2, 4, 9, 18, 37, 75, 150, 300, 601, 1202, 2405, 4811, 9622, 19244, 38489, 76978, 153957, 307915, 615830, 1231660, 2463321, 4926642, 9853285, 19706571, 39413142, 78826284, 157652569, 315305138, 630610277, 1261220555

Offset: 1

Hieronymus Fischer, Mar 24 2012

Subsequence of A206926.
From left to right, the binary representation of a(n) consists of a concatenation of the bit pattern 100101 (=37). If the number of places is not a multiple of 6, the least significant places are truncated. This leads to a simple linear recurrence.
Example: a(19)=615830=10010110010110_2=concatenate('100101','100101','10')

			a(3)=9=1001_2 has 6 [=A206925(9)] contiguous palindromic bit patterns. This is the minimum value for binary numbers with 4 places and 9 is the least number with this property.
a(9)=601=1001011001_2 has 18 [=A206925(601)] contiguous palindromic bit patterns. This is the minimum value for binary numbers with 10 places and 601 is the least number with this property.

Hieronymus Fischer, Table of n, a(n) for n = 1..500
Index entries for linear recurrences with constant coefficients, signature (2,0,0,0,0,1,-2).

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

a(n) = 37*2^(1+n mod 6)*(2^(6*floor(n/6))-1)/63 + floor(37*2^(n mod 6)/2^5).
a(n) = floor((37*2^(n+1)/63)) mod 2^(n+1).
A206925(a(n)) = 2*floor(log_2(a(n))).
a(n+1) = 2a(n) + floor(37*2^(n+2)/63) mod 2.
G.f.: x*( 2+x^2+x^4+x^5-2*x^6 ) / ( (x-1)*(2*x-1)*(1+x)*(x^2-x+1)*(1+x+x^2) ). - R. J. Mathar, Apr 02 2012
Also, g.f. x*(2+x^2+x^4+x^5-2*x^6)/((1-2*x)*(1-x^6)).

Further formulas added by Hieronymus Fischer, Jan 13 2013

A217100 Greatest number such that the number of contiguous palindromic bit patterns in its binary representation is n, or 0, if there is no such number.

Original entry on oeis.org

1, 2, 3, 6, 0, 13, 14, 26, 29, 52, 58, 105, 116, 211, 233, 422, 467, 845, 934, 1690, 1869, 3380, 3738, 6761, 7476, 13523, 14953, 27046, 29907, 54093, 59814, 108186, 119629, 216372, 239258, 432745, 478516, 865491, 957033, 1730982, 1914067, 3461965, 3828134

Offset: 1

Hieronymus Fischer, Jan 23 2013

The set of numbers which have n contiguous palindromic bit patterns (in their binary representation) is not empty and finite, provided n<>5. Proof: compare A217101 for the proof of existence. The finiteness follows from A206925, since each number p > 2^floor((n+1)/2) has at least A206925(p) >= 2*floor(log_2(p)) > 2*floor((n+1)/2) = n + n mod 2 palindromic substrings. Thus, there is a boundary b <= 2^floor((n+1)/2) such that all numbers > b have more than n palindromic substrings. It follows, that the set of numbers with n palindromic substrings is finite.
a(5)=0, and this is the only zero term. Proof: cf. A217101.
The binary expansion of a(n) has 1 + floor(n/2) digits (n<>5).
a(2n) is the maximal number with n+1 binary digits such that the number of contiguous palindromic bit patterns in the binary representation is minimal (cf. A206926).

			a(3)=3, since 3=11_2 has 3 contiguous palindromic bit patterns, and this is the greatest such number.
a(6)=13. Since 13=1101_2 has 6 contiguous palindromic bit patterns, and this is the greatest such number.
a(8)=26. Since 26=11010_2 has 8 contiguous palindromic bit patterns (1, 1, 0, 1, 0, 11, 101 and 010), and this is the greatest such number.
a(9)=27. Since 17=11011_2 has 9 contiguous palindromic bit patterns (1, 1, 0, 1, 1, 11, 11, 101 and 11011), and this is the greatest such number.

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

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

a(n) = max(k | A206925(k) = n), for n<>5.
A206925(a(n)) = n, n<>5.
a(n) => A217101(n), equality holds for n = 1, 2, 3 and 5, only.
Iteration formula:
a(n+2) = 2*a(n) + floor(52*2^floor((n+4-(-1)^n)/2)/63) mod 2, n>5.
a(n+2) = 2*a(n) + floor(52*2^((2*n+7-3*(-1)^n)/4)/63) mod 2, n>5.
Direct calculation formula:
a(n) = floor(52*2^floor((n+1+(-1)^n)/2)/63) mod 2^floor((n+1+(-1)^n)/2)) + (1-(-1)^n)*2^floor((n-2)/2)), for n>5.
a(n) = floor(52*2^((2*n + 1 + 3*(-1)^n)/4)/63) + (1-(-1)^n)*2^((2*n - 5 + (-1)^n)/4), for n>5.
a(2k) = A206926(6k-9), k>2.
G.f.: x*(1 +2*x +x^2 +2*x^3 -6*x^4 +x^5 +14*x^6 +x^8 +x^11 -x^12 -x^13 -2*x^15 +7*x^16 -14*x^18)/((1-2*x^2)*(1-x^3)*(1+x^3)*(1+x^6)); also:
x*(1 -x +3*x^2 +x*(3+14*x^5)/(1-2*x^2) +x^5*(1+x^3)*(1+x^6+x^8)/((1-2*x^2)*(1-x^12))).

A217101 Minimal number such that the number of contiguous palindromic bit patterns in its binary representation is n, or 0, if there is no such number.

Original entry on oeis.org

1, 2, 3, 4, 0, 7, 8, 18, 17, 15, 16, 42, 33, 68, 31, 32, 133, 65, 267, 130, 63, 64, 260, 129, 341, 258, 447, 127, 128, 682, 257, 1040, 514, 895, 1029, 255, 256, 1919, 513, 2056, 1026, 1791, 2053, 2052, 511, 512, 5376, 1025, 5461, 2050, 3583, 4101, 4100, 8203, 1023, 1024, 8200

Offset: 1

Hieronymus Fischer, Jan 23 2013

The set of numbers which have n contiguous palindromic bit patterns (in their binary representation) is not empty, provided n<>5. Proof: For even n we have A206925(A206927(n/2)) = 2*(n/2) = n. For n=1,3,7,9 we get A206925(k)=n if we set k=1,3,8,17. For odd n>10 we define b(n) := 14*2^((n-9)/2)+A206927((n-9)/2). The b(n) have the binary expansion 11110, 111100, 1111001, 11110010, 111100101, 1111001011, 11110010110, 111100101100, 1111001011001, 11110010110010, 111100101100101, ..., for n=11, 13, 15, 17, ... . Evidently, b(n) is constructed by the concatenation of 111 with repeated bit patterns of 100101 (=37) truncated to 4+(n-9)/2 digits. As a result, the number of contiguous palindromic bit patterns of b(n) is A206925(111_2) + 3 + A206925(A206927((n-9)/2)) = 6 + 3 + n - 9 = n. This proves that there is always a number with n contiguous palindromic bit patterns.

a(5)=0, and this is the only zero term. Proof: The inequality A206925(n) >= 2*floor(log_2(n)) (cf. A206925) implies A206925(n) > 5 for n >= 8. By direct search we find A206925(n)<>5 for n=1..7. Thus, there is no k with A206925(k)=5, which implies a(5)=0.

			a(3) = 3, since 3=11_2 has 3 contiguous palindromic bit patterns, and this is the least such number.
a(6) = 7. Since 7=111_2 has 6 contiguous palindromic bit patterns, and this is the least such number.
a(8) = 18. Since 18=10010_2 has 8 contiguous palindromic bit patterns (1, 0, 0, 1, 0, 00, 010 and 1001), and this is the least such number.
a(9) = 17. Since 17=10001_2 has 9 contiguous palindromic bit patterns (1, 0, 0, 0, 1, 00, 00, 000, and 10001), and this is the least such number.

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

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

a(n) = min(k | A206925(k) = n), for n<>5.
A206925(a(n)) = n, n<>5.
a(n) <= A217100(n), equality holds for n = 1, 2, 3 and 5, only.
a(A000217(n))    = 2^n - 1.
a(A000217(n)+1)  = 2^n.
a(A000217(n)+3)  = 2^(n+1)+1, n>2.
a(A000217(n)+5)  = 2^(n+2)+2, n>4.
a(A000217(n)+6)  = 2^(n+3) - 2^n - 1, n>5.
a(A000217(n)+7)  = 2^(n+3)+5, n>6.
a(A000217(n)+8)  = 2^(n+3)+4, n>7.
a(A000217(n)+9)  = 2^(n+4)+11, n>8.
a(A000217(n)+10) = 2^(n+4) - 2^n - 1, n>9.
a(A000217(n)+11) = 21*2^n, n>10.
a(A000217(n)+12) = 2^(n+4)+8, n>11.
a(A000217(n)+13) = 2^(n+5)+18, n>12.

A217097 Least binary palindrome (cf. A006995) with n binary digits such that the number of contiguous palindromic bit patterns is minimal.

Original entry on oeis.org

0, 3, 5, 9, 17, 45, 73, 153, 297, 717, 1241, 2409, 4841, 13011, 21349, 38505, 76905, 183117, 307817, 632409, 1231465, 2929485, 5060185, 9853545, 19708521, 53261523, 87349605, 157653609, 315300457, 749917005, 1261214313, 2590611033, 5044869737, 11998647117, 20724946521

Offset: 1

Hieronymus Fischer, Feb 10 2013

Subsequence of A217099.

a(n) is the least binary palindrome with n binary digits which meets the minimal possible number of palindromic substrings for that number of digits.

			a(1) = 0, since 0 is the least binary palindrome with 1 palindromic substring (=0) which is the minimum for binary palindromes with 1 place.
a(3) = 5, since 5=101_2 is the least binary palindrome with 4 palindromic substrings which is the minimum for binary palindromes with 3 places.
a(6) = 45, since 45=101101_2 is the least binary palindrome with 11 palindromic substrings which is the minimum for binary palindromes with 6 places.

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

Cf. A006995, A206923, A206924, A206925, A206926, A070939, A217098, 217099, 217100, 217101.

a(n) = min(p | p is binary palindrome with n binary digits and A206925(p) = min(A206925(q) | q is binary palindrome with n binary digits)).
a(n) = A006995(j), where j := j(n) = min(k > A206915(2^(n-1)) | A206924(k) = min(A206925(A006995(i)) | i > A206915(2^(n-1)))).
a(n) = min(p | p is binary palindrome with n binary digits and A206925(p) = 2*(n-1) + floor((n-3)/2)).

A217098 Greatest binary palindrome (cf. A006995) with n binary digits such that the number of contiguous palindromic bit patterns is minimal.

Original entry on oeis.org

1, 3, 5, 9, 27, 51, 107, 165, 403, 843, 1675, 2661, 5709, 13515, 27083, 39513, 108235, 208083, 432843, 682341, 1664211, 3461835, 6922955, 10918245, 23434061, 55390923, 110785227, 161912409, 443134667, 852178131, 1772532427, 2795133285, 6817395923, 14180201163, 28360356555

Offset: 1

Hieronymus Fischer, Jan 23 2013

Subsequence of A217099.

a(n) is the greatest binary palindrome with n binary digits which meets the minimal possible number of palindromic substrings for that number of digits.

			a(1) = 1, since 1 is the largest binary palindrome with 1 palindromic substring (=1) which is the minimum for binary palindromes with 1 place.
a(3) = 5, since 5=101_2 is the largest binary palindrome with 4 palindromic substrings which is the minimum for binary palindromes with 3 places.
a(6) = 51, since 51=110011_2 is the largest binary palindrome with 11 palindromic substrings which is the minimum for binary palindromes with 6 places.

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

Cf. A006995, A206923, A206924, A206925, A206926, A070939, A217097, A217099, A217100, A217101.

a(n) = max(p | p is binary palindrome with n binary digits and A206925(p) = min(A206925(q) | q is binary palindrome with n binary digits)).
a(n) = A006995(j), where j := j(n) = max(k > A206915(2^(n-1)) | A206924(k) = min(A206925(A006995(i)) | i > A206915(2^(n-1)))).
a(n) = max(p | p is binary palindrome with n binary digits and A206925(p) = 2*(n-1) + floor((n-3)/2)).

A348664 Numbers whose binary expansion is not rich.

Original entry on oeis.org

203, 211, 300, 308, 333, 357, 395, 406, 407, 419, 422, 423, 459, 467, 556, 564, 600, 601, 604, 616, 617, 628, 653, 666, 667, 669, 690, 709, 714, 715, 723, 741, 779, 787, 790, 791, 803, 811, 812, 813, 814, 815, 820, 835, 838, 839, 844, 845, 846, 847, 851, 869

Offset: 1

Rémy Sigrist, Oct 28 2021

A word of length k is "rich" if it contains, as contiguous subsequences, exactly k + 1 distinct palindromes (including the empty word).

There are A225681(k)/2 terms with k binary digits.

			For n = 203:
- the binary expansion of 203 is "11001011" and has 8 binary digits,
- we have the following 8 palindromes: "", "0", "1", "00", "11", "010", "101", "1001"
- so 203 is not rich, and belongs to this sequence.
For n = 204:
- the binary expansion of 204 is "11001100" and has 8 binary digits,
- we have the following 9 palindromes: "", "0", "1", "00", "11", "0110", "1001", "001100", "110011"
- so 204 is rich, and does not belong to this sequence.

Rémy Sigrist, Table of n, a(n) for n = 1..10000

Cf. A206926, A216264, A225681, A070939, A137397.

Select[Range@1000,Length@Select[Union[Subsequences[s=IntegerDigits[#,2]]],PalindromeQ]<=Length@s&] (* Giorgos Kalogeropoulos, Oct 29 2021 *)

is(n) = { my (b=binary(n), p=select(w->w==Vecrev(w), setbinop((i,j)->b[i..j],[1..#b]))); #b!=#p }

def ispal(s): return s == s[::-1]
def ok(n):
  s = bin(n)[2:]
  return len(s) >= 1 + len(set(s[i:j] for i in range(len(s)) for j in range(i+1, len(s)+1) if ispal(s[i:j])))
print([k for k in range(870) if ok(k)]) # Michael S. Branicky, Oct 29 2021

{k: A137397(k) <= A070939(k)}. - Michael S. Branicky, Oct 29 2021

Showing 1-9 of 9 results.

The number of contiguous palindromic bit patterns in the binary representation of n is a measure for the grade of symmetry in an abstract arrangement of two kinds of elements (where the number of elements is the number of binary digits, of course).

The minimum value for a(n) is 2*floor(log_2(n)) and will be taken infinitely often (see A206926 and A206927). This means: For a given number of places m there are at least 2*(m-1) palindromic substrings in the binary representation. This lower bound indicates to a certain extent the minimal possible symmetry.

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 (cf. A210926 and A217099).

cp's OEIS Frontend

A206925 Number of contiguous palindromic bit patterns in the binary representation of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

PARI

Python

Smalltalk

Formula

Extensions

A206924 Number of contiguous palindromic bit patterns in the n-th binary palindrome.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Smalltalk

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Smalltalk

Formula

A206927 Minimal numbers of binary length n+1 such that the number of contiguous palindromic bit patterns in the binary representation is minimal.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A217100 Greatest number such that the number of contiguous palindromic bit patterns in its binary representation is n, or 0, if there is no such number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A217101 Minimal number such that the number of contiguous palindromic bit patterns in its binary representation is n, or 0, if there is no such number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A217097 Least binary palindrome (cf. A006995) with n binary digits such that the number of contiguous palindromic bit patterns is minimal.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A217098 Greatest binary palindrome (cf. A006995) with n binary digits such that the number of contiguous palindromic bit patterns is minimal.

Views

Author

Keywords