I wrote, about the Thue-Morse sequence:
Adjacent terms (f(n) vs. f(n+1)) differ 2/3 of the time. Terms two steps apart (f(n) vs. f(n+2)) *also* differ 2/3 of the time! (So much for my intuition.) I also checked differences up to 20 apart (f(n) vs. f(n+20)). Here's a table of what (asymptotic) proportion of the time the terms differed: ...
I have now extended my table to 200 (f(n) vs. f(n+200)). I can easily push it much farther if anyone is interested. I list only the odd numbers, since for an even number the value is always the same as that of half that even number. So it's 2/3 for all powers of 2, 1/3 for all numbers that are 3 times a power of 2, 1/2 for all numbers that are 5 times a power of 2, etc. 1: 2/3 3: 1/3 5: 1/2 7: 1/2 9: 5/12 11: 7/12 13: 7/12 15: 5/12 17: 11/24 19: 13/24 21: 11/24 23: 13/24 25: 13/24 27: 11/24 29: 13/24 31: 11/24 33: 7/16 35: 9/16 37: 25/48 39: 23/48 41: 25/48 43: 23/48 45: 7/16 47: 9/16 49: 9/16 51: 7/16 53: 23/48 55: 25/48 57: 23/48 59: 25/48 61: 9/16 63: 7/16 65: 43/96 67: 53/96 69: 47/96 71: 49/96 73: 17/32 75: 15/32 77: 47/96 79: 49/96 81: 47/96 83: 49/96 85: 17/32 87: 15/32 89: 47/96 91: 49/96 93: 43/96 95: 53/96 97: 53/96 99: 43/96 101: 49/96 103: 47/96 105: 15/32 107: 17/32 109: 49/96 111: 47/96 113: 49/96 115: 47/96 117: 15/32 119: 17/32 121: 49/96 123: 47/96 125: 53/96 127: 43/96 129: 85/192 131: 107/192 133: 97/192 135: 95/192 137: 101/192 139: 91/192 141: 89/192 143: 103/192 145: 101/192 147: 91/192 149: 97/192 151: 95/192 153: 31/64 155: 33/64 157: 97/192 159: 95/192 161: 97/192 163: 95/192 165: 31/64 167: 33/64 169: 97/192 171: 95/192 173: 101/192 175: 91/192 177: 89/192 179: 103/192 181: 101/192 183: 91/192 185: 97/192 187: 95/192 189: 85/192 191: 107/192 193: 107/192 195: 85/192 197: 95/192 199: 97/192
I don't see any other obvious patterns in the above table, except that the numerators are never more than 1 away from half the denominator,
Violated starting at 65, for which the proportion that differ is 43/96.
and the denominators are always either 2, or 3 times a (possibly zero) power of 2.
Still true. So, can anyone figure out the pattern? The nth term of the Thue-Morse sequence equals the parity of the number of 1-bits in the binary expression for n. For instance ten in binary is 1010, which has an even number of 1-bits, so the tenth term of the Thue-Morse sequence is zero. There's a similar sequence in which the nth term of the sequence equals the parity of the number of 1-bits in the *negabinary* (base minus two) expression for n; perhaps I'll try that sequence next. Everyone, please feel free to suggest other binary sequences to try. By binary I don't necessarily mean that all terms are 0 or 1, but that the terms only take two values.