A331362 a(n) is the greatest value of the form s_1 + ... + s_k such that the concatenation of the binary representations of s_1^2, ..., s_k^2 equals the binary representation of n.

0, 1, 1, 2, 2, 2, 2, 3, 2, 3, 2, 3, 3, 3, 3, 4, 4, 3, 3, 4, 3, 3, 3, 4, 3, 5, 3, 4, 4, 4, 4, 5, 4, 5, 3, 4, 6, 4, 4, 5, 3, 4, 3, 4, 4, 4, 4, 5, 5, 7, 5, 6, 4, 4, 4, 5, 4, 6, 4, 5, 5, 5, 5, 6, 8, 5, 5, 6, 4, 4, 4, 5, 6, 7, 4, 5, 5, 5, 5, 6, 5, 9, 4, 5, 4, 4, 4

Offset: 0

Author

Rémy Sigrist, Jan 14 2020

Keywords

• nonn
• base

Comments

As 0 and 1 are squares, we can always split the binary representation of a number into squares, and the sequence is well defined.

Examples

			For n = 8:
- the binary representation of 8 is "1000",
- we can split it into "100" and "0" (2^2 and 0^2),
- or into "1" and "0" and "0" and "0" (1^2 and 0^2 and 0^2 and 0^2),
- so a(8) = max(2+0, 1+0+0+0) = 2.
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 0..16384
• Rémy Sigrist, Density plot of the first 2^20 terms
• Rémy Sigrist, PARI program for A331362
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A000120, A003754.

Programs

PARI

See Links section.

Formula

a(n) >= A000120(n) with equality iff n belongs to A003754.

a(n^2) = n.