cp's OEIS Frontend

A368417 Binary numbers B whose binary expansion can be split into parts s and t where B = s^2 + t^2.

%I A368417 #40 Jan 20 2024 04:00:35
%S A368417 101,10100,110100,110010000,1010010000,1110001000000,10010001000000,
%T A368417 11110000100000000,100010000100000000,111110000010000000000,
%U A368417 1000010000010000000000,1111110000001000000000000,10000010000001000000000000,11111110000000100000000000000
%N A368417 Binary numbers B whose binary expansion can be split into parts s and t where B = s^2 + t^2.
%C A368417 The split is B = s*2^k + t where t cannot start with a 0 bit and k = length(t) is its bit length.
%C A368417 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).
%C A368417 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.
%C A368417 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.
%F A368417 a(2*n) = decimal digits 1^n 0^n 1 0^(2*n), where ^ denotes repetition, for n > 0;
%F A368417 a(2*n+1) = decimal digits (1 0^(n-1))^2 0 1 0^(2*n), similarly, for n > 0.
%e A368417 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.)
%e A368417 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.
%t A368417 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 *)
%Y A368417 Cf. A368416 (decimal splits).
%K A368417 nonn,base,easy
%O A368417 1,1
%A A368417 _A.H.M. Smeets_, Dec 23 2023