Powers of a Prime in the Image of Summatory Valuation Functions

J.-L. Nicolas asked how often a power of $2$ belongs to the image of $c(n)=\sum_{k\le n}2^{v_2(k)}$, where $v_2$ is the $2$-adic valuation, and showed that both the number $A(x)$ of exponents $a\le x$ with $2^a$ in the image and the number $B(x)$ of the other exponents tend to infinity. We prove the identity $c(n)=n+\frac12\sum_{i}i\,2^{i}$, the sum running over the positions of the binary digits $1$ of $n$, so that $2^a$ lies in the image of $c$ if and only if $2^{a+3}$ is a sum of distinct terms of the superincreasing sequence $(j2^j)_{j\ge1}$. For every exponent there is at most one possible largest term $K$, given by $K+\lceil\log_2K\rceil=a+3$, and no such $K$ exists exactly when $a=2^r+r-2$. The remaining exponents are decided by an explicit recursion on pairs of integers bounded by $a+3$, in at most $a+1$ steps. We give the closed formula $c(2^{K-2}+2^{K-s-2})=2^{K+h-3}$ for $s=2^k$, $h\equiv k\pmod{2^{k+1}}$ and $K=(2^{h+s}+s)/(2^s+1)$, and infinite explicit families of exponents $a$ for which $2^a$ is not in the image, indexed by $s=3$ and $s=2^i$; the families given by Nicolas are the cases $s=1$ and $s=2$. As a consequence, $A(x)\ge(2+o(1))\log_2x$ and $B(x)\ge(\frac54+\frac12\sum_{i\ge1}\frac{1}{2^i-1}+o(1))\log_2x=(2.0533\ldots+o(1))\log_2x$. We prove that the states of the recursion form a forest, rooted at the states $(J,0)$ and at the failing states, in which every state $(J',w')$ has exactly $v_2(J'+1+w')$ children; that the sets $S_J$ of successful states are symmetric; that exactly half of them lie in the tree of the root $(1,0)$; that $N(2k+1)=N(2k)$; that $4\mid N(J)$ for $J\ge4$; and that $S_J$ satisfies a recursion from the smallest elements upwards, with period $J/2$ for even $J$. The symmetry gives further explicit families, among them $c(2^{2^r}-1)=2^{2^r+r-1}$, and the improved bounds $A(x)\ge(3.9655\ldots+o(1))\log_2x$ and $B(x)\ge(2.8178\ldots+o(1))\log_2x$. For every prime $p$, the function $c_p(n)=\sum_{k\le n}p^{v_p(k)}$ counts the factor $1-X$ in $(1-X)\cdots(1-X^n)$ over $\mathbb{F}_p$; we extend to it the reduction, the unique candidate, the recursions and the symmetry, give explicit families, and describe completely the exponents rejected at the first step, which occur only for odd $p$. We also report experiments in exact integer arithmetic: every statement is checked by three independent methods, the values of $A(x)$ reproduce the table of Nicolas, the sets $S_J$ are computed for $J\le131072$, and $A(x)/x$ lies between $0.5132$ and $0.8750$ for $x=1000,2000,\dots,131000$.