login
Exponent of highest power of 2 dividing the sum 1^n + 2^n + ... + n^n.
2

%I #21 Jul 09 2022 11:10:34

%S 0,0,2,1,0,0,4,2,0,0,2,1,0,0,6,3,0,0,2,1,0,0,4,2,0,0,2,1,0,0,8,4,0,0,

%T 2,1,0,0,4,2,0,0,2,1,0,0,6,3,0,0,2,1,0,0,4,2,0,0,2,1,0,0,10,5,0,0,2,1,

%U 0,0,4,2,0,0,2,1,0,0,6,3,0,0,2,1,0,0,4

%N Exponent of highest power of 2 dividing the sum 1^n + 2^n + ... + n^n.

%C 2-adic valuation of Sum_{k = 1..n} k^n.

%C Omitting the zero terms (for n == 1 or 2 mod 4) gives A220780.

%H T. D. Noe, <a href="/A220779/b220779.txt">Table of n, a(n) for n = 1..1024</a>

%H T. Lengyel, <a href="http://www.emis.de/journals/INTEGERS/papers/h41/h41.Abstract.html">On divisibility of some power sums</a>, INTEGERS, 7(2007), A41, 1-6.

%H K. MacMillan and J. Sondow, <a href="https://www.mat.uniroma2.it/~tauraso/AMM/AMM11546.pdf">Problem 11546: 2-adic Valuation of Bernoulli-style Sums</a>, Amer. Math. Monthly, 118 (2011), 84 (proposal); 119 (2012), 886-887 (solution).

%H K. MacMillan and J. Sondow, <a href="http://arxiv.org/abs/1010.2275">Divisibility of power sums and the generalized Erdos-Moser equation</a>, arXiv:1010.2275 [math.NT], 2010-2011; Elemente der Mathematik, 67 (2012), 182-186.

%F a(n) = d - 1 or 2*(d - 1), according as n or n+1 = 2^d * odd, with d > 0.

%F a(n) = A007814(A031971(n)).

%e 1^3 + 2^3 + 3^3 = 1 + 8 + 27 = 36 = 2^2 * 9, so a(3) = 2.

%t Table[ IntegerExponent[ Sum[ k^n, {k, 1, n}], 2], {n, 150}]

%o (Python)

%o from sympy import harmonic

%o def A220779(n): return (~(m:=int(harmonic(n,-n)))&m-1).bit_length() # _Chai Wah Wu_, Jul 08 2022

%o (PARI) a(n) = valuation(sum(k=1, n, k^n), 2); \\ _Michel Marcus_, Jul 09 2022

%Y Cf. A031971, A001511, A007814, A220780.

%K nonn,easy

%O 1,3

%A _Jonathan Sondow_, Dec 20 2012