12
$\begingroup$

Is there a positive integer n such that the decimal representation of n! starts with 123456789?

$\endgroup$

2 Answers 2

14
$\begingroup$

This is true for a given $n$ if and only if

the fractional part of $\log_{10}n!$ is above, and "close enough" to, $\log_{10}1.23456789$. That is to say, if the fractional part of $\sum_{1\leq k\leq n}\log_{10}k$ is above, and close enough to, that value. Let's say it needs to be in the interval $[a,b]$ where $b$ is only a tiny bit bigger than $a$.

Now,

$\log_{10}$ is a pretty slowly growing function. In particular, the difference between $\log_{10}k$ and $\log_{10}(k+1)$ is proportional to $1/k$. So let's try to choose $n$ so that the fractional parts of logarithms of numbers near $n$ are just barely above 0, and then keep increasing $n$ by 1 until we first get a fractional part above $a$. If we can arrange that that happens before the (gradually increasing) fractional part changes get as large as $b-a$ then we'll have found a factorial with the right initial digits.

Can we make that work?

I spent a few minutes constructing a clever argument showing that we can find $k$ with the fractional part of $\log_{10}k$ just a little over 0. That was a waste of time, because this bit is obvious: take $k$ just a little over a power of 10. So let's suppose we take $k=10^N+r$ for some not-too-large $r$. Then $\log_{10}k=\log_{10}(10^N+r)=N+\log_{10}(1+10^{-N}r)$ so its fractional part is approximately $\frac{10^{-N}}{\log10}r$. Write $\varepsilon=\frac{10^{-N}}{\log10}$.

Therefore

as we go from $k=10^N$ to $k=10^N+r$, the fractional part of the factorial increases in steps of size roughly $\varepsilon,2\varepsilon,\dots,r\varepsilon$. Since at the outset this fractional part may take any value at all, we may need $r$ large enough that (roughly) $(1+\cdots+r)\varepsilon\geq1$; that is, roughly $r\geq\sqrt{2/\varepsilon}$. Note that for $r$ this large, the fractional part of $\log_{10}(10^N+r)$ is still only of order $\sqrt{\varepsilon}$. So if we take $N$ large enough that $\varepsilon$ is somewhat smaller than the square of the width of the interval of logarithms we need, then everything works: we can take enough steps to reach the required interval while still keeping the increments small.

Therefore

there is indeed such a positive integer.

The above argument may be difficult to follow. Let's look at it more concretely.

For the question as it stands, the required values of $N$ are inconveniently large, so let's take an easier version: can we get $n!$ to begin with the digits 123? This requires the fractional part of $\log_{10}n!$ to be between $\log_{10}1.23$ and $\log_{10}1.24$, or roughly between 0.089905 and 0.093422. The difference between these is about 0.0035, whose square is about $1.2\times10^{-5}$, so let's get $\varepsilon<10^{-6}$. That means we want $\frac{10^{-N}}{\log10}\leq10^{-6}$ so in particular $N=6$ should be fine.

Now

these numbers are on the large side for wholly explicit calculation (though not so large that a typical PC can't do that) but fortunately there are efficient ways to calculate logarithms of factorials with whatever accuracy one requires. According to Mathematica, the logarithm of 1000000! is about 5565708.917, and the logarithm of 1001000! is about 5571709.134, so $r$ won't need to be bigger than 1000. How fast are the fractional parts of the logarithms increasing at this point? The base-10 logarithm of 1001000 is about 6.00043, whose fractional part 0.00043 is much smaller than the width of the interval we're trying to land in, which you may recall is 0.0035. So, on the way from a fractional part of 0.917 to a fractional part of 0.134, taking steps no bigger than 0.00043, we are guaranteed to land at some point in the interval between 0.0900 and 0.0934 and therefore to get a factorial beginning with 123.

And in fact

just counting up in hundreds fairly readily finds that $\log_{10}1000900!$ is approximately 5571109.0932, and therefore 1000900! begins with the digits 123. In fact it turns out to begin 1239420243. And in fact, trying some slightly smaller values, we get lucky: 1000896 actually begins 1234. (But not 12345.)

To play the same game

with all the digits needed here, we would want to be taking factorials of numbers on the order of 20 digits long. That would be more painful, though one can still do the required calculations by computer if required. I haven't bothered to find an explicit $n$ such that $n!$ begins 123456789, though.

$\endgroup$
6
  • 3
    $\begingroup$ An earlier version of this answer was outright wrong. Annoyingly but amusingly (for me, anyway), more or less the argument here is what I originally intended, but I foolishly thought I'd found a simplification when in fact all I'd found was my own carelessness. $\endgroup$
    – Gareth McCaughan
    Jul 31, 2020 at 23:11
  • $\begingroup$ nice break down of the problem, well done! $\endgroup$
    – ThomasL
    Aug 1, 2020 at 21:15
  • $\begingroup$ can you share the code for getting "arbitrary precision of logarithm of factorials"? $\endgroup$ Aug 2, 2020 at 10:24
  • $\begingroup$ @GarethMcCaughan I obtained an explicit value of $n$ in my answer below. $\endgroup$
    – WhatsUp
    Aug 18, 2020 at 1:30
  • $\begingroup$ @WhatsUp Nice!$ $ $\endgroup$
    – Gareth McCaughan
    Aug 18, 2020 at 10:14
9
$\begingroup$

My approach is similar to the answer of @Gareth, but I use Stirling's formula to get an asymptotic expression of $\ln((10^m + r)!)\mod \ln 10$: $$\ln((10^m + r)!) + 10^m - \frac12\ln(2\pi) = \frac{r^2}{2\cdot 10^m} + o(1) \mod \ln 10,$$ where $r = O(10^{m/2})$ and $m$ is even.

If we denote by $C_m$ the value of $10^m - \frac12\ln(2\pi) \mod \ln10$, then we are looking for an $r$ such that $\frac{r^2}{2\cdot 10^m}$ lies in the interval $[L + C_m, H + C_m)$, where $L$ and $H$ are $\ln 1.23456789$ and $\ln 1.23456790$.

At this point, I simply check, for each even $m$, whether the difference $\sqrt{2\cdot 10^m \cdot (H + C_m)} - \sqrt{2\cdot 10^m \cdot (L + C_m)}$ is larger than $1$. Once this happens, we find our value of $r$ by taking an integer between the two square roots.

This gives $n = 1000000001257825294$, which has factorial $n! = 12345678950427775\dots$

It is not guaranteed to be the smallest, but at least we have some valid solution.

A final note is that everything can be done with paper + pencil + a high accuracy calculator: essentially no programming needed.

$\endgroup$
4
  • $\begingroup$ Hmm, do you have a version of Stirling that has explicit bounds on the error term that are good enough for this to work, rather than just asymptotic ones? $\endgroup$
    – Gareth McCaughan
    Aug 18, 2020 at 10:16
  • $\begingroup$ (I don't mean that your answer is wrong. Whatever cleverness Mathematica uses to calculate high-precision $\log(\Gamma(n))$ does indeed indicate that those digits are correct. But it feels to me like you need more analysis to make this rigorous. I may well be missing something, though.) $\endgroup$
    – Gareth McCaughan
    Aug 18, 2020 at 10:20
  • $\begingroup$ @GarethMcCaughan Stirling's formula can be derived from Euler-Maclaurin formula, so the usual estimation of error terms for Euler-Maclaurin can be applied. For this problem, I think it suffices to use the bounds of Robbins: $\sqrt{2\pi} n^{n + \frac12}e^{-n}e^{\frac1{12n + 1}}< n! <\sqrt{2\pi} n^{n + \frac12}e^{-n}e^{\frac1{12n}}$. This is given in the linked page, in the section "Speed of convergence and error estimates". $\endgroup$
    – WhatsUp
    Aug 18, 2020 at 12:56
  • $\begingroup$ Yeah, that seems good enough. $\endgroup$
    – Gareth McCaughan
    Aug 18, 2020 at 13:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.