Erdős Problem #1061

Erdős Problem 1061 --- collection record

PROVENANCE AND STATUS

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

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/1061.tex.

REUSED SOURCE 1

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

FORMAL RESTATEMENT

Let $\sigma(n)=\sum_{d\mid n} d$. For $x\ge 1$, let $N(x)$ be the number of ordered pairs $(a,b)\in\mathbb Z_{\ge 1}^2$ such that \[ \sigma(a)+\sigma(b)=\sigma(a+b)\quad\text{and}\quad a+b\le x. \] (If one instead counts unordered pairs, the count differs by at most a factor $2$.) The question asks for the growth of $N(x)$ and in particular whether $N(x)\sim c x$ for some constant $c>0$.

QUICK LITERATURE/CONTEXT CHECK

The problem is posed as an open question (Guy B15). I do not use or claim any external results.

ATTACK PLAN

Proof-track: look for parametric infinite families of solutions (to show $N(x)\gg x$) and then attempt to classify all solutions or at least show $N(x)=O(x)$. Disproof-track: search computationally for superlinear growth or irregular behavior.

WORK

FAST REALITY CHECK. A sieve computation of $\sigma(n)$ and a direct check of all $a+b\le x$ gives the exact counts:

x=1000:  N(x)=1620
x=2000:  N(x)=3806
x=5000:  N(x)=12484
x=10000: N(x)=30012
x=20000: N(x)=71612

In particular $N(x)/x$ is empirically about $1.62,1.90,2.50,3.00,3.58$ at these sample points. The smallest solutions include $(a,b,a+b)=(1,2,3)$ and $(2,6,8)$.

Lemma 1061.1 (proper-divisor reformulation). Let $s(n):=\sigma(n)-n$ be the sum of proper divisors of $n$ (with $s(1)=0$). Then \[ \sigma(a)+\sigma(b)=\sigma(a+b)\quad\Longleftrightarrow\quad s(a)+s(b)=s(a+b). \]

Proof. Using $\sigma(n)=n+s(n)$, \[ \sigma(a)+\sigma(b)= (a+s(a))+(b+s(b)) = (a+b) + (s(a)+s(b)). \] Also $\sigma(a+b)=(a+b)+s(a+b)$. Subtracting $(a+b)$ from both sides yields the equivalence. $\square$

Lemma 1061.2 (explicit infinite family). If $a\ge 1$ satisfies $\gcd(a,6)=1$, then $(a,2a)$ is a solution: \[ \sigma(a)+\sigma(2a)=\sigma(3a). \] Consequently $(2a,a)$ is also a solution.

Proof. Assume $\gcd(a,6)=1$, so in particular $\gcd(a,2)=\gcd(a,3)=1$. By multiplicativity of $\sigma$ on coprime inputs, \[ \sigma(2a)=\sigma(2)\sigma(a)=3\sigma(a),\qquad \sigma(3a)=\sigma(3)\sigma(a)=4\sigma(a). \] Therefore \[ \sigma(a)+\sigma(2a)=\sigma(a)+3\sigma(a)=4\sigma(a)=\sigma(3a), \] as required. $\square$

Corollary 1061.3 (linear lower bound). There exists an absolute constant $c_0>0$ such that $N(x)\ge c_0 x - O(1)$. In fact one may take $c_0=2/9$.

Proof. For each integer $a$ with $1\le a\le \lfloor x/3\rfloor$ and $\gcd(a,6)=1$, Lemma 1061.2 gives two ordered solutions $(a,2a)$ and $(2a,a)$ with sum $3a\le x$. The set of integers $a\le y$ coprime to $6$ has size $\ge \lfloor y/3\rfloor$ (one in each block of three consecutive integers avoids both factors $2$ and $3$), so the number of such $a$ with $a\le x/3$ is $\ge \lfloor x/9\rfloor$. Hence $N(x)\ge 2\lfloor x/9\rfloor = (2/9)x - O(1)$. $\square$

Lemma 1061.4 (no prime-sum solutions except $(1,2)$). If $a,b>1$ and $a+b$ is prime, then $\sigma(a)+\sigma(b)\ne \sigma(a+b)$. Equivalently, the only solutions with $a+b$ prime are $(a,b)=(1,2)$ and $(2,1)$.

Proof. If $n>1$ then $\sigma(n)\ge n+1$ because $1$ and $n$ are divisors. Thus for $a,b>1$, \[ \sigma(a)+\sigma(b)\ge (a+1)+(b+1)=a+b+2. \] If $a+b=p$ is prime, then $\sigma(a+b)=\sigma(p)=p+1=a+b+1$. Therefore $\sigma(a)+\sigma(b)\ge a+b+2> a+b+1=\sigma(a+b)$, so equality is impossible. If one of $a,b$ equals $1$, then the only way to have $a+b$ prime and satisfy the equation is the direct check $(1,2)$ (and symmetry). $\square$

VERIFICATION

Lemma 1061.2 uses only the standard multiplicativity of $\sigma$ for coprime arguments and the explicit values $\sigma(2)=3$, $\sigma(3)=4$; the coprimality condition $\gcd(a,6)=1$ is exactly what is needed. The corollary's counting bound $\#\{a\le y:\gcd(a,6)=1\}\ge \lfloor y/3\rfloor$ was checked by the simple observation that in each triple $(3t+1,3t+2,3t+3)$ at least one number is not divisible by $2$ or $3$. The numerical counts for $N(x)$ were computed by a direct sieve for $\sigma$ and then checking all pairs with $a+b\le x$.

FINAL

UNRESOLVED

1. (i) Strongest proved partial result. There are infinitely many solutions; in fact the explicit family $(a,2a)$ with $\gcd(a,6)=1$ gives the lower bound $N(x)\ge (2/9)x-O(1)$ (Lemma 1061.2 and Corollary 1061.3). Computations show $N(20000)=71612$ ordered solutions.
2. (ii) First gap (crisp). Prove a matching upper bound $N(x)=O(x)$ and, stronger, show that the limit $\lim_{x\to\infty} N(x)/x$ exists and is positive (or compute it).
3. (iii) Top 3 next moves. $1$ Classify all solutions with a fixed ratio $b/a$ or with $\gcd(a,b)=1$, using the multiplicativity of $\sigma$. $2$ Prove that for each fixed sum $n$ the number of solutions to $\sigma(a)+\sigma(n-a)=\sigma(n)$ is uniformly bounded, implying $N(x)=O(x)$ by summing over $n\le x$. $3$ Extend computations to larger $x$ and try to identify additional parametric families beyond $(a,2a)$ with $\gcd(a,6)=1$.
4. (iv) Minimal counterexample structure. A counterexample to $N(x)\sim cx$ would likely involve sums $n$ admitting an unusually large number of representations, i.e. many $a$ with $\sigma(a)+\sigma(n-a)=\sigma(n)$. Such $n$ might need to be highly composite (large $\sigma(n)$) to have room for many decompositions.

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 $\sigma(n)=\sum_{d\mid n} d$. For $x\ge 1$, let $N(x)$ be the number of ordered pairs $(a,b)\in\mathbb Z_{\ge 1}^2$ such that \[ \sigma(a)+\sigma(b)=\sigma(a+b)\quad\text{and}\quad a+b\le x. \] (If one instead counts unordered pairs, the count differs by at most a factor $2$.) The question asks for the growth of $N(x)$ and in particular whether $N(x)\sim c x$ for some constant $c>0$.

QUICK LITERATURE/CONTEXT CHECK

The problem is posed as an open question (Guy B15). I do not use or claim any external results.

ATTACK PLAN

Proof-track: look for parametric infinite families of solutions (to show $N(x)\gg x$) and then attempt to classify all solutions or at least show $N(x)=O(x)$. Disproof-track: search computationally for superlinear growth or irregular behavior.

WORK

FAST REALITY CHECK. A sieve computation of $\sigma(n)$ and a direct check of all $a+b\le x$ gives the exact counts:

x=1000:  N(x)=1620
x=2000:  N(x)=3806
x=5000:  N(x)=12484
x=10000: N(x)=30012
x=20000: N(x)=71612

In particular $N(x)/x$ is empirically about $1.62,1.90,2.50,3.00,3.58$ at these sample points. The smallest solutions include $(a,b,a+b)=(1,2,3)$ and $(2,6,8)$.

Lemma 1061.1 (proper-divisor reformulation). Let $s(n):=\sigma(n)-n$ be the sum of proper divisors of $n$ (with $s(1)=0$). Then \[ \sigma(a)+\sigma(b)=\sigma(a+b)\quad\Longleftrightarrow\quad s(a)+s(b)=s(a+b). \]

Proof. Using $\sigma(n)=n+s(n)$, \[ \sigma(a)+\sigma(b)= (a+s(a))+(b+s(b)) = (a+b) + (s(a)+s(b)). \] Also $\sigma(a+b)=(a+b)+s(a+b)$. Subtracting $(a+b)$ from both sides yields the equivalence. $\square$

Lemma 1061.2 (explicit infinite family). If $a\ge 1$ satisfies $\gcd(a,6)=1$, then $(a,2a)$ is a solution: \[ \sigma(a)+\sigma(2a)=\sigma(3a). \] Consequently $(2a,a)$ is also a solution.

Proof. Assume $\gcd(a,6)=1$, so in particular $\gcd(a,2)=\gcd(a,3)=1$. By multiplicativity of $\sigma$ on coprime inputs, \[ \sigma(2a)=\sigma(2)\sigma(a)=3\sigma(a),\qquad \sigma(3a)=\sigma(3)\sigma(a)=4\sigma(a). \] Therefore \[ \sigma(a)+\sigma(2a)=\sigma(a)+3\sigma(a)=4\sigma(a)=\sigma(3a), \] as required. $\square$

Corollary 1061.3 (linear lower bound). There exists an absolute constant $c_0>0$ such that $N(x)\ge c_0 x - O(1)$. In fact one may take $c_0=2/9$.

Proof. For each integer $a$ with $1\le a\le \lfloor x/3\rfloor$ and $\gcd(a,6)=1$, Lemma 1061.2 gives two ordered solutions $(a,2a)$ and $(2a,a)$ with sum $3a\le x$. The set of integers $a\le y$ coprime to $6$ has size $\ge \lfloor y/3\rfloor$ (one in each block of three consecutive integers avoids both factors $2$ and $3$), so the number of such $a$ with $a\le x/3$ is $\ge \lfloor x/9\rfloor$. Hence $N(x)\ge 2\lfloor x/9\rfloor = (2/9)x - O(1)$. $\square$

Lemma 1061.4 (no prime-sum solutions except $(1,2)$). If $a,b>1$ and $a+b$ is prime, then $\sigma(a)+\sigma(b)\ne \sigma(a+b)$. Equivalently, the only solutions with $a+b$ prime are $(a,b)=(1,2)$ and $(2,1)$.

Proof. If $n>1$ then $\sigma(n)\ge n+1$ because $1$ and $n$ are divisors. Thus for $a,b>1$, \[ \sigma(a)+\sigma(b)\ge (a+1)+(b+1)=a+b+2. \] If $a+b=p$ is prime, then $\sigma(a+b)=\sigma(p)=p+1=a+b+1$. Therefore $\sigma(a)+\sigma(b)\ge a+b+2> a+b+1=\sigma(a+b)$, so equality is impossible. If one of $a,b$ equals $1$, then the only way to have $a+b$ prime and satisfy the equation is the direct check $(1,2)$ (and symmetry). $\square$

VERIFICATION

Lemma 1061.2 uses only the standard multiplicativity of $\sigma$ for coprime arguments and the explicit values $\sigma(2)=3$, $\sigma(3)=4$; the coprimality condition $\gcd(a,6)=1$ is exactly what is needed. The corollary's counting bound $\#\{a\le y:\gcd(a,6)=1\}\ge \lfloor y/3\rfloor$ was checked by the simple observation that in each triple $(3t+1,3t+2,3t+3)$ at least one number is not divisible by $2$ or $3$. The numerical counts for $N(x)$ were computed by a direct sieve for $\sigma$ and then checking all pairs with $a+b\le x$.

FINAL

UNRESOLVED

1. (i) Strongest proved partial result. There are infinitely many solutions; in fact the explicit family $(a,2a)$ with $\gcd(a,6)=1$ gives the lower bound $N(x)\ge (2/9)x-O(1)$ (Lemma 1061.2 and Corollary 1061.3). Computations show $N(20000)=71612$ ordered solutions.
2. (ii) First gap (crisp). Prove a matching upper bound $N(x)=O(x)$ and, stronger, show that the limit $\lim_{x\to\infty} N(x)/x$ exists and is positive (or compute it).
3. (iii) Top 3 next moves. $1$ Classify all solutions with a fixed ratio $b/a$ or with $\gcd(a,b)=1$, using the multiplicativity of $\sigma$. $2$ Prove that for each fixed sum $n$ the number of solutions to $\sigma(a)+\sigma(n-a)=\sigma(n)$ is uniformly bounded, implying $N(x)=O(x)$ by summing over $n\le x$. $3$ Extend computations to larger $x$ and try to identify additional parametric families beyond $(a,2a)$ with $\gcd(a,6)=1$.
4. (iv) Minimal counterexample structure. A counterexample to $N(x)\sim cx$ would likely involve sums $n$ admitting an unusually large number of representations, i.e. many $a$ with $\sigma(a)+\sigma(n-a)=\sigma(n)$. Such $n$ might need to be highly composite (large $\sigma(n)$) to have room for many decompositions.