This site is supported by donations to The OEIS Foundation.
User talk:Thomas Scheuerle/workingdrafts/Proof A354169
We will use a(n) instead of A354169(n) in the text below.
Contents
Proof that if a(n+1) has Hamming weight = 1 in all cases where a(n) has Hamming weight = 2 then no a(m) with Hamming weight > 2 exists
To save words, let us say that two nonnegative numbers are perpendicular if their binary representations have no common 1's.
Theorem 1:
A number k with Hamming weight h_k > 1 can only occur if all numbers with Hamming weight < h_k and binary representation which is a subset of that of k are already in the sequence.
Proof:
This follows immediately from the word "smallest" in the definition. QED
Corollary:
To prove that no Hamming weight > 2 occurs in this sequence, it will suffice to prove that Hamming weight 3 is impossible. Let us assume a(tk) = k is the first number in this sequence with Hamming weight 3. Obviously all a(m) with m < n have Hamming weight < 3.
The possible configuration by theorem 1
U means: "yet unknown".
| before ta | ta | between ta and tb | tb | between tb and t1 | t1 | between t1 and tc | tc | between tc and t2 | t2 | between t2 and t3 | t3 | between t3 and tk | tk | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Greater than c | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 |
| c | U | 0 | U | 0 | U | 0 | U | 1 | U | 1 | U | 1 | U | 1 |
| option between b and c | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 |
| b | U | 0 | U | 1 | U | 1 | U | 0 | U | 0 | U | 1 | U | 1 |
| option between a and b | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 |
| a | U | 1 | U | 0 | U | 1 | U | 0 | U | 1 | U | 0 | U | 1 |
| option below a | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 |
| before ta | ta | between ta and tb | tb | between tb and t1 | t1 | between t1 and tc | tc | between tc and t3 | t3 | between t3 and t2 | t2 | between t2 and tk | tk | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Greater than c | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 |
| c | U | 0 | U | 0 | U | 0 | U | 1 | U | 1 | U | 1 | U | 1 |
| option between b and c | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 |
| b | U | 0 | U | 1 | U | 1 | U | 0 | U | 1 | U | 0 | U | 1 |
| option between a and b | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 |
| a | U | 1 | U | 0 | U | 1 | U | 0 | U | 0 | U | 1 | U | 1 |
| option below a | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 |
Column tk:
We define k as the first number in A354169 with Hamming weight = 3. Therefore we know that it will contain only three times a one and all other bits must be zero. In our example we represent these bits by a, b and c.
Column t1, t2 and t3:
We define these as the set of numbers with Hamming weight = 2 which represents all two bit combinations out of the three bits which are set in k.
Column ta, tb and tc:
We define these as the set of numbers with Hamming weight = 1 which represent the bits which are set in k.
The order of the columns:
From theorem 1 we know that ta and tb must appear before t1.
From the rule that the least number must appear first we know that ta appears before tb and tb appears before tc.
From theorem 1 we know that ta, tb, tc, t1, t2 and t3 must appear before k.
From theorem 1 we know that ta and tc must appear before t2.
From theorem 1 we know that tb and tc must appear before t3.
Theorem 2:
Let m be a number with Hamming weight > 1. By definition a(floor(m/2)+1), ..., a(m-1) are perpendicular to m. However, a(floor(m/2)) must share at least one bit with m in its binary representation.
[I suppose you want to say that a(n) = m, right? But don't forget you have already defined k = a(n) to be the first term with weight 3. So n is not a free letter. Also, in the proof, how do you know m is smaller than a(n-1)? Oh, I see, you use the assumption in the heading to this section. N. J. A. Sloane 23:38, 19 July 2022 (EDT)] [ I changed n to tk. n was from the old txt version and should not have be reused at this place. Also I need to be careful often thinking n wriiting n or forget to edit n into m :-( --Thomas Scheuerle (talk) 02:59, 20 July 2022 (EDT)]
Proof:
If a(floor(m/2)) did not share a bit with m, then m would be perpendicular to a(floor(m/2)), and would have been a smaller choice for a(m-1). QED
The possible configuration by theorem 1 and 2 for earliest possible appearance of k
| before ta | ta | between ta and tb | tb | between tb and t1 | t1 | between t1 and tc | tc | between tc and t2 | t2 | between t2 and t3 | t3 | between t3 and tk | tk | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Greater than c | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 |
| c | U | 0 | U | 0 | U | 0 | U | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| option between b and c | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 |
| b | U | 0 | U | 1 | 0 | 1 | U | 0 | U | 0 | 0 | 1 | 0 | 1 |
| option between a and b | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 |
| a | U | 1 | U | 0 | 0 | 1 | U | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| option below a | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 |
| before ta | ta | between ta and tb | tb | between tb and t1 | t1 | between t1 and tc | tc | between tc and t3 | t3 | between t3 and t2 | t2 | between t2 and tk | tk | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Greater than c | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 |
| c | U | 0 | U | 0 | U | 0 | U | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| option between b and c | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 |
| b | U | 0 | U | 1 | 0 | 1 | U | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| option between a and b | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 |
| a | U | 1 | U | 0 | 0 | 1 | U | 0 | U | 0 | 0 | 1 | 0 | 1 |
| option below a | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 | U | 0 |
Column between tb and t1:
As we know from theorem 2 that at floor(t1/2) must be a number not perpendicular to a(t1). We know that position must be the bit a or the bit b in usage. As we now want to look onto the case for the earliest possible appearance of k, it is obvious that this can only be earliest if no further number using the bits a or b is between tb and t1. In this case we know tb = floor(t1/2).
Column between tc and t2 or t3:
As we know from theorem 2 that at floor(t_n/2) must be a number not perpendicular to a(t_n). We know that position must be the bit a or the bit b in usage. As we now want to look onto the case for the earliest possible appearance of k, it is obvious that this can only be earliest if no further number using the bits of t_n between tc and t_n. In this case we know tc = floor(min(t2, t3)/2).
Column between t2 and t3 or t3 and t2:
Here the same rule like above applies. Note: There is an additional bit forced to zero, this is because it was previously set and may therefore not be set against in this interval.
Column between t2, t3 and tk:
See above.
Theorem 3:
The least possible distance between tc and t3 is greater than 2*tc+5. The least possible distance between t2 and tk is greater than 2*tc+5 too. This will imply that at least one bit from a(t2) or a(t3) will stay zero for more than 2*m+5 until tk is reached. (Let m be t2 or t3 depending on which case is used.)
Proof:
Let ta .. tk appear ordered as this allows the compactest sequence. Let ta = 1 to obtain the least values here. Let us assume that in all intervals which did not contain constrains already defined by theorem 1 and theorem 2 no new numbers will appear. Then we see by theorem 2 the relations: tb = ta+1, t1 = 2*tb+1, tc = t1+1, t2 = 2*tc+1, t3 = 2*t2+1, tk = 2*t3+1. From the previous theorems we know that the bit a must be zero between t3 and tk otherwise it would block the appearance of tk. Also we know that the bit a must be zero between t2 and t3 as it was 1 in a(t2). QED
The possible configuration by theorem 1 and 2 and 3 for earliest possible appearance of k
| t = 0 | ta = 1 | tb = 2 | between tb and t1 | t1 = 5 | tc = 6 | between tc and t2 | t2 = 13 | between t2 and t3 | t3 = 27 | between t3 and tk | tk = 55 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Greater than c | U | 0 | 0 | U | 0 | 0 | U | 0 | U | 0 | U | 0 |
| c | U | 0 | 0 | U | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| option between b and c | U | 0 | 0 | U | 0 | 0 | U | 0 | U | 0 | U | 0 |
| b | U | 0 | 1 | 0 | 1 | 0 | U | 0 | 0 | 1 | 0 | 1 |
| option between a and b | U | 0 | 0 | U | 0 | 0 | U | 0 | U | 0 | U | 0 |
| a | U | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| option below a | U | 0 | 0 | U | 0 | 0 | U | 0 | U | 0 | U | 0 |
Contradiction with observation:
Let m be an integer > 0. If we expect that Hamming weight = 3 is indeed happening there for all three two-bit combinations a(t1), a(t2) and a(t3) that will appear in this sequence, then Theorem 3 requires us to assume that a bit below the record powers of two in this sequence may stay unoccupied for longer than 2*m+5 if m was the position of the last usage of that bit. From observation it appears that this will not happen as in this interval always a power of two below the actual records frees up for its first time second usage and would be used together with this bit as soon as this happens.
Possible proof for Hamming weight <= 2 by contradiction:
If we can prove that a bit used at position m will be reused in the very latest case at position 2*m+5, then we would be able to prove by contradiction that no Hamming weight > 2 can appear in this sequence. As we already know, the appearance of Hamming weight = 3 also requires the appearance of all the two-bit combinations included. By this contradiction only two of these combinations will be seen.
Theorem 4:
The condition that a bit will be reused in the latest case at position 2*m+5 is fulfilled if, after each number which does not have Hamming weight 1, a number with Hamming weight 1 will appear which is also a new record value in the sequence and the number whose bit shall be reused has Hamming weight < 3.
Proof:
A bit will not be reused until 2*m+1 by the definition of this sequence. After this it may be used immediately or we need a new power of two. If m+1 is a new power of two, it may be used in the soonest case at 2*m+3. If the number at position m had Hamming weight 2 we may use one bit of this number at 2*m+3 and the second bit at 2*m+5.
How the situation changes if after HW = 2, HW = 1 must follow:
| t2 | t2+1 | between t2+1 and t3 | t3 = 2*t2+1 | t3+1 | between t3+1 and 2*(t2+1)+1 | 2*(t2+1)+1 | ||
|---|---|---|---|---|---|---|---|---|
| d | 0 | 1 | 0 | 0 | 0 | 0 | 1 | |
| option between c and d | 0 | 0 | U | 0 | 0 | U | 0 | |
| c | 1 | 0 | 0 | 1 | 0 | 0 | 0 | |
| option between b and c | 0 | 0 | U | 0 | 0 | U | 0 | |
| b | 0 | 0 | 0 | 1 | 0 | 0 | 0 | |
| option between a and b | 0 | 0 | U | 0 | 0 | U | 0 | |
| a | 1 | 0 | 0 | 0 | 0 | 0 | 1 | |
| option below a | 0 | 0 | U | 0 | 0 | U | 0 | |
| Index m | m | m+1 | 2*m+1 | 2*m+2 | 2*m+3 |
Conclusion:
We reduced the problem of proving that no Hamming weight > 2 is possible to the question of why every number with Hamming weight > 1 is followed by a record power of two in this sequence. This appears to be the case because the sequence is in a state of self-sustaining saturation; this means the supply of new possible bits for a second usage will only increase every two steps in this sequence but in contrast we need to add a new number every step. So obviously the frequency of numbers which are not record powers of two must be below 50%.
Verification of the theory by experiment:
If we change the definition of this sequence by replacing floor(n/2) with floor(n/4), or by artificially injecting some two-bit numbers directly after a two-bit number which appeared naturally, we will observe at least a Hamming weight = 3.
