|
| |
|
|
A368417
|
|
Binary numbers B whose binary expansion can be split into parts s and t where B = s^2 + t^2.
|
|
1
|
|
|
|
101, 10100, 110100, 110010000, 1010010000, 1110001000000, 10010001000000, 11110000100000000, 100010000100000000, 111110000010000000000, 1000010000010000000000, 1111110000001000000000000, 10000010000001000000000000, 11111110000000100000000000000
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
The split is B = s*2^k + t where t cannot start with a 0 bit and k = length(t) is its bit length.
For all terms except for a(1), the bit lengths of the parts are length(s) = floor(L/2) and length(t) = ceiling(L/2), where L = length(B).
The whole sequence is also defined by the language {101} union {1^n # 0^n # 1 # 0^(2*n) | n > 0} union {(1 # 0^(n-1))^2 # 0 # 1 + 0^(2*n) | n > 0}. Note that this language is neither regular nor context-free.
Proof: We have to solve s^2 + t^2 = 2^k * s + t. Multiplying both sides by 4 and splitting off squares results finally in (2^k - 2*s)^2 + (2*t - 1)^2 = 2^(2*k) + 1. I.e., (2*t - 1) <= 2^k, and thus t <= 2^(k-1). Avoiding leading zeros in t leads to t >= 2^(k-1). Therefore t must be of the form t = 2^(k-1), with k > 0, from which the only two (one if k = 1) possibilities for s are easily obtained from (2^k - 2*s)^2 = 2^(k+1) so 2^(k-1) - s = +- 2^((k-1)/2) and thus k must be odd, so t = 2^(k-1), s = 2^(k-1) +- 2^((k-1)/2), and k == 1 (mod 2). If k = 1, the solution s = 0 must be rejected.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(2*n) = decimal digits 1^n 0^n 1 0^(2*n), where ^ denotes repetition, for n > 0;
a(2*n+1) = decimal digits (1 0^(n-1))^2 0 1 0^(2*n), similarly, for n > 0.
|
|
|
EXAMPLE
|
a(1) = 101 is B=5 which splits as bits s = 10_2 and t = 1_2 with s^2 + t^2 = 5. (This holds in any base.)
a(3) = 110100 is B=52 which splits as bits s = 110_2 = 6 and t = 100_2 = 4 with 6^2 + 4^2 = 52.
|
|
|
MATHEMATICA
|
zero[n_]:=0; one[n_]:=1; a[n_]:=If[EvenQ[n], FromDigits[Join[Array[one, n/2], Array[zero, n/2], {1}, Array[zero, n]]], FromDigits[Join[{1}, Array[zero, (n-3)/2], {1}, Array[zero, (n-3)/2], {0}, {1}, Array[zero, n-1]]]]; Join[{101}, Array[a, 13, 2]] (* Stefano Spezia, Dec 25 2023 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,base,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
