login
A357658
a(n) is the maximum Hamming weight of squares k^2 in the range 2^n <= k^2 < 2^(n+1).
7
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
A357659 and A357660 are the minimal and the maximal values of k producing a(n).
Sequence in context: A163126 A304818 A088922 * A143092 A143089 A275314
KEYWORD
nonn,base
AUTHOR
Hugo Pfoertner, Oct 09 2022
STATUS
approved