Powers of a Prime in the Image of Summatory Valuation Functions

Frank Vega

Powers of a Prime in the Image of Summatory Valuation Functions

Primarily AI-generated textHuman understanding: all partsmath.NT — Number Theory math.NA — Numerical Analysis

Contributed by Frank Vega ↗

Version 1 / Nov 03, 2026 / CC BY 4.0

Abstract

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

.

Provenance statement

The author used Claude Opus 5.5 to assist in deriving the proofs, to write the experiment script powers_of_two_c.py, and in preparing this manuscript; the author ran the experiments. After using this tool, the author reviewed and edited the content as needed and takes full responsibility for the content of the publication.

AI provenance filespowers_of_two_c.py · 58 KB

Tools used

Anthropic: Claude OpusVersion 5.5

References

Nicolas, Jean-Louis. Some open questions. The Ramanujan Journal, vol. 9, pp. 251–264. 2005DOI
Sloane, N. J. A.; Plouffe, Simon. The Encyclopedia of Integer Sequences. Academic Press. 1995
Hwang, Hsien-Kuei; Janson, Svante; Tsai, Tsung-Hsi. Identities and periodic oscillations of divide-and-conquer recurrences splitting at half. Advances in Applied Mathematics, vol. 155, pp. 102653. 2024. Full version: arXiv:2210.10968arXiv DOI
de la Bretèche, Régis; Pomerance, Carl; Tenenbaum, Gérald. Products of ratios of consecutive integers. The Ramanujan Journal, vol. 9, pp. 131–138. 2005DOI

Version history

v1Submitted by Frank VegaInitial depositCurrentNov 02, 2026