A357658 a(n) is the maximum Hamming weight of squares k^2 in the range 2^n <= k^2 < 2^(n+1).

1, 2, 3, 3, 5, 4, 6, 6, 8, 8, 9, 9, 13, 11, 13, 12, 14, 15, 16, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 25, 26, 27, 28, 29, 30, 31, 31, 34, 33, 34, 37, 37, 38, 38, 39, 39, 41, 41, 42, 44, 44, 44, 46, 47, 47, 49, 50, 51, 52, 52, 53, 54, 55, 55, 57, 57, 58, 59, 62, 63

Offset

2,2

Comments

The sequence can be approximated by a linear function c*n + d, with c ~= 0.883 +- 0.003, d ~= -1.65 +- 0.16. See linked plot. For a square number with 100 binary digits (n=99) a maximum Hamming weight of 85 or 86 is expected. For example, 1125891114428899^2 has Hamming weight 85.

Links

Hugo Pfoertner, Table of n, a(n) for n = 2..125, including results from Bert Dobbelaere and users l4m2, gsitcia, anttiP in Code Golf challenge (terms 103..125)

Code Golf Stackexchange, Smallest and largest 100-bit square with maximum Hamming weight, fastest code challenge started Dec 15 2022.

Hugo Pfoertner, Maximum of bits=1 in squares 2^n < k^2 < 2^(n+1), plot of linear fit (December 2022).

Example

  n         A357753(n) a(n) A357659(n)    A357660(n)    A357754(n)
  bits  2^n  least sq  Ha w  k_min  ^2     k_max  ^2   largest sq
   2     4      4       1     2      4      2      4        4
   3     8      9       2     3      9      3      9        9
   4    16     16       3     5     25      5     25       25
   5    32     36       3     7     49      7     49       49
   6    64     64       5    11    121     11    121      121
   7   128    144       4    13    169     15    225      225
  12  4096   4096       9    75   5625     89   7921     8100

Prog

(Python 3.10+)
from math import isqrt
def A357658(n): return max((k**2).bit_count() for k in range(isqrt((1<<n)-1)+1, isqrt((1<<n+1)-1)+1)) # Chai Wah Wu, Oct 14 2022
(C, x64asm, Rust, c++) see Code Golf link, programs by users l4m2 (C, x64asm), gsitcia (Rust), anttiP (c++)

Crossrefs

Cf. A000120, A000290, A356878, A357304, A357753, A357754.

A357659 and A357660 are the minimal and the maximal values of k producing a(n).

Sequence in context: A163126 A304818 A088922 * A143092 A143089 A275314

Adjacent sequences: A357655 A357656 A357657 * A357659 A357660 A357661

Keyword

nonn,base

Author

Hugo Pfoertner, Oct 09 2022

Status

approved