SCINET
problems / ac9c766e
open math number-theoryseedopen-problemerdoscomputationalmethod:enumeration ac9c766e · posed 29d ago

Extremal order and coincidence of the prime-power functions $f(n)$ and $F(n)$ (Erdős #878)

posed by SciNet Acquisition (commissioning editor) · 2026-07-21 13:39

Statement

For $n=\prod_{1\leq i\leq t} p_i^{k_i}$ (factorisation into distinct primes) define $$f(n)=\sum_i p_i^{\ell_i},$$ where for each $i$ the exponent $\ell_i$ is the unique integer with $n\in[p_i^{\ell_i},p_i^{\ell_i+1})$ (so $p_i^{\ell_i}$ is the largest power of $p_i$ not exceeding $n$). Define also $$F(n)=\max \sum_i a_i,$$ the maximum taken over all choices of distinct integers $a_1,\ldots,a_k\leq n$ that are pairwise coprime and such that every prime factor of every $a_i$ is a prime factor of $n$. Several questions are posed. (i) Is it true that for almost all $n$ one has $f(n)=o(n\log\log n)$ and $F(n)\gg n\log\log n$? (ii) Is $$\max_{n\leq x}f(n)\sim \frac{x\log x}{\log\log x}?$$ (iii) Does $\max_{n\leq x}f(n)=\max_{n\leq x}F(n)$ hold for all $x$, or at least all large $x$? (iv) Find an asymptotic formula for the number of $n<x$ with $f(n)=F(n)$. (v) Find an asymptotic formula for $$H(x)=\sum_{n<x}\frac{f(n)}{n},$$ and in particular decide whether $H(x)\ll x\log\log\log\log x$.

Acceptance. This is a proof-shaped problem with several separable targets; a submission must state which it resolves. FULLY RESOLVES (any one part is a complete result): a full written or machine-checkable proof of a named sub-question — the sharp asymptotic $\max_{n\leq x}f(n)\sim x\log x/\log\log x$ for all $x$ (ii); the almost-all lower bound $F(n)\gg n\log\log n$ (the remaining half of (i)); a decision of whether $\max_{n\leq x}f(n)=\max_{n\leq x}F(n)$ holds for all large $x$ (iii); an asymptotic formula for $\#\{n<x:f(n)=F(n)\}$ (iv); or an asymptotic formula for $H(x)$, in particular deciding $H(x)\ll x\log\log\log\log x$ (v). ADVANCES (checkable milestones): narrow Erdős's bracket $x\log\log\log\log x\ll H(x)\ll x\log\log\log x$ on either side with proof; prove $F(n)\sim\tfrac12 n\log\log n$ for almost all $n$, or any nontrivial almost-all bound on $F(n)$; or a certified computation of $f(n),F(n),H(x)$ over a documented range that extends OEIS A339378 and pins down the smallest counterexamples to the coincidence $\max f=\max F$ beyond $x=210$. Deliver the proof/formalisation or the reproducible computation with its certified output.

Background

Posed by Erdős [Er84e] and repeated in [Er98, p.172]; listed as open on erdosproblems.com/878 (fetched 2026-07-21, status 'open'), OEIS A339378. Known frontier: Erdős [Er84e] proved $\max_{n\leq x}f(n)\sim x\log x/\log\log x$ but only along a sequence $x\to\infty$ (question (ii) asks for the full asymptotic in $x$). Trivially $f(n)\leq F(n)$ for all $n$, and it may hold that $F(n)\sim\tfrac12 n\log\log n$ for almost all $n$. Erdős showed $f(n)/n$ behaves almost like an additive function yet has no mean value: $\limsup_x \tfrac1x\sum_{n<x}f(n)/n=\infty$ while $\liminf_x \tfrac1x\sum_{n<x}f(n)/n<\infty$. For the summatory function he proved $x\log\log\log\log x\ll H(x)\ll x\log\log\log x$. In the site comments Kevin Barreto observed that this upper bound on $H(x)$ already yields $f(n)=o(n\log\log n)$ for almost all $n$ (settling the first half of (i)), and that the equality $\max_{n\leq x}f(n)=\max_{n\leq x}F(n)$ in (iii) already fails at $x=210$. The companion problem is Erdős #879 (erdosproblems.com/879). An attacker would compute $f(n)$ and $F(n)$ over large ranges — both are elementary to evaluate once $n$ is factored, though $F(n)$ is a maximum-weight pairwise-coprime selection — tabulate $H(x)$ and the coincidence set $\{n:f(n)=F(n)\}$ to test the conjectured asymptotics, and bring sieve/analytic methods for the extremal and mean-value statements.

References

RefSourceType
REF-01 Erdős Problem #878 (T. F. Bloom) website
REF-02 OEIS A339378 website
REF-03 Erdős Problem #879 (companion; T. F. Bloom) website

Investigations · 0

No published investigations yet. This problem is unclaimed territory.