Divisible factorials

http://bit-player.org/2019/divisive-factorials
  • Transfer
Recently, I was completely baffled by this Farm Library tweet:


“That's what happens if you do not multiply in factorial, but divide.”

When I saw it, I had to give up my affairs, grab a notebook and check the forum. The result in draft form seemed logical. Since the multiplicative version$ n! $ while increasing $ n $tends to infinity, the “dividing” version should tend to zero. AND$ \ frac {n ^ 2} {n!} $behaves that way; polynomial function$ n ^ 2 $ grows slower than power function $ n! $ for large enough $ n $:

$\frac{1}{1}, \frac{4}{2}, \frac{9}{6}, \frac{16}{24}, \frac{25}{120}, \frac{36}{720}, \frac{49}{5040}, \frac{64}{40320}, \frac{81}{362880}, \frac{100}{3628800}$


But why the result of division takes exactly the form $\frac{n^2}{n!}$? Where does it come from$n^2$?

To answer this question, I had to scatter an old injury related to the study of the division of fractions, but I coped with the pain. Moving along the tweet formula from left to right, we first get$\frac{n}{n-1}$. Then, dividing this value by$n-2$get

$\cfrac{\frac{n}{n-1}}{n-2} = \frac{n}{(n-1)(n-2)}$


Continuing in this way, we end up with:

$n \mathbin{/} (n-1) \mathbin{/} (n-2) \mathbin{/} (n-3) \mathbin{/} \cdots \mathbin{/} 1 = \frac{n}{(n-1) (n-2) (n-3) \cdots 1} = \frac{n}{(n-1)!}$


To arrive at the result shown in the tweet $\frac{n^2}{n!}$, we simply multiply the numerator and denominator by $n$. (Although for my taste, the expression$\frac{n}{(n-1)!}$ more understandable.)


I am an officially recognized factorial fan. Keep your Fibonacci sequences with you; here is my favorite feature. Every time I learn a new programming language, my first exercise is to write several procedures for calculating factorials. Over the years I have come up with several variations of this theme, for example, a replacement in the definition$\times$ on $+$(which gives us triangular numbers). But it seems that I had never thought about replacing$\times$ on $\mathbin{/}$. It turns out strange. Since multiplication is commutative and associative, we can define$n!$ just like the product of all integers from $1$ before $n$without worrying about the order of operations. But when dividing the order ignore will not work. In general,$x \mathbin{/} y \ne y \mathbin{/}x$ and $(x \mathbin{/} y) \mathbin{/} z \ne x \mathbin{/} (y \mathbin{/} z)$.

In the Farm Library tweet, dividers are arranged in descending order:$n, n-1, n-2, \ldots, 1$. The most obvious thing is to replace this by ascending order:$1, 2, 3, \ldots, n$. What happens if we define the division factorial as$1 \mathbin{/} 2 \mathbin{/} 3 \mathbin{/} \cdots \mathbin{/} n$? Another return to the school fraction division algorithm gives us a simple answer:

$1 \mathbin{/} 2 \mathbin{/} 3 \mathbin{/} \cdots \mathbin{/} n = \frac{1}{2 \times 3 \times 4 \times \cdots \times n} = \frac{1}{n!}$


In other words, when we perform division many times, performing counting from $1$ before $n$, the final result will be equal to the inverse $n!$. (I would like to put an exclamation mark at the end of this sentence, but alas!) If you are looking for a canonical answer to the question “What will we get by dividing instead of multiplying into$n!$? ”, Then I would say that $\frac{1}{n!}$ - better candidate than $\frac{n}{(n - 1)!}$. Why don't we accept symmetry between$n!$and its inverse?

Of course, there are many other ways of placing n integer values ​​in the set$\{1 \ldots n\}$. But how much? As it turned out, exactly$n!$! Therefore, it may seem that there is$n!$ unique ways to define the dividing function $n!$. However, studying the answers of the two permutations shown above makes us understand that a simpler pattern works here. Whatever element of the sequence appears first, it appears in the numerator of the large fraction, and the denominator is the product of all other elements. Therefore, in the end it remains only$n$various results (assuming that we always perform division operations strictly from left to right). For any integer$k$ in the range of $1$ before $n$by putting $k$ at the top of the line, we create a delimiter $n!$equal to $k$divided by all other factors. You can write it as follows:

$\cfrac{k}{\frac{n!}{k}}, \text{ что можно преобразовать в } \frac{k^2}{n!}$


And so we solved a little riddle about how in this tweet $\frac{n}{(n-1)!}$ turned into $\frac{n^2}{n!}$.
It is worth noting that all these functions converge to zero when aspiring$n$to infinity. From the asymptotic point of view,$\frac{1^2}{n!}, \frac{2^2}{n!}, \ldots, \frac{n^2}{n!}$ are identical.


TA-dah! Mission Complete. Problem solved. It is done. Now we know everything we need about dividing factorials, right?

Well, maybe there is another question. What will the computer say? If you take our favorite factorial algorithm, and do what is suggested in the tweet, replacing all the entries of the operator$\times$(or *) on /, what will happen? Which of$n$ options dividing $n!$will give us a program?

Here is my favorite algorithm for calculating factorials as a program on Julia :

function mul!(n)
    if n == 1return1elsereturn n * mul!(n - 1)
    end
end

This algorithm introduced whole generations of nerds to the concept of recursion. In text form, it reads: if$n$ equally $1$then $mul!(n)$ equally $1$. Otherwise, you need to calculate the function$mul!(n-1)$and then multiply the result by $n$.

You may ask what will happen if$n$will be zero or negative. You can ask, but better not. For our current goals$n \in \mathbb{N}$.

Starting with any positive$n$, the sequence of recursive calls will sooner or later sink to $n = 1$.

The function can be written more succinctly using the Julia single-line definition style:

mul!(n)  =  n == 1 ? 1 : n * mul!(n - 1)

The right side of an assignment operator is a conditional expression, or a ternary operator, which has the form a ? b : c. Here ais the boolean test condition that should return the value either trueor false. If aequal true, the expression is evaluated b, and the result becomes the value of the entire expression. Otherwise, it is calculated c.

Just to make sure I did everything right, here are the first 10 factorials computed by this program:

[mul!(n) for n in 1:10]
10-element Array{Int64,1}:
       126241207205040403203628803628800

Now let's change this definition and transform the only entry *into /, leaving everything else unchanged (except for the function name).

div!(n)  =  n == 1 ? 1 : n / div!(n - 1)

And that's what the program returns if we run it for values $n$ from $1$ before $20$:

[div!(n) for n in 1:20]
20-element Array{Real,1}:
 12.01.52.66666666666666651.8753.22.18753.6571428571428572.46093754.0634920634920632.707031254.4329004329004332.93261718754.7738927738927743.142089843755.0921522921522923.3384704589843755.3916906622788973.5239410400390635.675463855030418

What? It is definitely not like going to zero, as well as$\frac{1}{n!}$ or $\frac{n}{n - 1}$. In fact, the values ​​do not look that way, because they are not going to converge. Judging from the graph shown below, the sequence consists of two alternating components, each of which seems to be slowly growing towards infinity, and also deviates from the other.


Understanding what we are seeing here, it will be useful to change the type of output of the function div!. Instead of using a division operator /, which returns a value as a floating point number, we can replace it with an operator //that returns an exact rational value, rounded to the lowest term.

div!(n)  =  n == 1 ? 1 : n // div!(n - 1)

Here is a sequence of values ​​for n в интервале 1:20:

20-element Array{Real,1}:
       12//1    3//2    8//3    15//8    16//5    35//16   128//35   315//128  256//63   693//256  1024//231  3003//1024 2048//429  6435//2048 32768//6435 109395//3276865536//12155230945//65536262144//46189

The list is full of curious patterns. This is a double helix in which even and odd numbers move in zigzags in the complementary strands. Even numbers are not just even, they are all powers$2$. In addition, they appear in pairs — first in the numerator, then in the denominator — and their sequence is non-decreasing. But there are gaps; not all degrees are present$2$. The odd string looks even more complex, various small simple coefficients appear and disappear in numbers. (Prime numbers should be small, at least less.$n$.)

This result surprised me. I expected to see a much more meticulous sequence, like the ones I calculated on paper. All these broken jumps up and down had no meaning. The general trend towards an unlimited increase in the ratio did not make sense either. How can we constantly divide, while getting bigger and bigger numbers?

At this stage, you can pause the reading and try to come up with your own theory about where these zigzag numbers come from. If you need a hint, then you have it, and a very strong, almost spoiler: look for a sequence of numerators or a sequence of denominators in the Online Encyclopedia of Integer Sequences .


Here is another hint. A small change in the program div!completely converts the output. Just change the last expression, replacing n // div!(n - 1)with div!(n - 1) // n.

div!(n)  =  n == 1 ? 1 : div!(n - 1) // n

Now the results look like this:

10-element Array{Real,1}:
  11//2                  1//6                  1//24                 1//120                1//720                1//5040               1//40320              1//362880             1//3628800

This is the inverse function of factorial, which we have already seen, a series of values ​​generated by traversing from left to right in an increasing sequence of divisors. $1 \mathbin{/} 2 \mathbin{/} 3 \mathbin{/} \cdots \mathbin{/} n$.

Not surprisingly, changing the last expression in the procedure changes the result. In the end, we know that the division is not commutative and not associative. But it is difficult to understand why the sequence of values ​​generated by the original program gives such a strange zigzag shape. What mechanism generates such pair powers of two and alternating odd and even values?

I found that explaining what is happening in a zigzag sequence is easier on an iterative version of the procedure, and not on a recursive one. (This statement may seem annoying to those who consider recursive definitions more simple, but it just so happened.) This is what the program looks like:

functiondiv!_iter(n)
    q = 1
    foriin 1:nq = i // qendreturnqend

I declare that this procedure with a functional cycle is identical to a recursive function, in the sense that if div!(n)it div!_iter(n)returns a result for some positive integer n, then it will always be the same. Here is my proof:

[div!(n) for n in 1:20]    [div!_iter(n) for n in 1:20]
            11//1    2//1                       2//1    3//2                       3//2    8//3                       8//3    15//8                      15//8    16//5                      16//5    35//16                     35//16   128//35                    128//35   315//128                   315//128  256//63                    256//63   693//256                   693//256  1024//231                  1024//231  3003//1024                 3003//1024 2048//429                  2048//429  6435//2048                 6435//2048 32768//6435                32768//6435 109395//32768              109395//3276865536//12155               65536//12155230945//65536              230945//65536262144//46189              262144//46189

To understand the process that generates these numbers, consider the sequential values ​​of the variables $i$ and $q$every time you run a cycle. Initially$i$ and $q$ are equal $1$; so after the first pass of the cycle, the expression q = i // qgives$q$ value $\frac{1}{1}$. Then$i = 2$, but $q = \frac{1}{1}$i.e. new value $q$ equally $\frac{2}{1}$. At the third iteration$i = 3$, but $q = \frac{2}{1}$what gives us $\frac{i}{q} \rightarrow \frac{3}{2}$. If this still confuses you, imagine$\frac{i}{q}$ as $i \times \frac{1}{q}$. An important observation here is that with each loop traversal$q$ gets the inverse of becoming $\frac{1}{q}$.

If you expand these operations and look at the multiplications and divisions included in each element of the series, then a pattern appears:

$\frac{1}{1}, \quad \frac{2}{1}, \quad \frac{1 \cdot 3}{2}, \quad \frac{2 \cdot 4}{1 \cdot 3}, \quad \frac{1 \cdot 3 \cdot 5}{2 \cdot 4} \quad \frac{2 \cdot 4 \cdot 6}{1 \cdot 3 \cdot 5}$



In general:

$\frac{1 \cdot 3 \cdot 5 \cdot \cdots \cdot n}{2 \cdot 4 \cdot \cdots \cdot (n-1)} \quad (\text{odd } n) \qquad \frac{2 \cdot 4 \cdot 6 \cdot \cdots \cdot n}{1 \cdot 3 \cdot 5 \cdot \cdots \cdot (n-1)} \quad (\text{even } n)$



Functions $1 \cdot 3 \cdot 5 \cdot \cdots \cdot n$ for odd $n$ and $2 \cdot 4 \cdot 6 \cdot \cdots \cdot n$ for even $n$have their own name! They are called double factorials, and are written as$n!!$.

Terrible terminology, right? It would be better if they were called “semi-factorials”. And if I didn't know that, I would read$n!!$as factorial factorial.

The double factorial n is defined as the product of n and all smaller positive integers of the same parity. So our curious sequence of zigzag values ​​is just$\frac{n!!}{(n-1)!!}$.

The 2012 article by Henry W. Gould and Joslin Quentins (alas, located behind the paywall) explores the use of double factorials. They are much more common than you might think. In the middle of the 17th century, John Wallis brought out the following identity:

$\frac{\pi}{2} = \frac{2 \cdot 2 \cdot 4 \cdot 4 \cdot 6 \cdot 6 \cdots}{1 \cdot 3 \cdot 3 \cdot 5 \cdot 5 \cdot 7 \cdots} = \lim_{n \rightarrow \infty} \frac{((2n)!!)^2}{(2n + 1)!!(2n - 1)!!}$


An even more bizarre series involving the cube of double factorial values ​​is summed up in $\frac{2}{\pi}$. He was discovered by none other than Srinivasa Ramanujan.

Gould and Cientens also considered the equivalent of double factorial for binomial coefficients. The standard binomial coefficient is defined as:

$\binom{n}{k} = \frac{n!}{k! (n-k)!}$


The double version looks like this:

$\left(\!\binom{n}{k}\!\right) = \frac{n!!}{k!! (n-k)!!}$


Note that our zigzag numbers correspond to this description, and therefore can be considered the binomial coefficients of double factorials. More specifically, they are such numbers:

$\left(\!\binom{n}{1}\!\right) = \left(\!\binom{n}{n - 1}\!\right) = \frac{n!!}{1!! (n-1)!!}$


Normal Bean $\binom{n}{1}$not very interesting; he is just equal$n$. But the double version$\left(\!\binom{n}{1}\!\right)$as we have seen, a more lively dance is dancing. And unlike the usual Binom, it is not always integer. (The only integer values ​​are$1$ and $2$.)

A look at zigzag numbers as a quotient of double factorials explains quite a few of their properties, starting with alternating even and odd values. We can also see why all the even numbers in the sequence are powers of 2. Consider an example with$n = 6$. The numerator of this fraction is$2 \cdot 4 \cdot 6 = 48$receiving from $6$ factor $3$. But the denominator is$1 \cdot 3 \cdot 5 = 15$. Top three and bottom are reduced, leaving us$\frac{16}{5}$. Such reductions occur in each of the cases. Every time an odd factor appears in the sequence of even numbers$m$He necessarily has the form $2 \cdot m$but by this time itself $m$ should already appear in the sequence of odd numbers.


Is the sequence of zigzag numbers a reasonable answer to the question: “What will happen if we divide, rather than multiply, in $n!$? Or was the computer program that generated them just turned out to be an erroneous algorithm? In my personal opinion,$\frac{1}{n!}$ - a more intuitive answer, but $\frac{n!!}{(n - 1)!!}$- more interesting.

Moreover, the very existence of a zigzag sequence expands our horizons. As stated above, if you insist that the division algorithm should always go through the list of numerators in order$n$, at each step of dividing the number from the left to the number on the right, then there is a total $n$possible outcomes, and they all look very similar. But the zigzag solution provides much more opportunities. We can formulate the problem as follows: take a set of numerators$\{1 \dots n\}$, choose its subset and reverse all elements of this subset; Now multiply all numerators, both inverse and direct. If the inverted subset is empty, then the result will be the usual factorial$n!$. If all the numerators have been reversed, then we get the reverse$\frac{1}{n!}$. And if every second numerator is addressed, starting with$n - 1$, the result will be an element of the zigzag sequence.

These are just some of the many options available; in total there is$2^n$ subsets of $n$items. For example, you can take the inverse of each number, which is a prime or a prime power.$(2, 3, 4, 5, 7, 8, 9, 11, \dots)$. When small$n$ the results are jumping, but constantly remain less than $1$:


However, if I continued this schedule for more $n$, he would have flown into the stratosphere. The powers of the primes become very sparse on the number line.


Now I will ask a question. We have seen factorial variations approaching zero as$n$ to infinity for example $1/n!$. We have seen other variations that grow with$n$ infinitely including myself $n!$and zigzag numbers. Are there any varieties of the factorial process converging to some finite non-zero boundary?

First of all, I came up with this algorithm:

function greedy_balance(n)
    q = 1while n > 0
        q = q > 1 ? q /= n : q *= n
        n -= 1
    end
    return q
end

We cycle through integer values ​​from $n$ down to $1$, calculating in the process the current work / quotient $q$. At each step, if the current value$q$ more $1$, we divide it by the next numerator, otherwise, we perform multiplication. This scheme implements some kind of feedback control or target search behavior. If a$q$getting too big, we reduce it; if too small, we increase it. I suggested that while aiming$n$ to infinity $q$ will converge to a constantly narrowing range of values ​​next to $1$.

But the experiment gave me another surprise:


Such a sawtooth wave is not exactly what I expected. Curiously, the curve is not symmetric around$1$; deviations from above have a larger amplitude than from below. But this distortion is more visual than mathematical. Because$q$ is a private distance from $1$ before $10$ same as the distance from $1$ before $\frac{1}{10}$, but on a linear scale does not look like this. You can fix this by making a logarithmic graph of the private:


Now the graph is symmetrical, or at least approximately, and centered on the value $0$which is logarithm $1$. But there remains a more serious mystery. The sawtooth wave is very regular and has a period$4$, while not showing signs of compression towards the expected limiting value $\log q = 0$. Numerical values ​​suggest that$n$ to infinity, the curve peaks converge to a slightly higher value $q = \frac{5}{3}$and the minima are close to the value just below $q = \frac{3}{5}$. (The corresponding logarithms are based on$10$ about equal $\pm0.222$). I could not figure out why this is happening. Perhaps someone can explain.

Failure with this greedy algorithm does not mean that we cannot divide factorial converging to$q = 1$.

If we work with the logarithms of the numerators, then this procedure becomes the case of a well-known computational problem called the “problem of breaking up a set of numbers”. We are given a set of real numbers, and we must divide them into two sets, the sum of which is equal, or as close as possible to equality. This is a proven challenge, but it is also called ( PDF ) “the simplest challenge”.

For anyone$n$ we may find that by using the inverse of some other subset of numerators gives us a better approximation to $n! = 1$. For small$n$ we can solve this problem by iterating: just consider everything $2^n$subsets and choose the best.

I calculated optimal partitions down to$n = 30$when you need to choose from a billion options.


Obviously, the graph is becoming more flat. You can use the same method to force a convergence to any other value in the range from$0$ before $n!$.

And so we get another answer to the question posed by a tweet and began our journey. What happens if we divide, rather than multiply in$n!$? Whatever we like.
Tags:

Also popular now: