Short shoulder matching

James Tanton scatters puzzles in number theory with the same generosity with which John D. Rockefeller handed out dimes. I already wrote about one of Tanton's tasks. A few weeks later, this tweet about factorials and squares attracted my attention and did not give me rest:


“4! +1 = 25, the square of the number. 5! +1 = 121, also the square of a number. Can you give another example? Two more examples? ”

With a pen and paper, it’s easy to show that$$6 ! not suitable. Factorial$$6 ! - this$$1 × 2 × 3 × 4 × 5 × 6 = 720 ; adding$$1 , we get the number$$721 , which is not a square. (It is factorized as$$7 × 103. ) On the other hand,$$7 ! equally$$5040 , and adding$$1 , we will get$$5041 , which is equal$$71 2 . This gives us a very nice equation:

$$7 ! + 1 = 71 2

Continuing further, we find out that $$8 ! + 1 ,$$9 ! + 1 and$$10 ! + 1 are not squares of numbers. But to continue the search, we need mechanized assistance. Here is a function onJuliathat does the obvious work - calculating consecutive factorials and checking if they are on$$1 less than square:

functionsearch_fac_sqr(maxn)
  fac = big(1)                      # большие целые нужны для n > 20for n in1:maxn
    fac *= n                        # инкрементный факториал
    r = isqrt(fac + 1)              # округление sqrt в меньшую сторону
    if r * r == fac + 1
      println(n, "! + 1 = ", r, "^2 = ", r^2)
    endend
  println("Вот и всё, ребята!")
end

Armed with this tool, let's check $$n ! + 1 for everyone$$n from$$1 to$$100 . Here is what the program tells us:

search_fac_sqr(100)4! + 1 = 5^2 = 255! + 1 = 11^2 = 1217! + 1 = 71^2 = 5041
Вот и всё, ребята!

These are the same three cases that we have already discovered with a pen and paper - and there is nothing else on the list. In other words, among all the meanings$$n ! + 1 up to$$n = 100 only$$n = 4 ,$$n = 5 and$$n = 7 give squares of numbers. When I continued searching until$$n = 1000 , I got exactly the same result. The same thing happened with$$n = 10000 and$$n = 100000 . It is worth mentioning that factorial$$100,000 is a fairly large number of$$456574 decimal places. At this point in the search, I began to run out of steam; moreover, I began to lose hope. When$$99993 sequential values$$n fails to get a single square, it is difficult to continue to hope that success can wait for us around the corner. However, I continued to persist. I got to$$n = 500000 , the factorial of which contains$$2632341 decimal places. In the whole set, not a single square came across.

What can we learn from this evidence - or lack thereof? Are 4, 5, and 7 the only values$$n ! which on$$1 square integer? Or is there somewhere else on the number line, perhaps right after my interval? Can there be infinitely many? And if so, where are they? If they are not, then why?

---

For my taste, the most satisfactory way to resolve these issues will be to find some principle of number theory, which guarantees that $$n ! + 1 ≠ m 2 for$$n > 7 . I could not find such a principle, but in my dreams I can roughly imagine what the proof might look like. Suppose we get rid of part of the formula "$$+ 1 ", and begin the search for integers such that$$n ! = m 2 . It turns out that this equation has only one solution, for$$n = m = 1 . You should not burden your laptop with a search for greater solutions - there is simple evidence that they do not exist. In any square of an integer, all prime divisors must be present an even number of times, for example, as in$$36 = 2 × 2 × 3 × 3 . In a factorial, at least one simple divisor - the largest - is always present only once. (If you don’t understand why, readBertrand’s postulate / Chebyshev’s theorem.)

Of course, when we substitute "$$+ 1 "into the formula, then the whole chain of reasoning falls apart. In the general case, factorization$$n ! and$$n ! + 1 is completely different. But maybe there is some other property$$n ! + 1 , which conflicts with squareness. It may be somehow connected with congruence classes or with square remnants. From the definition of factorial, we know that$$n ! divisible by all positive integers less than or equal to$$n , which means that$$n ! + 1 cannot bedivisible by any of these numbers (except$$1 ). This observation excludes certain types of squares, namely those that have small primes in the factorization. But for everyone$$n > 4 square root$$n ! far superior$$n , therefore, there is enough space for larger divisors, as is the case with$$7 ! + 1 = 71 2 .

Here is another way worth exploring. The decimal representation of any large factorial ends with a line from$$0 created as works$$5 and$$2 among the divisors of the number. In this way,$$n ! + 1 should look like

$$X X X X X ... X X X X X 00000 ... 00001

Where $$X stands for any decimal digit, and the next row of$$0 ends with a single$$1 . Can we find a way to prove that a number like this is never a square? Well, if the last digit would be different from$$1 ,$$4 or$$9 , then the proof would be simple, but many squares end with$$... 01 , for example,$$10201 = 101 2$$62001 = 249 2 . If there is any algebraic consideration showing that$$n ! + 1 can not be a square, then it is more subtle.

All of the above is fictional math. I mixed a few ingredients that should turn into a delicious dough, but I have no idea how to bake a pie. Maybe someone else will help me with the recipe. In the meantime, I want to have fun with an alternative hypothesis: nothing bothers$$n ! + 1 to be a square, besides improbability.

---

The pattern observed in the task $$n ! + 1 = m 2 - several matches among the smallest elements of sequences, and then not a single match in many thousands of elements - is not unique to factorials and squares. Other pairs of sequences exhibit similar behavior. Triangular numbers starting with$$1 , 3 , 6 , 10 , 15 , 21 , ... , are given by the formula$$T ( m ) = m ( m + 1 ) / 2 . If we look for factorials that are also triangular, we get$$1 ! = T ( 1 ) = 1 , then$$3 ! = T ( 3 ) = 6 and finally$$5 ! = T ( 15 ) = 120 . No more examples before$$n = 100000 does not occur.

What about factorials that are on$$1 is less than a triangular number satisfying the equation$$n ! + 1 = T ( m ) ? I know the only such case:$$2 ! + 1 = 3 . Expanding my search a bit, I found that$$n ! + 4 triangular for$$n ∈ 2 , 3 , 4 , after which again there are no matches until$$100,000 .

For another experiment, we can return to the squares of numbers and abandon factorials, replacing them with the ever-popular Fibonacci series$$1 , 1 , 2 , 3 , 5 , 8 , 13 , ... , defined by recursion$$F ( n ) = F ( n - 1 ) + F ( n - 2 ) , where$$F ( 1 ) = F ( 2 ) = 1 . Since the 1960s it was knownthat$$1 and$$144 are the only positive integer numbers that are both Fibonacci numbers and squares of integers. Looking for the Fibonacci numbers that are on$$1 less than a square, I found out that$$F ( 4 ) + 1 = 4 and$$F ( 6 ) + 1 = 9 , and there are no other cases before$$F ( 500,000 ) .

We can do the same withCatalan numbers,$$1 , 1 , 2 , 5 , 14 , 42 , 132 ... , one more next to a huge fan club. I found out that among the Catalan numbers there are no other squares except$$1 up to$$n = 100,000 ; I do not know if anyone has proven that they do not exist. Search for cases in which$$C ( n ) + 1 = m 2 , also does not give results, but there are several correspondences with low values ​​for$$C ( n ) + k = m 2 for$$k ∈ 2 , 3 , 4 .

Finding similar behavior in all of these different sequences, in my opinion, changes the complexity of the task. If we discover some mysterious special property$$n ! + 1 , explaining why it never corresponds to squares (for large values$$n ), will we need to reinvent another mechanism for Fibonacci numbers and another one for Catalan numbers? Does it not seem more convincing that behind all these observations is the only common reason?

But this reason cannot betoogeneral. This is not the case when you can take any two numerical sequences and expect to see the same pattern at their intersections. Consider factorials and primes. By the very nature of factorials, not one of them is 2! = 2 cannot be a prime, but there are no obvious reasons why$$n ! + 1 cannot be a prime. And indeed, for$$n ≤ 100 simple are nine values$$n ! + 1 . Extending the boundaries of the search to$$n ≤ 1000 , we will find seven more. Here is acomplete set of known numbersfor which$$n ! + 1 is simple:

$$1 , 2 , 3 , 11 , 27 , 37 , 41 , 73 , 77 , 116 , 154 , 320 , 340 , 399 , 427 , 872 , 1477 ,6380 , 26951 , 110059 , 150209

With increasing $$n they are found less and less, but there are no signs of a sharp limit, as in the cases considered earlier. Does this series go on indefinitely? This seems like a logical hypothesis. (For more information on this sequence, including reference materials, seeChris Caldwell'sfactorial primepage.)

---

My question is this: can we perceive these curious patterns as pure coincidence? Values$$n ! + 1 form an infinite sequence of integers distributed along all the number line, densely located near the beginning, but becoming extremely sparse with increasing$$n . Values$$m 2 form another infinite sequence, also with decreasing density, although not with such a sharp decline. It is possible that factorials coincide with squares among the smallest integers, simply because these integers are not enough to “go wild,” and some of them have to do double work. But in vast open spaces, a numerical direct factorial can wander for years - perhaps forever - without ever meeting a square.

Let me state this idea more clearly. Insofar as$$n ! cannot be a square, then we know that it is somewhere between two squares; the location on the number line looks like$$( m - 1 ) 2 < n ! < m 2 . The distance between the endpoints of this interval is$$m 2 - ( m - 1 ) 2 = 2 m - 1 . Now choose a random number from the interval$$k and ask whether$$n ! + k = m 2 . Exactly one value must satisfy this condition.$$k , i.e., the probability of coincidence is$$1 / ( 2 m - 1 ) , or approximately$$1 / ( 2 √n ! ). Insofar as$$√n ! grows very fast, this probability instantly tends to zero with increasing$$n . In the chart below, this is indicated by a purple line. Notice that to$$n = 100 purple curve almost reached$$10 - 80 .



The green curve indicates the probability of a match between Fibonacci numbers and squares; the form is similar, but it "dives" from the "cliff" a little later. The Fibonacci-squares curve is approximately equal to the negative exponential function: the probability is proportional$$ϕ - √F ( n ) where$$ϕ = ( √5 +1)/2≈1.618. The factorial-squares curve is even sharper because the factorial function issuperexponential:$$n ! growing faster than$$c n , for any constant$$c .

The blue curve fixing the probability of coincidences between factorials and primes has a completely different shape. In the surrounding area$$n ! the average distance between consecutive primes is approximately equal$$log n ! that grows a little faster than itself$$n and much slower than$$n ! . The probability of a match between factorials and primes is approximately equal$$1 / log n ! . A continuous blue curve corresponds to this smooth approximation. The blue dots scattered next to the line are probability values ​​based on real distances between consecutive primes.

---

What can be done with these curves? Is it permissible to apply probability theory to these absolutely determinate sequences of numbers? I don’t know for sure. Before posing this question directly, I prefer to take a few steps back and consider a simpler model in which probability has every right to use.

Let's borrow one of the famous Jacob Bernoulli urns, which has enough space to store an infinite number of ping-pong balls. Let's start with one black and one white ball in the ballot box, then we will pull the balls randomly. Obviously, the probability of choosing black is$$1 / 2 . Put the selected ball back in the ballot box, and also add another white ball. Now there are three balls and only one of them is black, so the probability of drawing black is$$1 / 3 . Add the fourth ball, and the probability of black drops to$$1 / 4 . Continuing in the same way, we get that the probability of black on$$nth pull should be equal$$onen + 1 .

If we continue this process indefinitely - always choose a random ball, return it back and add another white ball - then what is the likelihood that we will see the black ball at least once? It will be easier to answer the corollary of this question - to calculate the probability ofneverseeing a black ball. This is an endless work$$one2 ×23 ×34 ×45 ..., or:

$$P ( never black ) = ∞ ∏ n = 1 1 - 1n + 1

If a $$n tends to infinity, the product tends to zero. In other words, in an endless series of attempts, the probability of never pulling out a black ball is$$0 ; this means that the probability of meeting black at least once is$$1 . ("Probability$$1 "is not exactly the same as" certainty ", but incredibly close.)

Now let's put another experiment. Again we start with one black and one white balls, but after the first pull-back cycle we add two white balls, then four white balls, and so on, so that the total number of balls in the ballot box at the stage$$n is equal$$2 n ; During this process, all but one of the balls will be white. Now the probability of never seeing a black ball is equal$$one2 ×34 ×78 ×1516 ..., or:

$$P ( never black ) = ∞ ∏ n = 1 1 - 12 n P(never black)= ∞ ∏ n=11-12 n

This product does not tend to zero, regardless of the magnitude$$n . Nor does it seek to$$1 . The product convergesto a constant with anapproximate value$$0.288788095 . This is strange, isn't it? Even with an endless series of pulls from the urn, we cannot be sure whether a black ball will appear or not.

These two urn experiments are not directly related to any of the matching tasks described above; they simply illustrate the range of possible outcomes. But we can create a process with an urn that imitates a probabilistic approach to the problem of factorials and squares. On$$The nth stage of the urn contains$$1 + 2 √n ! balls, only one of which is black. The probability of never seeing a black ball even with an endless series of attempts is equal to

$$∞ ∏ n=11-11 + 2 √n !

This expression converges to a value approximately equal to $$0.2921426977 . It follows that the probability of seeing a black ball at least once is$$1 - 0.2921426977 , or$$0.7078573023 . (No, this number is not$$1 / √2 , although close to it.) A

process with an urn reminiscent of the problem of factorials and primes gives a rather different result. Here the number of balls in the ballot box at the stage$$n is equal$$log n ! again with only one black ball. The infinite product governing the total probability is

$$∞ ∏ n=21-1log n !

In the numerical proof, it seems that this expression tends to zero as $$n to infinity (although I'm not 100% sure about this). If itreallystrives for$$0 , until the additional probability that the black ball appears sooner or later should be equal to$$1 .

Some of these results made me feel fooled, and even a little annoyed. You can call me old-fashioned, but I always thought that an infinite number of bone rolls should be enough to eliminate any doubts as to whether the pattern will appear or not. In the cruel light of infinity, I would say, everything is either forbidden or obligatory; when$$n tends to infinity, probability or tends to$$0 , or tends to$$1 . But obviously this is not so. In the factorial urn model, the probability of never seeing a black ball is neither equal to$$0 nor$$1 and is located somewhere near$$0.2921426977 . What does this mean? How should I make sure the number is correct or even check its first few digits? Performing an endless series of attempts is not enough; it is necessary to collect a statistically significant sample of endless experiments. For an accurate result, you need to conduct an endless series of endless experiments. Alas.

---

The urn model naturally correlates with a randomized version of the factorial-square problem, in which we look at $$n ! + k = m 2 and choose random$$k from the corresponding range of values. What about the original problem$$n ! + 1 = m 2 ? In this case, there is no random variable, and therefore it makes no sense to perform many experiments for each value$$n . The system is deterministic. For each$$n factorial$$n has an exact value and it is close, or not close to the square of an integer. There are no "maybe."

However, there is a workaround that can add probabilities here. To do this, we must assume that factorials and squares constitute a kind of ergodic system in which observing a chain of events over a long period of time is similar to observing a lot of shorter chains. Suppose that factorials and squares are not related to their location on the number line — that when a factorial is between two squares, then the distance to the larger square can be considered a random variable and each possible distance has the same probability. If we adhere to this assumption, then instead of considering one value$$n ! and checking many random values$$k we can take a single value$$k (namely$$k = 1 ) and consider$$n ! for many values$$n .

Is such an ergodic assumption reasoned? Not really. It is known that some distances between$$n ! and$$m 2 is more likely than others, and some distances are impossible at all. However, empirical evidence indicates that such deviations should be negligible. The graph below shows the distance distribution between the factorial and the next larger square for the first$$100,000 values$$n ! . Distances are normalized in the interval$$( 0 , 1 ) and are classified into$$100 columns. Obvious signs of displacement are imperceptible. The calculation of the mean and standard deviation of the same$$100,000 relative distances result in values ​​within$$1 percent of those expected with a uniform random distribution. (Expected values ​​are equal$$μ = 1 / 2 and$$σ = 1 / 12 ).



If such a probabilistic approach can be taken seriously, then I can make some numerical judgments about the prospects of finding a large factorial adjacent to the square of an integer. As mentioned above, the overall probability that one or more values$$n ! + 1 equal to squares, approximately equal$$0.7078573023 . Thus, we should not be too surprised that three such cases are already known, namely, examples with$$n = 4 ,$$5 and$$7 . Now we can apply the same method to calculate the probability of finding at least one more case with$$n > 7 . Let's make the question more general: “Regardless of whether we saw squares among the first$$C values$$n ! + 1 , what are the chances that we will see them after? ”To answer this question, we can simply remove the first$$C elements from an endless product:

$$∞ ∏ n=C+11-11 + 2 √n !

At $$C = 7 answer is approximately equal$$0.0037 . At$$C = 100 is approximately equal$$5.7 × 10 - 80 . We go down the steep slope of the purple curve.

From a practical point of view, further searches for another pair of factorial squares do not look like a promising way to waste time and processor cycles. The probability of success is quickly reduced to ridiculously small numbers, such as$$10 - 1,000,000 . And yet, from a mathematical point of view, probability never disappears. Removing a finite number of terms from the front of an infinite product cannot change its convergence properties. If the original product converged to a nonzero value, the shortened version will behave the same way. Thus, we found ourselves in a canyon of maximum disappointment, in which there is no realistic way to find a reward, but the probabilities still tell us that it can exist.

---

I conclude this awkward essay by looking at yet another example (very advanced). Suppose we apply probabilistic reasoning to find a cube that$$1 less than a square. If we consider the exact correspondence between cubes and squares, then there are quite a lot of them - these are six degrees:$$1 , 64 , 729 , ... . But whole solutions to the equation$$n 3 + 1 = m 2 are not so frequent. One low-value example is easy to find:$$2 3 + 1 = 3 2 , but when after$$8 and$$9 can we expect to see consecutive cube and square?

The probabilistic approach suggests that we have reasons for optimism. Compared to factorials and Fibonacci numbers, cubes grow much more slowly; their speed is polynomial, not exponential and not superexponential. As a result, the probability of finding the cube at a given distance from the square decreases much less sharply than it does for$$n ! or$$F ( n ) . In the chart below$$P ( n 3 + k = m 2 ) is the orange curve.



Notice that the orange curve lies directly below the blue, which represents the probability that $$n ! is next to a prime number. The proximity of these two curves suggests that two problems — factorials adjacent to primes, cubes adjacent to squares — may belong to the same class. We already know that factorial-simple arise over and over again, possibly ad infinitum. This analogy leads us to a hunch: perhaps the coincidence of square cubes is also unlimited. If we continue to observe, we will see many more, except$$8 and$$9 .

But such a conjecture is completely false. This task has a very long history. In 1844, Eugene Catalan suggested that$$8 and$$9 are the only consecutive power values ​​among integers; this assumption wasfinally provedin 2004 by Preda Mihailescu. Euler decided the special case of squares and cubes in the eighteenth century. Thus, the probabilities have nothing to do with it.

All the questions considered in the article belong to the category of Diophantine analysis — studies of equations whose solutions must be integers. This area of ​​mathematics is notorious for problems that are easy to set but hard to solve. The Catalan hypothesis is one of the most famous examples, along with Fermat's great theorem. When the Diophantine problems are finally solved, the proofs are usually very non-elementary, they use sophisticated tools from deep areas of mathematics - algebraic geometry in the proof of the great theorem of Fermat by Andrew Wiles and Richard Taylor, circular fields in the proof of the Mihailesco hypothesis of Catalan. As far as I know, probability theory did not play a central role in any such evidence.

When I began to deal with these issues a few weeks ago, I did not expect to find a concrete solution. And my expectations were fully met! In fact, in my head the situation has become even more confusing than at the beginning. The realization that even an endless series of experiments does not necessarily provide answers to some questions deeply upsets me and makes me wonder how well I really understand probability theory. But this situation is unlikely to be rare in mathematics. I think I should get used to it already.

Update:thanks to another tip from Tanton, I realized that this task has a long history and even its name: Brokar's task, named after Henri Brokar, who published publications about it in 1876 and 1885. Ramanujan mentioned it in 1913. Erdös suggested that there are no more solutions. Marius Overholt associated it with the abc hypothesis. Bruce Berndt and William Galway find that there are no solutions before$$10 9 . All this I learned from anarticle about the Brokar problem on Wikipedia. This article also mentions that solutions are called Brownian numbers [approx. transl.: the origin of the name is unknown, it is unclear whether they are associated with Robert Brown].

So I still have something to read.