A230097 -id:A230097 - cp's OEIS frontend

A159918 Number of ones in binary representation of n^2.

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

Offset: 0

Reinhard Zumkeller, Apr 25 2009

The binary weight (A000120) of n^2.

a(n) = 0 iff n = 0. a(n) = 1 iff n = 2^k for some k >= 0. a(n) = 2 iff n = 3*2^k for some k >= 0. Szalay proves that a(n) = 3 iff n = 7*2^k, 23*2^k, or 2^a + 2^b for k >= 0 and a > b >= 0. It seems that a(n) = 4 iff n = 13*2^k, 15*2^k, 47*2^k, or 111*2^k but this has not been proven! Any other n with a(n) = 4 are greater than 10^50, and there are finitely many odd solutions. - Charles R Greathouse IV, Jan 20 2022

L. Szalay, The equations 2^n ± 2^m ± 2^l = z^2, Indagationes Mathematicae (N.S.) 13, no. 1 (2002), pp. 131-142.

Nathaniel Johnston, Table of n, a(n) for n = 0..10000
Bernt Lindström, On the binary digits of a power, Journal of Number Theory, Volume 65, Issue 2, August 1997, Pages 321-324.
Nick MacKinnon, Problems and Solutions #12140, The American Mathematical Monthly, 126:9 (2019), 850.
K. B. Stolarsky, The binary digits of a power, Proc. Amer. Math. Soc. 71 (1978), 1-5.
Index entries for sequences related to binary expansion of n

Cf. A000120, A007088, A192085, A004159, A214560, A231897, A231898. For records see A230097.

a159918 = a000120 . a000290  -- Reinhard Zumkeller, Oct 12 2013

A159918 := proc(n) return add(b, b=convert(n^2, base, 2)): end: seq(A159918(n), n=0..100); # Nathaniel Johnston, Jun 23 2011

a[n_] := Total[IntegerDigits[n^2, 2]];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Oct 27 2021 *)

a(n)=hammingweight(n^2) \\ Charles R Greathouse IV, Aug 06 2015

def A159918(n):
    return bin(n*n).count('1') # Chai Wah Wu, Sep 03 2014

a(n) = A000120(A000290(n)); a(A077436(n)) = A000120(A077436(n)).
Lindström shows that lim sup wt(m^2)/log_2 m = 2. - N. J. A. Sloane, Oct 11 2013
a(n) = [x^(n^2)] (1/(1 - x))*Sum_{k>=0} x^(2^k)/(1 + x^(2^k)). - Ilya Gutkovskiy, Mar 27 2018

A231897 a(n) = smallest m such that wt(m^2) = n (where wt(i) = A000120(i)), or -1 if no such m exists.

Original entry on oeis.org

0, 1, 3, 5, 13, 11, 21, 39, 45, 75, 155, 217, 331, 181, 627, 923, 1241, 2505, 3915, 5221, 6475, 11309, 15595, 19637, 31595, 44491, 69451, 113447, 185269, 244661, 357081, 453677, 1015143, 908091, 980853, 2960011, 4568757, 2965685, 5931189, 11862197, 20437147

Offset: 0

N. J. A. Sloane, Nov 19 2013

Conjecture: a(n) is never -1. (It seems likely that the arguments of Lindström (1997) could be modified to establish this conjecture.)

a(n) is the smallest m such that A159918(m) = n (or -1 if ...).

Hugo Pfoertner, Table of n, a(n) for n = 0..110 (terms 0..70 from Donovan Johnson, significant extension enabled by programs provided in Code Golf challenge).
Code Golf Stackexchange, Smallest and largest 100-bit square with maximum Hamming weight, fastest code challenge started Dec 15 2022.
Bernt Lindström, On the binary digits of a power, Journal of Number Theory, Volume 65, Issue 2, August 1997, Pages 321-324.

Cf. A000120, A159918, A230097, A211201, A231898, A214560.

A089998 are the corresponding squares.

a231897 n = head [x | x <- [1..], a159918 x == n]
-- Reinhard Zumkeller, Nov 20 2013

a(n)=if(n,my(k); while(hammingweight(k++^2)!=n,); k, 0) \\ Charles R Greathouse IV, Aug 06 2015

def wt(n): return bin(n).count('1')
def a(n):
    m = 2**(n//2) - 1
    while wt(m**2) != n: m += 1
    return m
print([a(n) for n in range(32)]) # Michael S. Branicky, Feb 06 2022

a(n) = 2*A211201(n-1) + 1 for n >= 1. - Hugo Pfoertner, Feb 06 2022

a(26)-a(40) from Reinhard Zumkeller, Nov 20 2013

A231898 a(n) = smallest k with property that for all m >= k, there is a square N^2 whose binary expansion contains exactly n 1's and m 0's; or -1 if no such k exists.

Original entry on oeis.org

-1, -1, 2, -1, 4, 3, 4, 3, 4, 5, 5, 5, 6, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6

Offset: 1

N. J. A. Sloane, Nov 19 2013

a(n) = -1 for n = 1, 2 and 4, because all squares with exactly 1, 2 or 4 1's in their binary expansion must contain an even number of 0's.
Conjecture: Apart from n=1, 2 and 4, no other a(n) is -1.
See A214560 for a related conjecture.

			Here is a table whose columns give:
N, N^2, number of bits in N^2, number of 1's in N^2, number of 0's in N^2:
0 0 1 0 1
1 1 1 1 0
2 4 3 1 2
3 9 4 2 2
4 16 5 1 4
5 25 5 3 2
6 36 6 2 4
7 49 6 3 3
8 64 7 1 6
9 81 7 3 4
10 100 7 3 4
11 121 7 5 2
12 144 8 2 6
13 169 8 4 4
14 196 8 3 5
15 225 8 4 4
16 256 9 1 8
17 289 9 3 6
18 324 9 3 6
19 361 9 5 4
...
a(n) is defined by the property that for all m >= a(n), the table contains a row ending n m. For example, there are rows ending 3 2, 3 3, 3 4, 3 5, ..., but not 3 1, so a(3) = 2.
a(5)=4: for t>=0, (11*2^t)^2 contains 5 1's and 2t+2 0's and (25*2^t)^2 contains 5 1's and 2t+5 0's, so for m >= 4 there is a number N such that N^2 contains 5 1's and m 0's. Also 4 is the smallest number with this property, so a(5) = 4.

Cf. A000120, A023416, A159918, A214560, A230097, A231897.

Missing word in definition supplied by Jon Perry, Nov 20 2013.

A357304 Records of the Hamming weight of squares.

Original entry on oeis.org

0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 33, 34, 35, 37, 38, 39, 40, 41, 42, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 62, 63, 64, 65, 66, 67, 68, 69, 70, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 85, 87, 88, 89

Offset: 1

Hugo Pfoertner, Oct 01 2022

			a(70) = 77 corresponds to A230097(70) = 34895284158283. Its square 1217680856487316499797508089 is the smallest and the only 90-bit square with this Hamming weight.

A230097 gives the values of k such that A000120(k^2) sets a new record.

Cf. A000120, A000290, A159918, A357658.

Missing a(68)=75 and a(71)-a(80) from Bert Dobbelaere, Nov 20 2022

A357305 Numbers k > 1 such that the ratio (numbers of zeros)/(total length) in the binary representation of k^2 is a new minimum.

Original entry on oeis.org

2, 3, 5, 11, 45, 181, 48589783221, 66537313397, 398064946368587, 796095014224053

Offset: 1

Hugo Pfoertner, Oct 01 2022

			    k    k^2  (binary zeros)/A070939(k^2)
    .      .   .     k^2 written in binary
    2      4  2/3   [1, 0, 0]
    3      9  1/2   [1, 0, 0, 1]
    5     25  2/5   [1, 1, 0, 0, 1]
   11    121  2/7   [1, 1, 1, 1, 0, 0, 1]
   45   2025  3/11  [1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1]
  181  32761  2/15  [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1]

Cf. A000120, A000290, A070939, A159918, A230097.

a(7)-a(8) from Michael S. Branicky, Oct 01 2022 using A230097, verified with exhaustive search Oct 02 2022

a(9)-a(10) from Hugo Pfoertner, Nov 30 2022

A260986 Numbers n such that H(n)/H(n^2) is a new record, where H(n) = A000120(n) is the sum of the binary digits of n.

Original entry on oeis.org

1, 23, 111, 479, 1471, 6015, 24319, 28415, 490495, 6025215, 8122367, 98549759, 132104191, 1593769983, 1862205439, 29930291199, 479961546751, 514321285119, 8237743079423, 131872659079167, 136270705590271, 35461448750596095, 7998111458938322943, 9151032963545169919

Offset: 1

Charles R Greathouse IV, Aug 06 2015

This sequence is infinite, a result which follows from Stolarsky's Theorem 2.
a(22) > 2.4*10^13. - Giovanni Resta, Aug 07 2015
a(25) > 5.8*10^20. - Karl-Heinz Hofmann, Oct 14 2022

			23 is 10111 in binary and 23^2 = 529 is 1000010001 in binary. Each smaller number has H(n)/H(n^2) <= 1, but H(23)/H(529) = 4/3 > 1, so 23 is in this sequence.

Kevin G. Hare, Shanta Laishram, and Thomas Stoll, Stolarsky's conjecture and the sum of digits of polynomial values, Proc. Amer. Math. Soc. 139:1 (2011), pp. 39-49.
K. B. Stolarsky, The binary digits of a power, Proc. Amer. Math. Soc. 71 (1978), pp. 1-5.

Cf. A000120, A159918, A230097.

Subsequence of A356877.

DeleteDuplicates[Table[{n,Total[IntegerDigits[n,2]]/Total[IntegerDigits[n^2,2]]},{n,500000}],GreaterEqual[ #1[[2]],#2[[2]]]&][[;;,1]] (* The program generates the first 9 terms of the sequence. *) (* Harvey P. Dale, Sep 21 2023 *)

r=2; forstep(n=1,1e9,2, t=hammingweight(n^2)/hammingweight(n); if(t

a(16)-a(21) from Giovanni Resta, Aug 07 2015

a(22)-a(24) from Karl-Heinz Hofmann, Oct 14 2022

A357656 a(n) is a lower bound for the largest Hamming weight of squares with exactly n binary zeros.

Original entry on oeis.org

1, 0, 13, 8, 13, 16, 37, 38, 44

Offset: 0

Karl-Heinz Hofmann and Hugo Pfoertner, Oct 07 2022

The terms from a(2) onwards must be regarded as lower bounds, because no proof for the non-existence of squares with a very small number of binary zeros in the range k^2 > 2^90 (see b-file of A230097) is known.

a(9) >= 63, a(10) >= 57.

			                A357657(n)
   n  a(n) bits     k       k^2          k^2 in binary
   0    1    1      1         1                      1
   1    0    1      0         0                      0
   2   13   15    181     32761        111111111111001
   3    8   11     45      2025            11111101001
   4   13   17    362    131044      11111111111100100
   5   16   21   1241   1540081  101110111111111110001

A357657 are the corresponding square roots of the record-setting squares.

Cf. A000120, A000290, A159918, A230097, A356878, A357304, A357305.

A357657 a(n) is a lower bound for the square root of the maximum square with exactly n zeros in its binary representation.

Original entry on oeis.org

1, 0, 181, 45, 362, 1241, 2965685, 5931189, 57804981

Offset: 0

Karl-Heinz Hofmann and Hugo Pfoertner, Oct 08 2022

See A357656 for more information.

a(9) >= 66537313397, a(10) >= 10520476455.

A357656 gives the Hamming weight of the squared terms.

Cf. A000120, A000290, A159918, A230097, A356838, A357304, A357305, A357753, A357754.

cp's OEIS Frontend

A159918 Number of ones in binary representation of n^2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A231897 a(n) = smallest m such that wt(m^2) = n (where wt(i) = A000120(i)), or -1 if no such m exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

PARI

Python

Formula

Extensions

A231898 a(n) = smallest k with property that for all m >= k, there is a square N^2 whose binary expansion contains exactly n 1's and m 0's; or -1 if no such k exists.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A357304 Records of the Hamming weight of squares.

Views

Author

Keywords

Examples

Crossrefs

Extensions

A357305 Numbers k > 1 such that the ratio (numbers of zeros)/(total length) in the binary representation of k^2 is a new minimum.

Views

Author

Keywords

Examples

Crossrefs

Extensions

A260986 Numbers n such that H(n)/H(n^2) is a new record, where H(n) = A000120(n) is the sum of the binary digits of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A357656 a(n) is a lower bound for the largest Hamming weight of squares with exactly n binary zeros.

Views

Author

Keywords

Comments

Examples

Crossrefs

A357657 a(n) is a lower bound for the square root of the maximum square with exactly n zeros in its binary representation.

Views

Author

Keywords

Comments

Crossrefs