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.

1, 21, 2697, 4736533, 14244123157, 4804953862344753

Offset: 1

Author

Bernard Schott, Mar 06 2022

Keywords

• nonn
• base
• more

Comments

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

Examples

			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.
		

Links

• 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.

Crossrefs

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

Programs

Mathematica

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 *)

Python

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

Formula

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

Extensions

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