Erdős problem #1059 — wave6t report

Date of live-page check and computation: 2026-07-27 UTC.

Claim labels used throughout:

• (a) elementary-rigorous: proved here from elementary facts or directly

checked source metadata.

• (b) rigorous-modulo-named-theorem: depends on an explicitly named

theorem.

• (c) plausible/structural-unverified: heuristic or a route for which a

necessary uniformity statement is unproved.

• (d) computational-only: an exact finite computation, not a statement

about infinitely many integers.

0. Mandatory live-page gate

I fetched the live problem page through the Bright Data cloud browser rather than ordinary curl. (a)

The verbatim live statement is:

Are there infinitely many primes \(p\) such that \(p-k!\) is composite for each \(k\) such that \(1\leq k!<p\)?

The live page showed all of the following. (a)

• Status: OPEN.
• It calls this a question of Erdős reported as problem A2 in Guy's 2004

collection.

• Its two examples are \(p=101\) and \(p=211\).
• It records Erdős's suggested easier problem: find infinitely many \(n\)

with \(l!<n\leq(l+1)!\), every prime factor of \(n\) greater than \(l\), and every \(n-k!\), \(1\leq k\leq l\), composite.

• Comments: 0.
• Claimed proofs: 0.
• “Interested in collaborating”: None.
• “Currently working on this problem”: None.
• “Likes this problem”: Dogmachine.
• “This problem looks difficult”: Dogmachine.
• “This problem looks tractable”: None.
• “The results on this problem could be formalisable”: None.
• “I am working on formalising the results”: None.
• “Formalised statement?”: Yes.
• Related OEIS sequence: A064152.

Thus neither skip condition was present, so I proceeded. (a)

1. Primary-source and literature audit

1. The only literature cited on the live page is Richard K. Guy,

Unsolved Problems in Number Theory, third edition (2004), problem A2. The publisher record confirms that the “Prime Numbers” chapter is pages 3–69 and has DOI 10.1007/978-0-387-26677-0_2. OEIS identifies A2 specifically as page 11. (a)

1. The current OEIS A064152 gives a finite list,

counts through \(10^9\), and a conjectural \(1/8\)-density comment. It cites only Guy for the problem. Its history shows that the current extended b-file and count comment were installed in March 2024. This is a computational database record, not a proof of infinitude. (a,d)

1. Exact-phrase searches for "all p-k! ... composite", "p-k!" 101 211,

"all the numbers n-k! are composite", “Erdős primes”, and the Guy A2 citation produced no dedicated primary paper or arXiv preprint proving or advancing this exact question. This is a search miss, not a proof that no such literature exists. (a)

1. A nearby primary paper that search results surfaced,

G. E. Hardy and M. V. Subbarao, “A Modified Problem of Pillai and Some Related Questions”, American Mathematical Monthly 109 (2002), 554–559, is about prime divisors of \(n!+1\) and related congruences. Inspection of the paper confirms that it does not answer the simultaneous compositeness question here. (a)

I therefore found no source-supported reason to change the live page's open status. (a)

2. A definition bug in OEIS A064152

Guy's own chapter preview separates positive integers into the unit \(1\), primes, and composites, and explicitly lists composites starting at \(4\). Thus “composite” in the cited source does not include \(1\). (a)

Proposition 1

\(p=2\), the first term of OEIS A064152, does not satisfy the live statement. (a)

Proof. For \(p=2\), \(k=1\) is eligible because \(1!=1<2\), but

and \(1\) is not composite. \(\square\)

The OEIS Mathematica and PARI snippets test only whether \(p-k!\) is prime. That accepts \(1\), which is nonprime but not composite. This explains the spurious first term. (a)

More generally, replacing “composite” by “nonprime” can differ only when \(p-k!=1\), i.e. at a factorial-plus-one candidate \(p=k!+1\). The exact sieve checked all such candidates through \(10^9\); only \(p=2\) passes the loose “nonprime” test while failing the strict statement. (d)

Consequently the strict counts through \(10^9\) are exactly one below the published OEIS counts:

All entries in this table are finite exact computations. (d)

The strict sequence therefore starts

not with \(2\). (d)

3. An elementary factor obstruction

Let \(r(k)\) denote the least prime strictly greater than \(k\).

Theorem 2

If \(p\) is prime and \(k!<p\), then

If in addition \(p-k!\) is composite, then every prime divisor of \(p-k!\) exceeds \(k\), and

(a)

Proof.

because the prime \(p\) is larger than \(k!\). If a prime \(q\leq k\) divided \(p-k!\), then \(q\mid k!\), contradicting the displayed gcd. Hence every prime factor is at least \(r(k)\). A composite integer contains at least two prime factors counted with multiplicity, so it is at least \(r(k)^2\). \(\square\)

Factorial-edge corollary

If \(l!<p<(l+1)!\) is a solution, then

Thus the entire interval

is solution-free, for every \(l\geq2\). (a)

This bound is sharp even with all the other factorial conditions imposed. For \(l=6\),

is prime, and the following nontrivial divisors certify every required difference:

Trial division through \(\sqrt{769}<28\) proves the primality claim, and the displayed factors prove compositeness. (a)

There is a second exact equality example:

Trial division of the left side by every integer through \(\lfloor\sqrt{6\,227\,021\,089}\rfloor=78\,911\) finds no divisor. The following table supplies a nontrivial divisor of each difference. (a)

For every row with \(k\geq2\), the displayed divisor is \(>k\), as Theorem 2 requires. The standalone checker recomputes the primality test and all divisibility assertions by elementary trial division; no probable-prime call is used for these two certificates. (a)

I do not claim that the larger example is new; it is an explicit, from-scratch-verifiable solution and another equality case for the bound.

4. Exact computation by factorial band

Define

The original question is equivalent to asking whether \(E_l>0\) for infinitely many \(l\). (a)

The exact sieve gives:

These are exact finite counts. In particular \(E_l>0\) for every \(4\leq l\leq12\); the trial-division certificate above proves \(E_{13}>0\) as well. Neither fact supplies uniform control as \(l\to\infty\). (d)

At \(10^9\), the exact prime count is \(\pi(10^9)=50\,847\,534\), and the strict solutions form the ratio

The OEIS \(1/8\) comment is therefore numerically plausible at this scale but remains conjectural. (d,c)

5. Exact congruence-cover reduction

For a prime \(p\) in the \(l\)-th factorial band, Theorem 2 gives the following equivalence:

(a)

The forward implication takes the least prime factor of \(p-k!\); the reverse implication exhibits a proper divisor. This is an exact finite covering formulation, not a heuristic. (a)

It also explains why a fixed CRT construction cannot settle the problem. If a fixed modulus \(M\) and reduced residue \(a\bmod M\) are used to produce infinitely many primes, then for every prime \(q\mid M\) and every \(k\geq q\), \(k!\equiv0\pmod q\) but \(a\not\equiv0\pmod q\). Thus the fixed primes dividing \(M\) can force compositeness for only finitely many factorial shifts; the covering moduli must grow with \(l\). (a)

The exact missing statement for this route is therefore a uniform growing-dimensional prime/composite covering lemma: one must show, for infinitely many \(l\), that the changing union of residue conditions above contains a prime before \((l+1)!\). A prime-composite tuple statement for each fixed finite set of shifts is insufficient, because after taking its prime arbitrarily large, additional factorials become eligible. (a)

6. Why the first standard sieve attempt stalls

This subsection is diagnostic only. It assumes the Hardy–Littlewood prime-pair heuristic, from Hardy–Littlewood (1923), with uniformity far beyond the fixed-shift conjecture. (c)

For fixed even \(h\), the heuristic prime-pair singular series is

For \(h=k!\), all primes \(q\leq k\) divide \(h\), so the Euler products and Mertens's prime-product theorem formally give

If \(l!\) is of scale \(x\), summing the expected incidences “\(p\) and \(p-k!\) both prime” for \(2\leq k\leq l\) gives, relative to the number of primes near \(x\),

(c)

Thus even the conjectural first-moment union bound has constant \(>1\); an unconditional upper-bound pair sieve has still more loss. Pairwise estimates alone cannot prove that some primes have zero prime factorial companions. This route needs control of overlaps involving three and more simultaneous primes, uniformly for a family whose dimension is \(l\asymp\log x/\log\log x\). Current fixed-pattern prime-tuple machinery does not supply that lower-bound/zero-count distribution. (c)

This identifies the wall more precisely than “the problem seems hard”: the missing input is either

1. the growing-dimensional covering lemma in Section 5, or
2. a uniform lower bound for the zero class in the distribution of

\(\#\{k\leq l:p-k!\text{ is prime}\}\) among primes in a factorial band.

Both must retain uniformity as \(l\to\infty\); proving a statement for each fixed \(l\) does not close the problem. (a)

7. Reproducible computation

The complete standalone verifier is erdos1059_wave6t_verify.py. It uses only the Python standard library. Its core is an exact odd-only Eratosthenes sieve followed by the literal strict test:

def is_composite_sieve(n, odd_is_prime):
    return n > 1 and not sieve_is_prime(n, odd_is_prime)

for p in all_sieved_primes:
    ok = True
    f = 1
    k = 1
    while f < p:
        if not is_composite_sieve(p - f, odd_is_prime):
            ok = False
            break
        k += 1
        f *= k
    if ok:
        solutions.append(p)

The full script additionally:

• recomputes an independent trial-division enumeration through \(10^5\)

and asserts equality with the sieve (900 strict solutions);

• uses deterministic 64-bit Miller–Rabin plus explicit divisors for sample

certificates;

• uses wholly independent elementary trial division for the equality

examples \(769\) and \(6\,227\,021\,089\);

• checks the factorial-edge bound on every enumerated solution;
• locates all “nonprime but not composite” false positives among

factorial-plus-one candidates.

Commands run:

python -m py_compile runs/erdos1059_wave6t_verify.py
python runs/erdos1059_wave6t_verify.py \
  --limit 10000000 \
  --output runs/erdos1059_wave6t_1e7.json
python runs/erdos1059_wave6t_verify.py \
  --limit 1000000000 \
  --output runs/erdos1059_wave6t_1e9.json

The \(10^9\) pass sieved all \(50\,847\,534\) primes and took 172.807 single-core seconds, of which 12.354 seconds built the sieve. The exact artifacts are erdos1059_wave6t_1e7.json and erdos1059_wave6t_1e9.json. (d)

Final SHA-256 values at report time:

517944c676525006f2c677777c1101cc03b23306df1e850c39ce0f77171f6f85  erdos1059_wave6t_verify.py
7e53d85cbeac6318415a9de89ada4e5380863f6874a74cb1a148d31b69e853f0  erdos1059_wave6t_1e7.json
d021a71051234706cb1417773f08f733d68c11c95e3540672c28027e7efcc385  erdos1059_wave6t_1e9.json

Extending the same byte-per-odd sieve through \(13!=6\,227\,020\,800\) would require a 3.11 GB primality bytearray plus the solution list. Linear scaling from the measured \(10^9\) run predicts about 17.9 single-core minutes, or 0.30 core-hours, so I did not run it under the few-minute cap. At a representative commodity CPU rate of USD 0.04–0.10/core-hour, the CPU charge would be roughly USD 0.01–0.03; it would complete another finite band but would not address uniform infinitude. (c)

PARTIAL: proved the sharp bound \(p-k!\geq\operatorname{nextprime}(k)^2\), certified equality solutions \(769\) and \(6\,227\,021\,089\), and exactly corrected/enumerated the strict sequence through \(10^9\) (5,901,408 terms); infinitude remains open at a growing-dimensional sieve/covering wall.