Sums of integer powers similar to Prouhet–Tarry–Escott problem

Solution 1:

The exponential generating function for $S_{n,m}=\displaystyle\sum_{k=0}^{2^n-1}(-1)^{\sigma_2(k)}k^m$ (w.r.t. $m$) is $$\sum_{m=0}^\infty S_{n,m}\frac{x^m}{m!}=\sum_{k=0}^{2^n-1}(-1)^{\sigma_2(k)}e^{kx}=\prod_{k=0}^{n-1}(1-e^{2^k x})=2^{n(n-1)/2}(-x)^n\exp\sum_{k=0}^{n-1}f(2^k x),$$ where $$f(x)=\log\frac{e^x-1}{x}=\sum_{m=1}^\infty\frac{B_m^+}{m}\frac{x^m}{m!}$$ using the Bernoulli numbers (look at $f'(x)$ to see the expansion). Thus, \begin{align*} S_{n,n+p}&=(-1)^n 2^{n(n-1)/2}(n+p)!\ A_p(2^n), \\A_p(a)&=[x^p]\exp\sum_{m=1}^\infty\frac{a^m-1}{2^m-1}\frac{B_m^+}{m}\frac{x^m}{m!}. \end{align*}

This gives an algorithmic way to compute $S_{n,n+p}$ for any fixed $p$. Continuing your table, \begin{align*} A_0(a)&=1 \\2A_1(a)&=a-1 \\36A_2(a)&=(a-1)(5a-4) \\72A_3(a)&=(a-1)^2(2a-1) \\32400A_4(a)&=(a-1)(143a^3-307a^2+193a-32) \\64800A_5(a)&=(a-1)^2(2a-1)(19a^2-24a+2) \\85730400A_6(a)&=(a-1)(5765a^5-19372a^4+22670a^3-10405a^2+1355a+32) \\342921600A_7(a)&=(a-1)^2(2a-1)(1166a^4-2850a^3+1715a^2+60a-1) \end{align*}

Observe that $A_p(a)$ is always divisible by $a-1$, and even by $(a-1)^2(2a-1)$ if $p>1$ is odd (because of $B_m^+=0$ for odd $m>1$, and [the g.f. of] $A_p(1/2)$ in closed form).