Explanation of a solution method for finding terms of A056744, illustrated by its application to A056744(49) Jon E. Schoenfield, May 30 2021 By definition, A056744(49) is the smallest integer k whose binary expansion, taken as a string of bits, contains as substrings the binary expansions of all the integers in 1..49. Let S be the set of ceiling(n/2) integers j in the interval [1+floor(n/2), n], i.e., 25..49. Any integer k whose binary expansion contains as substrings the binary expansions of all integers j in S will necessarily also contain as substrings the binary expansions of all the smaller positive integers as well. However, accounting for the presence of just the substrings for 25..49 will make things simpler. Also note that, since 49 < 25*2, no two integers j in 25..49 can start at the same bit position in the binary expansion of k: the substring for each j in S will have its own starting position. Given the string s(j) of bits in the binary expansion of any positive integer j, define its "prefix" as the substring consisting of all bits to the left of (i.e., more significant than) the 2nd 1-bit of s(j), and define the remainder of the string (i.e., the 2nd 1-bit and all subsequent bits) as the "suffix". E.g., 44 = 101100_2 has '10' as its prefix and '1100' as its suffix. Note that if j is a power of 2, there is no 2nd 1-bit; in this case, we define the entire bit string s(j) as the prefix, and the suffix is the zero-length string. E.g., s(32) = '100000'; the prefix is '100000' and the suffix is '' (the zero-length string). The total number of bits in the prefixes of all ceiling(n/2) numbers in S provides a lower bound L on the number of bits in the expansion of a(n). That bound is achieved by any L-bit integer k for which there exists an arrangement of the ceiling(n/2) substrings in which each bit in k coincides with a bit in the prefix of one of the ceiling(n/2) numbers. This means that the 2nd 1-bit in each substring must coincide with the 1st 1-bit in the next substring. To see how this lower bound works, the following illustration may be helpful. Using n = 11 (so that S contains the six integers 6 through 11), suppose we take an index card, draw on it a square grid with grid lines spaced 1/2 inch apart, and cut out (cutting along the grid lines) six rectangular pieces, each piece 1/2" high: four rectangles that are 2" wide (i.e., four cells) and two rectangles that are 1.5" wide (i.e., three cells). Then, on those six pieces, write one digit (1 or 0) in each cell, using either a red pen or a green pen, as follows: . . <- green digits ->.<- red digits -> . +---+---+---+ | 1 | 1 | 0 | +---+---+---+ . +---+---+---+ | 1 | 1 | 1 | +---+---+---+ . +---+---+---+---+ | 1 | 0 | 0 | 0 | +---+---+---+---+ . +---+---+---+---+ | 1 | 0 | 0 | 1 | +---+---+---+---+ . +---+---+---+---+ | 1 | 0 | 1 | 0 | +---+---+---+---+ . +---+---+---+---+ | 1 | 0 | 1 | 1 | +---+---+---+---+ . . . (Thus, the bits in each prefix are written in green, and the bits in each suffix are written in red.) Now, on a piece of paper, draw a 6" X 0.5" rectangle, divided into 12 half-inch squares; each of these squares represents a bit position in the binary expansion of a 12-bit integer k. We could try arranging the six rectangular pieces within the 6" X 0.5" space, overlapping them as necessary, but never placing a 0 on top of a 1 or vice versa. For any assignment of the six pieces to locations within the 6" X 0.5" space, we could place each of the six pieces in its assigned place, placing them there from left to right, e.g., Place the 1001 at the left: 1001 then place, say, the 1011 1011 (with its first 1 covering the 1001's last 1) which would give us 1001011 thus far; then place the 111: 111 (with its first two 1's covering the 1011's last two 1's) which would give us 10010111 thus far ... and since no two pieces can start at the same bit location (because no two of the substrings '110', '111', '1000', '1001', '1010', and '1011' are identical in their leftmost 3 bits), each successively placed substring must start somewhere to the right of the one placed before it, and none of the six substrings begins with a '0', so each one must be placed so that it does not overlap any part of the previously placed substring's prefix (green bits) -- i.e., its leading '1' bit and all consecutive '0' bits immediately following it, if any -- so no green bit can be overlapped by the placement of any subsequent string. In other words, after all six substrings have been placed, working from left to right, all the green bits must be on top. Since the pieces for 6 (110), 7 (111), 8 (1000), 9 (1001), 10 (1010), and 11 (1011) have 1, 1, 4, 3, 2, and 2 prefix bits, respectively, and 1+1+4+3+2+2 = 13, there are 13 green bits, so there is no way to place all 6 pieces (substrings) in the 12-cell rectangle (representing a 12-bit number). There are multiple 13-bit numbers, however, into whose binary expansions all 6 pieces can be placed: 1001010111000_2 = 4792 1001011101000_2 = 4840 1010111001000_2 = 5576 1011101001000_2 = 5960 Note that each of these ends with '1000'; this is necessary for a 13-bit number containing all six substrings, because there are a total of 13 prefix bits (green bits), and placing the '1000' anywhere other than at the end would mean that some other substring is placed farthest to the right, and every substring except '1000' (the power of 2) has at least one suffix bit (red bit), which would remain uncovered, so the total number of bits in k would have to be at least 14 (13 for the green bits plus at least 1 for the 1 or more red bits that would remain uncovered). The lower bound L on the number of bits in a(n) as described above is then L = Sum_{j=1+floor(n/2)..n} (f(j) - f(j - 2^(f(j)-1))) where f(j) = 1 + floor(log_2(j)) for j > 0, 0 for j = 0. In the summation, the expression f(j) is the number of bits in the binary expansion of j for j > 0, or 0 for j = 0; thus, the expression 2^(f(j)-1) is the value of just the initial 1 in the binary expansion of j, so j - 2^(f(j)-1) is the value that would remain if that initial 1 were removed -- i.e., the value of the suffix -- so f(j) - f(j - 2^(f(j)-1)) is the number of bits in j minus the number of bits in j's suffix (i.e., it's the number of bits in j's prefix). E.g., for j = 44 = 101100_2, the number of bits in the prefix of j is f(44) - f(44 - 2^(f(44)-1)) = 6 - f(44 - 2^(6-1)) = 6 - f(44 - 32) = 6 - f(12) = 6 - 4 = 2. Using the above formula for the lower bound at n = 49, we get L = 56. (There's one 1-bit in each prefix, hence 25 "green" one-bits, and there are a total of 31 0-bits among the prefixes.) For some values of n, however, including 22, 23, and 39..56, the bound described above is not tight. To tighten that lower bound on the number of bits in a(49), let us first consider three things: 1. Given positive integers n and k, every 1-bit in the binary expansion of k begins a substring in the interval [j_min, 2*j_min - 1] where j_min = 1 + floor(n/2), with the exception of each 1-bit (if any) that is so close to the end of the binary expansion of k that the substring starting with that 1-bit and extending to the end of the binary expansion of k is that of a number j < j_min. 2. In searching for the minimum number k whose binary expansion contains as substrings the binary expansion of each j in S, we can disregard any number k whose binary expansion contains more than floor(log_2(n)) 0's in a row: any such k has at least one 0-bit that is wasted, i.e., can be removed from k's binary expansion without losing the substring for any j in S. 3. In searching for the minimum number k whose binary expansion contains as substrings the binary expansion of each j in S, we can also disregard any number k whose binary expansion has any bits that extend beyond the end of the last substring for a number j in S; such bits are wasted, and can be removed as above. (E.g., with n=49, a number k whose binary expansion ends with ...100010000 can be disregarded, since -- after the substring '100010' (34), the next substring starting with a '1' bit is just '10000' (16, which is not in S = {25, 26, 27, ..., 49}), running out of bits at the end of the binary expansion of k. Thus, for any string of bits that starts with a 1, does not have more than floor(log_2(n)) 0's in a row, and does not have any bits beyond the end of the last substring whose value j is in S, we can uniquely characterize that string of bits using the sequence of j values of the substrings that start at its 1-bits and have values j in [j_min, 2*j_min - 1] where j_min = 1 + floor(n/2). (And any string of bits that does not meet those criteria cannot be the binary expansion of a(n).) Suppose for now that we are searching for a(n) for some value of n such that the lower bound L described above, i.e., L = Sum_{j=1+floor(n/2)..n} (f(j) - f(j - 2^(f(j)-1))) where f(j) = 1 + floor(log_2(j)) for j > 0, 0 for j = 0 *is* tight, i.e., there does exist at least one integer k whose binary expansion is exactly L digits in length and contains as substrings the binary expansion of every j in S. Then there are exactly ceiling(n/2) substrings (i.e., values j in S), and each of those substrings appears exactly once in k, so for each j in S, the substring for j has as its predecessor substring (i.e., the one starting at the nearest 1-bit to its left) and its successor substring (i.e., the one starting at the nearest 1-bit to the right of the one at which j starts) two distinct substrings. That is, the substrings for j, its predecessor, and its successor are the substrings for three distinct integers. (The first and last substrings in k are special cases; we could say that the first substring has an empty substring as its predecessor, and that the last substring similarly has an empty substring as its successor.) That all substrings are distinct makes the problem of determining the optimal order of the substrings well-suited to the use of a simple solving chart, similar to the kind used in popular puzzle books offering logic problems that can be solved by deductive reasoning. Let's consider again the case where n=11: the values of j in S are 6, 7, 8, 9, 10, and 11. We could set up a table in which to determine the order in which the substrings appear in a(n) by eliminating possible predecessor/successor pairs. Let's construct a table in which each predecessor substring is represented by a row labeled with that substring's value, each successor substring is represented by a column labeled with that substring's value, and the artificial substrings representing the first substring's predecessor and the last substring's successor are represented by the characters "[" and "]", respectively (suggesting a pair of beginning and ending brackets around a sequence of numbers). To make it easier to see groupings of cells in the table that allow the elimination of some cells by deductive reasoning (this will be more helpful with tables larger than the present one), let's sort the columns according to the lexicographic order of their substrings, and sort the rows according to the lexicographic order of their substrings' suffixes. I.e., for n=11, the columns, from left to right, will be in the order substring | j ----------+--- 1 0 0 0 | 8 1 0 0 1 | 9 1 0 1 0 | 10 1 0 1 1 | 11 1 1 0 | 6 1 1 1 | 7 (sorted in lexicographic order, "left-aligned"; for every n, this will list all numbers j in S that are >= the power of 2 in S, in increasing order, followed by all the remaining numbers j in S, also listed in increasing order), while their rows, from top to bottom, will instead be in the order prefix | suffix | j -------+--------+--- 1 0 0 0| | 8 1 0 0|1 | 9 1 0|1 0 | 10 1|1 0 | 6 1 0|1 1 | 11 1|1 1 | 7 (also sorted in lexicographic order, but by their ["left-aligned"] suffixes). Note that 10 and 6 have the same suffix, as do 11 and 7. The substring for each j and the artificial "[" row will have exactly one successor, and the substring for each j and the artificial "]" column will have exactly one predecessor. So with the rows and columns arranged as specified above, and adding the "[" row and the "]" column for the start and end of the sequence of substrings, respectively, we get the following, prior to populating the body of the table: 1 1 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 -------+--------+----+-------------------- prefix | suffix | j | ] 8 9 10 11 6 7 -------+--------+----+-------------------- | | [ | 1 0 0 0| | 8 | 1 0 0|1 | 9 | 1 0|1 0 | 10 | 1|1 0 | 6 | 1 0|1 1 | 11 | 1|1 1 | 7 | Now, in each cell in the body of the table, i.e., at the intersection of each row and column, insert an asterisk if and only if the substring represented by the row can have as its successor the substring represented by the column, i.e., if and only if the row value's substring's suffix, as far as it extends, agrees with the initial bits of the column value's substring. E.g., for row j = 11 = 1011_2, the suffix 11 agrees with the beginning bits of 6 = 110_2 and 7 = 111_2, but not with the beginning bits of any of the other columns, so we put an asterisk in the j=11 row only in the columns for j=6 and j=7. (For now, we can say that since the artificial "[" row has no bits, it is compatible with every column; similarly, for now, we can say that since the artificial "]" column has no bits, it is compatible with every row. In other words, for now, we'll allow that any substring can be the first or last one in the sequence (i.e., the leftmost or rightmost one in the binary expansion of k). Populating the table this way gives 1 1 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 -------+--------+----+-------------------- prefix | suffix | j | ] 8 9 10 11 6 7 -------+--------+----+-------------------- | | [ | * * * * * * * 1 0 0 0| | 8 | * * * * * * * 1 0 0|1 | 9 | * * * * * * * 1 0|1 0 | 10 | * * * * * 1|1 0 | 6 | * * * * * 1 0|1 1 | 11 | * * * 1|1 1 | 7 | * * * Note, however, that since the substring for each j in S will appear in the binary expansion of k exactly once, there are no duplicate substrings; thus, the substring for j cannot have another substring for j as its own successor (nor as its own predecessor). So we can remove the asterisk from each cell that represents a predecessor/successor pair in which the predecessor (row) and successor (column) have the same j. (Of course, since the rows and columns are not sorted the same way, these cells do not necessarily lie along the main diagonal.) Also, the "[" can't have the "]" as its successor, as this would mean that the sequence of substrings in the binary expansion of k is empty. (It must contain all six actual substrings, i.e., 6 through 11.) So we remove that asterisk as well. This leaves 1 1 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 -------+--------+----+-------------------- prefix | suffix | j | ] 8 9 10 11 6 7 -------+--------+----+-------------------- | | [ | * * * * * * 1 0 0 0| | 8 | * * * * * * 1 0 0|1 | 9 | * * * * * * 1 0|1 0 | 10 | * * * * 1|1 0 | 6 | * * * * * 1 0|1 1 | 11 | * * * 1|1 1 | 7 | * * This would seem to leave a large number of solutions. However, since we are looking for a solution k such that k is a 13-bit number (L=13 is the lower bound on the number of bits in k), and a 13-bit solution requires placement of the substrings so that no "red" (i.e., suffix) bits are left uncovered when they're placed from left to right, the only way to do that is to have the substring for the power of 2 (i.e., 8 = 1000_2) at the right end of the binary expansion of k. I.e., the successor of the 8 must be the "]" (end of sequence). By elimination, then, the 8 cannot have any successor other than the "]", so we can clear the remaining asterisks from that row, and the "]" cannot have any predecessor other than the 8, so we can clear the remaining asterisks from that column. This leaves 1 1 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 -------+--------+----+-------------------- prefix | suffix | j | ] 8 9 10 11 6 7 -------+--------+----+-------------------- | | [ | * * * * * * 1 0 0 0| | 8 | * 1 0 0|1 | 9 | * * * * * 1 0|1 0 | 10 | * * * 1|1 0 | 6 | * * * * 1 0|1 1 | 11 | * * 1|1 1 | 7 | * But then the 7 row shows that 7's only possible successor is the 6, so the 7 is succeeded by the 6, so the 6 cannot have any predecessor other than the 7, so we can clear the other asterisks from that column, which leaves 1 1 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 -------+--------+----+-------------------- prefix | suffix | j | ] 8 9 10 11 6 7 -------+--------+----+-------------------- | | [ | * * * * * 1 0 0 0| | 8 | * 1 0 0|1 | 9 | * * * * 1 0|1 0 | 10 | * * * 1|1 0 | 6 | * * * * 1 0|1 1 | 11 | * 1|1 1 | 7 | * This reveals that the 7 is the only possible successor for the 11. Removing the other asterisks from the 7 column leaves 1 1 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 -------+--------+----+-------------------- prefix | suffix | j | ] 8 9 10 11 6 7 -------+--------+----+-------------------- | | [ | * * * * 1 0 0 0| | 8 | * 1 0 0|1 | 9 | * * * 1 0|1 0 | 10 | * * * 1|1 0 | 6 | * * * * 1 0|1 1 | 11 | * 1|1 1 | 7 | * Note that any solution, written as a sequence of substrings, i.e., [ __, __, __, __, __, __ ], must have 8 as the final substring, and each substring will appear exactly once in the sequence, so the 8 cannot be the first substring, i.e., it can't be the successor on the "[" row. So we have 1 1 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 -------+--------+----+-------------------- prefix | suffix | j | ] 8 9 10 11 6 7 -------+--------+----+-------------------- | | [ | * * * 1 0 0 0| | 8 | * 1 0 0|1 | 9 | * * * 1 0|1 0 | 10 | * * * 1|1 0 | 6 | * * * * 1 0|1 1 | 11 | * 1|1 1 | 7 | * Readers who have done similar logic puzzles before might note that the 6 can't be followed by the 11, because the 11 must be followed by the 7, which must be followed by the 6, which would create a loop (6 -> 11 -> 7 -> 6), which is impossible. However, unlike most of those popular logic puzzles, the problem of finding a 13-bit number k whose binary expansion contains as substrings the binary expansion of each number j in 6..11 is a problem with multiple solutions (four solutions were listed earlier). We want the smallest solution value, i.e., the smallest value of k. Thus, *if* selecting the lexicographically first remaining possible substring as the starting substring does not leave us with a subproblem with no solutions, we want a solution that has that lexicographically first remaining possible substring as the starting substring. If we already happen to know that at least one solution (whether or not it is the minimum k) exists with that choice of starting substring, then we know that the optimal (smallest k) solution must use that choice of starting substring. (We could make use of this fact when we return to the problem for n=49 below, if we have as a known upper bound a solution that uses that lexicographically first remaining possible substring as the starting substring.) If we don't know whether that choice of starting substring leaves any solutions available, we can assume that it does and, if we later find that that assumption necessarily excludes all solutions, then backtrack and remove that choice of starting substring from the ones shown in the table as available. In my experience, however, in applying methods similar to the ones used here and below for a number of values of n, I've never had to backtrack. At this point, we have that the sequence of substrings for any 13-bit solution is [ __, __, __, __, __, 8 ], and the lexicographically first remaining option for the first unknown in the sequence of substrings (hence the one that, unless it yields no solution, must be included in the lexicographically first 13-bit binary expansion among all those for values k that include all substrings in 6..11) is 9. So let's head down this first branch of the search. (As it will turn out, we will not need to backtrack from this decision.) Selecting 9 as the the first substring, i.e., the successor for the "[" row, gives us [ 9, __, __, __, __, 8 ] and reduces the table to 1 1 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 -------+--------+----+-------------------- prefix | suffix | j | ] 8 9 10 11 6 7 -------+--------+----+-------------------- | | [ | * 1 0 0 0| | 8 | * 1 0 0|1 | 9 | * * * 1 0|1 0 | 10 | * * 1|1 0 | 6 | * * * 1 0|1 1 | 11 | * 1|1 1 | 7 | * Also, since there are intervening substrings in the sequence between the 9 and the 8, the 9 cannot have the 8 as its successor, so we have 1 1 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 -------+--------+----+-------------------- prefix | suffix | j | ] 8 9 10 11 6 7 -------+--------+----+-------------------- | | [ | * 1 0 0 0| | 8 | * 1 0 0|1 | 9 | * * 1 0|1 0 | 10 | * * 1|1 0 | 6 | * * * 1 0|1 1 | 11 | * 1|1 1 | 7 | * This still does not appear to be sufficient to yield the single value of k that is the optimum. (Indeed, it allows for two different sequences of substrings.) So, again, if selecting the lexicographically first remaining available choice for the first unknown position in the sequence of substrings does not rule out all solutions, it must be part of the optimal solution; let's try it. Selecting the 10 as the successor of the 9 gives us [ 9, 10, __, __, __, 8 ] and the 10 can't then have the 8 as its successor, so the 10's successor is the 11, so we have [ 9, 10, 11, __, __, 8 ] and updating the table gives 1 1 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 -------+--------+----+-------------------- prefix | suffix | j | ] 8 9 10 11 6 7 -------+--------+----+-------------------- | | [ | * 1 0 0 0| | 8 | * 1 0 0|1 | 9 | * 1 0|1 0 | 10 | * 1|1 0 | 6 | * 1 0|1 1 | 11 | * 1|1 1 | 7 | * which has only one solution: the sequence is [ 9, 10, 11, 7, 6, 8 ], so the substrings are 1001 1010 1011 111 110 1000, and assembling them (with each one starting at the same 1-bit as its predecessor's suffix) gives 1001 1010 1011 111 110 1000, i.e., 1001010111000_2 = 4792 which is the correct value of a(11). Having introduced the above approach for constructing the precedence table, let's return to the more challenging problem of determining a(49). To tighten the lower bound on the number of bits in a(49), consider that, of the 25 integers in 25..49, there are eleven whose suffixes start with 1,1,... -- i.e., 28 (11100), 29 (11101), 30 (11110), 31 (11111), 35 (100011), 38 (100110), 39 (100111), 44 (101100), 45 (101101), 46 (101110), 47 (101111) -- but there are only nine whose entire substrings start with bits 1,1,... -- i.e., 48 (110000), 49 (110001), 25 (11001), 26 (11010), 27 (11011), 28 (11100), 29 (11101), 30 (11110), and 31 (11111). Consequently, given exactly 25 substrings, one for each integer in 25..49, at least 11 - 9 = 2 of those 11 substrings whose suffixes start with 1,1,... will not have the first 1 in their suffix covered by the prefix of the next substring. However, as shown above, a(n) must be an integer k whose binary expansion is a string of bits that can be uniquely characterized using the sequence of j values of the substrings that start at its 1-bits and have values j in [j_min, 2*j_min - 1] where j_min = 1 + floor(n/2). Note, however, that some of those j values may be duplicates. Indeed, in a situation like the one here, in which the number of integers j in S whose substrings have their suffix beginning with 1,1,... exceeds the number of integers j in S whose substrings begin with 1,1,..., if we place *only one* instance of the substring for each of the ceiling(n/2) numbers j in S, any solution will necessarily include at least one 1-bit in a suffix that is not covered by the 1-bit at the beginning of the successor substring (i.e., any solution will necessarily include at least one "red" 1-bit). In the present case, there must be at least 11-9 = 2 "red" 1-bits, and all the "green" 1-bits (i.e., the initial 1-bit in each of the ceiling(n/2) substrings) must also be present, so the number of 1-bits in a(49) will be at least ceiling(49/2) + 2 = 27. In addition to the above 11 > 9 problem, consider also that, of the 25 integers in 25..49, there are five whose suffixes start with bits 1,1,1,... -- i.e., 30 (11110), 31 (11111), 39 (100111), 46 (101110), and 47 (101111) -- but there are only four whose entire substrings start with bits 1,1,1,... -- i.e., 28 (11100), 29 (11101), 30 (11110), and 31 (11111). So if we want to account for *every* substring in [j_min, 2*j_min - 1], i.e., [25, 49] that starts at a 1-bit in the binary expansion of a yet-unknown number k whose binary expansion includes as substrings the binary expansion of every j in S, we will need to account for more than the ceiling(n/2) = 25 distinct substrings in 25..49; we will also need at least two duplicate substrings that start with 1,1,... but have suffixes that do not, so those two substrings must start with 1,1,0,..., and we will need at least 5 - 4 = 1 duplicate substring that starts with 1,1,1,... but has a suffix that does not, so that substring must start with 1,1,1,0,... Clearly, the set of two or more duplicates starting with 1,1,0,... and the set of one or more duplicates starting with 1,1,1,0,... are disjoint. We need at least two duplicates starting with 1,1,0,..., so they must be duplicates of j values from the set {25,26,27} (24 is not in S), and we need at least one duplicate starting with 1,1,1,0,..., so the duplicate(s) in that set must be of j values from the set {28,28}. Since these three or more duplicates and all the original 25 substrings must start at distinct 1-bits in the binary expansion of a(49), that binary expansion must have at least ceiling(n/2)+3 = 28 1's. The lower bound on its number of 0's is still the number of 0's in the prefixes (and none of the duplicates to be added have any 0's in their prefixes; since each starts with 1,1,..., each one's prefix consists only of a single 1-bit). So we've strengthened the lower bound on the number of bits in a(49) from 56 to 59. *If* there exists a 59-bit solution for n=49, then it must have exactly 28 1-bits (since it must have *at least* 28, as shown above), and hence exactly 31 0-bits (i.e., all the 0-bits are "green"); thus, there cannot be any "red" (suffix) 0-bits in the solution. Since this is the case, every 0-bit in any suffix must be covered by a 0-bit in a successor substring's prefix. I *think* it follows from this (I would appreciate confirmation, or a better way of proving this conclusion!) that the substring for j=32 must be the last of the 25+3 = 28 substrings whose values are integers in [25, 49] in the binary expansion of a(49). So we're looking for a solution that has the substring for j=32 last, has one substring for each integer j from 25 through 49, and also has two duplicate substrings that are for unknown values of j, both in {25,26,27} (maybe both from the same one of those three numbers, but maybe not), and also one duplicate substring for an unknown value of j in {28,29}. Let's call the two duplicate substrings of unknown value(s) in {25,26,27} "D1" and "D2", and call the duplicate substring of unknown value in {28,29} "D3". Without loss of generality, we can distinguish D1 from D2 by specifying that D1's value does not exceed that of D2. Also, without loss of generality, we can specify that each of the three duplicates occurs later in the sequence of 28 substrings than does the "original" (non-duplicate) substring of the same value. Additionally, *if* it turns out that D1 and D2 have the same value, then we can distinguish between them by specifying that D1 appears before D2 in the sequence of 28 substrings. (As it turns out, in the steps described below, not all of this specificity regarding the duplicates is needed, but I think it has been helpful for some other values of n where two or more duplicates had to be present.) We can modify the table solution approach used above for n=11 by including rows and columns for all integers in [25, 49] plus a row and column for each of the three duplicates. That the value of those duplicates is not yet known adds some complexity to the problem. This time, the table originally looks like this: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 ? ? 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 ? ? 0 0 1 0 1 ? 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 -----------+----------+----+-------------------------------------------------------------------------------------- prefix | suffix | j | ] 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 D1 D2 48 49 25 26 27 D3 28 29 30 31 -----------+----------+----+-------------------------------------------------------------------------------------- | | [ | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 1 0 0 0 0 0| | 32 | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 1 0 0 0 0|1 | 33 | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 1 0 0 0|1 0 | 34 | * * * * * * * * * * * * * * * * * 1|1 0 ? ? | D1 | * * * * * * * * * * * * * * * * * 1|1 0 ? ? | D2 | * * * * * * * * * * * * * * * * * 1 0 0|1 0 0 | 36 | * * * * * * * * * 1 0|1 0 0 0 | 40 | * * * * * 1|1 0 0 0 0 | 48 | * * * 1|1 0 0 0 1 | 49 | * * * 1 0|1 0 0 1 | 41 | * * * * * 1|1 0 0 1 | 25 | * * * * * 1 0 0|1 0 1 | 37 | * * * * * * * * * 1 0|1 0 1 0 | 42 | * * * * * 1|1 0 1 0 | 26 | * * * * * 1 0|1 0 1 1 | 43 | * * * * * 1|1 0 1 1 | 27 | * * * * * 1 0 0 0|1 1 | 35 | * * * * * * * * * * * * * 1 0 0|1 1 0 | 38 | * * * * * * * * 1|1 1 0 ? | D3 | * * * * * * * * 1 0|1 1 0 0 | 44 | * * * * * * 1|1 1 0 0 | 28 | * * * * * * 1 0|1 1 0 1 | 45 | * * * * * 1|1 1 0 1 | 29 | * * * * * 1 0 0|1 1 1 | 39 | * * * * * * 1 0|1 1 1 0 | 46 | * * * * 1|1 1 1 0 | 30 | * * * * 1 0|1 1 1 1 | 47 | * * * 1|1 1 1 1 | 31 | * * * Note that the list of allowable successors for 38 is the same as for D3 -- their rows contain the same set of 7 asterisks. (At this point, D3 is known to be either 28 or 29, so its suffix begins with 1,1,0,... but the next bit is not yet known. The suffix of 38 is just 1,1,0.) Given the above argument that the substring for j=32 must be the last, the sequence of substring values is [ __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, 32] and given that no substring can be its own successor, and that the 32 cannot be the first substring (since it's the last), the table becomes 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 ? ? 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 ? ? 0 0 1 0 1 ? 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 -----------+----------+----+-------------------------------------------------------------------------------------- prefix | suffix | j | ] 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 D1 D2 48 49 25 26 27 D3 28 29 30 31 -----------+----------+----+-------------------------------------------------------------------------------------- | | [ | * * * * * * * * * * * * * * * * * * * * * * * * * * * 1 0 0 0 0 0| | 32 | * 1 0 0 0 0|1 | 33 | * * * * * * * * * * * * * * * * * * * * * * * * * * * 1 0 0 0|1 0 | 34 | * * * * * * * * * * * * * * * 1|1 0 ? ? | D1 | * * * * * * * * * * * * * * * * 1|1 0 ? ? | D2 | * * * * * * * * * * * * * * * * 1 0 0|1 0 0 | 36 | * * * * * * * 1 0|1 0 0 0 | 40 | * * * * 1|1 0 0 0 0 | 48 | * * 1|1 0 0 0 1 | 49 | * * 1 0|1 0 0 1 | 41 | * * * * 1|1 0 0 1 | 25 | * * * * 1 0 0|1 0 1 | 37 | * * * * * * * * 1 0|1 0 1 0 | 42 | * * * 1|1 0 1 0 | 26 | * * * * 1 0|1 0 1 1 | 43 | * * * * 1|1 0 1 1 | 27 | * * * * 1 0 0 0|1 1 | 35 | * * * * * * * * * * * * 1 0 0|1 1 0 | 38 | * * * * * * * 1|1 1 0 ? | D3 | * * * * * * * 1 0|1 1 0 0 | 44 | * * * * * 1|1 1 0 0 | 28 | * * * * * 1 0|1 1 0 1 | 45 | * * * * 1|1 1 0 1 | 29 | * * * * 1 0 0|1 1 1 | 39 | * * * * * 1 0|1 1 1 0 | 46 | * * * 1|1 1 1 0 | 30 | * * * 1 0|1 1 1 1 | 47 | * * 1|1 1 1 1 | 31 | * So the 31's successor is the 30, so the 47's successor is the 31, so the predecessors of the D3, 28, and 29 are the 39, 46, and 30, in some order, and we have [ __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, 32] and the table becomes 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 ? ? 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 ? ? 0 0 1 0 1 ? 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 -----------+----------+----+-------------------------------------------------------------------------------------- prefix | suffix | j | ] 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 D1 D2 48 49 25 26 27 D3 28 29 30 31 -----------+----------+----+-------------------------------------------------------------------------------------- | | [ | * * * * * * * * * * * * * * * * * * * * * * 1 0 0 0 0 0| | 32 | * 1 0 0 0 0|1 | 33 | * * * * * * * * * * * * * * * * * * * * * * 1 0 0 0|1 0 | 34 | * * * * * * * * * * * * * * * 1|1 0 ? ? | D1 | * * * * * * * * * * * * * * * * 1|1 0 ? ? | D2 | * * * * * * * * * * * * * * * * 1 0 0|1 0 0 | 36 | * * * * * * * 1 0|1 0 0 0 | 40 | * * * * 1|1 0 0 0 0 | 48 | * * 1|1 0 0 0 1 | 49 | * * 1 0|1 0 0 1 | 41 | * * * * 1|1 0 0 1 | 25 | * * * * 1 0 0|1 0 1 | 37 | * * * * * * * * 1 0|1 0 1 0 | 42 | * * * 1|1 0 1 0 | 26 | * * * * 1 0|1 0 1 1 | 43 | * * * * 1|1 0 1 1 | 27 | * * * * 1 0 0 0|1 1 | 35 | * * * * * * * 1 0 0|1 1 0 | 38 | * * * * * * * 1|1 1 0 ? | D3 | * * * * * * * 1 0|1 1 0 0 | 44 | * * * * * 1|1 1 0 0 | 28 | * * * * * 1 0|1 1 0 1 | 45 | * * * * 1|1 1 0 1 | 29 | * * * * 1 0 0|1 1 1 | 39 | * * * 1 0|1 1 1 0 | 46 | * * * 1|1 1 1 0 | 30 | * * * 1 0|1 1 1 1 | 47 | * 1|1 1 1 1 | 31 | * The sequence of 28 substrings that uniquely defines the binary expansion of a(49) either begins with the lexicographically first option listed as possible in the table, i.e., the first possible successor remaining on the "[" row, which is 33, or it doesn't. If it doesn't, then there is no solution that begins with 33, and when we find that out we can backtrack to here and update the table to show that 33 cannot be the successor of the "[". But if it does, then making that assumption will allow us to simplify the table and make progress toward the solution. (Spoiler alert: no backtracking will be necessary for this value of n.) :-) So take that first path: assume that the 33 is the first substring in the sequence. Then we have [ 33, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, 32] and the table becomes 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 ? ? 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 ? ? 0 0 1 0 1 ? 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 -----------+----------+----+-------------------------------------------------------------------------------------- prefix | suffix | j | ] 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 D1 D2 48 49 25 26 27 D3 28 29 30 31 -----------+----------+----+-------------------------------------------------------------------------------------- | | [ | * 1 0 0 0 0 0| | 32 | * 1 0 0 0 0|1 | 33 | * * * * * * * * * * * * * * * * * * * * * * 1 0 0 0|1 0 | 34 | * * * * * * * * * * * * * * 1|1 0 ? ? | D1 | * * * * * * * * * * * * * * * 1|1 0 ? ? | D2 | * * * * * * * * * * * * * * * 1 0 0|1 0 0 | 36 | * * * * * * 1 0|1 0 0 0 | 40 | * * * 1|1 0 0 0 0 | 48 | * 1|1 0 0 0 1 | 49 | * * 1 0|1 0 0 1 | 41 | * * * * 1|1 0 0 1 | 25 | * * * * 1 0 0|1 0 1 | 37 | * * * * * * * * 1 0|1 0 1 0 | 42 | * * * 1|1 0 1 0 | 26 | * * * * 1 0|1 0 1 1 | 43 | * * * * 1|1 0 1 1 | 27 | * * * * 1 0 0 0|1 1 | 35 | * * * * * * * 1 0 0|1 1 0 | 38 | * * * * * * * 1|1 1 0 ? | D3 | * * * * * * * 1 0|1 1 0 0 | 44 | * * * * * 1|1 1 0 0 | 28 | * * * * * 1 0|1 1 0 1 | 45 | * * * * 1|1 1 0 1 | 29 | * * * * 1 0 0|1 1 1 | 39 | * * * 1 0|1 1 1 0 | 46 | * * * 1|1 1 1 0 | 30 | * * * 1 0|1 1 1 1 | 47 | * 1|1 1 1 1 | 31 | * so the 48's successor must be the 32, so we have [ 33, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, 48, 32] so the 33's successor can't be the 48, so the table becomes 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 ? ? 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 ? ? 0 0 1 0 1 ? 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 -----------+----------+----+-------------------------------------------------------------------------------------- prefix | suffix | j | ] 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 D1 D2 48 49 25 26 27 D3 28 29 30 31 -----------+----------+----+-------------------------------------------------------------------------------------- | | [ | * 1 0 0 0 0 0| | 32 | * 1 0 0 0 0|1 | 33 | * * * * * * * * * * * * * * * * * * * * 1 0 0 0|1 0 | 34 | * * * * * * * * * * * * * 1|1 0 ? ? | D1 | * * * * * * * * * * * * * * 1|1 0 ? ? | D2 | * * * * * * * * * * * * * * 1 0 0|1 0 0 | 36 | * * * * * 1 0|1 0 0 0 | 40 | * * 1|1 0 0 0 0 | 48 | * 1|1 0 0 0 1 | 49 | * * 1 0|1 0 0 1 | 41 | * * * * 1|1 0 0 1 | 25 | * * * * 1 0 0|1 0 1 | 37 | * * * * * * * * 1 0|1 0 1 0 | 42 | * * * 1|1 0 1 0 | 26 | * * * * 1 0|1 0 1 1 | 43 | * * * * 1|1 0 1 1 | 27 | * * * * 1 0 0 0|1 1 | 35 | * * * * * * * 1 0 0|1 1 0 | 38 | * * * * * * * 1|1 1 0 ? | D3 | * * * * * * * 1 0|1 1 0 0 | 44 | * * * * * 1|1 1 0 0 | 28 | * * * * * 1 0|1 1 0 1 | 45 | * * * * 1|1 1 0 1 | 29 | * * * * 1 0 0|1 1 1 | 39 | * * * 1 0|1 1 1 0 | 46 | * * * 1|1 1 1 0 | 30 | * * * 1 0|1 1 1 1 | 47 | * 1|1 1 1 1 | 31 | * so the successors of the 40 and the 49 must be the 34 and the 35, in some order, so the table updates to 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 ? ? 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 ? ? 0 0 1 0 1 ? 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 -----------+----------+----+-------------------------------------------------------------------------------------- prefix | suffix | j | ] 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 D1 D2 48 49 25 26 27 D3 28 29 30 31 -----------+----------+----+-------------------------------------------------------------------------------------- | | [ | * 1 0 0 0 0 0| | 32 | * 1 0 0 0 0|1 | 33 | * * * * * * * * * * * * * * * * * * 1 0 0 0|1 0 | 34 | * * * * * * * * * * * * 1|1 0 ? ? | D1 | * * * * * * * * * * * * 1|1 0 ? ? | D2 | * * * * * * * * * * * * 1 0 0|1 0 0 | 36 | * * * 1 0|1 0 0 0 | 40 | * * 1|1 0 0 0 0 | 48 | * 1|1 0 0 0 1 | 49 | * * 1 0|1 0 0 1 | 41 | * * * * 1|1 0 0 1 | 25 | * * * * 1 0 0|1 0 1 | 37 | * * * * * * * * 1 0|1 0 1 0 | 42 | * * * 1|1 0 1 0 | 26 | * * * * 1 0|1 0 1 1 | 43 | * * * * 1|1 0 1 1 | 27 | * * * * 1 0 0 0|1 1 | 35 | * * * * * * * 1 0 0|1 1 0 | 38 | * * * * * * * 1|1 1 0 ? | D3 | * * * * * * * 1 0|1 1 0 0 | 44 | * * * * * 1|1 1 0 0 | 28 | * * * * * 1 0|1 1 0 1 | 45 | * * * * 1|1 1 0 1 | 29 | * * * * 1 0 0|1 1 1 | 39 | * * * 1 0|1 1 1 0 | 46 | * * * 1|1 1 1 0 | 30 | * * * 1 0|1 1 1 1 | 47 | * 1|1 1 1 1 | 31 | * At this point, we could again assume that there's a solution in which the first remaining available option is chosen as the first unknown substring in the sequence, and thus either move closer to the solution or eventually find that there's no solution on the branch of the search. However, to try to keep this long file from getting much longer, I'll say that I tried this and found that choosing the lexicographically first available remaining option *now* shown in the table for each of the next four steps does not rule out a solution. I.e., we now have [ 33, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, 48, 32] and the table - shows the lexicographically first remaining available choice for the 33's successor as the 36, - shows the lexicographically first remaining available choice for the 36's successor as the 37, - shows the lexicographically first remaining available choice for the 37's successor as the 40, and - shows the lexicographically first remaining available choice for the 40's successor as the 34 so let's go ahead and make all those moves: this gives [ 33, 36, 37, 40, 34, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, 48, 32] and the table simplifies to 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 ? ? 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 ? ? 0 0 1 0 1 ? 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 -----------+----------+----+-------------------------------------------------------------------------------------- prefix | suffix | j | ] 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 D1 D2 48 49 25 26 27 D3 28 29 30 31 -----------+----------+----+-------------------------------------------------------------------------------------- | | [ | * 1 0 0 0 0 0| | 32 | * 1 0 0 0 0|1 | 33 | * 1 0 0 0|1 0 | 34 | * * * * * * * * * 1|1 0 ? ? | D1 | * * * * * * * * * 1|1 0 ? ? | D2 | * * * * * * * * * 1 0 0|1 0 0 | 36 | * 1 0|1 0 0 0 | 40 | * 1|1 0 0 0 0 | 48 | * 1|1 0 0 0 1 | 49 | * 1 0|1 0 0 1 | 41 | * * 1|1 0 0 1 | 25 | * * 1 0 0|1 0 1 | 37 | * 1 0|1 0 1 0 | 42 | * * 1|1 0 1 0 | 26 | * * * 1 0|1 0 1 1 | 43 | * * * * 1|1 0 1 1 | 27 | * * * * 1 0 0 0|1 1 | 35 | * * * * * * * 1 0 0|1 1 0 | 38 | * * * * * * * 1|1 1 0 ? | D3 | * * * * * * * 1 0|1 1 0 0 | 44 | * * * * * 1|1 1 0 0 | 28 | * * * * * 1 0|1 1 0 1 | 45 | * * * * 1|1 1 0 1 | 29 | * * * * 1 0 0|1 1 1 | 39 | * * * 1 0|1 1 1 0 | 46 | * * * 1|1 1 1 0 | 30 | * * * 1 0|1 1 1 1 | 47 | * 1|1 1 1 1 | 31 | * at which point it's apparent that the successors of the 41 and the 25 are the 38 and the 39, in some order, so the table simplifies to 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 ? ? 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 ? ? 0 0 1 0 1 ? 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 -----------+----------+----+-------------------------------------------------------------------------------------- prefix | suffix | j | ] 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 D1 D2 48 49 25 26 27 D3 28 29 30 31 -----------+----------+----+-------------------------------------------------------------------------------------- | | [ | * 1 0 0 0 0 0| | 32 | * 1 0 0 0 0|1 | 33 | * 1 0 0 0|1 0 | 34 | * * * * * * * 1|1 0 ? ? | D1 | * * * * * * * 1|1 0 ? ? | D2 | * * * * * * * 1 0 0|1 0 0 | 36 | * 1 0|1 0 0 0 | 40 | * 1|1 0 0 0 0 | 48 | * 1|1 0 0 0 1 | 49 | * 1 0|1 0 0 1 | 41 | * * 1|1 0 0 1 | 25 | * * 1 0 0|1 0 1 | 37 | * 1 0|1 0 1 0 | 42 | * * 1|1 0 1 0 | 26 | * * * 1 0|1 0 1 1 | 43 | * * * * 1|1 0 1 1 | 27 | * * * * 1 0 0 0|1 1 | 35 | * * * * * * * 1 0 0|1 1 0 | 38 | * * * * * * * 1|1 1 0 ? | D3 | * * * * * * * 1 0|1 1 0 0 | 44 | * * * * * 1|1 1 0 0 | 28 | * * * * * 1 0|1 1 0 1 | 45 | * * * * 1|1 1 0 1 | 29 | * * * * 1 0 0|1 1 1 | 39 | * * * 1 0|1 1 1 0 | 46 | * * * 1|1 1 1 0 | 30 | * * * 1 0|1 1 1 1 | 47 | * 1|1 1 1 1 | 31 | * Note that every remaining available successor for D1 and D2 now starts with 1,0,1,...; this means that the first unknown bit in the suffixes of D1 and D2 is a 1. (If either of them had a suffix beginning with 1,0,0, it would have no available options left for its successor.) So D1 and D2 both have substrings of the form 1,1,0,1,?, so neither D1 nor D2 is a 25; they're both 26's, or both 27's, or there's one of each. Since we now know that D1 and D2 are both from {26,27}, we can rule out both 44 and 28 as predecessors for them. So updating the table gives 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 ? ? 0 0 1 0 1 ? 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 -----------+----------+----+-------------------------------------------------------------------------------------- prefix | suffix | j | ] 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 D1 D2 48 49 25 26 27 D3 28 29 30 31 -----------+----------+----+-------------------------------------------------------------------------------------- | | [ | * 1 0 0 0 0 0| | 32 | * 1 0 0 0 0|1 | 33 | * 1 0 0 0|1 0 | 34 | * * * * * * * 1|1 0 1 ? | D1 | * * * * * * * 1|1 0 1 ? | D2 | * * * * * * * 1 0 0|1 0 0 | 36 | * 1 0|1 0 0 0 | 40 | * 1|1 0 0 0 0 | 48 | * 1|1 0 0 0 1 | 49 | * 1 0|1 0 0 1 | 41 | * * 1|1 0 0 1 | 25 | * * 1 0 0|1 0 1 | 37 | * 1 0|1 0 1 0 | 42 | * * 1|1 0 1 0 | 26 | * * * 1 0|1 0 1 1 | 43 | * * * * 1|1 0 1 1 | 27 | * * * * 1 0 0 0|1 1 | 35 | * * * * * * * 1 0 0|1 1 0 | 38 | * * * * * * * 1|1 1 0 ? | D3 | * * * * * * * 1 0|1 1 0 0 | 44 | * * * 1|1 1 0 0 | 28 | * * * 1 0|1 1 0 1 | 45 | * * * * 1|1 1 0 1 | 29 | * * * * 1 0 0|1 1 1 | 39 | * * * 1 0|1 1 1 0 | 46 | * * * 1|1 1 1 0 | 30 | * * * 1 0|1 1 1 1 | 47 | * 1|1 1 1 1 | 31 | * As always, choosing the lexicographically first available successor as the first unknown substring in the sequence of substrings will either (eventually) prove to leave no solutions and allow us to rule out that branch, or will keep us on the path to a(49). Let's take that next step, selecting the 41 as the successor to the 34. This gives [ 33, 36, 37, 40, 34, 41, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, 48, 32] and the table simplifies to 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 ? ? 0 0 1 0 1 ? 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 -----------+----------+----+-------------------------------------------------------------------------------------- prefix | suffix | j | ] 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 D1 D2 48 49 25 26 27 D3 28 29 30 31 -----------+----------+----+-------------------------------------------------------------------------------------- | | [ | * 1 0 0 0 0 0| | 32 | * 1 0 0 0 0|1 | 33 | * 1 0 0 0|1 0 | 34 | * 1|1 0 1 ? | D1 | * * * * * * 1|1 0 1 ? | D2 | * * * * * * 1 0 0|1 0 0 | 36 | * 1 0|1 0 0 0 | 40 | * 1|1 0 0 0 0 | 48 | * 1|1 0 0 0 1 | 49 | * 1 0|1 0 0 1 | 41 | * * 1|1 0 0 1 | 25 | * * 1 0 0|1 0 1 | 37 | * 1 0|1 0 1 0 | 42 | * 1|1 0 1 0 | 26 | * * 1 0|1 0 1 1 | 43 | * * * * 1|1 0 1 1 | 27 | * * * * 1 0 0 0|1 1 | 35 | * * * * * * * 1 0 0|1 1 0 | 38 | * * * * * * * 1|1 1 0 ? | D3 | * * * * * * * 1 0|1 1 0 0 | 44 | * * * 1|1 1 0 0 | 28 | * * * 1 0|1 1 0 1 | 45 | * * * * 1|1 1 0 1 | 29 | * * * * 1 0 0|1 1 1 | 39 | * * * 1 0|1 1 1 0 | 46 | * * * 1|1 1 1 0 | 30 | * * * 1 0|1 1 1 1 | 47 | * 1|1 1 1 1 | 31 | * so the 42's successor is the 43, and thus the 26's successor is the 42, and updating the table shows that the only possible successors left for the D1 and the D2 are in {44,45,46,47}, each of which starts with 1,0,1,1,..., so the remaining unknown bit in the suffix of D1 is a 1, and the same is true of D2, so D1 and D2 are both duplicate 27's, and the table updates to 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 0 1 ? 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 -----------+----------+----+-------------------------------------------------------------------------------------- prefix | suffix | j | ] 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 D1 D2 48 49 25 26 27 D3 28 29 30 31 -----------+----------+----+-------------------------------------------------------------------------------------- | | [ | * 1 0 0 0 0 0| | 32 | * 1 0 0 0 0|1 | 33 | * 1 0 0 0|1 0 | 34 | * 1|1 0 1 1 | D1 | * * * * 1|1 0 1 1 | D2 | * * * * 1 0 0|1 0 0 | 36 | * 1 0|1 0 0 0 | 40 | * 1|1 0 0 0 0 | 48 | * 1|1 0 0 0 1 | 49 | * 1 0|1 0 0 1 | 41 | * * 1|1 0 0 1 | 25 | * * 1 0 0|1 0 1 | 37 | * 1 0|1 0 1 0 | 42 | * 1|1 0 1 0 | 26 | * 1 0|1 0 1 1 | 43 | * * * * 1|1 0 1 1 | 27 | * * * * 1 0 0 0|1 1 | 35 | * * * * * * * 1 0 0|1 1 0 | 38 | * * * * * * * 1|1 1 0 ? | D3 | * * * * * * * 1 0|1 1 0 0 | 44 | * * * 1|1 1 0 0 | 28 | * * * 1 0|1 1 0 1 | 45 | * * * * 1|1 1 0 1 | 29 | * * * * 1 0 0|1 1 1 | 39 | * * * 1 0|1 1 1 0 | 46 | * * * 1|1 1 1 0 | 30 | * * * 1 0|1 1 1 1 | 47 | * 1|1 1 1 1 | 31 | * Once again, choosing the lexicographically first available successor as the first unknown substring in the sequence of substrings will either (eventually) prove to leave no solutions and allow us to rule out that branch, or keep us on the path to a(49). Let's take that next step, selecting the 38 as the successor to the 41. This gives [ 33, 36, 37, 40, 34, 41, 38, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, 48, 32] and the 38 can't be succeeded by the 48, so the table simplifies to 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 0 1 ? 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 -----------+----------+----+-------------------------------------------------------------------------------------- prefix | suffix | j | ] 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 D1 D2 48 49 25 26 27 D3 28 29 30 31 -----------+----------+----+-------------------------------------------------------------------------------------- | | [ | * 1 0 0 0 0 0| | 32 | * 1 0 0 0 0|1 | 33 | * 1 0 0 0|1 0 | 34 | * 1|1 0 1 1 | D1 | * * * * 1|1 0 1 1 | D2 | * * * * 1 0 0|1 0 0 | 36 | * 1 0|1 0 0 0 | 40 | * 1|1 0 0 0 0 | 48 | * 1|1 0 0 0 1 | 49 | * 1 0|1 0 0 1 | 41 | * 1|1 0 0 1 | 25 | * 1 0 0|1 0 1 | 37 | * 1 0|1 0 1 0 | 42 | * 1|1 0 1 0 | 26 | * 1 0|1 0 1 1 | 43 | * * * * 1|1 0 1 1 | 27 | * * * * 1 0 0 0|1 1 | 35 | * * * * * * 1 0 0|1 1 0 | 38 | * * * * * * 1|1 1 0 ? | D3 | * * * * * * * 1 0|1 1 0 0 | 44 | * * * 1|1 1 0 0 | 28 | * * * 1 0|1 1 0 1 | 45 | * * * * 1|1 1 0 1 | 29 | * * * * 1 0 0|1 1 1 | 39 | * * * 1 0|1 1 1 0 | 46 | * * * 1|1 1 1 0 | 30 | * * * 1 0|1 1 1 1 | 47 | * 1|1 1 1 1 | 31 | * Again, choosing the lexicographically first available successor as the first unknown substring in the sequence of substrings will either leave us with no solution or on the path to a(49). Selecting as the 38's successor the 49 (whose successor has already been determined to be the 35) gives [ 33, 36, 37, 40, 34, 41, 38, 49, 35, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, 48, 32] and the table reduces to 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 0 1 ? 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 -----------+----------+----+-------------------------------------------------------------------------------------- prefix | suffix | j | ] 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 D1 D2 48 49 25 26 27 D3 28 29 30 31 -----------+----------+----+-------------------------------------------------------------------------------------- | | [ | * 1 0 0 0 0 0| | 32 | * 1 0 0 0 0|1 | 33 | * 1 0 0 0|1 0 | 34 | * 1|1 0 1 1 | D1 | * * * * 1|1 0 1 1 | D2 | * * * * 1 0 0|1 0 0 | 36 | * 1 0|1 0 0 0 | 40 | * 1|1 0 0 0 0 | 48 | * 1|1 0 0 0 1 | 49 | * 1 0|1 0 0 1 | 41 | * 1|1 0 0 1 | 25 | * 1 0 0|1 0 1 | 37 | * 1 0|1 0 1 0 | 42 | * 1|1 0 1 0 | 26 | * 1 0|1 0 1 1 | 43 | * * * * 1|1 0 1 1 | 27 | * * * * 1 0 0 0|1 1 | 35 | * * * * * 1 0 0|1 1 0 | 38 | * 1|1 1 0 ? | D3 | * * * * * * 1 0|1 1 0 0 | 44 | * * 1|1 1 0 0 | 28 | * * 1 0|1 1 0 1 | 45 | * * * * 1|1 1 0 1 | 29 | * * * * 1 0 0|1 1 1 | 39 | * * * 1 0|1 1 1 0 | 46 | * * * 1|1 1 1 0 | 30 | * * * 1 0|1 1 1 1 | 47 | * 1|1 1 1 1 | 31 | * so the predecessors of the D1, the D2, the 26, and the (original) 27 are, in some order, the 35, the D3, the 45, and the 29, which further reduces the table to 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 0 1 ? 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 -----------+----------+----+-------------------------------------------------------------------------------------- prefix | suffix | j | ] 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 D1 D2 48 49 25 26 27 D3 28 29 30 31 -----------+----------+----+-------------------------------------------------------------------------------------- | | [ | * 1 0 0 0 0 0| | 32 | * 1 0 0 0 0|1 | 33 | * 1 0 0 0|1 0 | 34 | * 1|1 0 1 1 | D1 | * * * * 1|1 0 1 1 | D2 | * * * * 1 0 0|1 0 0 | 36 | * 1 0|1 0 0 0 | 40 | * 1|1 0 0 0 0 | 48 | * 1|1 0 0 0 1 | 49 | * 1 0|1 0 0 1 | 41 | * 1|1 0 0 1 | 25 | * 1 0 0|1 0 1 | 37 | * 1 0|1 0 1 0 | 42 | * 1|1 0 1 0 | 26 | * 1 0|1 0 1 1 | 43 | * * * * 1|1 0 1 1 | 27 | * * * * 1 0 0 0|1 1 | 35 | * * * * 1 0 0|1 1 0 | 38 | * 1|1 1 0 ? | D3 | * * * * 1 0|1 1 0 0 | 44 | * * 1|1 1 0 0 | 28 | * * 1 0|1 1 0 1 | 45 | * * * * 1|1 1 0 1 | 29 | * * * * 1 0 0|1 1 1 | 39 | * * * 1 0|1 1 1 0 | 46 | * * * 1|1 1 1 0 | 30 | * * * 1 0|1 1 1 1 | 47 | * 1|1 1 1 1 | 31 | * Now, since the only remaining possible successors for the 35 are the original 27, its two duplicates, and the 26, selecting the 26 (which is lexicographically first) will again either lead to no solution or keep us on the path to a(49). And since the 26 is already known to have the 42 as its successor, which, in turn, is succeeded by the 43, this gives [ 33, 36, 37, 40, 34, 41, 38, 49, 35, 26, 42, 43, __, __, __, __, __, __, __, __, __, __, __, __, __, __, 48, 32] and the table updates to 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 0 1 ? 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 -----------+----------+----+-------------------------------------------------------------------------------------- prefix | suffix | j | ] 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 D1 D2 48 49 25 26 27 D3 28 29 30 31 -----------+----------+----+-------------------------------------------------------------------------------------- | | [ | * 1 0 0 0 0 0| | 32 | * 1 0 0 0 0|1 | 33 | * 1 0 0 0|1 0 | 34 | * 1|1 0 1 1 | D1 | * * * * 1|1 0 1 1 | D2 | * * * * 1 0 0|1 0 0 | 36 | * 1 0|1 0 0 0 | 40 | * 1|1 0 0 0 0 | 48 | * 1|1 0 0 0 1 | 49 | * 1 0|1 0 0 1 | 41 | * 1|1 0 0 1 | 25 | * 1 0 0|1 0 1 | 37 | * 1 0|1 0 1 0 | 42 | * 1|1 0 1 0 | 26 | * 1 0|1 0 1 1 | 43 | * * * * 1|1 0 1 1 | 27 | * * * * 1 0 0 0|1 1 | 35 | * 1 0 0|1 1 0 | 38 | * 1|1 1 0 ? | D3 | * * * 1 0|1 1 0 0 | 44 | * * 1|1 1 0 0 | 28 | * * 1 0|1 1 0 1 | 45 | * * * 1|1 1 0 1 | 29 | * * * 1 0 0|1 1 1 | 39 | * * * 1 0|1 1 1 0 | 46 | * * * 1|1 1 1 0 | 30 | * * * 1 0|1 1 1 1 | 47 | * 1|1 1 1 1 | 31 | * So the D3 must be succeeded by one of the three 27's (i.e., the original 27, D1, or D2), so the remaining unknown bit in D3 is a 1, so D3 is a duplicate 29. There are still multiple solutions available, but a(49) is on the path on which the 43 is succeeded by its lexicographically first remaining available successor, which is 44, or there is no solution on that path. Choosing that path gives [ 33, 36, 37, 40, 34, 41, 38, 49, 35, 26, 42, 43, 44, __, __, __, __, __, __, __, __, __, __, __, __, __, 48, 32] and then the 44 can't be succeeded by the 48, so it must be succeeded by the 25, which in turn is succeeded by the 39, and the 28 is succeeded by the 48, yielding [ 33, 36, 37, 40, 34, 41, 38, 49, 35, 26, 42, 43, 44, 25, 39, __, __, __, __, __, __, __, __, __, __, 28, 48, 32] so the 39 can't be succeeded by the 28; the 39's only possible successors, then, are the original 29 and the D3, which is a duplicate 29; neither has appeared yet in the sequence, so choose the original 29. Similarly, the 29's only available successors are the original 27 and its two duplicates, none of which have yet appeared in the sequence, so choose as the original 29's successor the original 27. This yields [ 33, 36, 37, 40, 34, 41, 38, 49, 35, 26, 42, 43, 44, 25, 39, 29, 27, __, __, __, __, __, __, __, __, 28, 48, 32] and the table updates to 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 -----------+----------+----+-------------------------------------------------------------------------------------- prefix | suffix | j | ] 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 D1 D2 48 49 25 26 27 D3 28 29 30 31 -----------+----------+----+-------------------------------------------------------------------------------------- | | [ | * 1 0 0 0 0 0| | 32 | * 1 0 0 0 0|1 | 33 | * 1 0 0 0|1 0 | 34 | * 1|1 0 1 1 | D1 | * * * 1|1 0 1 1 | D2 | * * * 1 0 0|1 0 0 | 36 | * 1 0|1 0 0 0 | 40 | * 1|1 0 0 0 0 | 48 | * 1|1 0 0 0 1 | 49 | * 1 0|1 0 0 1 | 41 | * 1|1 0 0 1 | 25 | * 1 0 0|1 0 1 | 37 | * 1 0|1 0 1 0 | 42 | * 1|1 0 1 0 | 26 | * 1 0|1 0 1 1 | 43 | * 1|1 0 1 1 | 27 | * * * 1 0 0 0|1 1 | 35 | * 1 0 0|1 1 0 | 38 | * 1|1 1 0 1 | D3 | * * 1 0|1 1 0 0 | 44 | * 1|1 1 0 0 | 28 | * 1 0|1 1 0 1 | 45 | * * 1|1 1 0 1 | 29 | * 1 0 0|1 1 1 | 39 | * 1 0|1 1 1 0 | 46 | * * 1|1 1 1 0 | 30 | * * 1 0|1 1 1 1 | 47 | * 1|1 1 1 1 | 31 | * Again, choose the lexicographically first remaining available option for the first remaining unknown substring in the sequence, i.e., choose the 45 as the successor of the 27. This will give [ 33, 36, 37, 40, 34, 41, 38, 49, 35, 26, 42, 43, 44, 25, 39, 29, 27, 45, __, __, __, __, __, __, __, 28, 48, 32] and the table updates to 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 -----------+----------+----+-------------------------------------------------------------------------------------- prefix | suffix | j | ] 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 D1 D2 48 49 25 26 27 D3 28 29 30 31 -----------+----------+----+-------------------------------------------------------------------------------------- | | [ | * 1 0 0 0 0 0| | 32 | * 1 0 0 0 0|1 | 33 | * 1 0 0 0|1 0 | 34 | * 1|1 0 1 1 | D1 | * * 1|1 0 1 1 | D2 | * * 1 0 0|1 0 0 | 36 | * 1 0|1 0 0 0 | 40 | * 1|1 0 0 0 0 | 48 | * 1|1 0 0 0 1 | 49 | * 1 0|1 0 0 1 | 41 | * 1|1 0 0 1 | 25 | * 1 0 0|1 0 1 | 37 | * 1 0|1 0 1 0 | 42 | * 1|1 0 1 0 | 26 | * 1 0|1 0 1 1 | 43 | * 1|1 0 1 1 | 27 | * 1 0 0 0|1 1 | 35 | * 1 0 0|1 1 0 | 38 | * 1|1 1 0 1 | D3 | * * 1 0|1 1 0 0 | 44 | * 1|1 1 0 0 | 28 | * 1 0|1 1 0 1 | 45 | * * 1|1 1 0 1 | 29 | * 1 0 0|1 1 1 | 39 | * 1 0|1 1 1 0 | 46 | * * 1|1 1 1 0 | 30 | * * 1 0|1 1 1 1 | 47 | * 1|1 1 1 1 | 31 | * So the 45 must be succeeded by D1 or D2, both duplicate 27's, so choose (as the one that appears earlier in the sequence of substrings) D1 (which I'll denote as "27'" in the sequence), which yields [ 33, 36, 37, 40, 34, 41, 38, 49, 35, 26, 42, 43, 44, 25, 39, 29, 27, 45, 27', __, __, __, __, __, __, 28, 48, 32] and the table updates to 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 -----------+----------+----+-------------------------------------------------------------------------------------- prefix | suffix | j | ] 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 D1 D2 48 49 25 26 27 D3 28 29 30 31 -----------+----------+----+-------------------------------------------------------------------------------------- | | [ | * 1 0 0 0 0 0| | 32 | * 1 0 0 0 0|1 | 33 | * 1 0 0 0|1 0 | 34 | * 1|1 0 1 1 | D1 | * * 1|1 0 1 1 | D2 | * * 1 0 0|1 0 0 | 36 | * 1 0|1 0 0 0 | 40 | * 1|1 0 0 0 0 | 48 | * 1|1 0 0 0 1 | 49 | * 1 0|1 0 0 1 | 41 | * 1|1 0 0 1 | 25 | * 1 0 0|1 0 1 | 37 | * 1 0|1 0 1 0 | 42 | * 1|1 0 1 0 | 26 | * 1 0|1 0 1 1 | 43 | * 1|1 0 1 1 | 27 | * 1 0 0 0|1 1 | 35 | * 1 0 0|1 1 0 | 38 | * 1|1 1 0 1 | D3 | * 1 0|1 1 0 0 | 44 | * 1|1 1 0 0 | 28 | * 1 0|1 1 0 1 | 45 | * 1|1 1 0 1 | 29 | * 1 0 0|1 1 1 | 39 | * 1 0|1 1 1 0 | 46 | * * 1|1 1 1 0 | 30 | * * 1 0|1 1 1 1 | 47 | * 1|1 1 1 1 | 31 | * D1 must be succeeded by 46 or 47, so choose 46 (lexicographically first), which yields [ 33, 36, 37, 40, 34, 41, 38, 49, 35, 26, 42, 43, 44, 25, 39, 29, 27, 45, 27', 46, __, __, __, __, __, 28, 48, 32] and the 46 can't be succeeded by the 28, so the table updates to 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 -----------+----------+----+-------------------------------------------------------------------------------------- prefix | suffix | j | ] 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 D1 D2 48 49 25 26 27 D3 28 29 30 31 -----------+----------+----+-------------------------------------------------------------------------------------- | | [ | * 1 0 0 0 0 0| | 32 | * 1 0 0 0 0|1 | 33 | * 1 0 0 0|1 0 | 34 | * 1|1 0 1 1 | D1 | * 1|1 0 1 1 | D2 | * 1 0 0|1 0 0 | 36 | * 1 0|1 0 0 0 | 40 | * 1|1 0 0 0 0 | 48 | * 1|1 0 0 0 1 | 49 | * 1 0|1 0 0 1 | 41 | * 1|1 0 0 1 | 25 | * 1 0 0|1 0 1 | 37 | * 1 0|1 0 1 0 | 42 | * 1|1 0 1 0 | 26 | * 1 0|1 0 1 1 | 43 | * 1|1 0 1 1 | 27 | * 1 0 0 0|1 1 | 35 | * 1 0 0|1 1 0 | 38 | * 1|1 1 0 1 | D3 | * 1 0|1 1 0 0 | 44 | * 1|1 1 0 0 | 28 | * 1 0|1 1 0 1 | 45 | * 1|1 1 0 1 | 29 | * 1 0 0|1 1 1 | 39 | * 1 0|1 1 1 0 | 46 | * 1|1 1 1 0 | 30 | * 1 0|1 1 1 1 | 47 | * 1|1 1 1 1 | 31 | * So the 46 is succeeded by the D3 (the duplicate 29), which, in turn, is succeeded by D2 (the 2nd duplicate 27), 47, 31, 30, and 28, so we have [ 33, 36, 37, 40, 34, 41, 38, 49, 35, 26, 42, 43, 44, 25, 39, 29, 27, 45, 27', 46, 29', 27", 47, 31, 30, 28, 48, 32] so a(49) is obtained from the overlapping substrings (each beginning at the start of the suffix of its predecessor) 100001 100100 100101 101000 100010 101001 100110 110001 100011 11010 101010 101011 101100 11001 100111 11101 11011 101101 11011 101110 11101 11011 101111 11111 11110 11100 110000 100000 as a(49) = 10000100100101000101001100011010101100111011011101111100000_2 = 298542252615908320.