A159918 -id:A159918 - cp's OEIS frontend

A356877 a(n) is the least number k such that (the binary weight of k) - (the binary weight of k^2) = n.

0, 23, 111, 479, 1471, 6015, 24319, 28415, 114175, 457727, 490495, 1964031, 6025215, 8122367, 32497663, 98549759, 132104191, 528449535, 1593769983, 1862205439, 7448952831, 25635323903, 29930291199, 119721689087, 411242070015, 479961546751, 514321285119, 2057287237631, 7687987265535

Offset: 0

Karl-Heinz Hofmann, Oct 10 2022

Note that the terms of A260986 with n > 1 can all be found here. Terms here that are not in A260986 have the property not to be a record value of the ratio (binary weight k) / (binary weight k^2).

Observation: The difference of two neighboring terms is a multiple of 2^(number of the ones after the last zero in binary expression of the smaller term).

			  -----------------------------------------------------------------------------
  n       k          k^2           binary k                          binary k^2
  -----------------------------------------------------------------------------
  0       0            0                  0                                   0
  1      23          529              10111                          1000010001
  2     111        12321            1101111                      11000000100001
  3     479       229441          111011111                  111000000001000001
  4    1471      2163841        10110111111              1000010000010010000001
  5    6015     36180225      1011101111111          10001010000001000100000001
  6   24319    591413761    101111011111111      100011010000000100001000000001
  7   28415    807412225    110111011111111      110000001000000010001000000001
  8  114175  13035930625  11011110111111111  1100001001000000001000010000000001

K. B. Stolarsky, The binary digits of a power, Proc. Amer. Math. Soc. 71 (1978), pp. 1-5.

Cf. A000120, A159918, A260986, A357750.

a[0] = 0; a[n_] := a[n] = Module[{step = If[n == 1, 1, 2^Length[Split[IntegerDigits[a[n - 1], 2]][[-1]]]], k = a[n - 1]}, While[DigitCount[k, 2, 1] - DigitCount[k^2, 2, 1] != n, k += step]; k]; Array[a, 23, 0] (* Amiram Eldar, Oct 14 2022 *)

a(n) = my(k=0); while(hammingweight(k) - hammingweight(k^2) != n, k++); k; \\ Michel Marcus, Oct 14 2022

A356877 = [0]
for n in range(1,29):
    s, k = -1, A356877[-1]
    while bin(A356877[-1])[s] == "1": s -= 1
    while bin(k)[2:].count("1")-bin(k**2)[2:].count("1") != n: k += 2**(abs(s)-1)
    A356877.append(k)
print(A356877)

A094695 Numbers having in binary representation fewer ones than in their squares.

Original entry on oeis.org

5, 9, 10, 11, 13, 17, 18, 19, 20, 21, 22, 25, 26, 27, 29, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 49, 50, 51, 52, 53, 54, 55, 57, 58, 59, 61, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 93, 97, 98, 99

Offset: 1

Reinhard Zumkeller, May 20 2004

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000120, A001737, A007088, A077436, A094694, A159918.

Select[Range[100],DigitCount[#,2,1]Harvey P. Dale, May 29 2017 *)

A000120(a(n)) < A000120(A000290(a(n))).

A214561 Number of 1's in binary expansion of n^n.

Original entry on oeis.org

1, 1, 1, 4, 1, 6, 6, 11, 1, 14, 11, 20, 10, 28, 23, 33, 1, 31, 27, 41, 26, 49, 36, 59, 16, 58, 41, 68, 37, 62, 51, 83, 1, 79, 61, 88, 58, 97, 85, 98, 53, 115, 96, 116, 63, 123, 96, 128, 41, 138, 105, 144, 90, 163, 128, 164, 81, 172, 148, 181, 124, 167, 134, 201, 1

Offset: 0

Alex Ratushnyak, Jul 21 2012

nonn

a(n) + A214562(n) = 1+floor(log_2(n^n)) = 1, 1, 3, 5, 9, 12, 16, 20, 25, 29, 34, 39, 44, 49... is the number of binary digits in n^n. - R. J. Mathar, Jul 22 2012

Alois P. Heinz, Table of n, a(n) for n = 0..16384

Cf. A000120, A159918, A079584.

a:= proc(n) option remember; local m, r;
      m, r:= n^n, 0;
      while m>0 do r:= r +irem(m, 2, 'm') od; r
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Jul 21 2012

Table[Count[IntegerDigits[n^n,2],1],{n,1,64}] (* Geoffrey Critzer, Sep 30 2013 *)
Join[{1},Table[DigitCount[n^n,2,1],{n,100}]] (* Harvey P. Dale, Oct 13 2022 *)

vector(66, n, b=binary((n-1)^(n-1)); sum(j=1, #b, b[j])) /* Joerg Arndt, Jul 21 2012 */

for n in range(300):
    c = 0
    b = n**n
    while b>0:
        c += b&1
        b//=2
    print(c, end=',')

def a(n): return bin(n**n)[2:].count('1')
print([a(n) for n in range(65)]) # Michael S. Branicky, May 22 2021

a(n) = A000120(A000312(n)).

a(2^k)=1.

A232243 a(n) = wt(n^2) - wt(n), where wt(n) = A000120(n) is the binary weight function.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 2, 0, 1, 0, 0, 0, 1, 1, 2, 1, 3, 2, -1, 0, 2, 1, 2, 0, 1, 0, 0, 0, 1, 1, 2, 1, 3, 2, 3, 1, 2, 3, 3, 2, 4, -1, -1, 0, 2, 2, 1, 1, 4, 2, 2, 0, 2, 1, 2, 0, 1, 0, 0, 0, 1, 1, 2, 1, 3, 2, 3, 1, 3, 3, 5, 2, 3, 3, 0, 1, 3, 2, 4, 3, 3, 3, 2, 2, 5, 4, 0, -1, 1, -1, -1, 0, 2, 2, 2

Offset: 0

Jon Perry, Nov 20 2013

A077436 lists n for which a(n) = 0.

A094694 lists n for which a(n) < 0.

			a(5): 5 = 101_2, 25 = 11001_2, so a(5) = 3 - 2 = 1.
a(23): 23 = 10111_2, 529 = 10001001_2, so a(23) = 3 - 4 = -1.

Dumitru Damian, Table of n, a(n) for n = 0..10000

Cf. A000120, A159918, A077436, A094694, A231898.

function bitCount(n) {
   var i,c,s;
   c=0;
   s=n.toString(2);
   for (i=0;i

a(n) = hammingweight(n^2) - hammingweight(n); \\ Michel Marcus, Mar 05 2023

def A232243(n): return (n**2).bit_count()-n.bit_count()
print(list(A232243(n) for n in range(10**2)))  # Dumitru Damian, Mar 04 2023

a(n) = A159918(n) - A000120(n).

A352086 a(n) is the smallest positive integer k such that wt(k^2) / wt(k) = n where wt(k) = A000120(k) is the binary weight of k.

Original entry on oeis.org

1, 21, 2697, 4736533, 14244123157, 4804953862344753

Offset: 1

Bernard Schott, Mar 06 2022

Theorem (proofs in Diophante link):
For any n and any base b, there exists m such that sod_b(m^2) / sod_b(m) = n, where sod_b(m) = sum of digits of m in base b (A280012 for base 10).
a(n) is odd. Proof: a(n) exists. Furthermore, if a(n) is even then wt(a(n)) = wt(a(n)/2) and wt(a(n)^2) = wt((a(n)/2)^2) so then a(n)/2 so that a(n)/2 is a lesser candidate, a contradiction. - David A. Corneth, Mar 06 2022

			We have 21_10 = 10101_2, so wt(21) = 3 ones; then 21^2 = 441_10 = 110111001_2, so wt(21^2) = 6 ones; as 6/3 = 2 and 21 is the smallest integer k such that wt(k^2) / wt(k) = 2, hence a(2) = 21.

Diophante, A1730 - Des chiffres à sommer pour un entier (in French).
Wojciech Muła, Nathan Kurz and Daniel Lemire, Faster Population Counts using AVX2 Instructions, arXiv:1611.07612 [cs.DS], Sep 05 2018.

Cf. A000120, A077436, A083567, A159918, A280012, A352084, A352085.

r[n_] := Total[IntegerDigits[n^2, 2]]/Total[IntegerDigits[n, 2]]; seq[max_, nmax_] := Module[{s = Table[0, {max}], c = 0, n = 1, i}, While[c < max && n < nmax, i = r[n]; If[IntegerQ[i] && s[[i]] == 0, c++; s[[i]] = n]; n+=2]; TakeWhile[s, # > 0 &]]; seq[4, 5*10^6] (* Amiram Eldar, Mar 06 2022 *)

from gmpy2 import popcount
aDict=dict()
for k in range(1, 10**11, 2):
    if popcount(k*k)%popcount(k)==0:
        n=popcount(k*k)//popcount(k)
        if not n in aDict:
            print(n, k); aDict[n]=k # Martin Ehrenstein, Mar 16 2022

a(n) > 2^(n^2/2) for n > 1. - Charles R Greathouse IV, Mar 16 2022

a(3)-a(5) from David A. Corneth, Mar 06 2022

a(6) -- using the Muła et al. Faster Population Counts algorithm -- from Martin Ehrenstein, Mar 15 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

A357750 a(n) is the least k such that B(k^2) - B(k) = n, where B(m) is the binary weight A000120(m).

Original entry on oeis.org

0, 5, 11, 21, 45, 75, 217, 331, 181, 789, 1241, 2505, 5701, 5221, 11309, 19637, 43151, 69451, 82709, 166027, 346389, 607307, 689685, 1458357, 1380917, 2507541, 5906699, 2965685, 5931189, 11862197, 47448787, 82188309, 57804981, 94905541, 188883211, 373457573, 640164021

Offset: 0

Karl-Heinz Hofmann and Hugo Pfoertner, Oct 17 2022

			  ----------------------------------------------------
  n     k      k^2     binary k             binary k^2
  ----------------------------------------------------
  0     0        0            0                      0
  1     5       25          101                  11001
  2    11      121         1011                1111001
  3    21      441        10101              110111001
  4    45     2025       101101            11111101001
  5    75     5625      1001011          1010111111001
  6   217    47089     11011001       1011011111110001
  7   331   109561    101001011      11010101111111001
  8   181    32761     10110101        111111111111001
  9   789   622521   1100010101   10010111111110111001

Cf. A000120, A000290, A159918, A164343, A164344, A356877, A357658.

a(n) = my(k=0); while(hammingweight(k^2) - hammingweight(k) != n, k++); k;

from itertools import count
def A357750(n):
    for k in count(0):
        if (k**2).bit_count()-k.bit_count()==n:
            return k # Chai Wah Wu, Oct 17 2022

A192086 Numbers n such that the binary weight (A000120) of n^3 is less than the binary weight of n^2.

Original entry on oeis.org

219, 309, 349, 438, 467, 565, 618, 665, 698, 701, 817, 876, 885, 934, 1130, 1141, 1143, 1236, 1291, 1297, 1299, 1330, 1396, 1397, 1402, 1435, 1629, 1634, 1659, 1752, 1755, 1770, 1771, 1773, 1868, 1905, 2155, 2229, 2260, 2282, 2286, 2353, 2401, 2472, 2582

Offset: 1

Carl R. White, Jun 23 2011

Numbers n such that A192085(n) < A159918(n).

This sequence is infinite, since if k is in the sequence then so is 2k. - Charles R Greathouse IV, Sep 27 2016

			219^2 decimal = 1011101101011001 binary, and 219^3 decimal = 101000000100010100100011; Since the cube has fewer ones in its binary expansion than the square (eight versus ten), 219 is in the list.

Nathaniel Johnston, Table of n, a(n) for n = 1..2500

Cf. A000120, A159918, A192085.

[ n: n in [0..2600] | &+Intseq(n^3,2) lt &+Intseq(n^2,2) ];  // Bruno Berselli, Jun 24 2011

A192086 := proc(n) return `if`(add(b,b=convert(n^3,base,2))A192086(n),n=0..3000); # Nathaniel Johnston, Jun 23 2011

Select[Range[2800],DigitCount[#^3,2,1]Harvey P. Dale, Jun 30 2011 *)
Flatten@Position[Flatten@(Differences@DigitSum[#^2*{1, #}, 2] & /@Range@15000), ?(# < 0 &)] (* _Hans Rudolf Widmer, Aug 05 2024 *)

is(n)=hammingweight(n^3)Charles R Greathouse IV, Sep 27 2016

A234037 The union of odious numbers with evil squares and evil numbers with odious squares.

Original entry on oeis.org

5, 9, 10, 13, 17, 18, 20, 21, 23, 26, 29, 33, 34, 36, 37, 39, 40, 42, 43, 46, 47, 51, 52, 58, 61, 65, 66, 68, 69, 71, 72, 73, 74, 75, 77, 78, 80, 81, 84, 85, 86, 89, 92, 93, 94, 95, 101, 102, 104, 107, 109, 113, 115, 116, 122, 125, 129, 130, 132, 133, 135, 136, 137

Offset: 1

Gerasimov Sergey, Jan 13 2014

Numbers n with odd sum of binary weight of n and binary weight of n^2.
Primes are in this sequence: 5, 13, 17, 23, 29, 37, 43, 47, 61, 71, 73,....
Evil numbers with odious squares: 5, 9, 10, 17, 18, 20, 23, 29, 33, 34,...
Odious numbers with evil squares: 13, 21, 26, 37, 42, 47, 52, 61, 69,...

			a(3) = 10 because 2 (binary weight of 10) + 3 (binary weight of 100) = 5 (odd).
a(4) = 13 because 3 (binary weight of 13) + 4 (binary weight of 169) = 7 (odd).

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000069, A000120, A001969, A159918, A231431, A235001.

Select[Range[100], Mod[DigitCount[#, 2, 1], 2] != Mod[DigitCount[#^2, 2, 1], 2] &] (* Amiram Eldar, Aug 31 2020 *)

Wrong term removed by Amiram Eldar, Aug 31 2020

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

cp's OEIS Frontend

A356877 a(n) is the least number k such that (the binary weight of k) - (the binary weight of k^2) = n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

A094695 Numbers having in binary representation fewer ones than in their squares.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A214561 Number of 1's in binary expansion of n^n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Python

Formula

A232243 a(n) = wt(n^2) - wt(n), where wt(n) = A000120(n) is the binary weight function.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

JavaScript

PARI

Python

Formula

A352086 a(n) is the smallest positive integer k such that wt(k^2) / wt(k) = n where wt(k) = A000120(k) is the binary weight of k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

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

A357750 a(n) is the least k such that B(k^2) - B(k) = n, where B(m) is the binary weight A000120(m).

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Python

A192086 Numbers n such that the binary weight (A000120) of n^3 is less than the binary weight of n^2.

Views