math.NT — Number Theory
Contributed by Frank Vega
J.-L. Nicolas asked how often a power of 2 belongs to the image of c(n)=∑k≤n2v2(k), where v2 is the 2-adic valuation, and showed that both the number A(x) of exponents a≤x with 2a in the image and the number B(x) of the other exponents tend to infinity. We prove the identity c(n)=n+21∑ii2i, the sum running over the positions of the binary digits 1 of n, so that 2a lies in the image of c if and only if 2a+3 is a sum of distinct terms of the superincreasing sequence (j2j)j≥1. For every exponent there is at most one possible largest term K, given by K+⌈log2K⌉=a+3, and no such K exists exactly when a=2r+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(2K−2+2K−s−2)=2K+h−3 for s=2k, h≡k(mod2k+1) and K=(2h+s+s)/(2s+1), and infinite explicit families of exponents a for which 2a is not in the image, indexed by s=3 and s=2i; the families given by Nicolas are the cases s=1 and s=2. As a consequence, A(x)≥(2+o(1))log2x and B(x)≥(45+21∑i≥12i−11+o(1))log2x=(2.0533…+o(1))log2x. 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 v2(J′+1+w′) children; that the sets SJ 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∣N(J) for J≥4; and that SJ satisfies a recursion from the smallest elements upwards, with period J/2 for even J. The symmetry gives further explicit families, among them c(22r−1)=22r+r−1, and the improved bounds A(x)≥(3.9655…+o(1))log2x and B(x)≥(2.8178…+o(1))log2x. For every prime p, the function cp(n)=∑k≤npvp(k) counts the factor 1−X in (1−X)⋯(1−Xn) over Fp; 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 SJ are computed for J≤131072, and A(x)/x lies between 0.5132 and 0.8750 for x=1000,2000,…,131000.
Primarily AI-generated textHuman understanding: all parts$2$-adic valuationArithmetic functionsBinary expansionOpen questions of NicolasPolynomials over $\mathbb{F}_2$Superincreasing sequences