cp's OEIS Frontend

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

%I A357658 #44 Dec 21 2022 20:18:06
%S A357658 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,
%T A357658 24,25,25,26,27,28,29,30,31,31,34,33,34,37,37,38,38,39,39,41,41,42,44,
%U A357658 44,44,46,47,47,49,50,51,52,52,53,54,55,55,57,57,58,59,62,63
%N A357658 a(n) is the maximum Hamming weight of squares k^2 in the range 2^n <= k^2 < 2^(n+1).
%C A357658 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.
%H A357658 Hugo Pfoertner, <a href="/A357658/b357658.txt">Table of n, a(n) for n = 2..125</a>, including results from Bert Dobbelaere and users l4m2, gsitcia, anttiP in Code Golf challenge (terms 103..125)
%H A357658 Code Golf Stackexchange, <a href="https://codegolf.stackexchange.com/questions/255529/smallest-and-largest-100-bit-square-with-maximum-hamming-weight">Smallest and largest 100-bit square with maximum Hamming weight</a>, fastest code challenge started Dec 15 2022.
%H A357658 Hugo Pfoertner, <a href="/A357658/a357658_1.pdf">Maximum of bits=1 in squares 2^n < k^2 < 2^(n+1)</a>, plot of linear fit (December 2022).
%e A357658   n         A357753(n) a(n) A357659(n)    A357660(n)    A357754(n)
%e A357658   bits  2^n  least sq  Ha w  k_min  ^2     k_max  ^2   largest sq
%e A357658    2     4      4       1     2      4      2      4        4
%e A357658    3     8      9       2     3      9      3      9        9
%e A357658    4    16     16       3     5     25      5     25       25
%e A357658    5    32     36       3     7     49      7     49       49
%e A357658    6    64     64       5    11    121     11    121      121
%e A357658    7   128    144       4    13    169     15    225      225
%e A357658   12  4096   4096       9    75   5625     89   7921     8100
%o A357658 (Python 3.10+)
%o A357658 from math import isqrt
%o A357658 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
%o A357658 (C, x64asm, Rust, c++) see Code Golf link, programs by users l4m2 (C, x64asm), gsitcia (Rust), anttiP (c++)
%Y A357658 Cf. A000120, A000290, A356878, A357304, A357753, A357754.
%Y A357658 A357659 and A357660 are the minimal and the maximal values of k producing a(n).
%K A357658 nonn,base
%O A357658 2,2
%A A357658 _Hugo Pfoertner_, Oct 09 2022