# When is $n/\ln(n)$ close to an integer?

As usual I expect to be critisised for "duplicating" this question. But I do not! As Gjergji immediately notified, that question was from numerology. The one I ask you here (after putting it in my response) is a mathematics question motivated by Kevin's (O'Bryant) comment to the earlier post.

Problem. For any $\epsilon>0$, there exists an $n$ such that $\|n/\log(n)\|<\epsilon$ where $\|\ \cdot\ \|$ denotes the distance to the nearest integer.

In spite of the simple formulation, it is likely that the diophantine problem is open. I wonder whether it follows from some known conjectures (for example, Schanuel's conjecture).

-
Hi, Wadim. Let me just mention Ramanujan's trick for producing a sequence of new world records, I think Erdos and Alaoglu (spelling?) called the process champion numbers, anyway the original were Ramanujan's "superior highly composite numbers," a subsequence of the highly composite numbers but with an explicit recipe. – Will Jagy Jun 14 '10 at 3:45
The real question is whether you can bound your $n$ in terms of $\epsilon$. My memory --- it's been a while --- is that for certain desired bounds, there is a finite list of "good" approximations, 163 being the largest. – Theo Johnson-Freyd Jun 14 '10 at 15:55
If you follow the solution below, you'll find that the one can bound $n$ by means of $\epsilon$. 163 is not the largest (because the largest does not exist!) but you could also check Kevin O'Bryant's computation in the preceding Q. – Wadim Zudilin Jun 14 '10 at 16:04
Er, my memory is wrong, anyway. And yes, for the solution below the bound is definitely there, but it grows super fast. My point was to propose a revised question: for some prescribed bound $n \lesssim f(\epsilon)$, is it true that there is an $n$ with $\| n/\log n\| < \epsilon$? How good of a bound can we get? – Theo Johnson-Freyd Jun 14 '10 at 17:16
Therefore, a reasonable revised problem is to get especially small values of $$\frac{\parallel \frac{n}{ \log n} \parallel}{\left( \frac{1}{ \log n} - \frac{1}{ \log^2 n} \right)} \; \; \; \; \sim \; \; \; \; \parallel \frac{n}{ \log n} \parallel \cdot \log n$$ – Will Jagy Jun 14 '10 at 18:07

If $f(x)=\frac{x}{\log x}$, then $f'(x)=\frac{1}{\log x} - \frac{1}{(\log x)^2}$, which tends to zero as $x\rightarrow \infty$. Choose some large real number $x$ for which $f(x)$ is integral. Then the value of $f$ on any integer near $x$ must be very close to integral.

-
So, if we can choose a sequence of $x$'s whose distance to $\mathbb Z$ decreases, then we have the desired result. (Maybe, you wish to use in some way the fact that $f$ is contraction, but then it's still non-obvious to me, so please expand your argument or let me to think more.) How to guarantee that $x$ is close to an integer? This would refer to arithmetic properties of Lambert-like ($W$) function which are not even conjecturally studied... – Wadim Zudilin Jun 14 '10 at 4:18
Let $[ ]$ denote the ceiling function. Fix $\epsilon>0$. Choose a real number $x$ so that $f(x)\in \mathbb{Z}$ and choose it large enough so that $\frac{1}{\log x} - \frac{1}{(\log x)^2}<\epsilon$. Then one can show $||f([x])||<\epsilon$ by combining the Mean Value Theorem with the fact that $|x-[x]|<1$. – Kevin Ventullo Jun 14 '10 at 4:33
In fact, taking that $x_0$ such that $f(x_0) = k \in Z,$ with $0 < f'(x_0) < \epsilon,$ and writing $n < x_0 < n+1,$ we get $k < f(n+1) < k + \epsilon$ and then $k - \epsilon < f(n) < k.$ – Will Jagy Jun 14 '10 at 4:44
Excellent! I am happy to see how the numerological problem is demustified. Thank you very much, Kevin! I was far from the internet, but your argument is indeed very clear. Sorry for asking you more details. – Wadim Zudilin Jun 14 '10 at 7:41
I ought to have said, with $n < x_0 < n+1,$ that we demand $0 < f'(n) < \epsilon,$ as $f''(x) < 0$ when $x > e^2.$ The numerology question stands, when do we get especially small $k - f(n)$ or $f(n+1) - k.$ With my choice of symbols, we could simply ask when either $x_0 - n$ or $n+1 - x_0$ is small. This formulation takes the size of $f'$ out of the discussion. – Will Jagy Jun 14 '10 at 15:46

[Edited mostly to extend the computation from $1.5 \cdot 10^{13}$ to a bit over $2^{50} > 10^{15}$ and give the heuristics for expected number of records for $\| r(n) \|$ vs. $\log n \cdot \| r(n) \|$]

Just ran across this. I see that Kevin's answer completely settles the original question, but meanwhile Will Jagy raised the question of finding new record lows for $$\log n \cdot \left\| \frac{n}{\log n} \right\|$$ and proving their infinitude. I next outline a proof that there are infinitely many such record lows, and then report on a computation of all such $n$ up to $1.5 \cdot 10^{13}$.

For the infinitude: Since $r(n) := n / \log n$ can never be an exact integer, it is enough to prove that for each $\epsilon > 0$ there exist infinitely many solutions of $\| r(n) \| < \epsilon/\log n$. In fact it's not hard to show that $\| r(n) \|$ can get as small as some negative power of $n$, because $r(n)$ is almost linear (its second derivative is $o(n^{-1})$ as $n \rightarrow \infty$) and we can choose $n_0$ to make $r'(n_0)$ as far as possible from any rational number. If I did this right, we can find intervals $|n - n_0| \leq h$ in which $\min_n \| r(n) \| \ll h^{-1}$ where $h^{-1} = |r''(n_0)|^{1/3} \sim (n_0 \log^2 n_0)^{-1/3}$. For instance, we may choose $n_0$ so that $r'(n_0) = 1 / (k + \sqrt 2)$ for $k = 1, 2, 3, \ldots$ [that is, so that $\log n_0$ solves the quadratic equation $\lambda^2 = (k+\sqrt2) (\lambda-1)$]. On such an interval, $r(n)$ is approximated by $r(n_0) + r'(n_0)(n-n_0)$ to within $O(r''(n_0) (n-n_0)^2) = O(h^2/h^3) = O(h^{-1})$, and (since $h$ grows much faster than $k$) the arithmetic sequence with common difference $r'(n_0)$ is close enough to being equidistributed that it comes within $O(1/h)$ of an integer. [We probably expect that $\| r(n) \|$ is random enough that it gets as small as $c/n$ or even $o(1/n)$, but proving such a result must be well out of reach.]

For the numerical search, the problem is quite similar to MO.19170 on nearly-integral values of $\log_{10} n!$ (since $n/ \log n$, like $\log_{10} n!$, is nearly linear in $n$). Again it takes time only $\tilde O(N^{2/3})$ to find all examples with $n < N$ using a linear-approximation technique such as described at the bottom of page 15 of Lefèvre's slides. This is actually the same idea as in the previous paragraph: partition $[1,N]$ into intervals $|n-n_0| \leq h \sim (n_0 \log^2 n_0)^{1/3}$; in general $r'(n_0)$ might be so close to a rational number that equidistribution fails, but we can still use continued fractions to find all $n$ in that interval for which $\|r(n)\| \ll h^{-1}$.

I ran this with $N = 2^{50} > 10^{15}$ on ten alhambra heads. Most finished in under two days; two took an extra day or two, probably spending most of them on $n_0$ for which $r'(n_0)$ was nearly rational (in this case one can do much better than trying every $n \in [n_0-h,n_0+h]$ for which $\| r(n_0) + r'(n_0)(n-n_0) \|$ is small, but I didn't take the extra time to implement that refinement). The computation found fourteen new records beyond the 12 initial terms 2, 17, 163, 715533, 1432276, 6517719, 11523158, 11985596, 24102781, 254977309, 451207448, 1219588338 of OEIS sequence A178806, namely

2048539023, 10066616717, 42116139191, 47657002570, 73831354169, 122478947521, 143949453227, 3152420311977, 5624690531099, 14964977749017, 25999244327633, 92799025313425, 164330745650026, and 604329910739082.

There is also a new example, namely $n = 3040705645816$, of a number that is not in this sequence but does belong in the closely related OEIS sequence A178805, which consists of $n$ that achieve record low values of $\| r(n) \|$ instead of $\log n \cdot \| r(n) \|$. In general a $\log n \cdot \| r(n) \|$ record is automatically also an $\| r(n) \|$ record, but the converse can fail on occasion. If we imagine that the $\| r(n) \|$ are independent random numbers uniformly distributed on $(0,1/2)$ then the probability that $\| r(n) \|$ is a new record is $1/n$, so we expect $\log N + O(1)$ record values with $n \leq N$. The same question for $\log n \cdot \| r(n) \|$ is trickier, but if I did this right the probability that $\| r(n) \|$ is a new record but $\log n \cdot \| r(n) \|$ is not one is approximately $1 / n \log n$, so we expect only $\log\log N + O(1)$ examples such as $n = 3040705645816$ up to $N$, and might never see another one even though there should be infinitely many more.

Here is a table of the values of $n < 2^{50}$ for which $\| r(n) \|$ attains a new record low, together with the signed fractional part of $r(n)$, and $\log n$ times that fractional part: $$\begin{array}{rrrc} 2 & -0.1146099 & -0.0794415 & \\ 5 & 0.1066747 & 0.1716863 & ! \\ 9 & 0.0960765 & 0.2111017 & ! \\ 13 & 0.0683262 & 0.1752532 & ! \\ 17 & 0.0002541 & 0.0007199 & \\ 163 & -1.26 \cdot 10^{-6} & -6.43 \cdot 10^{-6} & \\ 53453 & 1.22 \cdot 10^{-6} & 1.33 \cdot 10^{-5} & ! \\ 110673 & 6.68 \cdot 10^{-7} & 7.76 \cdot 10^{-6} & ! \\ 715533 & 3.84 \cdot 10^{-7} & 5.17 \cdot 10^{-6} & \\ 1432276 & 2.33 \cdot 10^{-7} & 3.30 \cdot 10^{-6} & \\ 6517719 & -2.00 \cdot 10^{-7} & -3.14 \cdot 10^{-6} & \\ 11523158 & -9.95 \cdot 10^{-8} & -1.62 \cdot 10^{-6} & \\ 11985596 & -7.26 \cdot 10^{-8} & -1.18 \cdot 10^{-6} & \\ 24102781 & 4.43 \cdot 10^{-9} & 7.53 \cdot 10^{-8} & \\ 254977309 & 9.12 \cdot 10^{-10} & 1.76 \cdot 10^{-8} & \\ 451207448 & 3.68 \cdot 10^{-10} & 7.33 \cdot 10^{-9} & \\ 1219588338 & -2.57 \cdot 10^{-10} & -5.38 \cdot 10^{-9} & \\ 2048539023 & -5.89 \cdot 10^{-11} & -1.26 \cdot 10^{-9} & \\ 10066616717 & 4.85 \cdot 10^{-11} & 1.12 \cdot 10^{-9} & \\ 42116139191 & -4.47 \cdot 10^{-11} & -1.09 \cdot 10^{-9} & \\ 47657002570 & -2.43 \cdot 10^{-11} & -5.97 \cdot 10^{-10} & \\ 73831354169 & 1.35 \cdot 10^{-11} & 3.38 \cdot 10^{-10} & \\ 122478947521 & 7.53 \cdot 10^{-13} & 1.92 \cdot 10^{-11} & \\ 143949453227 & -5.50 \cdot 10^{-13} & -1.41 \cdot 10^{-11} & \\ 3040705645816 & 5.18 \cdot 10^{-13} & 1.49 \cdot 10^{-11} & ! \\ 3152420311977 & -3.36 \cdot 10^{-13} & -9.67 \cdot 10^{-12} & \\ 5624690531099 & 1.28 \cdot 10^{-13} & 3.76 \cdot 10^{-12} & \\ 14964977749017 & -7.15 \cdot 10^{-14} & -2.17 \cdot 10^{-12} & \\ 25999244327633 & -2.02 \cdot 10^{-14} & -6.25 \cdot 10^{-13} & \\ 92799025313425 & 6.01 \cdot 10^{-15} & 1.93 \cdot 10^{-13} & \\ 164330745650026 & -1.00 \cdot 10^{-15} & -3.28 \cdot 10^{-14} & \\ 604329910739082 & -4.59 \cdot 10^{-16} & -2.27 \cdot 10^{-14} & \end{array}$$ the "!"'s mark the $\| r(n) \|$ records that aren't $\log n \cdot \| r(n) \|$ records.

-
Got it. Your first three without exclamation marks are n = 2, 17, 163. So the log factor outside the || || does not usually matter, on account of being nearly constant I guess.. – Will Jagy Dec 24 '12 at 23:14
Noam, Thanks for providing this new life to the old question. – Wadim Zudilin Dec 25 '12 at 3:28
Can you say anything about how many records there are in $||r(n)||$ that are not records in $\log n \dot ||r(n)||$? – Zach Hamaker Dec 25 '12 at 17:07

Hi Wadim, I decided to do a numerical run the same way that Kevin O'Bryant did for the previous question, but this time for the easiest version of my revised problem, find new record lows for $$\parallel n / \log n \parallel \cdot \log n$$

       2      0.0794415
17      0.000719936
163      6.42582e-06
715533      5.17294e-06
1432276      3.30032e-06
6517719      3.13803e-06
11523158      1.61843e-06
11985596      1.18403e-06
24102781      7.51947e-08


The results are pretty similar to what O'Bryant found. I suspect there is an infinite sequence of "champion" numbers. I do not think any full analysis of these is possible (you mention Lambert $W$), but there might (who knows?) be a subsequence with an explicit Ramanujan style recipe for construction.

Meanwhile, this is from C++ using "double" type, I imagine the accuracy is good enough. Easy enough to confirm with arbitrary precision in GP-Pari.

-
Well, Will, this could be a really open problem for MO. BTW, this month's Notices has an opinion on MO: ams.org/notices/201006/rtx100600701p.pdf . – Wadim Zudilin Jun 15 '10 at 3:07
This sequence of values of $n$ has been entered into the Online Encyclopedia of Integer Sequences, 192.20.225.10/~njas/sequences/A178806 and it has been extended by T D Noe to three more terms. – Gerry Myerson Sep 22 '10 at 6:24