A083567 -id:A083567 - cp's OEIS frontend

A077436 Let B(n) be the sum of binary digits of n. This sequence contains n such that B(n) = B(n^2).

0, 1, 2, 3, 4, 6, 7, 8, 12, 14, 15, 16, 24, 28, 30, 31, 32, 48, 56, 60, 62, 63, 64, 79, 91, 96, 112, 120, 124, 126, 127, 128, 157, 158, 159, 182, 183, 187, 192, 224, 240, 248, 252, 254, 255, 256, 279, 287, 314, 316, 317, 318, 319, 351, 364, 365, 366, 374, 375, 379, 384

Offset: 1

Giuseppe Melfi, Nov 30 2002

Superset of A023758.

Hare, Laishram, & Stoll show that this sequence contains infinitely many odd numbers. In particular for each k in {12, 13, 16, 17, 18, 19, 20, ...} there are infinitely many terms in this sequence with binary digit sum k. - Charles R Greathouse IV, Aug 25 2015

			The element 79 belongs to the sequence because 79=(1001111) and 79^2=(1100001100001), so B(79)=B(79^2)

Reinhard Zumkeller, Table of n, a(n) for n = 1..10476, all terms <= 2^20
Karam Aloui, Damien Jamet, Hajime Kaneko, Steffen Kopecki, Pierre Popoli, and Thomas Stoll, On the binary digits of n and n^2, arXiv:2203.05451 [math.NT], 2022.
K. G. Hare, S. Laishram, and T. Stoll, The sum of digits of n and n^2, International Journal of Number Theory 7:7 (2011), pp. 1737-1752.
Giuseppe Melfi, On simultaneous binary expansions of n and n^2, arXiv:math/0402458 [math.NT], 2004.
Giuseppe Melfi, Su alcune successioni di interi (English with an Italian title)

Cf. A058369, A000120, A000290, A083567.
Cf. A211676 (number of n-bit numbers in this sequence).
A261586 is a subsequence. Subsequence of A352084.

import Data.List (elemIndices)
import Data.Function (on)
a077436 n = a077436_list !! (n-1)
a077436_list = elemIndices 0
   $ zipWith ((-) `on` a000120) [0..] a000290_list
-- Reinhard Zumkeller, Apr 12 2011

[n: n in [0..400] | &+Intseq(n, 2) eq &+Intseq(n^2, 2)]; // Vincenzo Librandi, Aug 30 2015

select(t -> convert(convert(t,base,2),`+`) = convert(convert(t^2,base,2),`+`), [$0..1000]); # Robert Israel, Aug 27 2015

t={}; Do[If[DigitCount[n, 2, 1] == DigitCount[n^2, 2, 1], AppendTo[t, n]], {n, 0, 364}]; t
f[n_] := Total@ IntegerDigits[n, 2]; Select[Range[0, 384], f@ # == f[#^2] &] (* Michael De Vlieger, Aug 27 2015 *)

is(n)=hammingweight(n)==hammingweight(n^2) \\ Charles R Greathouse IV, Aug 25 2015

def ok(n): return bin(n).count('1') == bin(n**2).count('1')
print([m for m in range(400) if ok(m)]) # Michael S. Branicky, Mar 11 2022

A159918(a(n)) = A000120(a(n)). - Reinhard Zumkeller, Apr 25 2009

Initial 0 added by Reinhard Zumkeller, Apr 28 2012, Apr 12 2011

A352084 Integers m such that wt(m) divides wt(m^2) where wt(m) = A000120(m) is the binary weight of m.

Original entry on oeis.org

1, 2, 3, 4, 6, 7, 8, 12, 14, 15, 16, 21, 24, 28, 30, 31, 32, 37, 42, 45, 48, 53, 56, 60, 62, 63, 64, 69, 73, 74, 79, 81, 83, 84, 90, 91, 96, 106, 112, 120, 124, 126, 127, 128, 133, 137, 138, 141, 146, 148, 155, 157, 158, 159, 161, 162, 165, 166, 168, 177, 180

Offset: 1

Bernard Schott, Mar 03 2022

Integers m such that A000120(m) divides A159918(m).
This is a problem proposed by the French site Diophante in the links section.
The first 18 terms are the same as A268415, then A268415(19) = 41 while a(19) = 42.
The corresponding quotients are in A352085.
The smallest term k such that the corresponding quotient = n is A352086(n).
Some subsequences:
-> wt(m^2) = wt(m) iff m is in A077436.
-> wt(m^2) / wt(m) = 2 iff m is in A083567.
-> When m is a power of 2 (A000079): wt(2^k) = wt((2^k)^2) = wt(2^(2k)) = 1.

			37_10 = 100101_2, digsum_2(37) = 1+1+1 = 3; then 37^2 = 1369_10 = 10101011001_2, digsum_2(1369) = 1+1+1+1+1+1 = 6; as 3 divides 6, 37 is a term.

Martin Ehrenstein, Table of n, a(n) for n = 1..10000
Diophante, A1730 - Des chiffres à sommer pour un entier (in French).

Cf. A000120, A159918, A268415, A351650, A352085, A352086.
Cf. A351650 (similar for base 10).
Subsequences: A000079, A023758, A077436, A083567.

Select[Range[180], Divisible[Total[IntegerDigits[#^2, 2]], Total[IntegerDigits[#, 2]]] &] (* Amiram Eldar, Mar 03 2022 *)

isok(m) = !(hammingweight(m^2) % hammingweight(m)); \\ Michel Marcus, Mar 03 2022

def ok(n): return n > 0 and bin(n**2).count('1')%bin(n).count('1') == 0
print([m for m in range(1, 200) if ok(m)]) # Michael S. Branicky, Mar 03 2022

More terms from Amiram Eldar, Mar 03 2022

A212314 Numbers m such that B(m^3) = 3*B(m), where B(m) is the binary weight of m (A000120).

Original entry on oeis.org

0, 5, 9, 10, 17, 18, 20, 33, 34, 36, 39, 40, 49, 65, 66, 68, 69, 72, 78, 80, 98, 105, 129, 130, 132, 135, 136, 138, 144, 156, 160, 169, 196, 199, 209, 210, 229, 257, 258, 260, 263, 264, 270, 272, 276, 277, 288, 291, 297, 312, 313, 320, 338, 359, 365, 392, 395, 398, 418

Offset: 1

Alex Ratushnyak, Oct 24 2013

2*k is a term if and only if k is a term. - Robert Israel, Nov 06 2022

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A000120, A077436, A083567, A118655, A212315.

Includes A136318.

select(n -> convert(convert(n^3,base,2),`+`) = 3*convert(convert(n,base,2),`+`), [$0..1000]); # Robert Israel, Nov 06 2022

isok(m) = hammingweight(m^3) == 3*hammingweight(m); \\ Michel Marcus, Nov 06 2022

import math
for n in range(10000):
    c1 = c2 = 0
    t = n
    while t:
        c1+=t&1
        t>>=1
    t = n*n*n
    while t:
        c2+=t&1
        t>>=1
    if c1*3==c2: print(str(n), end=',')

s = lambda n: sum((n^3).digits(2)) - 3*sum(n.digits(2))
[n for n in (0..418) if s(n)==0]  # Peter Luschny, Oct 24 2013

A000120(a(n)^3) = A000120(a(n)) * 3.

A352085 a(n) is the quotient wt(m^2) / wt(m), where wt = binary weight = A000120 and m = A352084(n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 2, 2, 1, 2, 1, 1, 1, 1, 1, 2, 2, 2, 1, 2, 2, 2, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 1, 2, 2, 2, 2, 2, 2

Offset: 1

Bernard Schott, Mar 05 2022

All positive integers are terms of this sequence and the smallest integer k such that a(k) = n is A352086(n).

a(n) = 1 iff m = A352084(n) is a term of A077436, and a(n) = 2 iff m = A352084(n) is a term of A083567.

			For n=19, A352084(19) = 42_10 = 101010_2 => wt(42) = 3 ones; then 42^2 = 1764_10 = 11011100100_2 => wt(1764) = 6 ones, so that a(19) = wt(42^2) / wt(42) = 6/3 = 2.

Martin Ehrenstein, Table of n, a(n) for n = 1..10000
Diophante, A1730 - Des chiffres à sommer pour un entier (in French).

Cf. A000120, A077436, A083567, A159918, A352084, A352086.

Select[Total[IntegerDigits[#^2, 2]]/Total[IntegerDigits[#, 2]] & /@ Range[300], IntegerQ] (* Amiram Eldar, Mar 05 2022 *)

lista(nn) = my(list = List(), q); for (n=1, nn, if (denominator(q=hammingweight(n^2)/hammingweight(n)) == 1, listput(list, q));); Vec(list); \\ Michel Marcus, Mar 05 2022

from itertools import count, islice
def agen(): # generator of terms
    for m in count(1):
        q, r = divmod(bin(m**2).count('1'), bin(m).count('1'))
        if r == 0:
            yield q
print(list(islice(agen(), 100))) # Michael S. Branicky, Mar 05 2022

a(n) = A159918(A352084(n))/A000120(A352084(n)).

More terms from Michel Marcus, Mar 05 2022

A212315 Numbers m such that B(m) = B(triangular(m)), where B(m) is the binary weight of m (A000120).

Original entry on oeis.org

0, 1, 3, 7, 15, 31, 39, 45, 63, 78, 79, 91, 93, 127, 139, 143, 158, 159, 175, 182, 187, 189, 222, 255, 286, 287, 318, 319, 351, 367, 375, 379, 381, 407, 446, 487, 511, 535, 543, 572, 574, 575, 607, 627, 638, 639, 703, 724, 727, 731, 747, 750, 759, 763, 765, 799, 823, 830

Offset: 1

Alex Ratushnyak, Oct 24 2013

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

Cf. A000120, A077436, A083567, A118655, A212314.

def isa(n): return n.bit_count()==((n*(n+1))>>1).bit_count()
print(list(n for n in range(10**3) if isa(n)))  # Dumitru Damian, Mar 04 2023

A000120(a(n)) = A000120(a(n)*(a(n)+1)/2).

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

A358268 a(n) is the least number k > 0 such that the binary weight of k^n is n times the binary weight of k.

Original entry on oeis.org

1, 21, 5, 21, 17, 17, 9, 113, 17, 49, 665, 37, 149, 17, 275, 163, 33, 41, 97, 67, 141, 67, 135, 197, 49, 267, 81, 81, 69, 779, 1163, 69, 325, 49, 587, 837, 281, 197, 293, 49, 147, 677, 67, 651, 647, 67, 793, 277, 353, 49, 1233, 1177, 165, 775, 721, 353, 817, 69, 647, 709, 209, 1233, 69, 67, 263

Offset: 1

Robert Israel, Nov 06 2022

a(n) is the least number k > 0 such that A000120(k^n) = n*A000120(k).
All terms are odd.
Conjecture: lim_{n -> infinity} a(n) = infinity.

			a(3) = 5 because 5 = 101_2 and 5^3 = 1111101_2 so A000120(5) = 2, A000120(5^3) = 6 and 6 = 3*2.

Chai Wah Wu, Table of n, a(n) for n = 1..10000 (n = 1..1004 from Robert Israel)

Cf. A000120, A083567, A212314.

f:= proc(n) local k;
    for k from 1 by 2 do
      if convert(convert(k^n,base,2),`+`) = n*convert(convert(k,base,2),`+`) then return k
      fi
    od
end proc:
map(f, [$1..50]);

a[n_] := Module[{k = 1}, While[Divide @@ DigitCount[k^{n, 1}, 2, 1] != n, k += 2]; k]; Array[a, 65] (* Amiram Eldar, Nov 07 2022 *)

a(n) = my(k=1); while (hammingweight(k^n) != n*hammingweight(k), k++); k; \\ Michel Marcus, Nov 07 2022

def a(n):
    k = 1
    while bin(k**n).count("1") != n*bin(k).count("1"): k += 2
    return k
print([a(n) for n in range(1, 66)]) # Michael S. Branicky, Nov 06 2022

from itertools import count
def A358268(n): return next(filter(lambda k:k.bit_count()*n==(k**n).bit_count(),count(1,2))) # Chai Wah Wu, Nov 07 2022

cp's OEIS Frontend

A077436 Let B(n) be the sum of binary digits of n. This sequence contains n such that B(n) = B(n^2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A352084 Integers m such that wt(m) divides wt(m^2) where wt(m) = A000120(m) is the binary weight of m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

A212314 Numbers m such that B(m^3) = 3*B(m), where B(m) is the binary weight of m (A000120).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

Python

Sage

Formula

A352085 a(n) is the quotient wt(m^2) / wt(m), where wt = binary weight = A000120 and m = A352084(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A212315 Numbers m such that B(m) = B(triangular(m)), where B(m) is the binary weight of m (A000120).

Views

Author

Keywords

Links

Crossrefs

Programs

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