OPEN
This is open, and cannot be resolved with a finite computation.
Fix some integer $n$ and define a decreasing sequence in $[1,n)$ by $a_1=n-1$ and, for $k\geq 2$, letting $a_k$ be the greatest integer in $[1,a_{k-1})$ such that all of the prime factors of $a_k$ are $>n-a_k$.
Is it true that, for sufficiently large $n$, not all of this sequence can be prime?
Disclaimer: The open status of this problem reflects the current belief of the owner of this website. There may be literature on this problem that I am unaware of, which may partially or completely solve the stated problem. Please do your own literature search before expending significant effort on solving this problem. If you find any relevant literature not mentioned here, please add this in a comment.
Erdős and Graham write 'preliminary calculations made by Selfridge indicate that this is the case but no proof is in sight'. For example if $n=8$ we have $a_1=7$ and $a_2=5$ and then must stop.
Sarosh Adenwalla has observed that this problem is equivalent to (the first part of)
[385]. Indeed, assuming a positive answer to that, for all large $n$, there exists a composite $m<n$ such that all primes dividing $m$ are $>n-m$. It follows that such an $m$ is equal to some $a_i$ in the sequence defined for $[1,n)$, and $m$ is composite by assumption.
View the LaTeX source
View history
|
Likes this problem
|
None
|
|
Interested in collaborating
|
None
|
|
Currently working on this problem
|
None
|
|
This problem looks difficult
|
TerenceTao
|
|
This problem looks tractable
|
None
|
|
The results on this problem could be formalisable
|
None
|
|
I am working on formalising the results on this problem
|
None
|
Additional thanks to: Sarosh Adenwalla
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #430, https://www.erdosproblems.com/430, accessed 2026-04-11
