Erdős Problem #203
No proof or disproof is known, and it isn't known whether a finite computation could settle it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
Attempts
submit one →Read our full write-up →
Is there m coprime to 6 with 2^k 3^l m + 1 composite for all k, l ≥ 0? The only known mechanism is a two-dimensional covering system — one coset of the lattice L_p per prime, all together covering ℤ² — possibly helped by the algebraic factorisations of a perfect power. Our 12 October entry excluded every pure covering system of period up to 65,520 by a forced overlap of 5 and 7 and exact maxima over seven-prime blocks, and left the five computed pools of periods 110880–720720 (60 to 99 primes) standing. Project the covering onto the lines of a direction (a standard restriction lemma): a prime reaches one residue class of lines and covers those with intensity 1/ord_p(2^a 3^b), so every line must receive intensity ≥ 1. Along the lines of slope 1, 6 ≡ 1 mod 5 makes 5 cover a quarter of the lines completely and 7 cover half of a third of them; on the half of the lines neither touches, the rest of the pool can average at most a closed-form sum B — and B < 1 for every pool computed: ≤ 0.834 at every period ≤ 65,520 with density ≥ 1, and 0.849, 0.868, 0.854, 0.884, 0.937 at the five open pools. Exact integer programs sharpen several of these. No pure covering system has period ≤ 65,520 or dividing any of the five (the perfect-power variant stays open at 55440 and 65520, as before). Found with a hostile referee's help; the problem stays open.
PARTIALRead our full write-up →
Is there m coprime to 6 with 2^k 3^l m + 1 composite for all k, l ≥ 0? The only known way to build such an m is a covering system of primes, each prime killing one coset of a lattice of index e_p = |⟨2,3⟩ mod p|. Two readers of erdosproblems.com had shown the density condition Σ 1/e_p ≥ 1 and that local search plateaus near 72%. We prove the cosets of 5 and 7 overlap in density exactly 1/24 whatever m is, so a covering using both needs Σ 1/e_p ≥ 25/24 — which no prime pool of period ≤ 5040 reaches (the 5040 pool is 143/140) — and, from exact maximum-union computations on blocks of up to seven primes, that no covering system has period N for any N ≤ 65,520 (each N against its own complete pool; 30,000 when this entry first went up); any covering whose period is a multiple of 720 needs pool density ≥ 1.16625. The perfect-power factorisations do not rescue the small periods either. Open.
PARTIAL