A234957 Highest power of 4 dividing n.

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, 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, 1, 4, 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1, 16

Offset: 1

Author

Tom Edgar, Jan 01 2014

Keywords

• nonn
• easy
• mult

Comments

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

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

Examples

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

Links

• G. C. Greubel, Table of n, a(n) for n = 1..1000
• Tyler Ball, Tom Edgar, and Daniel Juda, Dominance Orders, Generalized Binomial Coefficients, and Kummer's Theorem, Mathematics Magazine, Vol. 87, No. 2, April 2014, pp. 135-143.
• Index entries for sequences related to binary expansion of n.

Crossrefs

Cf. A001620, A006519, A038500.

Programs

Mathematica

Table[4^(IntegerExponent[n, 4]), {n, 1, 50}] (* G. C. Greubel, Apr 13 2017 *)

PARI

a(n)=4^valuation(n,4) \\ Charles R Greathouse IV, Aug 05 2015

Python

def A234957(n): return 1<<((~n&n-1).bit_length()&-2) # Chai Wah Wu, Jul 08 2022

Sage

n=200 #change n for more terms
[4^(valuation(i,4)) for i in [1..n]]

Formula

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

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

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

From Amiram Eldar, Dec 31 2022: (Start)

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

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

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)

Extensions

Keyword:mult added by Andrew Howroyd, Jul 23 2018