login
Highest power of 4 dividing n.
15

%I #45 Dec 31 2022 03:44:19

%S 1,1,1,4,1,1,1,4,1,1,1,4,1,1,1,16,1,1,1,4,1,1,1,4,1,1,1,4,1,1,1,16,1,

%T 1,1,4,1,1,1,4,1,1,1,4,1,1,1,16,1,1,1,4,1,1,1,4,1,1,1,4,1,1,1,64,1,1,

%U 1,4,1,1,1,4,1,1,1,4,1,1,1,16

%N Highest power of 4 dividing n.

%C The generalized binomial coefficients produced by this sequence provide an analog to Kummer's Theorem using arithmetic in base 4.

%C In the binary representation of n, remove zeros from the right until the number of zeros is even, then remove all but the rightmost one bit. - _Ralf Stephan_, Jan 05 2014

%H G. C. Greubel, <a href="/A234957/b234957.txt">Table of n, a(n) for n = 1..1000</a>

%H Tyler Ball, Tom Edgar, and Daniel Juda, <a href="http://dx.doi.org/10.4169/math.mag.87.2.135">Dominance Orders, Generalized Binomial Coefficients, and Kummer's Theorem</a>, Mathematics Magazine, Vol. 87, No. 2, April 2014, pp. 135-143.

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>.

%F a(n) = 4^(valuation(n,4)).

%F a(n) = 4^(floor(valuation(n,2)/2)) = 4^A004526(A007814(n)). Recurrence: a(4n) = 4a(n), a(4n+k) = 1 for k=1,2,3. - _Ralf Stephan_, Jan 05 2014

%F G.f.: x/(1 - x) + 3 * Sum_{k>=1} 4^(k-1)*x^(4^k)/(1 - x^(4^k)). - _Ilya Gutkovskiy_, Jul 10 2019

%F From _Amiram Eldar_, Dec 31 2022: (Start)

%F Multiplicative with a(2^e) = 2^(2*floor(e/2)), and a(p^e) = 1 if p >= 3.

%F Dirichlet g.f.: zeta(s)*(4^s-1)/(4^s-4).

%F Sum_{k=1..n} a(k) ~ (3/(8*log(2)))*n*log(n) + (5/8 + 3*(gamma-1)/(8*log(2)))*n, where gamma is Euler's constant (A001620). (End)

%e Since 8=4*2, then a(8)=4. Likewise, since 4 does not divide 9, a(9)=1.

%t Table[4^(IntegerExponent[n, 4]), {n, 1, 50}] (* _G. C. Greubel_, Apr 13 2017 *)

%o (Sage)

%o n=200 #change n for more terms

%o [4^(valuation(i,4)) for i in [1..n]]

%o (PARI) a(n)=4^valuation(n,4) \\ _Charles R Greathouse IV_, Aug 05 2015

%o (Python)

%o def A234957(n): return 1<<((~n&n-1).bit_length()&-2) # _Chai Wah Wu_, Jul 08 2022

%Y Cf. A001620, A006519, A038500.

%K nonn,easy,mult

%O 1,4

%A _Tom Edgar_, Jan 01 2014

%E Keyword:mult added by _Andrew Howroyd_, Jul 23 2018