A352631 Minimum number of zeros in a binary n-digit perfect square, or -1 if there are no such numbers.

0, -1, 2, 2, 2, 3, 2, 4, 3, 4, 3, 4, 4, 5, 2, 5, 4, 6, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 8, 6, 8, 8, 6, 7, 7, 8, 8, 9, 8, 9, 9, 8, 9, 10, 9, 9, 10, 9, 9, 9, 9, 10, 10, 10, 10, 11, 10, 11, 11, 11, 9, 9, 11, 11, 11, 12, 11, 12, 11, 12

Offset

1,3

Comments

Is there a formula that is easy to compute?

Links

Table of n, a(n) for n=1..80.

Example

a(6) = 3, because there are two 6-bit squares 36 = 100100_2 and 49 110001_2 with 4 and 3 zeros, respectively.
a(2) = -1, because the first two perfect squares 1 = 1_2 and 4 = 100_2 have 1 and 3 bits, respectively.

Prog

(Python)
from gmpy2 import is_square, popcount
for n in range(1, 33):
    m=n+1
    for k in range(2**(n-1), 2**n):
        if is_square(k):
            m=min(m, n-popcount(k))
    print(n, -1 if m>n else m)
(Python 3.10+)
def A352631(n): return -1 if n == 2 else min(n-(k**2).bit_count() for k in range(1+isqrt(2**(n-1)-1), 1+isqrt(2**n))) # Chai Wah Wu, Mar 28 2022

Crossrefs

Cf. A000290, A023416, A070939.

Sequence in context: A376497 A126336 A364421 * A134446 A378251 A125749

Adjacent sequences: A352628 A352629 A352630 * A352632 A352633 A352634

Keyword

sign,base

Author

Martin Ehrenstein, Mar 25 2022

Extensions

a(43)-a(71) from Pontus von Brömssen, Mar 26 2022

a(72)-a(80) from Chai Wah Wu, Apr 01 2022

Status

approved