Erdős Problem #878

Erdős Problem 878 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/878

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/878.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/878.tex.

FORMAL RESTATEMENT. Let $n\ge 2$ with prime factorization \[ n=\prod_{i=1}^t p_i^{k_i}, \] where the $p_i$ are distinct primes. For each $i$, define $\ell_i\in\mathbb N$ by \[ p_i^{\ell_i}\le n < p_i^{\ell_i+1}, \] i.e. $\ell_i=\lfloor\log_{p_i} n\rfloor$. Define \[ f(n)=\sum_{i=1}^t p_i^{\ell_i}. \]

Define $F(n)$ as follows. Let $a_1,\dots,a_t$ be integers with $1\le a_i\le n$, such that:

• $\gcd(a_i,a_j)=1$ for $i\ne j$;
• every prime factor of each $a_i$ is among $\{p_1,\dots,p_t\}$.

(Here $a_i=1$ is allowed, since it has no prime factors.) Then \[ F(n)=\max \sum_{i=1}^t a_i \] over all such choices.

The problem asks several asymptotic questions about $f$ and $F$, including:

• whether $f(n)=o(n\log\log n)$ for almost all $n$;
• whether $F(n)\gg n\log\log n$ for almost all $n$;
• extremal behavior of $\max_{n\le x} f(n)$ and whether $\max_{n\le x} f(n)=\max_{n\le x}F(n)$;
• the count of $n<x$ with $f(n)=F(n)$;
• asymptotics of $H(x)=\sum_{n<x} f(n)/n$ and upper bounds such as $H(x)\ll x\log\log\log\log x$.

QUICK LITERATURE/CONTEXT CHECK. The problem text states:

• $f(n)\le F(n)$ is "trivial".
• Erdős proved that $\max_{n\le x} f(n)\sim \frac{x\log x}{\log\log x}$ for a sequence of $x\to\infty$.
• Erdős proved bounds $x\log\log\log\log x\ll H(x)\ll x\log\log\log x$ and that $H(x)/x$ has no limit in the sense described.

I do not use any results not explicitly stated above.

ATTACK PLAN.

1. Understand structural constraints: $F(n)$ corresponds to partitioning the prime set into disjoint "blocks" assigned to pairwise coprime numbers.
2. Prove basic inequalities and simple bounds for $f(n)$ in terms of $n$ and the prime factors.
3. Compute $f(n)$ and $F(n)$ for small $n$ to sanity-check questions like $f=F$ frequency and maxima.

WORK.

Lemma 1 ($f(n)\le F(n)$). For every $n\ge 2$, one has $f(n)\le F(n)$.

Proof. For each prime divisor $p_i$ of $n$, let $b_i:=p_i^{\ell_i}$. By definition of $\ell_i$, we have $1\le b_i\le n$. The numbers $b_i$ are pairwise coprime because they are powers of distinct primes. Each $b_i$ has prime factors contained in $\{p_1,\dots,p_t\}$. Thus $(a_1,\dots,a_t)=(b_1,\dots,b_t)$ is an admissible choice in the definition of $F(n)$, giving \[ F(n)\ge \sum_{i=1}^t b_i = f(n). \] $\square$

Lemma 2 (size of each summand in $f(n)$). Let $p$ be a prime divisor of $n$, and let $L_p:=p^{\lfloor\log_p n\rfloor}$ (the largest power of $p$ not exceeding $n$). Then \[ \frac{n}{p} < L_p \le n. \] Consequently, writing $\omega(n)$ for the number of distinct prime divisors of $n$, \[ n\sum_{p\mid n}\frac{1}{p} < f(n)\le n\,\omega(n). \]

Proof. By definition, $L_p\le n < p\,L_p$. Dividing the strict inequality $n < p L_p$ by $p$ gives $n/p < L_p$. The upper bound $L_p\le n$ is part of the definition. Summing $n/p < L_p\le n$ over all distinct primes $p\mid n$ gives the stated bounds on $f(n)$. $\square$

Lemma 3 (partition formulation for $F(n)$). Let $P=\{p_1,\dots,p_t\}$ be the set of distinct prime divisors of $n$. For each nonempty subset $Q\subseteq P$, define \[ g(Q):=\max\{m\le n: \text{every prime factor of }m\text{ lies in }Q\}. \] Then \[ F(n)=t+\max\Big\{\sum_{j=1}^s (g(Q_j)-1):\ \{Q_1,\dots,Q_s\}\text{ is a partition of }P\Big\}. \]

Proof. Given any admissible $(a_1,\dots,a_t)$ for $F(n)$, delete the indices with $a_i=1$; suppose $s$ indices remain. The remaining $s$ numbers are pairwise coprime and each uses primes from $P$, hence their prime supports form a partition $Q_1,\dots,Q_s$ of $P$. For each $j$, $a_{i_j}\le g(Q_j)$ by definition of $g(Q_j)$. Therefore \[ \sum_{i=1}^t a_i = (t-s)\cdot 1 + \sum_{j=1}^s a_{i_j} \le (t-s)+\sum_{j=1}^s g(Q_j)= t+\sum_{j=1}^s(g(Q_j)-1). \] Maximizing over all admissible tuples yields \[ F(n)\le t+\max_{\text{partitions}}\sum_{j}(g(Q_j)-1). \] Conversely, given a partition $Q_1,\dots,Q_s$ of $P$, choose $b_j=g(Q_j)$ for $j\le s$ and set the remaining $t-s$ numbers equal to $1$. The $b_j$ are pairwise coprime because their prime supports are disjoint. This gives an admissible choice with sum $t+\sum_j(g(Q_j)-1)$. Taking the maximum over partitions yields the reverse inequality and thus equality. $\square$

VERIFICATION (FAST REALITY CHECK). Using brute-force computation for $n\le 1000$ (with the above definitions):

• For $2\le n\le 1000$, the counts are:

  # {n : f(n)=F(n)} = 596
  # {n : F(n)>f(n)} = 403
  

  Including $n=1$ (where $f(1)=F(1)=0$ by the empty-sum convention) gives $597$ equalities among $1\le n\le 1000$.
• The maxima on $2\le n\le 1000$ are

  max_{n<=1000} f(n) = 2707 at n=870
  max_{n<=1000} F(n) = 2707 at n=870
  

  with $870=2\cdot 3\cdot 5\cdot 29$ and \[ f(870)=2^9+3^6+5^4+29^2=512+729+625+841=2707. \]
• Small explicit example with strict inequality: $n=15$ gives \[ f(15)=9+5=14,\qquad F(15)\ge 15+1=16. \]
• Numerical values of $H_f(x):=\sum_{n<x} f(n)/n$ for a few small $x$:

  H_f(10)= 8.1666666667
  H_f(50)= 53.6289963452
  H_f(100)=108.2303681634
  H_f(1000)=1132.6889768131
  

FINAL. UNRESOLVED.

(i) Strongest proved partial result here. Lemma 1 ($f\le F$) and Lemma 2 (each summand in $f$ lies in $(n/p,n]$), plus Lemma 3 giving a precise partition/optimization formulation for $F(n)$.

(ii) First gap (crisp). Prove any of the main asymptotic statements in the problem text (e.g. $f(n)=o(n\log\log n)$ for almost all $n$, or $F(n)\gg n\log\log n$ for almost all $n$) from first principles, without importing results beyond those stated.

(iii) Top 3 next moves (concrete).

1. Use Lemma 2 together with probabilistic/average estimates on $\sum_{p\mid n} 1/p$ and $\omega(n)$ to try to bound typical size of $f(n)$ (this resembles studying an "additive function" but with the unconventional cutoff $p^{\lfloor\log_p n\rfloor}$).
2. For $F(n)$, analyze the partition optimization (Lemma 3): understand for typical $n$ whether it is advantageous to group many primes into one block (making a number close to $n$) or to separate them into prime-power blocks.
3. Compute $\#\{n\le x: f(n)=F(n)\}$ for larger $x$ and inspect correlations with the size and distribution of prime factors of $n$.

(iv) Minimal counterexample structure. A counterexample to "$f(n)=o(n\log\log n)$ for almost all $n$" would be a set of $n$ of positive density with unusually many distinct prime factors and/or with many small prime divisors making $\sum_{p\mid n} n/p$ large. A counterexample to "$F(n)\gg n\log\log n$ for almost all $n$" would require a dense set of $n$ for which every partition of the prime set forces all $g(Q_j)$ to be much smaller than $n$, preventing the sum from reaching size $\asymp n\log\log n$.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

FORMAL RESTATEMENT. Let $n\ge 2$ with prime factorization \[ n=\prod_{i=1}^t p_i^{k_i}, \] where the $p_i$ are distinct primes. For each $i$, define $\ell_i\in\mathbb N$ by \[ p_i^{\ell_i}\le n < p_i^{\ell_i+1}, \] i.e. $\ell_i=\lfloor\log_{p_i} n\rfloor$. Define \[ f(n)=\sum_{i=1}^t p_i^{\ell_i}. \]

Define $F(n)$ as follows. Let $a_1,\dots,a_t$ be integers with $1\le a_i\le n$, such that:

• $\gcd(a_i,a_j)=1$ for $i\ne j$;
• every prime factor of each $a_i$ is among $\{p_1,\dots,p_t\}$.

(Here $a_i=1$ is allowed, since it has no prime factors.) Then \[ F(n)=\max \sum_{i=1}^t a_i \] over all such choices.

The problem asks several asymptotic questions about $f$ and $F$, including:

• whether $f(n)=o(n\log\log n)$ for almost all $n$;
• whether $F(n)\gg n\log\log n$ for almost all $n$;
• extremal behavior of $\max_{n\le x} f(n)$ and whether $\max_{n\le x} f(n)=\max_{n\le x}F(n)$;
• the count of $n<x$ with $f(n)=F(n)$;
• asymptotics of $H(x)=\sum_{n<x} f(n)/n$ and upper bounds such as $H(x)\ll x\log\log\log\log x$.

QUICK LITERATURE/CONTEXT CHECK. The problem text states:

• $f(n)\le F(n)$ is "trivial".
• Erdős proved that $\max_{n\le x} f(n)\sim \frac{x\log x}{\log\log x}$ for a sequence of $x\to\infty$.
• Erdős proved bounds $x\log\log\log\log x\ll H(x)\ll x\log\log\log x$ and that $H(x)/x$ has no limit in the sense described.

I do not use any results not explicitly stated above.

ATTACK PLAN.

1. Understand structural constraints: $F(n)$ corresponds to partitioning the prime set into disjoint "blocks" assigned to pairwise coprime numbers.
2. Prove basic inequalities and simple bounds for $f(n)$ in terms of $n$ and the prime factors.
3. Compute $f(n)$ and $F(n)$ for small $n$ to sanity-check questions like $f=F$ frequency and maxima.

WORK.

Lemma 1 ($f(n)\le F(n)$). For every $n\ge 2$, one has $f(n)\le F(n)$.

Proof. For each prime divisor $p_i$ of $n$, let $b_i:=p_i^{\ell_i}$. By definition of $\ell_i$, we have $1\le b_i\le n$. The numbers $b_i$ are pairwise coprime because they are powers of distinct primes. Each $b_i$ has prime factors contained in $\{p_1,\dots,p_t\}$. Thus $(a_1,\dots,a_t)=(b_1,\dots,b_t)$ is an admissible choice in the definition of $F(n)$, giving \[ F(n)\ge \sum_{i=1}^t b_i = f(n). \] $\square$

Lemma 2 (size of each summand in $f(n)$). Let $p$ be a prime divisor of $n$, and let $L_p:=p^{\lfloor\log_p n\rfloor}$ (the largest power of $p$ not exceeding $n$). Then \[ \frac{n}{p} < L_p \le n. \] Consequently, writing $\omega(n)$ for the number of distinct prime divisors of $n$, \[ n\sum_{p\mid n}\frac{1}{p} < f(n)\le n\,\omega(n). \]

Proof. By definition, $L_p\le n < p\,L_p$. Dividing the strict inequality $n < p L_p$ by $p$ gives $n/p < L_p$. The upper bound $L_p\le n$ is part of the definition. Summing $n/p < L_p\le n$ over all distinct primes $p\mid n$ gives the stated bounds on $f(n)$. $\square$

Lemma 3 (partition formulation for $F(n)$). Let $P=\{p_1,\dots,p_t\}$ be the set of distinct prime divisors of $n$. For each nonempty subset $Q\subseteq P$, define \[ g(Q):=\max\{m\le n: \text{every prime factor of }m\text{ lies in }Q\}. \] Then \[ F(n)=t+\max\Big\{\sum_{j=1}^s (g(Q_j)-1):\ \{Q_1,\dots,Q_s\}\text{ is a partition of }P\Big\}. \]

Proof. Given any admissible $(a_1,\dots,a_t)$ for $F(n)$, delete the indices with $a_i=1$; suppose $s$ indices remain. The remaining $s$ numbers are pairwise coprime and each uses primes from $P$, hence their prime supports form a partition $Q_1,\dots,Q_s$ of $P$. For each $j$, $a_{i_j}\le g(Q_j)$ by definition of $g(Q_j)$. Therefore \[ \sum_{i=1}^t a_i = (t-s)\cdot 1 + \sum_{j=1}^s a_{i_j} \le (t-s)+\sum_{j=1}^s g(Q_j)= t+\sum_{j=1}^s(g(Q_j)-1). \] Maximizing over all admissible tuples yields \[ F(n)\le t+\max_{\text{partitions}}\sum_{j}(g(Q_j)-1). \] Conversely, given a partition $Q_1,\dots,Q_s$ of $P$, choose $b_j=g(Q_j)$ for $j\le s$ and set the remaining $t-s$ numbers equal to $1$. The $b_j$ are pairwise coprime because their prime supports are disjoint. This gives an admissible choice with sum $t+\sum_j(g(Q_j)-1)$. Taking the maximum over partitions yields the reverse inequality and thus equality. $\square$

VERIFICATION (FAST REALITY CHECK). Using brute-force computation for $n\le 1000$ (with the above definitions):

• For $2\le n\le 1000$, the counts are:

  # {n : f(n)=F(n)} = 596
  # {n : F(n)>f(n)} = 403
  

  Including $n=1$ (where $f(1)=F(1)=0$ by the empty-sum convention) gives $597$ equalities among $1\le n\le 1000$.
• The maxima on $2\le n\le 1000$ are

  max_{n<=1000} f(n) = 2707 at n=870
  max_{n<=1000} F(n) = 2707 at n=870
  

  with $870=2\cdot 3\cdot 5\cdot 29$ and \[ f(870)=2^9+3^6+5^4+29^2=512+729+625+841=2707. \]
• Small explicit example with strict inequality: $n=15$ gives \[ f(15)=9+5=14,\qquad F(15)\ge 15+1=16. \]
• Numerical values of $H_f(x):=\sum_{n<x} f(n)/n$ for a few small $x$:

  H_f(10)= 8.1666666667
  H_f(50)= 53.6289963452
  H_f(100)=108.2303681634
  H_f(1000)=1132.6889768131
  

FINAL. UNRESOLVED.

(i) Strongest proved partial result here. Lemma 1 ($f\le F$) and Lemma 2 (each summand in $f$ lies in $(n/p,n]$), plus Lemma 3 giving a precise partition/optimization formulation for $F(n)$.

(ii) First gap (crisp). Prove any of the main asymptotic statements in the problem text (e.g. $f(n)=o(n\log\log n)$ for almost all $n$, or $F(n)\gg n\log\log n$ for almost all $n$) from first principles, without importing results beyond those stated.

(iii) Top 3 next moves (concrete).

1. Use Lemma 2 together with probabilistic/average estimates on $\sum_{p\mid n} 1/p$ and $\omega(n)$ to try to bound typical size of $f(n)$ (this resembles studying an "additive function" but with the unconventional cutoff $p^{\lfloor\log_p n\rfloor}$).
2. For $F(n)$, analyze the partition optimization (Lemma 3): understand for typical $n$ whether it is advantageous to group many primes into one block (making a number close to $n$) or to separate them into prime-power blocks.
3. Compute $\#\{n\le x: f(n)=F(n)\}$ for larger $x$ and inspect correlations with the size and distribution of prime factors of $n$.

(iv) Minimal counterexample structure. A counterexample to "$f(n)=o(n\log\log n)$ for almost all $n$" would be a set of $n$ of positive density with unusually many distinct prime factors and/or with many small prime divisors making $\sum_{p\mid n} n/p$ large. A counterexample to "$F(n)\gg n\log\log n$ for almost all $n$" would require a dense set of $n$ for which every partition of the prime set forces all $g(Q_j)$ to be much smaller than $n$, preventing the sum from reaching size $\asymp n\log\log n$.