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

101, 10100, 110100, 110010000, 1010010000, 1110001000000, 10010001000000, 11110000100000000, 100010000100000000, 111110000010000000000, 1000010000010000000000, 1111110000001000000000000, 10000010000001000000000000, 11111110000000100000000000000

Offset: 1

Author

A.H.M. Smeets, Dec 23 2023

Keywords

• nonn
• base
• easy

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.

Examples

			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.
		

Crossrefs

Cf. A368416 (decimal splits).

Programs

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 *)

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.