Short shoulder match
James Tanton throws away puzzles on number theory with the same generosity with which John D. Rockefeller handed out tenths. I already wrote about one of Tanton's tasks. After a few weeks, my attention was drawn to this tweet about factorials and squares and didn’t give me any rest:
“4! +1 = 25, square of number. 5! +1 = 121, is also a square number. Can you give another example? Two more examples? ”
With a pen and paper, it is easy to show that 6! does not fit. Factorial 6! - this 1 times2 times3 times4 times5 times6=$72 ; adding on 1 get a number 721 which is not a square. (It is factorized as 7 times103 .) On the other hand, 7! equally 5040 , and adding 1 , we'll get 5041 which is equal to 712 . This gives us a very nice equation:
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's a function on Julia that does the obvious work — calculating successive factorials and checking whether they are 1 less square:
')
Armed with this tool, let's check n!+1 for all n from 1 before 100 . Here is what the program tells us:
These are the same three cases that we have already discovered with a pen and paper - and there is nothing more in the list. In other words, among all the values 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 then got exactly the same result. Similar happened with n=$10,00 and n=$100,00 . It is worth mentioning that factorial 100,000 - quite a large number of 456574 decimal places. At this stage of the search, I began to run out of steam; moreover, I began to lose hope. When 99993 sequential values n it is not possible to get a single square, it is difficult to continue to hope that success can be expected around the corner. However, I continued to persist. I got to n=$500,00 whose factorial contains 2632341 decimal places. In the whole set, no more squares were found.
What can we learn from this evidence - or lack thereof? Are 4, 5 and 7 the only values n! which on 1 the square of an integer? Or somewhere on the number line there are still such cases, perhaps right after my interval? Can they be infinitely many? And if so, where are they? If not, then why?
To my taste, the most satisfactory way to resolve these issues would be to find some principle of the theory of numbers, which guarantees that n!+1 nem2 for n gt7 . I could not find such a principle, but in my dreams I can roughly imagine what the evidence might look like. Suppose we get rid of part of the formula " +1 ", and start searching for integers such that n!=m2 . It turns out that this equation has only one solution, with n=m=1 . Do not burden your laptop with the search for more solutions - there is simple evidence that they do not exist. In any square of an integer, all prime dividers must be present an even number of times, for example, as in 36=2 times2 times3 times3 . In factorial, at least one simple divisor — the largest — is always present only once. (If you don’t understand why, read Bertrand’s postulate / Chebyshev theorem .)
Of course, when we substitute " +1 "in the formula, then the whole chain of reasoning falls apart. In the general case, factoring n! and n!+1 completely different. But maybe there is some other property. n!+1 confronted with squareness. It can be somehow connected with classes of congruences or with square residues. From the definition of factorial, we know that n! divided by all positive integers less than or equal to n which means that n!+1 can not be divided into any of these numbers (except 1 ). This observation excludes certain types of squares, namely those that have small primes in the factorization. But for all n gt4 Square root n! far superior n therefore there is enough space for larger dividers, as is the case 7!+1=712 .
Here is another way to explore. The decimal representation of any large factorial ends with a string of 0 created as works 5 and 2 among the divisors of the number. In this way, n!+1 should look like
Where X denotes any decimal digit, and the next row of 0 ends only 1 . Can we find a way to prove that a number in this form is never a square? Well, if the last figure were different from 1 , 4 or 9 , the proof would be simple, but many squares end in ldots$0 , eg, 10201=101262001=2492 . If there is any algebraic consideration showing that n!+1 can not be a square, it is more subtle.
All of the above is fictional mathematics. I mixed a few ingredients that should turn into a tasty 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 prevents n!+1 be a square, except incredibility.
The pattern observed in the task n!+1=m2 - several matches among the smallest elements of sequences, and then not a single match in many thousands of elements - is not unique for factorials and squares. Other sequence pairs exhibit similar behavior. Triangular numbers starting with 1,3,6,10,15,21, ldots 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)=$12 . No more examples to n=$100,00 not found.
What about the factorials that 1 less than the triangular number satisfying the equation n!+1=T(m) ? I know the only such case: 2!+1=3 . By expanding the search a bit, I found that n!+4 triangular for n in2,3,4 then again there are no matches until 100,000 .
For another experiment, we can return to the squares of numbers and abandon the factorials, replacing them with the ever-popular Fibonacci series 1,1,2,3,5,8,13, ldots specified by recursion F(n)=F(n−1)+F(n−2) where F(1)=F(2)=1 . Since the 1960s, it was known that 1 and 144 - The only positive integers are numbers, which are both Fibonacci numbers and squares of integers. Looking for Fibonacci numbers that are on 1 less square I found out that F(4)+1=4 and F(6)+1=9 , and other cases do not occur until F(500,000) .
We can do the same with the numbers Catalan , 1,1,2,5,14,42,132 ldots , another one next to a huge fan club. I found out that among the numbers of Catalan there are no other squares, except 1 up to n=$100,00 ; I don't know if anyone has proven that they don't exist. Search for cases in which C(n)+1=m2 , also does not give results, but there are several correspondences with low values for C(n)+k=m2 at k in2,3,4 .
Finding similar behavior in all 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 matches squares (for large values n ), will we need to reinvent another mechanism for Fibonacci numbers and another one for Catalan numbers? Does it seem more convincing that behind all these observations lies the only common reason?
But this reason cannot be too general. This is not the case when you can take any two numeric sequences and expect to see the same pattern at their intersections. Consider factorials and prime numbers. By the very nature of factorials, none of them but 2! = 2, may not be a prime number, but there are no obvious reasons for n!+1 can not be a prime number. And indeed, for n le100 simple are nine values n!+1 . Expand your search to n le1000 , we will find seven more. Here is the complete set of known numbers for which n!+1 is simple:
With increasing n they are becoming increasingly rare, but there are no signs of a sharp limit, as in the cases considered earlier. Does this series continue endlessly? This seems like a logical hypothesis. (For more information about this sequence, including reference materials, see Chris Caldwell’s factorial prime page.)
My question is: can we perceive these curious patterns as pure coincidence? Meanings n!+1 form an infinite sequence of integers distributed over all the number line, densely located near the beginning, but becoming extremely sparse with increasing n . Meanings m2 form another infinite sequence, also with decreasing density, although not with such a sharp decline. Perhaps factorials coincide with the squares among the smallest integers, simply because these integers are not enough to “roam”, and some of them have to do double work. But in vast open spaces, the numerical straight factorial can wander for years — perhaps forever — without encountering 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; location on the number line looks like (m−1)2 ltn! ltm2 . The distance between the end points of this interval is m2−(m−1)2=2m−1 . Now choose a random number from the interval. k and ask if it's fair n!+k=m2 . This condition must satisfy exactly one value. k , that is, the probability of coincidence is 1/(2m−1) or approximately 1/(2 sqrtn!) . Insofar as sqrtn! grows very quickly, this probability instantly goes to zero with increasing n . The graph below shows this as a purple line. Notice that to n=100 the purple curve almost reached 10−80 .
The green curve represents the probability of a match between Fibonacci numbers and squares; the form is similar, however it “dives” from the “cliff” a bit later. The Fibonacci squares curve is approximately equal to the negative exponential function: the probability is proportional to phi− sqrtF(n) where phi=( sqrt5+1)/2 approx1.618 . The factorial-squares curve is even sharper because the factorial function is superexponential : n! growing faster than cn at any constant c .
The blue curve, fixing the probability of coincidence between factorials and prime numbers, has a completely different form. In the surrounding area n! average distance between consecutive prime numbers is approximately logn! that grows a little faster than itself n and much slower than n! . The probability of coincidence between factorials and prime numbers is approximately equal to 1/ logn! . The continuous blue curve corresponds to this smooth approximation. The blue dots scattered next to the line are probability values based on true distances between consecutive primes.
What can be done with these curves? Is it permissible to apply probability theory to these absolutely deterministic sequences of numbers? I don't know exactly. Before asking this question directly, I would 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 urns of Jacob Bernoulli, in which there is enough space to store an infinite number of ping-pong balls. Let's start with one black and one white ball in the urn, then we will pull the balls randomly. Obviously, the probability of choosing black is 1/2 . Put the selected ball back into the urn, and also add another white ball. Now there are three balls and only one of them is black, so the probability of black pulling is equal to 1/3 . Add the fourth ball, and the probability of black falls to 1/4 . Continuing in the same way, we get that black’s probability on n in the drawing should be equal frac1n+1 .
If we continue this procedure endlessly - always choose a random ball, return it back and add another white ball - what is the probability that we will see a black ball at least once? It will be easier to answer the consequence of this question - to calculate the probability of never seeing the black ball. This infinite work frac12 times frac23 times frac34 times frac45 ldots , or:
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 the black ball is equal 0 ; This means that the probability of meeting black is at least once 1 . ("Probability 1 "Is not exactly the same thing as" certainty ", but incredibly close.)
Let's now put another experiment. Let's start again with one black and one white balls, but after the first cycle of pulling-return we add two white balls, then four white, and so on, so that the total number of balls in the urn at the stage n equals 2n ; throughout this process, all but one of the balls will be white. Now the chance to never see a black ball is equal frac12 times frac34 times frac78 times frac1516 ldots , or:
This product does not tend to zero, regardless of the magnitude n . Nor does it seek to 1 . The product converges to a constant with an approximate value. 0.288788095 . It's weird, isn't it? Even with an endless series of pulling out of an urn, we cannot be sure whether a black ball will appear or not.
These two experiments with urns do not directly relate to any of the matching tasks described above; they simply illustrate the range of possible outcomes. But we can create a urn process that mimics the probabilistic approach to the problem of factorials and squares. On n the second stage urn contains 1+2 sqrtn! 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
This expression converges to a value approximately equal to 0.2921426977 . From this 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/ sqrt2 , although close to him.)
A process with an urn resembling a problem of factorials and primes gives a rather different result. Here is the number of balls in the urn on the stage n equally logn! , again with just one black ball. The infinite product that controls the total probability is
In numerical proof, it seems that this expression tends to zero as n to infinity (although I’m not 100% sure). If it really tends to 0 , before the additional probability that a black ball will appear sooner or later, must be equal to 1 .
Some of these results made me feel fooled, and even a bit annoyed. You can call me old-fashioned, but I always thought that an infinite number of dice should be enough to remove any doubt about whether a 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 it is obvious that it is not. In the factorial urn model, the probability of never seeing a black ball is equal to or 0 neither 1 and is 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 is naturally related to the randomized version of the factorial-squares problem, in which we look at n!+k=m2 and choose random k from the corresponding interval of values. What about the original problem n!+1=m2 ? In this case, there is no random variable, and therefore there is no point in performing a lot of 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 for a long period of time is analogous to observing many shorter chains. Suppose that factorials and squares are not related to their location on the number line — that when factorial is between two squares, the distance to the larger square can be considered a random variable and each possible distance has the same probability. If you stick to this assumption, instead of considering one value n! and checking a set of random values k we can take the only meaning k (namely k=1 ) and consider n! for a variety of values n .
Is this ergodic suggestion argued? Not really. It is known that some distances between n! and m2 more likely than others, and some distances are not possible at all. However, empirical evidence shows that such deviations should be minor. The graph below shows the distribution of the distances between the factorial and the next larger square for the first 100,000 values n! . Distances are normalized in the interval (0,1) and classified into 100 columns. Obvious signs of bias imperceptibly. Calculate the mean and standard deviation of the same 100,000 relative distances results in values within 1 percent of those expected with a uniform random distribution. (Expected values are equal m u = 1 / 2 and s i g m a = 1 / 12 .)
If such a probabilistic approach can be taken seriously, then I can make some numerical judgments about the prospects for 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 squares, approximately equal 0.7078573023 . Thus, we should not be too surprised that already three such cases are known, namely examples with n = 4 , five and 7 . Now we can apply the same method to calculate the probability of finding at least one more case with n g t 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 the infinite product:
With C = 7 answer is approximately equal0.0037 . With C = 100 is approximately equal to5.7 × 10 - 80 .We go down the sharp slope of the violet curve.
From a practical point of view, further searches for another factorial-square pair do not look promising as a waste of time and processor cycles. The probability of success quickly decreases to ridiculously small numbers, such as10 - 1,000,000 .And yet, from a mathematical point of view, the probability never disappears. Removing a finite number of terms from the front of an infinite product cannot change its convergence properties. If the original work converges to a non-zero value, the shortened version will also behave. Thus, we fell into a canyon of maximum disappointment, in which there is no realistic way to find a reward, but probabilities still tell us that it can exist.
I will complete this awkward essay with another example (a very advanced one). Suppose we apply probabilistic reasoning to the search for a cube that is1 is smaller than square. If we consider the exact correspondences between cubes and squares, then there are quite a lot of them - these are the sixth degrees:1 , 64 , 729 , ... . But whole solutions to the equation n 3 + 1 = m 2 not so frequent. One example with low values is easy to find:2 3 + 1 = 3 2 , but when aftereight 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 slower; their speed is polynomial, not exponential and not superexponential. As a result, the probability of finding a cube at a given distance from the square decreases much less dramatically than it does for
n ! or F ( n ) . On the chart below P ( n 3 + k = m 2 ) is an orange curve.
Notice that the orange curve lies right below the blue, which represents the probability that n ! is next to a prime number. The proximity of these two curves suggests that two tasks — factorials adjacent to prime numbers, cubes adjacent to squares — can belong to the same class. We already know that factorial-simple occur again and again, perhaps to infinity. This analogy leads us to a conjecture: perhaps the coincidence of cubes-squares is also unlimited. If we continue to observe, we will see many more, excepteight and 9 .
But such a guess is completely wrong. This task has a very long history. In 1844, Eugene Catalan suggested thateight and 9 are the only consecutive power values among integers; This assumption wasfinally provedin 2004 by Preda Mihaylescu. A special case of squares and cubes was decided by Euler 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 - the study of equations whose solutions must be integers. This area of mathematics is notorious for tasks that are easy to set, but difficult to solve. The Catalan hypothesis is one of the most famous examples, together with Fermat's great theorem. When 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 Ferm Andrew Wiles and Richard Taylor, circular fields in the proof of the Mihalescu Catalan hypothesis. 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 specific solution. And my expectations were fully met! In fact, the situation in my head has become even more confusing than at the beginning. The realization that even an endless series of experiments does not necessarily give 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.
Update:thanks to another hint of Tenton, I realized that this task has a long history and even a name: the problem of Brocard, by the name of Henri Brocard, who published publications about her in 1876 and 1885. Ramanujan mentioned it in 1913. Erdös suggested that there are no more solutions. Marius Overholt connected it with the abc-hypothesis. Bruce Berndt and William Galway found out that there is no solution before10 9 .All this I learned from an article about the problem of Brocard on Wikipedia . This article also mentions that the solutions are called Brownian numbers [approx. Per .: the origin of the name is unknown, it is unclear whether they are associated with Robert Brown].
So I still have something to read.
“4! +1 = 25, square of number. 5! +1 = 121, is also a square number. Can you give another example? Two more examples? ”
With a pen and paper, it is easy to show that 6! does not fit. Factorial 6! - this 1 times2 times3 times4 times5 times6=$72 ; adding on 1 get a number 721 which is not a square. (It is factorized as 7 times103 .) On the other hand, 7! equally 5040 , and adding 1 , we'll get 5041 which is equal to 712 . This gives us a very nice equation:
7!+1=712
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's a function on Julia that does the obvious work — calculating successive factorials and checking whether they are 1 less 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) end end println(" , !") end Armed with this tool, let's check n!+1 for all n from 1 before 100 . Here is what the program tells us:
search_fac_sqr(100) 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 more in the list. In other words, among all the values 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 then got exactly the same result. Similar happened with n=$10,00 and n=$100,00 . It is worth mentioning that factorial 100,000 - quite a large number of 456574 decimal places. At this stage of the search, I began to run out of steam; moreover, I began to lose hope. When 99993 sequential values n it is not possible to get a single square, it is difficult to continue to hope that success can be expected around the corner. However, I continued to persist. I got to n=$500,00 whose factorial contains 2632341 decimal places. In the whole set, no more squares were found.
What can we learn from this evidence - or lack thereof? Are 4, 5 and 7 the only values n! which on 1 the square of an integer? Or somewhere on the number line there are still such cases, perhaps right after my interval? Can they be infinitely many? And if so, where are they? If not, then why?
To my taste, the most satisfactory way to resolve these issues would be to find some principle of the theory of numbers, which guarantees that n!+1 nem2 for n gt7 . I could not find such a principle, but in my dreams I can roughly imagine what the evidence might look like. Suppose we get rid of part of the formula " +1 ", and start searching for integers such that n!=m2 . It turns out that this equation has only one solution, with n=m=1 . Do not burden your laptop with the search for more solutions - there is simple evidence that they do not exist. In any square of an integer, all prime dividers must be present an even number of times, for example, as in 36=2 times2 times3 times3 . In factorial, at least one simple divisor — the largest — is always present only once. (If you don’t understand why, read Bertrand’s postulate / Chebyshev theorem .)
Of course, when we substitute " +1 "in the formula, then the whole chain of reasoning falls apart. In the general case, factoring n! and n!+1 completely different. But maybe there is some other property. n!+1 confronted with squareness. It can be somehow connected with classes of congruences or with square residues. From the definition of factorial, we know that n! divided by all positive integers less than or equal to n which means that n!+1 can not be divided into any of these numbers (except 1 ). This observation excludes certain types of squares, namely those that have small primes in the factorization. But for all n gt4 Square root n! far superior n therefore there is enough space for larger dividers, as is the case 7!+1=712 .
Here is another way to explore. The decimal representation of any large factorial ends with a string of 0 created as works 5 and 2 among the divisors of the number. In this way, n!+1 should look like
XXXXX ldotsXXXXX00000 ldots$0000
Where X denotes any decimal digit, and the next row of 0 ends only 1 . Can we find a way to prove that a number in this form is never a square? Well, if the last figure were different from 1 , 4 or 9 , the proof would be simple, but many squares end in ldots$0 , eg, 10201=101262001=2492 . If there is any algebraic consideration showing that n!+1 can not be a square, it is more subtle.
All of the above is fictional mathematics. I mixed a few ingredients that should turn into a tasty 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 prevents n!+1 be a square, except incredibility.
The pattern observed in the task n!+1=m2 - several matches among the smallest elements of sequences, and then not a single match in many thousands of elements - is not unique for factorials and squares. Other sequence pairs exhibit similar behavior. Triangular numbers starting with 1,3,6,10,15,21, ldots 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)=$12 . No more examples to n=$100,00 not found.
What about the factorials that 1 less than the triangular number satisfying the equation n!+1=T(m) ? I know the only such case: 2!+1=3 . By expanding the search a bit, I found that n!+4 triangular for n in2,3,4 then again there are no matches until 100,000 .
For another experiment, we can return to the squares of numbers and abandon the factorials, replacing them with the ever-popular Fibonacci series 1,1,2,3,5,8,13, ldots specified by recursion F(n)=F(n−1)+F(n−2) where F(1)=F(2)=1 . Since the 1960s, it was known that 1 and 144 - The only positive integers are numbers, which are both Fibonacci numbers and squares of integers. Looking for Fibonacci numbers that are on 1 less square I found out that F(4)+1=4 and F(6)+1=9 , and other cases do not occur until F(500,000) .
We can do the same with the numbers Catalan , 1,1,2,5,14,42,132 ldots , another one next to a huge fan club. I found out that among the numbers of Catalan there are no other squares, except 1 up to n=$100,00 ; I don't know if anyone has proven that they don't exist. Search for cases in which C(n)+1=m2 , also does not give results, but there are several correspondences with low values for C(n)+k=m2 at k in2,3,4 .
Finding similar behavior in all 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 matches squares (for large values n ), will we need to reinvent another mechanism for Fibonacci numbers and another one for Catalan numbers? Does it seem more convincing that behind all these observations lies the only common reason?
But this reason cannot be too general. This is not the case when you can take any two numeric sequences and expect to see the same pattern at their intersections. Consider factorials and prime numbers. By the very nature of factorials, none of them but 2! = 2, may not be a prime number, but there are no obvious reasons for n!+1 can not be a prime number. And indeed, for n le100 simple are nine values n!+1 . Expand your search to n le1000 , we will find seven more. Here is the complete set of known numbers for 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,$15020
With increasing n they are becoming increasingly rare, but there are no signs of a sharp limit, as in the cases considered earlier. Does this series continue endlessly? This seems like a logical hypothesis. (For more information about this sequence, including reference materials, see Chris Caldwell’s factorial prime page.)
My question is: can we perceive these curious patterns as pure coincidence? Meanings n!+1 form an infinite sequence of integers distributed over all the number line, densely located near the beginning, but becoming extremely sparse with increasing n . Meanings m2 form another infinite sequence, also with decreasing density, although not with such a sharp decline. Perhaps factorials coincide with the squares among the smallest integers, simply because these integers are not enough to “roam”, and some of them have to do double work. But in vast open spaces, the numerical straight factorial can wander for years — perhaps forever — without encountering 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; location on the number line looks like (m−1)2 ltn! ltm2 . The distance between the end points of this interval is m2−(m−1)2=2m−1 . Now choose a random number from the interval. k and ask if it's fair n!+k=m2 . This condition must satisfy exactly one value. k , that is, the probability of coincidence is 1/(2m−1) or approximately 1/(2 sqrtn!) . Insofar as sqrtn! grows very quickly, this probability instantly goes to zero with increasing n . The graph below shows this as a purple line. Notice that to n=100 the purple curve almost reached 10−80 .
The green curve represents the probability of a match between Fibonacci numbers and squares; the form is similar, however it “dives” from the “cliff” a bit later. The Fibonacci squares curve is approximately equal to the negative exponential function: the probability is proportional to phi− sqrtF(n) where phi=( sqrt5+1)/2 approx1.618 . The factorial-squares curve is even sharper because the factorial function is superexponential : n! growing faster than cn at any constant c .
The blue curve, fixing the probability of coincidence between factorials and prime numbers, has a completely different form. In the surrounding area n! average distance between consecutive prime numbers is approximately logn! that grows a little faster than itself n and much slower than n! . The probability of coincidence between factorials and prime numbers is approximately equal to 1/ logn! . The continuous blue curve corresponds to this smooth approximation. The blue dots scattered next to the line are probability values based on true distances between consecutive primes.
What can be done with these curves? Is it permissible to apply probability theory to these absolutely deterministic sequences of numbers? I don't know exactly. Before asking this question directly, I would 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 urns of Jacob Bernoulli, in which there is enough space to store an infinite number of ping-pong balls. Let's start with one black and one white ball in the urn, then we will pull the balls randomly. Obviously, the probability of choosing black is 1/2 . Put the selected ball back into the urn, and also add another white ball. Now there are three balls and only one of them is black, so the probability of black pulling is equal to 1/3 . Add the fourth ball, and the probability of black falls to 1/4 . Continuing in the same way, we get that black’s probability on n in the drawing should be equal frac1n+1 .
If we continue this procedure endlessly - always choose a random ball, return it back and add another white ball - what is the probability that we will see a black ball at least once? It will be easier to answer the consequence of this question - to calculate the probability of never seeing the black ball. This infinite work frac12 times frac23 times frac34 times frac45 ldots , or:
P( textrmneverblack)= prod inftyn=11− frac1n+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 the black ball is equal 0 ; This means that the probability of meeting black is at least once 1 . ("Probability 1 "Is not exactly the same thing as" certainty ", but incredibly close.)
Let's now put another experiment. Let's start again with one black and one white balls, but after the first cycle of pulling-return we add two white balls, then four white, and so on, so that the total number of balls in the urn at the stage n equals 2n ; throughout this process, all but one of the balls will be white. Now the chance to never see a black ball is equal frac12 times frac34 times frac78 times frac1516 ldots , or:
P( textrmneverblack)= prod inftyn=11− frac12nP( textrmneverblack)= prod inftyn=11− frac12n
This product does not tend to zero, regardless of the magnitude n . Nor does it seek to 1 . The product converges to a constant with an approximate value. 0.288788095 . It's weird, isn't it? Even with an endless series of pulling out of an urn, we cannot be sure whether a black ball will appear or not.
These two experiments with urns do not directly relate to any of the matching tasks described above; they simply illustrate the range of possible outcomes. But we can create a urn process that mimics the probabilistic approach to the problem of factorials and squares. On n the second stage urn contains 1+2 sqrtn! 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
prod inftyn=11− frac11+2 sqrtn!
This expression converges to a value approximately equal to 0.2921426977 . From this 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/ sqrt2 , although close to him.)
A process with an urn resembling a problem of factorials and primes gives a rather different result. Here is the number of balls in the urn on the stage n equally logn! , again with just one black ball. The infinite product that controls the total probability is
prod inftyn=21− frac1 logn!
In numerical proof, it seems that this expression tends to zero as n to infinity (although I’m not 100% sure). If it really tends to 0 , before the additional probability that a black ball will appear sooner or later, must be equal to 1 .
Some of these results made me feel fooled, and even a bit annoyed. You can call me old-fashioned, but I always thought that an infinite number of dice should be enough to remove any doubt about whether a 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 it is obvious that it is not. In the factorial urn model, the probability of never seeing a black ball is equal to or 0 neither 1 and is 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 is naturally related to the randomized version of the factorial-squares problem, in which we look at n!+k=m2 and choose random k from the corresponding interval of values. What about the original problem n!+1=m2 ? In this case, there is no random variable, and therefore there is no point in performing a lot of 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 for a long period of time is analogous to observing many shorter chains. Suppose that factorials and squares are not related to their location on the number line — that when factorial is between two squares, the distance to the larger square can be considered a random variable and each possible distance has the same probability. If you stick to this assumption, instead of considering one value n! and checking a set of random values k we can take the only meaning k (namely k=1 ) and consider n! for a variety of values n .
Is this ergodic suggestion argued? Not really. It is known that some distances between n! and m2 more likely than others, and some distances are not possible at all. However, empirical evidence shows that such deviations should be minor. The graph below shows the distribution of the distances between the factorial and the next larger square for the first 100,000 values n! . Distances are normalized in the interval (0,1) and classified into 100 columns. Obvious signs of bias imperceptibly. Calculate the mean and standard deviation of the same 100,000 relative distances results in values within 1 percent of those expected with a uniform random distribution. (Expected values are equal m u = 1 / 2 and s i g m a = 1 / 12 .)
If such a probabilistic approach can be taken seriously, then I can make some numerical judgments about the prospects for 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 squares, approximately equal 0.7078573023 . Thus, we should not be too surprised that already three such cases are known, namely examples with n = 4 , five and 7 . Now we can apply the same method to calculate the probability of finding at least one more case with n g t 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 the infinite product:
∞ ∏ n=C+11-11 + 2 √n !
With C = 7 answer is approximately equal0.0037 . With C = 100 is approximately equal to5.7 × 10 - 80 .We go down the sharp slope of the violet curve.
From a practical point of view, further searches for another factorial-square pair do not look promising as a waste of time and processor cycles. The probability of success quickly decreases to ridiculously small numbers, such as10 - 1,000,000 .And yet, from a mathematical point of view, the probability never disappears. Removing a finite number of terms from the front of an infinite product cannot change its convergence properties. If the original work converges to a non-zero value, the shortened version will also behave. Thus, we fell into a canyon of maximum disappointment, in which there is no realistic way to find a reward, but probabilities still tell us that it can exist.
I will complete this awkward essay with another example (a very advanced one). Suppose we apply probabilistic reasoning to the search for a cube that is1 is smaller than square. If we consider the exact correspondences between cubes and squares, then there are quite a lot of them - these are the sixth degrees:1 , 64 , 729 , ... . But whole solutions to the equation n 3 + 1 = m 2 not so frequent. One example with low values is easy to find:2 3 + 1 = 3 2 , but when aftereight 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 slower; their speed is polynomial, not exponential and not superexponential. As a result, the probability of finding a cube at a given distance from the square decreases much less dramatically than it does for
n ! or F ( n ) . On the chart below P ( n 3 + k = m 2 ) is an orange curve.
Notice that the orange curve lies right below the blue, which represents the probability that n ! is next to a prime number. The proximity of these two curves suggests that two tasks — factorials adjacent to prime numbers, cubes adjacent to squares — can belong to the same class. We already know that factorial-simple occur again and again, perhaps to infinity. This analogy leads us to a conjecture: perhaps the coincidence of cubes-squares is also unlimited. If we continue to observe, we will see many more, excepteight and 9 .
But such a guess is completely wrong. This task has a very long history. In 1844, Eugene Catalan suggested thateight and 9 are the only consecutive power values among integers; This assumption wasfinally provedin 2004 by Preda Mihaylescu. A special case of squares and cubes was decided by Euler 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 - the study of equations whose solutions must be integers. This area of mathematics is notorious for tasks that are easy to set, but difficult to solve. The Catalan hypothesis is one of the most famous examples, together with Fermat's great theorem. When 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 Ferm Andrew Wiles and Richard Taylor, circular fields in the proof of the Mihalescu Catalan hypothesis. 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 specific solution. And my expectations were fully met! In fact, the situation in my head has become even more confusing than at the beginning. The realization that even an endless series of experiments does not necessarily give 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.
Update:thanks to another hint of Tenton, I realized that this task has a long history and even a name: the problem of Brocard, by the name of Henri Brocard, who published publications about her in 1876 and 1885. Ramanujan mentioned it in 1913. Erdös suggested that there are no more solutions. Marius Overholt connected it with the abc-hypothesis. Bruce Berndt and William Galway found out that there is no solution before10 9 .All this I learned from an article about the problem of Brocard on Wikipedia . This article also mentions that the solutions are called Brownian numbers [approx. Per .: the origin of the name is unknown, it is unclear whether they are associated with Robert Brown].
So I still have something to read.
Source: https://habr.com/ru/post/344052/
All Articles