A352084 -id:A352084 - cp's OEIS frontend

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

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

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

Original entry on oeis.org

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

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

cp's OEIS Frontend

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

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

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