Short shoulder matching

Published on December 08, 2017

Short shoulder matching

Original author: Brian Hayes
  • Transfer
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:

Tweet reads: 4! +1 = 25, a square number.  5! +1 = 121, a square number.  Another example?  Two more examples?

“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 that6 ! not suitable. Factorial6 ! - this1 × 2 × 3 × 4 × 5 × 6 = 720 ; adding1 , we get the number721 , which is not a square. (It is factorized as7 × 103. ) On the other hand,7 ! equally5040 , and adding1 , we will get5041 , which is equal71 2 . This gives us a very nice equation:

7 ! + 1 = 71 2

Continuing further, we find out that 8 ! + 1 ,9 ! + 1 and10 ! + 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 on1 less than square:

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

Armed with this tool, let's check n ! + 1 for everyonen from1 to100 . Here is what the program tells us:

4! + 1 = 5^2 = 25
5! + 1 = 11^2 = 121
7! + 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 meaningsn ! + 1 up ton = 100 onlyn = 4 ,n = 5 andn = 7 give squares of numbers. When I continued searching untiln = 1000 , I got exactly the same result. The same thing happened withn = 10000 andn = 100000 . It is worth mentioning that factorial100,000 is a fairly large number of456574 decimal places. At this point in the search, I began to run out of steam; moreover, I began to lose hope. When99993 sequential valuesn 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 ton = 500000 , the factorial of which contains2632341 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 valuesn ! which on1 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 forn > 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 thatn ! = m 2 . It turns out that this equation has only one solution, forn = 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 in36 = 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, factorizationn ! andn ! + 1 is completely different. But maybe there is some other propertyn ! + 1 , which conflicts with squareness. It may be somehow connected with congruence classes or with square remnants. From the definition of factorial, we know thatn ! divisible by all positive integers less than or equal ton , which means thatn ! + 1 cannot bedivisible by any of these numbers (except1 ). This observation excludes certain types of squares, namely those that have small primes in the factorization. But for everyonen > 4 square rootn ! far superiorn , therefore, there is enough space for larger divisors, as is the case with7 ! + 1 = 71 2 .

Here is another way worth exploring. The decimal representation of any large factorial ends with a line from0 created as works5 and2 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 of0 ends with a single1 . Can we find a way to prove that a number like this is never a square? Well, if the last digit would be different from1 ,4 or9 , 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 thatn ! + 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 bothersn ! + 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 with1 , 3 , 6 , 10 , 15 , 21 , ... , are given by the formulaT ( m ) = m ( m + 1 ) / 2 . If we look for factorials that are also triangular, we get1 ! = T ( 1 ) = 1 , then3 ! = T ( 3 ) = 6 and finally5 ! = T ( 15 ) = 120 . No more examples beforen = 100000 does not occur.

What about factorials that are on1 is less than a triangular number satisfying the equationn ! + 1 = T ( m ) ? I know the only such case:2 ! + 1 = 3 . Expanding my search a bit, I found thatn ! + 4 triangular forn 2 , 3 , 4 , after which again there are no matches until100,000 .

For another experiment, we can return to the squares of numbers and abandon factorials, replacing them with the ever-popular Fibonacci series1 , 1 , 2 , 3 , 5 , 8 , 13 , ... , defined by recursionF ( n ) = F ( n - 1 ) + F ( n - 2 ) , whereF ( 1 ) = F ( 2 ) = 1 . Since the 1960s it was knownthat1 and144 are the only positive integer numbers that are both Fibonacci numbers and squares of integers. Looking for the Fibonacci numbers that are on1 less than a square, I found out thatF ( 4 ) + 1 = 4 andF ( 6 ) + 1 = 9 , and there are no other cases beforeF ( 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 except1 up ton = 100,000 ; I do not know if anyone has proven that they do not exist. Search for cases in whichC ( n ) + 1 = m 2 , also does not give results, but there are several correspondences with low values ​​forC ( n ) + k = m 2 fork 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 propertyn ! + 1 , explaining why it never corresponds to squares (for large valuesn ), 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 whyn ! + 1 cannot be a prime. And indeed, forn 100 simple are nine valuesn ! + 1 . Extending the boundaries of the search ton 1000 , we will find seven more. Here is acomplete set of known numbersfor whichn ! + 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? Valuesn ! + 1 form an infinite sequence of integers distributed along all the number line, densely located near the beginning, but becoming extremely sparse with increasingn . Valuesm 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 asn ! 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 ism 2 - ( m - 1 ) 2 = 2 m - 1 . Now choose a random number from the intervalk and ask whethern ! + k = m 2 . Exactly one value must satisfy this condition.k , i.e., the probability of coincidence is1 / ( 2 m - 1 ) , or approximately1 / ( 2 n ! ). Insofar asn ! grows very fast, this probability instantly tends to zero with increasingn . In the chart below, this is indicated by a purple line. Notice that ton = 100 purple curve almost reached10 - 80 .

Plot of probability of coincidence of factorial and square, fibonacci and square, factorial and prime

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)/21.618. The factorial-squares curve is even sharper because the factorial function issuperexponential:n ! growing faster thanc n , for any constantc .

The blue curve fixing the probability of coincidences between factorials and primes has a completely different shape. In the surrounding arean ! the average distance between consecutive primes is approximately equallog n ! that grows a little faster than itselfn and much slower thann ! . The probability of a match between factorials and primes is approximately equal1 / 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 is1 / 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 is1 / 3 . Add the fourth ball, and the probability of black drops to1 / 4 . Continuing in the same way, we get that the probability of black onnth pull should be equalonen + 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 workone2 ×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 is0 ; this means that the probability of meeting black at least once is1 . ("Probability1 "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 stagen is equal2 n ; During this process, all but one of the balls will be white. Now the probability of never seeing a black ball is equalone2 ×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 magnituden . Nor does it seek to1 . 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. OnThe nth stage of the urn contains1 + 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 is1 - 0.2921426977 , or0.7078573023 . (No, this number is not1 / 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 stagen is equallog 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 for0 , until the additional probability that the black ball appears sooner or later should be equal to1 .

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; whenn tends to infinity, probability or tends to0 , or tends to1 . But obviously this is not so. In the factorial urn model, the probability of never seeing a black ball is neither equal to0 nor1 and is located somewhere near0.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 randomk from the corresponding range of values. What about the original problemn ! + 1 = m 2 ? In this case, there is no random variable, and therefore it makes no sense to perform many experiments for each valuen . The system is deterministic. For eachn factorialn 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 valuen ! and checking many random valuesk we can take a single valuek (namelyk = 1 ) and considern ! for many valuesn .

Is such an ergodic assumption reasoned? Not really. It is known that some distances betweenn ! andm 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 first100,000 valuesn ! . Distances are normalized in the interval( 0 , 1 ) and are classified into100 columns. Obvious signs of displacement are imperceptible. The calculation of the mean and standard deviation of the same100,000 relative distances result in values ​​within1 percent of those expected with a uniform random distribution. (Expected values ​​are equalμ = 1 / 2 andσ = 1 / 12 ).

relative distance of n!  from m ^ 2, in 100 bins, for n ranging from 2 to 100,000

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 valuesn ! + 1 equal to squares, approximately equal0.7078573023 . Thus, we should not be too surprised that three such cases are already known, namely, examples withn = 4 ,5 and7 . Now we can apply the same method to calculate the probability of finding at least one more case withn > 7 . Let's make the question more general: “Regardless of whether we saw squares among the firstC valuesn ! + 1 , what are the chances that we will see them after? ”To answer this question, we can simply remove the firstC elements from an endless product:

n=C+11-11 + 2 n !

At C = 7 answer is approximately equal0.0037 . AtC = 100 is approximately equal5.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 as10 - 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 that1 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 equationn 3 + 1 = m 2 are not so frequent. One low-value example is easy to find:2 3 + 1 = 3 2 , but when after8 and9 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 forn ! orF ( n ) . In the chart belowP ( n 3 + k = m 2 ) is the orange curve.

Plot of probability of coincidence of factorial and square, fibonacci and square, factorial and prime, with added curve for cubes and squares

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, except8 and9 .

But such a conjecture is completely false. This task has a very long history. In 1844, Eugene Catalan suggested that8 and9 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 before10 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.