This is a very strange mathematical conjecture, because its expression is very simple and easy to understand, and the form of the problem seems so attractive.
But even the top mathematician failed to give a proof! !
Don't try to solve this problem yourself!
Although I have issued a warning, you must still be confused by this question, because its expression is so simple , then is easy to understand , and the form of the question looks so attractive.
choose an integer arbitrarily, if it is even, divide it by two; if it is odd, multiply it by three and add one. For the newly generated number, we perform the previous operation on it, and so on.
If you keep doing this, you will definitely fall into a cycle . At least we guess it will be so.
Next, take 10 as an example to illustrate this problem:
10 is an even number, so we divide it by 2 and get 5; and because 5 is an odd number, multiply 3 by 5 and add 1 to get 16; 16 is an even number, 16 Divide by 2 to get 8. Then you get 4, then 2, and then 1. Because 1 is an odd number, 3 times 1 plus 1 is 4, finally enters the 4-2-1-4-2-1... cycle .
If we take 11 as an example, we can get the following process: 11-34-17-52-26-13-40-20-10-5-16-8-4-2-1-4-2-1.. .. In the end we still fall into the same cycle as . The "notorious" Koraz conjecture of
says that if you start with a positive integer, you will end up in a loop. Maybe you will try to solve it regardless of my warning: because it looks simple and easy to understand. In fact, most mathematicians have worked on this problem.
I was attracted to this conjecture when I first learned it in school. My friend and I spent a long time thinking about this question, but this did not give us an answer. The reason why the
Koraz conjecture is notorious is that even if you can prove that all the numbers you have seen meet this conjecture, then you cannot prove that it must be correct. Therefore, it is just a conjecture so far.
seems simple, but it is extremely difficult.
In order to understand the Koraz conjecture, we start with the following function:
You may remember the "piecewise function" taught in school: the above function contains a positive integer as an independent variable n, and there are two rules to operate on it, we need to choose one of the two rules according to the parity of n. The
function f represents the rule that we operate on n, for example: f(10)=10/2=5, f(5)=3*5+1=16. According to the operation of the function f on the input odd numbers, the Koraz conjecture is also called the 3n+1 conjecture.
Koraz conjecture deals with the "trajectory" of function f. The trajectory refers to if you calculate the function value from a positive integer, and then substitute the calculated value into the function to get the new function value. We call this operation the " iteration " of the function. We have calculated the trajectory of the function f when the input is 10:
f (10) = 10/2 = 5
f (5) = 3 × 5 + 1 = 16
f (16) = 16/2 = 8
f (8) = 8/ 2 = 4
A more convenient way to express the function trajectory is as follows:
10 5 16 8 4 2 1 4 2 1 …
At the end of the trajectory, we can see a cycle of 1 4 2 1.
Similarly, for 11 there are:
11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 4 ....
We are also caught in the same cycle. After trying other examples, we will find that the orbit will always end up in the loop 4 2 1 ….
The Koraz conjecture claims that z5Any positive integer of z will eventually pass through 1. Although no one can prove this conjecture, someone has already proved that any positive integer less than 2^68 conforms to the Koraz conjecture. So, if you want to find a counterexample, you have to look for an integer greater than 300000000000000000000.
is easy to prove whether a certain number conforms to the Kollaz conjecture: just calculate the corresponding trajectory until you get the number 1. But if you want to know why this conjecture is so difficult to prove, let us first study a slightly simpler function, g(n).
Function g is similar to f, but for odd numbers, function g just adds 1 to the number. Since functions f and g are different, the trajectory of numbers in function g is different from that in f. For example, the trajectories of 10 and 11 in g are:
10 5 6 3 4 2 1 2 1 2 …
11 12 6 3 4 2 1 2 1 2 …
You can see that the trajectory of 11 in g is faster and reaches 1 . Similarly, the trajectory of 27 in g also reaches 1.
27 28 14 7 8 4 2 1 2 …
In these examples, the trajectory in g will also fall into a loop, but it is more than the loop in f Simple:
2 1 2 1 ....
We can guess that the trajectory in g will eventually reach 1. I can call it the "Noraz" conjecture, but I still want to call it the n+1 conjecture. We will study it by examining the trajectories of more numbers. Even if we prove that many numbers satisfy this conjecture, we cannot conclude that all numbers satisfy this conjecture. Fortunately, Noraz’s conjecture can be proved by the following method:
First, we know that half of a positive integer is always less than the number itself . So if n is a positive even number, g(n) = n/2 If n is an odd number, g(n) = n + 1, the resulting number will become larger. But since n is an odd number, n+1 must be an even number, and the next number is (n+1)/2, so the track of an odd number is as follows: ... n + 1 (n+1)/2 ... can be seen (n+1)/2 = n/2 + 1/2. Because n/2 tell us that when the orbit in g reaches an odd number greater than 1, we can always obtain a smaller number for and after two steps. Now we can give the idea of proving Noraz's conjecture: at a certain point in the trajectory, no matter whether it is even or odd, then the subsequent points will always gradually become smaller, and eventually, the trajectory will reach 1. Then it gets stuck in a loop, just like we guessed. Where is the problem with ? Can be used similarly to prove the Koraz conjecture? Let us return to the original functional form. is like function g. Function f will make an even number smaller, and will also make an odd number even, and then halve the new even number. An odd-numbered orbit is as follows: ...n 3n + 1 (3n+1)/2... and this is where our strategy will fail. The difference between and the previous example is that (3n+1)/2 >n. The key to prove Noraz's conjecture is that the odd number will become smaller after being acted on by the function g twice, but this is not applicable in the Koraz conjecture. So our strategy failed. Isn’t Koraz’s conjecture wrong? After all, the number on the orbit seems to be increasing, so how can it slowly become 1? This is to examine what will happen next. What happens next will explain why Koraz’s conjecture is so difficult to prove: because we can’t determine whether (3n+1)/2 is odd or even . we know3n+1 is an even number. If 3n+1 is divisible by 4, then (3n+1)/2 is an even number, and the number on the track will become smaller. If 3n+1 is not divisible by 4, then (3n+1)/2 is an odd number, and then the number on the trajectory will become larger. We cannot predict what the next situation will be , so the method of proving Noraz’s conjecture fails here. However, this method is not useless. Because half of the integers are even numbers, (3n+1)/2 has a half chance of being even numbers, so the next number is (3n+1)/4. For n>1, (3n+1/)4 So in an average sense, all trajectories must reduce . Although this makes sense in the theory of probability, no one can fully prove the Koraz conjecture. still has a little progress... However, several mathematicians have proved that the Koraz conjecture " is almost always " correct. This means that they have proved that the number of numbers that have not been proven is negligible relative to the positive integers that they know satisfy the Koraz conjecture. In 1976, Riho Terras, an Estonian American mathematician, proved that after repeated application of the Koraz function, almost all numbers in would eventually be lower than the original value . As we have seen above, showing that the numbers on the trajectory will keep getting smaller is a way to prove that they will eventually reach 1. In 2019, the famous mathematician Tao Zhexuan improved this result. After Terras proved that the Koraz trajectory of almost all numbers n would eventually become smaller, Tao Zhexuan proved that for almost all numbers, the Koraz trajectory of n was ultimately much smaller: lower than n/2 and lower than √n , Lower than lnn. But Tao Zexuan said that this result is " is the closest to fully proving its work without actually solving it. " Despite this, this conjecture will continue to attract the attention of a large number of mathematicians and enthusiasts. So you can choose a number and try it. Remember, someone warned you: don't get caught in an endless loop. Here are a few small exercises for everyone slide up to see the answer 1. Prove that there are infinitely many numbers that can make Koulaz's trajectory pass through 1 . For example, we can easily notice: 24 23 22 2 1 … since the power of 2 You can write an infinite number, so obviously there are an infinite number of Kolas trajectories passing through 1. Swipe up to see the answer 2. The minimum number of operations for the Koalas trajectory of n to reach 1 is called "stop time". For example, the stop time of 10 is 6, and the stop time of 11 is 14. Find two numbers whose stop time is 5. is easy to notice that the stop time of 25 is 5, because 25242322 2 1 …. and the stop time of 24 is 4, so the stop time of the number from 24 to the outside is 5, such as 5 16 8 4 2 1 Can you think about any other ideas? slide up to see the answer 3. In a recent report, Tao Zhexuan mentioned a function similar to the Koraz function: . He proposed that in addition to cycles 1 2 1 2 1..., there are two other types of cycles, you can find them ? The other two cycles of are: 5 14 7 20 10 5 … 17 50 25 74 37 110 55 164 82 41 122 61 182 91 272 136 68 34 17 …. How did you find ?
