{'fraction_non_alphanumeric': 0.05287887828162291, 'fraction_numerical': 0.03602326968973747, 'mean_word_length': 3.7398373983739837, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Exploration of Sequence A000975

Sequence A000975 in the Online Encyclopedia of Integer Sequences (OEIS) starts out 1, 2, 5, 10, 21, 42, 85, ... . As of July 1, 2016, the description in the OEIS lists several characterizations of this sequence and numerous examples of instances where this sequence occurs. It also presents a"not yet proved"result, a conjecture, and an unanswered question concerning this sequence. In this paper we show that all of these proposed results are in fact true.

Multiplying this value by 2 n moves the binary point n places to the right. Rounding down then truncates this expression, yielding A(n), according to Characterization 2, and giving us our next characterization.

Other expressions are
It is an easy exercise to prove that all these characterizations of A(n) are equivalent. We observe that A(n) is even or odd exactly when n is even or odd, respectively.

Occurrences of Sequence A000975
Why do we care about a particular sequence? Often it is because the sequence occurs as the answer to some counting problem. The OEIS lists several places where the values in sequence A000975 occur. Here are some of the more interesting.
Occurrence 1: A(n) is the number of moves needed to solve the n-ring Chinese Rings puzzle (baguenaudier) if the rings are moved one at a time. See, for example, [2, Chapter 1]. Figure 1 shows the state graph for the 4-ring puzzle. The 16 vertices represent the possible states of the puzzle, and two vertices are joined by an edge if the two corresponding states are one move apart. The labels on the vertices denote the positions of the 4 rings in that state, with 0 representing a ring that is off the sliding bar and 1 a ring that is on. It is easy to confirm that the state graph for the n-ring puzzle is a path of length 2 n − 1 from the state labeled 0 n to the state labeled 10 n−1 . The sub-path from state 0 n to state 1 n constitutes an optimal solution of the n-ring puzzle, while the sub-path from state 1 n to state 10 n−1 represents an optimal solution of the (n−1)-ring puzzle. The number of moves in an optimal solution to this puzzle thus satisfies Characterization 3 of sequence A. Occurrence 2: A(n) is the distance between a string of n zeros and a string of n ones in the standard n-bit binary Gray code. Again, see, for example, [2, Chapter 1].
A special case of a problem posed by Donald Knuth [3] and solved by O. P. Lossers [4] provides our next occurrence Occurrence 3: A(n) is the number of ways to partition a set of n+2 people sitting around a circular table into three affinity groups with no two members of a group seated next to each other.
We illustrate this occurrence in Figure 2, showing the A(4) = 10 partitions of six people into three affinity groups. For concreteness we assign the names A and B to the affinity groups of the people at the bottom left and bottom right, respectively. Following [4], we note that there are 2 n −1 strings of length n+2 that start with AB, contain all the letters A, B, and C, and have no two adjacent letters the same. If such a string ends in either B or C, it can be wrapped into a circle to represent an affinity partition of n+2 people. If such a string ends in A, the A can be deleted and the shortened string will represent an affinity partition of n+1 people. The number of affinity partitions of n+2 people is thus another problem that satisfies Characterization 3 of sequence A.
Equivalently, A(n) is the number of different 3-colorings for the vertices of all triangulated (n+2)-gons if the colors of the two base vertices are fixed.

A "not yet proved" property proposed by Antti Karttunen
Antti Karttunen has suggested that our sequence A000975 serves as a link between sequences A0000217 (the triangular numbers) and A048702 (the even length binary palindromes divided by 3) in the OEIS. The triangular numbers, which we represent by T (n), are well-known: T (n) = n(n + 1)/2. The even length binary palindromes, denoted P (n), (sequence A048701 in the OEIS), are less well known. We illustrate the sequence P (n)/3 in Table 2.  Table 2: The sequence of even length binary palindromes divided by 3.
The proposal of Karttunen is that the values A(k) serve as the indices n where T (n) and P (n)/3 agree, as illustrated in Table 3.  Table 3: Common values of T (n) and P (n)/3. Lemma 3.1. For any positive integer n let k = log 2 (n) + 1. Then the binary representation of n is k bits long, and P (n) satisfies where R(n) is the binary reversal of n (sequence A030101 in the OEIS).
Note that Lemmas 4.1 and 4.2 together imply that for all k ≥ 2 there is a run of zeros in sequence B beginning at index n = A(k) + 1.  Proof. We again use induction on k. For k = 2 we consider n such that A(2) + 1 = 3 ≤ n ≤ 3 = 2 2 − 1, or n = 3. Now B(3) = 0 so the claim is true in this case. We now consider the claim for some k > 2, and assume the claim is true for smaller values of k. We know from Lemma 4.2 that B(n) = 0 for n = A(k) + 1, so we need consider only those n such that A(k) + 2 ≤ n ≤ 2 k − 1. If n is even, this implies A(k−1) + 1 ≤ n/2 ≤ 2 k−1 − 1, so by the induction hypothesis we have B(n) = 2B(n/2) = 2(0) = 0.
For all k ≥ 2, then, we have a run of zeros in sequence B(n) starting at A(k) + 1 and ending at 2 k − 1, of length 2 k −1 − A(k) = A(k−1). That these are precisely the runs of record length follows from the fact that B(2 k ) > 0 for all k ≥ 0 and that each of these runs covers two-thirds of the entries between consecutive powers of 2.
We can say more about the number and lengths of runs of zeros in B if we write the index n in binary. Using ω to denote an arbitrary word, or string, over the alphabet A = {0, 1}, we can restate the definition of B(n) as follows: With this characterization, we can compute the value of B(n) by reading the bits of the binary form of the index n from left to right. The initial 1 in the index tells us to start with an initial value of 1. Each time we encounter the bit 0 we double our current value; each time we encounter a 1 we halve the current value, unless the current value is 1, in which case the value becomes and remains 0. For example, suppose n = 18 = 10010 (2) . The left-most bit is 1, and we start with an initial value of 1; B(1) = 1. The next bit is 0, so we double our current value to 2; B(10 (2) ) = 2. The next bit is again 0, so we again double our current value to 4; B(100 (2) ) = 4. The next bit is 1, so we halve our current value back to 2; B(1001 (2) ) = 2. The final bit is again 0, so our current value is doubled to our final value of 4; B(10010 (2) ) = 4. On the other hand, for n = 22 = 10110 (2) , our current value starts at 1 and progresses to 2, back to 1, and then to 0, where it remains; B(1011ω (2) ) = 0 for any bit string ω.
The above observation provides us with a useful way of identifying the indices where B(n) = 0. Lemma 4.5. B(n) = 0 if and only if, when reading the bits of the binary representation of n from left to right, we at some point have encountered more ones than zeros, not counting the initial 1.
We will call a word ω of length 2n over A a Catalan word if it consists of n ones and n zeros, and at no point, reading from left to right, does it contain more ones than zeros. The first few Catalan words are λ (the null word), 01, 0011, 0101, 000111, 001011, 001101, 010011, and 010101. It is well known that the number of Catalan words of length 2n is the nth Catalan number 2n n /(n + 1) for all n ≥ 0. These Catalan numbers, which we denote C(n), form sequence A000108 in the OEIS.
Lemma 4.6. There is a run of zeros in sequence B beginning at index n if any only if the binary representation of n has the form 1ω1 (2) or 1ω10 (2) , where ω is a (perhaps null) Catalan word.
Proof. Suppose n = 1ω1 (2) , with ω a Catalan word. Then n−1 = 1ω0 (2) . By Lemma 4.6 we have B(n) = 0 and B(n−1) = 0. Likewise, if n = 1ω10 (2) then n−1 = 1ω01 (2) , and again we have B(n) = 0 and B(n−1) = 0. In both cases, then, a run of zeros starts at index n. Now suppose n is an index where B(n) = 0 but n is not of the above form. There are three cases to consider.
3. n = 1ω1υ (2) where ω is a Catalan word and υ is a string of zeros of length at least 2. Then n − 1 = 1ω0υ (2) where υ is a string of ones of length at least 2. Once again, B(n−1) = 0.
In all three cases, then, B(n) = 0 but is not the start of a run of zeros.
We conclude that for 2 2k−1 ≤ n < 2 2k , where the binary representation of n contains 2k bits, there are exactly C(k − 1) runs of zeros in sequence B, corresponding to the C(k − 1) Catalan sequences of length 2k − 2. The longest run of zeros in this range is the last one, of length A(k). There are an additional C(k − 1) runs when 2 2k ≤ n < 2 2k+1 and n is 2k + 1 bits long. The longest run here is also the last one, of length A(k + 1).
The Theorem 4.7. The nth record-length run of zeros in sequence B has length A(n) and is run number A155051(n−1). More concisely, A(n) = R(A155051(n−1)).

The Question of N. J. A. Sloane
Continuing in the OEIS listing for sequence A (sequence A0000975) there is a link to an electronic paper Enveloping Operads and Bicoloured Noncrossing Configuration [1] by F. Chapoton and S. Giraudo. In Table 2 of that paper the sequence 1, 2, 5, 10, 21, 42, 85 is listed twice. In the OEIS Sloane asks "Is the sequence in Table 2 this sequence [i.e., sequence A]?". In this section we demonstrate that the answer to this question is "yes." In the somewhat peculiar language of [1], these numbers are the first few coefficients of the colored Hilbert series giving the number of bubbles of increasing arity, first based and then nonbased, of the 2-colored suboperad ∆, ∆ of the 2-colored operad Bubble generated by these two generators of arity 2.
In more simple languge, a bubble is a polygon consisting of a base edge and two or more nonbase edges, with each edge either colored blue or left uncolored. The bubble is based if and only if the base edge is blue. The border of a bubble is its set of nonbase edges. The arity of a bubble is the number of edges in its border.
The based bubbles in the 2-colored suboperad of interest start with a triangle of blue edges. New bubbles are generated by either replacing a blue border edge with two consecutive uncolored edges, or by replacing an uncolored border edge with two consecutive blue edges. Unbased bubbles in this suboperad are the same, but with blue and uncolored interchanged. See Figure 3 for the based bubbles of arity 2, 3, and 4 in this suboperad. These based bubbles of arity n are characterized in [1] as those with the following properties.
1. the number of blue edges in the border is congruent to 2n+1 (mod 3) (and the number of uncolored edges in the border is thus congruent to 2n−1 (mod 3)); and 2. there exist 2 consecutive edges in the border that are either both blue or both uncolored.
In addition, the paper [1] gives 2-variable generating functions (or colored Hilbert series) for based and unbased bubbles in this suboperad. Unfortunately these generating functions are flawed: the numerator of the second term in the first generating function should be z 1 , not z 2 , and the numerator of the second term in the second generating function should be z 2 , not z 1 . We now produce our own count of these bubbles. Proof. Clearly the number of strings of length n with k occurrences of the character b is n k . So we have S(n) + S(n+1) = i n 3i + 2n + 1 + i n + 1 3i + 2(n + 1) + 1 = i n 3i + 2n + 1 + i n 3i + 2n + 2 + n 3i + 2n + 3 The restrictions on the number of b characters and u characters in a string imply that these counts cannot be equal, so an alternating string must be of odd length. If n = 2k +1 the number of b characters must be congruent to 2(2k+1) + 1 ≡ k (mod 3) and the number of u characters must be congruent to 2(2k+1)−1 ≡ k+1 (mod 3), so there is a unique alternating string of length n, consisting of k occurrences of the character b and k+1 occurrences of the character u.
Theorem 5.2. The number of based (or, equivalently, unbased) bubbles of arity n in the indicated suboperad of bubbles is A(n−1).
Proof. Every based bubble in our suboperad can be constructed from a blue base and a border colored according to a string described in Lemma 4. There is one based bubble of arity 2, and the number of based bubbles of arity n plus the number of based bubbles of arity n+1 is 2 n − 1. Thus the number of based bubbles satisfies Characterization 3 from Section 1. The result for unbased bubbles follows by interchanging blue and uncolored in all the proofs.
We conclude by illustrating an alternative approach to this counting problem: a oneto-one correspondence between the number of partitions into affinity groups described in Section 2 and the based bubbles described here. To construct a bubble from an affinity group partition, we traverse the diagram of the affinity group partition counter-clockwise. If an A is followed by a B, a B by a C, or a C by an A, we color the corresponding edge of the bubble blue. If an A is followed by a C, or a B by an A, or a C by a B, we leave the corresponding edge of the bubble uncolored. The correspondence between the 10 affinity group partitions for 6 people and the 10 bubbles of arity 5 is illustrated in Figure 4.
The confirmation that this is indeed always a one-to-one correspondence is left to the reader. Figure 4: A one-to-one correspondence.