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 2 / 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 the number

A(x)

of exponents

a\le x

with

2^a

in the image and the number

B(x)

of the other exponents both tend to infinity. We prove 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 membership is then decided by an explicit recursion on pairs of integers at most

a+3

, in at most

a+1

steps. The exponents without such a

K

and the exponents decided in at most one step form explicit infinite families, described completely, which contain the three families of Nicolas. The states of the recursion form a forest and the set of successful states is symmetric; this yields further explicit families and the bounds

A(x)\ge(3.9655\ldots+o(1))\log_2x

and

B(x)\ge(2.8178\ldots+o(1))\log_2x

, whereas the families of Nicolas give the constants

\frac12

and

\frac32

. The reduction, the unique candidate, the recursion and the symmetry extend to

c_p(n)=\sum_{k\le n}p^{v_p(k)}

for every prime

p

. Computations in exact integer arithmetic reproduce the table of Nicolas and give

A(x)

for

x\le262000

, with

A(x)/x

between

0.5132

and

0.8750

for

x=1000,2000,\dots,262000

.

Author comments: In this new version, we add new computer-based experiments.

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 · 66 KB

Tools used

Anthropic: Claude OpusVersion 5.5

References

Dixmier, Jacques; Nicolas, Jean-Louis. Parité de certains nombres de partitions. Travaux Mathématiques, Publication du Centre Universitaire de Luxembourg, vol. 13, pp. 93–153. 2002
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
OEIS Foundation Inc. Entry A006520, Partial sums of A006519, in The On-Line Encyclopedia of Integer Sequences. 2026. Accessed on 10 November 2026. https://oeis.org/A006520link
Allouche, Jean-Paul; Shallit, Jeffrey. The ring of $k$ -regular sequences. Theoretical Computer Science, vol. 98, no. 2, pp. 163–197. 1992DOI
Flajolet, Philippe; Grabner, Peter; Kirschenhofer, Peter; Prodinger, Helmut; Tichy, Robert F. Mellin transforms and asymptotics: digital sums. Theoretical Computer Science, vol. 123, no. 2, pp. 291–314. 1994
Merkle, Ralph C.; Hellman, Martin E. Hiding information and signatures in trapdoor knapsacks. IEEE Transactions on Information Theory, vol. 24, no. 5, pp. 525–530. 1978DOI

Version history

v1 · 22 pagesSubmitted by Frank VegaInitial depositSupersededNov 02, 2026
v2 · 29 pagesSubmitted by Frank VegaIn this new version, we add new computer-based experiments.CurrentNov 10, 2026