This site is supported by donations to The OEIS Foundation.
User:Thomas Scheuerle/workingdrafts/Proof A354169
Contents
- 1 Unfinished proof that in A354169(n) has Hamming weight < 3 for all n
- 1.1 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
- 1.2 Unfinished proof that a(n+1) has Hamming weight = 1 in all cases where a(n) has Hamming weight = 2
Unfinished proof that in A354169(n) has Hamming weight < 3 for all n
We will use a(n) instead of A354169(n) in the text below.
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(n) = 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
| 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 |
| Optional 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 |
| Optional 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 |
| Optional 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 |
| Optional 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 |
| Optional 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 |
| Optional 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(n/2)+1), ..., a(n-1) are perpendicular to m. However, a(floor(n/2)) must share at least one bit with m in its binary representation.
Proof:
If a(floor(n/2)) did not share a bit with m, then m would be perpendicular to a(floor(n/2)), and would have been a smaller choice for a(n-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 |
| Optional 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 |
| Optional 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 |
| Optional 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 |
| Optional 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 |
| Optional 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 |
| Optional 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 |
| Optional 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 |
| Optional 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 |
| Optional below a | U | 0 | 0 | U | 0 | 0 | U | 0 | U | 0 | U | 0 |
Contradiction with observation:
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 | |
| Optional between c and d | 0 | 0 | U | 0 | 0 | U | 0 | |
| c | 1 | 0 | 0 | 1 | 0 | 0 | 0 | |
| Optional between b and c | 0 | 0 | U | 0 | 0 | U | 0 | |
| b | 0 | 0 | 0 | 1 | 0 | 0 | 0 | |
| Optional between a and b | 0 | 0 | U | 0 | 0 | U | 0 | |
| a | 1 | 0 | 0 | 0 | 0 | 0 | 1 | |
| Optional 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.
Unfinished proof that a(n+1) has Hamming weight = 1 in all cases where a(n) has Hamming weight = 2
Theorem 5:
If a(n) is a power of two, then it greater than all max(a(0),...,a(n-1)).
Proof:
No number in this sequence can a pear a second time, and smaller numbers appear first. As a two and more bit numbers can only appear when the single bit numbers which are not perpendicular appeared first, all single bit numbers must be records in the sequence appearing in order. QED
Theorem 6:
A number with Hamming weight = 2 can only then be on an even position 2*m, when on 2*m-1 too is any number with Hamming weight > 1.
Proof:
From theorem 5 we know that Hamming weight = 1 means that this number is greater than all previously seen numbers. So if a(2*m) would have Hamming weight = 2 then 2*m-1 would have been earlier choice instead. QED
Theorem 7:
Is a number with Hamming weight = 2 on an even position 2*m and on 2*m-1 such a number too, then a(m-1) has at least Hamming weight 1.
Proof:
By application of theorem 2 we know now that a(m-1) must share at least one bit with a(2*m) and at least one with a(2*m-1) too.
| m-1 | between m-1 and 2*m-1 | 2*m-1 | 2*m | ||
|---|---|---|---|---|---|
| d | 0 | 0 | 0 | 1 | |
| Optional between c and d | 0 | U | 0 | 0 | |
| c | 0 | 0 | 1 | 0 | |
| Optional between b and c | 0 | U | 0 | 0 | |
| b | 1 | 0 | 0 | 1 | |
| option between a and b | 0 | U | 0 | 0 | |
| a | 1 | 0 | 1 | 0 | |
| option below a | 0 | U | 0 | 0 |
Corollary:
If m was an odd number m-1 is even. From this we know now that a number with Hamming weight > 1 on a position 2*m which contains only one factor 2 is not the first appearance of a number with the Hamming weight > 1 on an even position in this sequence.
Theorem 8:
Is a number with Hamming weight = 2 on an even position 4*m which can be divided by 4, then if we assume that no Hamming weight > 2 is appearing and on no even position was previously seen a Hamming weight > 1, it would be required that a bit position below the record powers of two stays at least for the interval m-1 to 4*m-1 zero.
Proof:
todo
| m-1 | between m-1 and 2*m-2 | 2*m-2 | 2*m-1 | between 2*m-1 and 4*m-1 | 4*m-1 | 4*m | ||
|---|---|---|---|---|---|---|---|---|
| d | 0 | 0 | 1 | 0 | 0 | 0 | 1 | |
| Optional between c and d | U | U | U | 0 | U | 0 | 0 | |
| c | 0 | 0 | 0 | 0 | 0 | 1 | 0 | |
| Optional between b and c | U | U | U | 0 | U | 0 | 0 | |
| b | 0 | 0 | 0 | 1 | 0 | 0 | 1 | |
| option between a and b | U | U | U | 0 | U | 0 | 0 | |
| a | 1 | 0 | 0 | 1 | 0 | 1 | 0 | |
| option below a | U | U | U | 0 | U | 0 | 0 |
Theorem 9:
Is a number with Hamming weight = 2 on an even position 2*m and on 2*m-1 such a number too, then the sequence is required to contain before m either at least one number with Hamming weight > 2 or a number with Hamming weight > 1 on an even position.
Proof:
If m is an odd number it already follows from theorem 7. If m is an even number theorem 8 applies which shows us the minimum length of an bit interval of zero below the record powers of two. We see that this interval must be greater than 2*m+5 (see theorem 3), if we exclude m < 5. If we now see theorem 4 we see that such a long interval of zero for such a bit would require at lest some number with Hamming weight > 1 on an even position somewhere in the sequence before this.
Final proof:
The beginning of the sequence is known and does neither contain Hamming weight > 2 or Hamming weight > 1 on an even position. By theorem 8 we see that if such would be possible this would also be required in a more early part of the sequence, such that this should be observable from the very beginning of the sequence. This contradiction proves that no Hamming weight > 1 is possible on even positions. By relation to the previous theorems, by this it is proved that Hamming weight > 2 will not appear in this sequence.
