Erdoes #411 - working report - Erdős Problem a Day

Erdős problem 411, wave 9e

Access/reverification date: 2026-07-28 UTC.

0. Mandatory live-page check

I fetched https://www.erdosproblems.com/411 and its discussion thread through the Bright Data browser, not datacenter curl. I also fetched the page's LaTeX view. The statement below is copied verbatim from that LaTeX view:

Let $g_1=g(n)=n+\phi(n)$ and $g_k(n)=g(g_{k-1}(n))$. For which $n$ and $r$ is it true that $g_{k+r}(n)=2g_k(n)$ for all large $k$?

The stop gate did not fire:

Status: OPEN.
Claimed proofs: 0 claimed proofs for this problem.
“Currently working on this problem”: None.
“Interested in collaborating”: None.
The other reaction fields (“looks difficult”, “looks tractable”, and “results

could be formalisable”) are also None.

A separate field says “I am working on formalising the results on this

problem: epassports”. This is not the page's “currently working on this problem” collision field, which is explicitly None, and it makes no claim to be solving the open mathematics.

The page says “Formalised statement? No”, links OEIS A383044 as “possible”,

reports four comments, and says it was last edited 28 October 2025.

All known-result text on the live page

The page records the following (these are source reports, not new claims here).

The known examples for

$g_{k+2}(n)=2g_k(n)$ are $n=10,94$.

Selfridge and Weintraub found examples with

$g_{k+9}(n)=9g_k(n)$; Weintraub found $g_{k+25}(3114)=729g_k(3114)$ for $k\geq6$.

Steinerberger reduces the $r=2$ cycle-state equation to

\[ \phi(n)+\phi(n+\phi(n))=n. \] The page gives the odd parts $\{1,3,5,7,35,47\}$, with any further case arising from a prime $8m+7\geq10^{10}$ and $\phi(6m+5)=4m+4$. It relates this to $\phi(q)=\frac23(q+1)$.

The page says Cambie conjectures that the only solutions have $r=2$ and

$n=2^\ell p$, where $p\in\{2,3,5,7,35,47\}$. It also reports a reduction involving $r,t\geq1$, primes $p\equiv7\pmod8$, and the displayed condition $g_k(2p^t)=4p^t$. The displayed page text has a free $r$ in this sentence; I do not silently repair it.

Cambie's other displayed examples are

\[ g_{k+4}(738)=3g_k(738),\quad g_{k+4}(148646)=4g_k(148646),\quad g_{k+4}(4325798)=4g_k(4325798) \] for $k\geq1$.

All four live comments

The site warns that comments are user responsibility and are not verified.

Alfaiz, 2025-12-09: points to C. Hercher's paper and lists its results:

every solution of $\phi(q)=\frac23(q+1)$ is square-free; distinct prime factors obey a nondivisibility condition; a new solution needs at least seven prime factors; and a new solution is at least $10^{14}$.

hoodieuser, 2026-04-03 04:30: claims that the square-free solutions are

generated by a prime recurrence, lists $5,35,1295,1679615$, and reports a search through $10^6$.

old-bielefelder, 2026-04-03 07:01: notes that $1295$, rather than the

typo $1195$ in Hercher's introduction, makes the proposed pattern look natural, and asks whether there is a Collatz connection.

Nat Sothanaphan, 2026-04-03 15:17: says hoodieuser's argument is

incorrect: deleting the largest prime factor of a solution need not leave another solution. Thus the proposed recurrence proves only a forward extension implication, not an exhaustive reverse classification.

The partial, subsequently refuted square-free assertion is not a claimed proof of Problem 411, and the page's proof-claim counter remains zero.

1. Primary-source check and current literature

I found and inspected these primary sources.

P. Erdős and R. L. Graham, *Old and New Problems and Results in

Combinatorial Number Theory* (1980), printed p.81: https://mathweb.ucsd.edu/~ronspubs/80_11_number_theory.pdf. The scan contains the quoted problem, the examples $10,94$, the Selfridge/Weintraub remarks, and the sentence “We know of no general rules for forming such examples.” Local PDF SHA-256: 0cbf0c32f0ab1e1c71db5121a88bac905bf976c4a6ab6bb6d7d9cf9ddd184ed3.

S. Steinerberger, *On an iterated arithmetic function problem of Erdős and

Graham*, arXiv:2504.08023v1 (2025): https://arxiv.org/abs/2504.08023. The arXiv history has only v1, submitted 2025-04-10. The paper proves the page's $r=2$ cycle-state reduction and the exceptional totient condition. Local PDF SHA-256: 65ba2e71991508ba630e801a7f7be9b14c5111a0f0747733b5a5e4c0585f9649.

C. Hercher, *On Positive Integers $n$ with

$\phi(n)=\frac23(n+1)$*, arXiv:2504.19915v1 (2025): https://arxiv.org/abs/2504.19915. The arXiv history has only v1, submitted 2025-04-28. Its elementary part proves square-freeness and the prime-factor nondivisibility condition. Its program-assisted results rule out five and six prime factors and, after about two desktop-days, rule out a new solution below $10^{14}$. I did not reproduce that two-day computation. Local PDF SHA-256: 50f176985758ef0b8e3d9e713c3804952e51a5261f07a29f2a9ae2c38694b7d7.

Targeted searches for the exact functional equation, both arXiv identifiers, the paper titles, and the iterated $g_{k+r}=2g_k$ equation did not find a newer primary paper treating $r>2$ or classifying transient preimages. This is a search miss, not a proof that none exists.

Two non-primary database leads were checked but are not used as theorems:

OEIS A383044 is the immediate cycle-state equation

$\phi(m)+\phi(m+\phi(m))=m$; it reports the six families empirically through $2^{24}$.

OEIS A383521 records the four known solutions of

$\phi(q)=\frac23(q+1)$ and has a 2026 user comment claiming no more below $10^{15}$. No reproducible certificate is attached there, so I do not upgrade that comment to a rigorous bound.

2. Claim labels used below

(a) elementary-rigorous: proved here from definitions.
(b) rigorous-modulo-named-theorem/source: attributed to the named

primary paper, without independently reproducing every part.

(c) plausible/structural-unverified: heuristic only.
(d) computational-only: exact finite computation reproduced by the

standalone checker, but not promoted to a uniform theorem.

3. Exact reduction: cycles versus transient basins

This is the key distinction missing from a literal reading of the page's conjectured list.

Lemma 1 (projectivised dynamics) — (a)

For an odd $u$, define

Z(u)=2u+\phi(u),\qquad H(u)=\frac{Z(u)}{2^{v_2(Z(u))}},\qquad d(u)=v_2(Z(u))-1.

If $x=2^a u$ with $a\geq1$, then

g(x)=2^{a+d(u)}H(u). \tag{1}

Indeed,

\phi(2^a u)=2^{a-1}\phi(u)

and hence

g(2^a u)=2^{a-1}(2u+\phi(u)).

For $u>1$, $\phi(u)$ is even, so $d(u)\geq0$. The exceptional value is $H(1)=3,d(1)=-1$.

Every orbit starting at an even $n>2$ stays even. Consequently:

An even $n>2$ satisfies $g_{k+r}(n)=2g_k(n)$ for all sufficiently large $k$ if and only if the $H$-orbit of its odd part eventually enters a cycle of minimal period $r$ whose total drift $\sum d$ is $1$. $\tag{2}$

Proof of the forward direction: at a sufficiently large $k$, write $g_k(n)=2^a u$. Equality after $r$ steps forces the same odd part and an exponent gain of one, so $H^r(u)=u$ and the drift is one. If the minimal period were a proper divisor $s\mid r$, then the total gain would be $(r/s)D=1$ for an integer cycle drift $D$, forcing $r=s,D=1$.

Conversely, a drift-one cycle gives $g^r(2^a u)=2^{a+1}u$. The identity

g(2y)=2g(y)\qquad(y\ \text{even}) \tag{3}

propagates the equality at every later iterate.

Odd starting values do not produce an eventual equality: odd values greater than one stay odd, while the right side is even; $1\to2\to3\to5\to\cdots$, and $2\to3\to5\to\cdots$, also leave the even dynamics.

Thus the original literal “for which $n$” problem asks for basins of drift-one cycles, not only the points lying on those cycles.

Lemma 2 (shape of a drift-one cycle) — (a)

Apart from the exceptional cycle $1\to3\to1$, every drift-one cycle has a unique maximum $p^t$, where $p\equiv7\pmod8$ is prime, and

H(p^t)=p^{t-1}\frac{3p-1}{4}. \tag{4}

All remaining edges are the strictly increasing map

R(u)=u+\frac{\phi(u)}2. \tag{5}

For odd $u>1$, $d(u)>0$ can occur only when $v_2(\phi(u))=1$, which is equivalent to $u=p^t$ with $p\equiv3\pmod4$. Since every drift is nonnegative and the cycle sum is one, exactly one edge has $d=1$ and all other edges have $d=0$. At a prime power,

\[ d(p^t)=v_2(3p-1)-1; \]

this equals one exactly when $p\equiv7\pmod8$. A zero-drift edge is (5) and strictly increases $u$, while (4) decreases it. This proves uniqueness of the maximum and gives the finite candidate search used below.

This recovers the substance of the reduction attributed to Cambie on the live page. It does not by itself prove that only $p=7,47,t=1$ return.

4. Explicit new transient families

Theorem 3 — (a)

For every $a,b\geq1$,

\[ n=2^a3^b \]

satisfies

g_{k+2}(n)=2g_k(n)

for every $k\geq\max(1,b-1)$.

Writing $g_0$ for the identity map, for $0\leq j\leq b$ direct multiplicativity gives

\phi(2^a3^b)=2^a3^{b-1},\qquad g_j(2^a3^b)=2^{a+2j}3^{b-j}. \tag{6}

After $b-1$ steps the odd part is $3$, which lies on the drift-one cycle $3\to1\to3$. Equation (3) then propagates the equality forever.

The smallest counterexample to the page's literal conjectured odd-part list is

18\to24\to32\to48\to64\to96\to128\to\cdots,

for which $g_{k+2}(18)=2g_k(18)$ already for every $k\geq1$. Its odd part is $9$, not one of $\{1,2,3,5,7,35,47\}$. This does not solve Problem 411; it shows that the displayed list describes cycle states rather than all transient starting values in the literal live statement.

Two more elementary one-step basin families are

n=25\cdot2^a,\qquad n=49\cdot2^a\qquad(a\geq1).

They map respectively to $35\cdot2^a$ and $35\cdot2^{a+1}$, and therefore satisfy the same eventual $r=2$ identity from $k=1$.

Theorem 4 (a larger parametric construction) — (a)

Let $c\geq3$ be odd and suppose

q_c=\frac{3^c+1}{4}

is prime. Then for every $a,b\geq1$,

\[ n=2^a3^bq_c \]

satisfies

g_{k+2}(n)=2g_k(n)\qquad(k\geq b+c-1). \tag{7}

The proof is one line of exact arithmetic:

\begin{aligned} g(2^a3^bq_c) &=2^a3^{b-1}\bigl(3q_c+(q_c-1)\bigr)\\ &=2^a3^{b-1}(4q_c-1) =2^a3^{b+c-1}, \end{aligned}

which enters the family (6).

The checker proves by exhaustive trial division up to the square root that the following are prime:

\begin{array}{c|r} c&q_c\\ \hline 3&7\\ 5&61\\ 7&547\\ 13&398581\\ 23&23535794707 \end{array}

Thus (7) gives five verified two-parameter families. For example

\begin{aligned} 366&\to486\to648\to864\to1152\\ &\to1536\to2048\to3072\to4096\to\cdots, \end{aligned}

and $g_{k+2}(366)=2g_k(366)$ for every $k\geq5$.

No infinitude claim is made for prime values of $q_c$; each displayed prime alone already yields infinitely many $n$ through $a,b$.

5. Exact bounded cycle computation

Computational statement — (d)

An exhaustive functional-graph traversal found every $H$-cycle whose maximum odd part is at most $10^7$. There are exactly five:

| cycle in transition order | period | drift $\sum d$ | multiplier per lap | |---|---:|---:|---:| | $1,3$ | 2 | 1 | 2 | | $5,7$ | 2 | 1 | 2 | | $35,47$ | 2 | 1 | 2 | | $27871,41487,55315,74323$ | 4 | 2 | 4 | | $811087,1192767,1590355,2162899$ | 4 | 2 | 4 |

Hence every drift-one cycle with maximum odd part at most $10^7$ is one of the three familiar period-two cycles. This is an exact finite result, not a uniform exclusion above $10^7$.

The two drift-two rows independently reproduce the live-page examples:

2\cdot74323=148646,\qquad 2\cdot2162899=4325798.

The computation was performed in two ways:

A direct traversal of the full odd functional graph, without assuming the

prime-power reduction, found all five rows.

An independent drift-one enumeration from Lemma 2 checked all $166237$

primes $p\leq10^7$, $p\equiv7\pmod8$, and all $166370$ admissible prime-power maxima. It found the two nonexceptional cycles $5,7$ and $35,47$; 15060 candidates suffered an additional descent and 151308 overshot their proposed maximum.

Every displayed factorization, totient, edge, drift, and direct $g$-orbit identity is recomputed by a separate trial-division routine. The full run takes about 13 seconds and 56 MB on this VM.

6. Reproduction

Standalone checker:

runs/erdos411_wave9e_reverify.py

Run:

python runs/erdos411_wave9e_reverify.py

Expected final output:

verified prime parameters: {3: 7, 5: 61, 7: 547, 13: 398581, 23: 23535794707}
projective bound: 10000000
all bounded cycles (cycle, 2-adic drift):
  ((1, 3), 1)
  ((5, 7), 1)
  ((35, 47), 1)
  ((27871, 41487, 55315, 74323), 2)
  ((811087, 1192767, 1590355, 2162899), 2)
p == 7 mod 8 primes tested: 166237
prime-power candidate outcomes: {'cycle': 2, 'extra_descent': 15060, 'overshoot': 151308}
PASS: all construction, reduction, direct-orbit, and bounded-cycle checks

The central exhaustive loop is:

def projective_step(u, phi):
    z = 2*u + phi[u]
    e = (z & -z).bit_length() - 1
    return z >> e, e - 1

# state: 0 unseen, 1 on current path, 2 finished
for start in range(1, B + 1, 2):
    if state[start // 2]:
        continue
    path, u = [], start
    while u <= B and state[u // 2] == 0:
        state[u // 2] = 1
        path.append(u)
        u, _ = projective_step(u, phi)
    if u <= B and state[u // 2] == 1:
        cycle = path[path.index(u):]
        drift = sum(projective_step(v, phi)[1] for v in cycle)
        cycles.append((cycle, drift))
    for v in path:
        state[v // 2] = 2

Because a cycle with maximum at most $B$ cannot leave $[1,B]$, this loop does not lose a bounded cycle when an unrelated transient path escapes.

7. What remains, exactly

The original problem is not closed. The remaining tasks separate cleanly:

Cycle problem. Prove that the monotone return chain of Lemma 2 has no

solution beyond $p=7,47,t=1$, or find one. For period two this includes Steinerberger's exceptional equation and Hercher's $\phi(q)=\frac23(q+1)$ work. For longer periods the missing lemma is a global obstruction preventing \[ p^{t-1}\frac{3p-1}{4} \xrightarrow{R}\cdots\xrightarrow{R}p^t \] with every intermediate edge of zero drift.

Basin problem. Even if the cycle list is proved, classify all odd

parts whose $H$-orbit enters a drift-one cycle. The families in §4 show that the basin is already much larger than the six cycle-state odd parts.

Uniformity. The $10^7$ traversal supplies no bound on a hypothetical

larger cycle. A naïve table at $10^{10}$ would require at least 40 GB merely for 32-bit totients and on the order of $10^{10}$ sieve/graph operations—well beyond the permitted few CPU-minutes and realistically tens of core-hours. A mathematical height/descent lemma, not a modest extension of this sieve, is the useful missing ingredient.

FOUND: The literal live statement has explicit infinite transient families outside the page's conjectured odd-part list, including every $2^a3^b$ with $a,b\geq1$; the exact basin/cycle reduction and a $10^7$ exhaustive cycle table are independently verified.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger