login
Number of ones in the binary expansion of 3^n.
20

%I #72 Apr 19 2024 17:38:51

%S 1,2,2,4,3,6,6,5,6,8,9,13,10,11,14,15,11,14,14,17,17,20,19,22,16,18,

%T 24,30,25,25,25,26,26,34,29,32,27,34,36,32,28,39,38,39,34,34,45,38,41,

%U 33,41,46,42,35,39,42,39,40,42,48,56,56,49,57,56,51,45,47,55,55,64,68,58

%N Number of ones in the binary expansion of 3^n.

%C Conjecture: a(n)/n tends to log(3)/(2*log(2)) = 0.792481250... (A094148). - _Ed Pegg Jr_, Dec 05 2002

%C Senge & Straus prove that for every m, there is some N such that for all n > N, a(n) > m. Dimitrov & Howe make this effective, proving that for n > 25, a(n) > 22. - _Charles R Greathouse IV_, Aug 23 2021

%C Ed Pegg's conjecture means that about half of the bits of 3^n are nonzero. It appears that the same is true for 5^n (A000351, cf. A118738) and 7^n (A000420). - _M. F. Hasler_, Apr 17 2024

%D S. Wolfram, "A new kind of science", p. 903.

%H Hugo Pfoertner, <a href="/A011754/b011754.txt">Table of n, a(n) for n = 0..10000</a> (terms 0..1000 from T. D. Noe)

%H Vassil S. Dimitrov and Everett W. Howe, <a href="https://arxiv.org/abs/2105.06440">Powers of 3 with few nonzero bits and a conjecture of Erdős</a>, arXiv:2105.06440 [math.NT], 2021.

%H Taylor Dupuy and David E. Weirich, <a href="https://doi.org/10.1016/j.jnt.2015.05.022">Bits of 3^n in binary, Wieferich primes and a conjecture of Erdős</a>, Journal of Number Theory, Volume 158, January 2016, Pages 268-280.

%H Hugo Pfoertner, <a href="/A011754/a011754.png">Plot of a(n) - 0.79248*n</a>, +-Pi*sqrt(n), n up to 10^6.

%H H. G. Senge and E. G. Straus, <a href="https://doi.org/10.1007/BF02018464">PV-numbers and sets of multiplicity</a>, Periodica Mathematica Hungarica 3 (1973), pp. 93-100.

%F a(n) = A000120(3^n). - _Benoit Cloitre_, Dec 06 2002

%F a(n) = A000120(A000244(n)). - _Reinhard Zumkeller_, Aug 14 2015

%p f:= n -> convert(convert(3^n,base,2),`+`):

%p map(f, [$0..100]); # _Robert Israel_, Apr 17 2024

%t Table[DigitCount[3^n, 2][[1]], {n, 0, 100}] (* _Stefan Steinerberger_, Apr 03 2006 *)

%t DigitCount[3^Range[0,100],2,1] (* _Harvey P. Dale_, Apr 06 2012 *)

%o (Haskell) a011754 = a000120 . a000244 -- _Reinhard Zumkeller_, Aug 14 2015

%o (Magma) [&+Intseq(3^n, 2): n in [0..79]]; // _Vincenzo Librandi_, Nov 28 2018

%o (PARI) a(n)=hammingweight(3^n) \\ _Charles R Greathouse IV_, Feb 09 2017

%o (Python) A011754 = lambda n: (3**n).bit_count() # _M. F. Hasler_, Apr 17 2024

%Y Cf. A007088, A000120 (Hamming weight), A000244 (3^n), A004656, A261009, A094148.

%Y Cf. A118738 (same for 5^n).

%K nonn,nice,easy

%O 0,2

%A _Allan C. Wechsler_, Dec 11 1999

%E More terms from _Stefan Steinerberger_, Apr 03 2006