Any number can start a factorial | Hacker News Reader

Any number can start a factorial

johndcook.com

62 pointsColinWright61 comments

The article's opening sentence: "Any positive number can be found at the beginning of a factorial..." is a strong statement but no proof is given.

Missing: "... with high probability, and supported by analysis of the digits of factorials from 1 to 10,000"

The work by Diaconis mentioned but not cited: [0] https://statweb.stanford.edu/~cgates/PERSI/papers/digits.pdf - The distribution of leading digits ad uniform distribution mod 1 - Persi Diaconis

The sequence: [1] https://oeis.org/A076219 - Smallest positive integer m such that m! begins with n in base 10 :: 1, 2, 9, 8, 7, 3, 6, 14, 96, 27, 22, 5, 15, 42, 25, 89, 69, 76, 63, 16, 87, 113, 54, ...

I'm not sure what you're getting at, but "any positive number can be found at the beginning of a factorial" is correct. Not with high probability, but with absolute certainty. I don't know which Diaconis proved, but it's pretty easy to construct a non-probabilistic, constructive proof.

Edit: The paper you linked does not prove it with high probability, it proves {n!} is a strong Benford sequence. Edit: Which implies absolute certainty.

> I'm not sure what you're getting at

I'm sure what I'm not getting at, which is the proof. I'll think about it. Processing ...

Could you provide such a proof? (just general outline would suffice...) I can't figure out a "pretty easy" way to do it.

Every time you hit a power of ten, fracPart(log10(n!)) gets the unit interval finely iterated by n=10^k, 10^k + 1, 10^k + 2, ..., 10^k + sqrt(2 log(10) 10^k).

Sorry, but how is that a proof?

It's not clear whether there is a number A with decimal expansion (a_1 a_2 ... a_k ) such that there doesn't exist a positive number X for which

   X ! = (a_{1} a_{2} ... a_{k}  x_{k+1} x_{k+1} ... x_{s} )

for some arbitrary length s in the decimal expansion of X! .

It shows {fracPart(log10(n!))} is dense.

I'm also not getting your proof. What does it mean every time you hit a power of 10? The sequence n! does not hit powers of 10 since all terms of the sequence after n=3 are at least divisible by 3.

I agree though, density in (0,1) of the fracPart(log10(n!)) is a good thing to try to prove, since 10^fracPart(log10(n!)) should have the same digits as 10^intPart(log10(n!))*10^fracPart(log10(n!))=10^log10(n!)=n!

Every time n hits a power of 10, not n!.

E.g. https://www.wolframalpha.com/input/?i=Table%5B%5Bfrac%28log1...

In general for b << 10^k, we have fracPart[log10((10^k + b)!)] ≈ fracPart[log10((10^k)!) + b(b+1)/(2 log(10) 10^k)]. So it takes sqrt(2 log(10) 10^k) steps for these factorial values to work their way around the unit interval. Increase k and you fill it arbitrarily finely.

Edit: ^^^ To be clear, the approximation there is formed using the linear approximation log(1 + b/10^k) ≈ b/10^k, and basic log multiplication/addition/division formulas.

The approximation holds only for b << 10^k. Then you don't get to take O(10^k) steps to work you way around the unit interval, do you? After the approximation breaks down, you don't know that the spacing is approximately uniform anymore.

You only need sqrt(2 log(10) 10^k) steps.

The spacing is not uniform, it's just bounded by O(1/10^(k/2)). The spacing is, at its greatest, about 1/sqrt(2 log(10) 10^k).

I'm not sure you only need that many steps. As you start out, each step gives you a lot of distance. But log gets flatter and flatter the more steps you take.

If you knew the number of steps, I think you could only make a lower bound on spacing, not an upper bound. Since at worst all the steps could be clustered really close, except for the last one.

But now I have to think more because it seems like it should actually help the argument that the spacing gets finer and finer as you step, because that is what we want anyway. And is the number of steps actually important to the proof?

The distance you cover with step b is about b/(log(10) 10^k). The exact distance is log10((10^k + b)/10^k). That's a funny way of saying fracPart(log10(10^k + b)).

The number of steps tells you how big the last step is.

Okay I think I buy it. Great proof, thanks!

For any target number K, we can pick lower and upper bounds N and M with the following properties:

1. Multiplying by N causes the leading digits to increase by at least 0.5 and at most 1.0 2. Multiplying by M causes the leading digits to increase by at most 1.0 3. M - N is more than twice as large as the target number. 4. M > N and M & N both have the same number of digits.

We start at N!, then checking N+1! etc, increasing the leading digits by at least 0.5 and at most 1.0. We do this more than 2K times, so we're guaranteed to hit exactly K.

The first two conditions are pretty simple to achieve - if we're targeting 2019, then 10,003 works for N and 10,004 works for M, and we can easily find some number that fills our need for whatever target we get. For the third condition, we can multiply both N and M by 10. This increases M-N by a factor of ten, but has the exact same effect for the leading digit multiplication.

What does "multiplying by N" mean? Like if my current guess is X! and that doesn't work, I should try (N*M)! ?

What does "increase by at least 0.5" mean? If my leading digits are 999, how do you increase them at all?

If your current guess is X such that N<X<M, then (X+1)!/(X!) = X+1. Since this is also between N and M inclusive, adding one to the factorial is equivalent to multiplying the leading digit by a number that is slightly larger than one. This multiplication will cause the leading digits of (X+1)! to be larger than the leading digits of (X!). If the leading digits are all nines, you just wrap around to 100 and the same logic gets you as far as you want to go.

Maybe an example will help me understand. Let's say I wanted to have the leading digits 921, and I start with a guess of X=5.

What do I do now?

6! / 5! = 6, which is way too big. So, instead try X=15. The leading digits of 16 is still too big, so go to X=105. Repeat this process until you get a sufficiently small change in the leading digits between adjacent numbers - 10,005 barely works, so might as well go to 100,005 instead and be sure we're hitting every number.

Now the problem is that you might not have enough small increments you can make. You can always replace X=100,005 with X=1,000,0050 - multiply by ten, and the leading digits behave the same on multiplication, but you have ten times as many numbers you can multiply by.

You basically can divvy up things in as many fine increments as you want, so you can always find some number that does things properly.

I haven't thought about this carefully but is it correct to say the probability of finding n as the leading digits for a bounded m (but both very large) is a decreasing function of n?

Very cool! Is there a pattern in the sequence of m's? It feels as though there must be some bounds on the terms of the sequence on m's given that the probability of appearance of n as the first digits decreases with n, in the sequence of factorials.

The footnote and comments talk about this, but don't exactly mention that what you want for the probability of the leading digits "2019" is log10(2.020)-log10(2.019).

While attempting to verify this, I was surprised to learn that bc has no built-in factorial function, even in the mathlib.

While looking into this, TIL bc is very scriptable:

  $ bc
  define fact_rec (n) { 
    if (n < 0) {
      print "oops";
      halt;
    }
    if (n < 2) return 1;
    return n*fact_rec(n-1);
  }
  fact_rec(5)
  120

In case anyone else was curious, Bedford's Law is apparently just a fancy name for the phenomenon where 1's appear much more frequently than 9's in any random sample of numbers. I think Bernie Madoff got caught faking the books due to the distributions not being shaped like Bedford's Law.

That's correct, but I think its "Benford's Law" rather than "Bedford's Law".

https://en.wikipedia.org/wiki/Benford%27s_law

What on Earth‽‽‽ How have I never heard of this before, and much more importantly - why is it true (I skimmed the wikipedia page and I didn't really see anything for 'why' but mostly for 'what')?

So it takes the data and draws it on a log scale to visualize it, but doesn't explain why the data naturally transposes to a log scale (we are talking about random data sets in nature). If I think of it as a village with 1,000 people is more likely than a village with 2,000 people is more likely than a village with 3,000 people (and this continues in both directions), the only real conclusion I can come to is that nature prefers smaller numbers of things. But that wouldn't extend to something like accounting books (or at least the jump is not immediately obvious to me).

EDIT: I guess I chose a bad example (although my point still is useful as a thought exercise), since this was used as an exception to the rule:

> Benford's law is violated by the populations of all places with population at least 2500 from five US states according to the 1960 and 1970 censuses, where only 19% began with digit 1 but 20% began with digit 2, for the simple reason that the truncation at 2500 introduces statistical bias.

It's because the ranges of distributions you sample from don't necessarily line up nicely with our number systems. For example, if you're measuring the distance between you and nearby stars in light years does it seem likely that the distances fit in the range of 0-99.99 light years perfectly? No, it's far more likely to overflow into 100s or even 200s of light years.

Hopefully that gives you an intuitive sense why Benford's law gives a highest probability for 1 as the leading number but 2 is the next most common and so on. You can also see the weaker application by the same argument to the following digits.

I'd wager that Benford's law doesn't apply to distances to stars.

See figure 1b. :)

https://digitalcommons.calpoly.edu/cgi/viewcontent.cgi?artic...

In fact, star distances follow Benford's law very well through multiple digits.

https://arxiv.org/abs/1401.5794

Among other things, the first digit is easier to change (percentage-wise) when a number starts with a large first digit.

StackExchange math has a decent analogy: https://math.stackexchange.com/questions/781/why-does-benfor...

For a village to grow from 1,000 people to 2,000 people, it has to double in size. But to grow from 9,000 people to 10,000 people, it only needs to grow by about 11%.

I need to think about it more, but I think this is the general direction my intuition is moving. Thank you!

”So it takes the data and draws it on a log scale to visualize it, but doesn't explain why the data naturally transposes to a log scale (we are talking about random data sets in nature)”

Random data sets in nature, measured in some arbitrary unit chosen by mankind. If one assumes expressing lengths in inches, feet, meters, parsecs, or any other arbitrary units will not change the distribution of initial digits, Benford’s law follows.

For example, when converting a set of lengths measured in yards to one measured in feet, the numbers originally beginning with a ‘1’, i.e. in the half-open interval [1,2) will start with a ‘3’, ‘4’, or ‘5’ i.e. lie in the half-open interval [3,6) in the new table. That can’t be true if initial digits are uniformly distributed.

Also, if that isn't convincing, number base. Even if we carefully defined the units such that Planck's constant is 6.6e-34 in base 10, it would still follow Benford's law (especially because that's a constant having a big exponent) for other number bases.

Your shock is warranted. It's actually a very deep question, called the Zipf mystery: https://www.youtube.com/watch?v=fCn8zs912OE

No one really knows why it's true. It's also true across physical constants, not just artificial quantities made up by humans.

The same type of distribution pops up in language, in nature, in numbers, popularity of opening chess moves, everywhere.

Zipf’s Law is related, but not quite the same thing: https://en.wikipedia.org/wiki/Zipf's_law

> No one really knows why it's true.

Any distribution of numbers that is "scale free" follows Benford's Law. This is extremely well understood.

The distribution of the areas of lakes, heights of trees, the proportion of the answers that start with the digit "1" should be the same no matter what units you use. You can measure heights in barleycorns, metres, inches, or cubits, the proportion of answers that start with the digit "1" should remain constant across those different units. Grind through the sums and Benford's Law pops out.

And Benford's Law is not Zipf's Law. Zipf's Law is also well-understood when you look at coding theory, and how we would expect language (and mutable codes in general) to change so that more frequently used "atoms" are "shorter.

So I don't really know what you're claiming here, but on the surface of it, with things I've studied, your comment seems mostly wrong.

At first I thought Zipf's had nothing to do with Benford's.

But then ..

https://terrytao.wordpress.com/2009/07/03/benfords-law-zipfs...

> No one really knows why it's true. This is what is so bizzare. We do know why it's true; the mystery is just pumped up in the press.

I have only skimmed the paper, but apparently Belevitch [0] showed (in 1959!) that Zipf's law and Mandelbrot's Law [1] are essentially just first-order and second-order approximations, respectively, for a large class of probability distributions, so no wonder it is so ubiquitous.

[0] Belevitch, V. (1959). On the statistical laws of linguistic distributions. Annales de la Societe Scientifique de Bruxelles, 73(3), 301–326.

[1] https://en.wikipedia.org/wiki/Zipf%E2%80%93Mandelbrot_law

did you type the first "‽" and then copy/paste the rest?

basically the reason for this is that for any probability distribution over natural numbers that can reasonably be called the average probability distribution of natural numbers, I have to assign smaller probabilities to larger numbers. There's a lot of ways in which this is formally true, but it's certainly true practically. Among the k digit numbers, the ones starting with 2 are larger than the numbers starting with 1, so they have to be at most equally likely, but there are the same number of each, so the probability of picking any number starting with two has to be less than or equal to the probability of picking any number starting with 1.

> did you type the first "‽" and then copy/paste the rest?

Typing that is easy with a composing keyboard. AltGr+!,? outputs ‽ (Or AltGr+?,! is ⸘)

Apologies for the off-topic tangent.

To be fair, I started it.

I wondered the same thing. Thank you for voicing the question.

One-off tangents like that are surprisingly fun, and informative.

For accounting, you have plenty of small things, and fewer large things.

A lot more small transactions than large transactions (how frequently do you buy a meal or groceries? vs how frequently do you buy a car or house?)

A lot more small companies (every independent bookstore, electrician, etc.) than large companies (how many >$1 billion market cap companies).

A lot more small salaries (entry level workers) vs large salaries (CEOs.)

A lot more small stock trades (minor portfolio adjustments) than large stock trades (liquidating your entire inventory as you enter/exit a market.)

Why is it true? It relates to exponential growth.

Start with any number and repeatedly add any percentage, e.g. 10%. Repeated multiplication will get you through the 2000s quicker than it got you through the 1000s.

What about what the other commenter mentioned - physical constants? There is no room for exponential growth there (or any sort of growth, for that matter).

What is meant by physical constants and in what context?

E.g. the boiling point of water starts with 1. That's not an aspect of Benford's law: it's intentionally set.

I think of it as less a statement about general data sets, and more a statement about base 10 representations.

In binary, every number begins with 1!

Not zero.

Fair enough :)

It works if you assume that the units are arbitrary. Suppose instead of people you're measuring heights. If there's going to be a distribution of leading numbers in random data, it has to be the same in feet and in yards.

To convert from yards to feet, you multiply by 3. Anything starting with 4 or 5 will always start with 1 after this multiplication, as will lots of things starting with 3 or 6. So starting with a 1 has to be as likely as starting with 3, 4, 5, 6.

The same sort of thing has to work if you multiply by any number. Benford's law gives you the distribution where this works.

The fact that this is scale-invariant means that it's not about preferring smaller numbers of things. It's just that the number of items in the range 10,000-19,999 is as large as the number of items in the range 0-9,999. Slightly bigger things also tend to start with ones.

This all just assumes that the distribution of leading digits doesn't change if you scale your data, which I find intuitive enough to be satisfying.

The first digit is a 1 much more frequently, the second digit less so, the third even less so, etc. The more digits the numbers in the sample have, on average, the smaller the difference in frequency, taken over all digits, gets.

So, in general, one cannot state that 1's appear much more frequently than 9's.

Also, that’s not in any random sample of numbers; you need to sample from a distribution with a certain property.

The distributions of many samples of real-world phenomena happen to have that property.

It's not true for any random sample of numbers. Spin up a Jupyter notebook and paste the following:

    %matplotlib inline
    import matplotlib.pyplot as plt
    import numpy as np
    import seaborn as sns
    sns.set_context('poster', font_scale=1.3)

    n_values = 10000
    lower_bound = 1
    upper_bound = 100000
    nums = np.array(
        [int(str(x)[0]) for x in np.random.randint(lower_bound, upper_bound, size=n_values)]
    )

    fig, ax = plt.subplots(figsize=(12, 8))
    sns.distplot(nums, kde=False, bins=list(range(1, 11)), ax=ax)
    ax.set_xticks(list(range(1, 11)))
    fig.tight_layout()

And you'll see it's essentially a uniform distribution of leading digits.

Real world random data often doesn't have a hard maximum. Try plotting a histogram of digits of -log(rand()). (I think this gives an exponential distribution with mean 1)

I'm glad that you agree that the original post was incorrect in stating that:

> Bedford's Law is apparently just a fancy name for the phenomenon where 1's appear much more frequently than 9's in any random sample of numbers.

because, as my example shows, it's false for the case of random numbers sampled uniformly across five orders of magnitude. You're also right that it's possible to construct a distribution (such as taking -log(rand())) where this behavior is observed.

> ... an observation about the frequency distribution of leading digits in many real-life sets of numerical data.

That's about leading digits only.

> in any random sample of numbers

To be more precise:

> Benford's law tends to apply most accurately to data that span several orders of magnitude. As a rule of thumb, the more orders of magnitude that the data evenly covers, the more accurately Benford's law applies. For instance, one can expect that Benford's law would apply to a list of numbers representing the populations of UK settlements. But if a "settlement" is defined as a village with population between 300 and 999, then Benford's law will not apply

https://en.wikipedia.org/wiki/Benford%27s_law#Explanations

Even this explanation is incorrect. Evenly sampled data across many orders of magnitude give an even distribution of leading numbers. See my comment for code here: https://news.ycombinator.com/item?id=21541264

There are many distributions which do lead to the distribution of leading digits that follow Benford's law, just not uniform. Nor "uniform over several orders of magnitude".

> Thus, real-world distributions that span several orders of magnitude rather uniformly

They mean uniformly on a log distribution. Ie, there are a uniform number of elements between 10^x and 10^(x+1), for many different values of x. This is best shown by the graph here:

https://en.wikipedia.org/wiki/Benford%27s_law#Overview

Reply on news.ycombinator.com