login
a(n) = a(floor(n/2)) + floor(n/2) with a(1) = 1.
4

%I #40 Sep 28 2024 13:00:05

%S 1,2,2,4,4,5,5,8,8,9,9,11,11,12,12,16,16,17,17,19,19,20,20,23,23,24,

%T 24,26,26,27,27,32,32,33,33,35,35,36,36,39,39,40,40,42,42,43,43,47,47,

%U 48,48,50,50,51,51,54,54,55,55,57,57,58,58,64,64,65,65,67,67,68,68,71,71

%N a(n) = a(floor(n/2)) + floor(n/2) with a(1) = 1.

%C a(2^n) = 2^n, in other cases a(n) < n. Except for the initial 1 all entries are repeated. Apparently no simple formula is known for a(n).

%C Taking every other term seems to give A101925. - _Dominick Cancilla_, Aug 03 2010

%C 1/a(n) is the probability that a randomly chosen divisor of n! is odd. This is because the product n! contains the prime factor 2 a total of a(n) - 1 times (cf. A011371) and thus the prime factor 2 can occur in a divisor of n! a total of a(n) times, ranging between 0 and a(n) - 1 times. - _Martin Renner_, Dec 28 2022

%H G. C. Greubel, <a href="/A113474/b113474.txt">Table of n, a(n) for n = 1..2500</a>

%H Tanya Khovanova, <a href="http://arxiv.org/abs/1410.2193">There are no coincidences</a>, arXiv:1410.2193 [math.CO], 2014.

%F From _Paul Barry_, Aug 27 2006: (Start)

%F a(n) = ( Sum_{k=0..n} floor(n/2^k) ) - n + 1.

%F a(n) = 2 + Sum_{k=0..n} ( floor(n/2^k)-1 ).

%F a(n) = A005187(n) - n + 1. (End)

%F a(n) = n + O(log n). - _Charles R Greathouse IV_, Mar 12 2017

%F a(n) = A011371(n) + 1 for n > 0. - _Martin Renner_, Dec 28 2022

%t a[1]=1;a[n_]:=a[n]=a[Floor[n/2]]+Floor[n/2]; Table[a[n], {n, 100}]

%o (PARI) for(n=1, 90, print1(1 - n + sum(k=0,n, n\2^k), ", ")) \\ _G. C. Greubel_, Mar 11 2017

%o (PARI) a(n)=sum(k=1,logint(n,2), n>>k)+1 \\ _Charles R Greathouse IV_, Mar 12 2017

%o (PARI) a(n)=n+1-hammingweight(n) \\ _Charles R Greathouse IV_, Dec 29 2022

%o (Magma)

%o A113474:= func< n | n+1-Multiplicity(Intseq(n, 2), 1) >;

%o [A113474(n): n in [1..90]]; // _G. C. Greubel_, Sep 28 2024

%o (SageMath)

%o def A113474(n): return n+1 - sum((n+0).digits(2))

%o [A113474(n) for n in range(1,90)] # _G. C. Greubel_, Sep 28 2024

%Y Cf. A005187, A011371, A101925.

%K nonn,easy

%O 1,2

%A _Zak Seidov_, Jan 08 2006