login
Numbers k with the property that the number of 1's in binary expansion of k (see A000120) divides k.
66

%I #82 Aug 30 2023 07:28:00

%S 1,2,4,6,8,10,12,16,18,20,21,24,32,34,36,40,42,48,55,60,64,66,68,69,

%T 72,80,81,84,92,96,108,110,115,116,120,126,128,130,132,136,138,144,

%U 155,156,160,162,168,172,180,184,185,192,204,205,212,216,220,222,228

%N Numbers k with the property that the number of 1's in binary expansion of k (see A000120) divides k.

%C If instead of base 2 we take base 10, then we have the so-called Harshad or Niven numbers (i.e., positive integers divisible by the sum of their digits; A005349). - _Emeric Deutsch_, Apr 11 2007

%C A199238(a(n)) = 0. - _Reinhard Zumkeller_, Nov 04 2011

%H Indranil Ghosh, <a href="/A049445/b049445.txt">Table of n, a(n) for n = 1..20000</a> (first 1000 terms from T. D. Noe)

%H Paul Dalenberg and Tom Edgar, <a href="https://www.fq.math.ca/56-2.html">Consecutive factorial base Niven numbers</a>, Fibonacci Quarterly, Vol. 56, No. 2 (2018), pp. 163-166.

%H Jean-Marie De Koninck, Nicolas Doyon and Imre Kátai, <a href="https://eudml.org/doc/278575">On the counting function for the Niven numbers</a>, Acta Arithmetica, Vol. 106, No. 3 (2003), pp. 265-275.

%F {k : A000120(k) | k}. - _R. J. Mathar_, Mar 03 2008

%F a(n) seems to be asymptotic to c*n*log(n) where 0.7 < c < 0.8. - _Benoit Cloitre_, Jan 22 2003

%F Heuristically, c should be 1/(2*log(2)), since a random d-bit number should have probability approximately 2/d of being in the sequence. - _Robert Israel_, Aug 22 2014

%F {a(n)} = {k : A199238(k) = 0}. - _M. F. Hasler_, Oct 09 2012

%F De Koninck et al. (2003) proved that the number of base-b Niven numbers not exceeding x, N_b(x), is asymptotically equal to ((2*log(b)/(b-1)^2) * Sum_{j=1..b-1} gcd(j, b-1) + o(1)) * x/log(x). For b=2, N_2(n) ~ (2*log(2) + o(1)) * x/log(x). Therefore, the constant c mentioned above is indeed 1/(2*log(2)). - _Amiram Eldar_, Aug 16 2020

%e 20 is in the sequence because 20 is written 10100 in binary and 1 + 1 = 2, which divides 20.

%e 21 is in the sequence because 21 is written 10101 in binary and 1 + 1 + 1 = 3, which divides 21.

%e 22 is not in the sequence because 22 is written 10110 in binary 1 + 1 + 1 = 3, which does not divide 22.

%p a:=proc(n) local n2: n2:=convert(n,base,2): if n mod add(n2[i],i=1..nops(n2)) = 0 then n else fi end: seq(a(n),n=1..300); # _Emeric Deutsch_, Apr 11 2007

%t binHarshadQ[n_] := Divisible[n, Count[IntegerDigits[n, 2], 1]]; Select[Range[228], binHarshadQ] (* _Jean-François Alcover_, Dec 01 2011 *)

%t Select[Range[300],Divisible[#,DigitCount[#,2,1]]&] (* _Harvey P. Dale_, Mar 20 2016 *)

%o (PARI) for(n=1,1000,b=binary(n);l=length(b); if(n%sum(i=1,l, component(b,i))==0,print1(n,",")))

%o (PARI) is_A049445(n)={n%norml2(binary(n))==0} \\ _M. F. Hasler_, Oct 09 2012

%o (PARI) isok(n) = ! (n % hammingweight(n)); \\ _Michel Marcus_, Feb 10 2016

%o (Haskell)

%o a049445 n = a049445_list !! (n-1)

%o a049445_list = map (+ 1) $ elemIndices 0 a199238_list

%o -- _Reinhard Zumkeller_, Nov 04 2011

%o (Python)

%o A049445 = [n for n in range(1,10**5) if not n % sum([int(d) for d in bin(n)[2:]])] # _Chai Wah Wu_, Aug 22 2014

%Y Cf. A000120, A005349, A199238.

%K nonn,easy,nice,base

%O 1,2

%A _N. J. A. Sloane_

%E More terms from _Michael Somos_

%E Edited by _N. J. A. Sloane_, Oct 07 2005 and May 16 2008