For any natural number a,
(1) A. If a is even, divide by 2.
B If a is odd, multiply it by 3 and add 1.
Write down the number as B.
(2) Replace A with B to perform the operation of (1) again.
After a few steps, the number is 1.
This conjecture is called the corner-valley conjecture, and there is no counterexample or proof at present. However, many people try to prove this problem:
[Edit this paragraph] A wrong proof
The Simplest Proof Method of Corner Valley (3n+ 1)
Because any even number can become 2 a or odd number multiplied by 2 b, the former must be 1 after being divided by 2, because they only have a prime factor of 2. The latter can only be left with odd numbers, and we can put even numbers aside.
Now there are only odd numbers left.
Let's assume an odd number m, which becomes 3m+ 1 after operation. If this conjecture is wrong, then there is (3m+ 1)/2 c = m, and m is not equal to 1. Let's try:
When c = 1, 3m+ 1 = 2m,,, m =- 1, if not, discard it;
When c = 2, 3m+ 1 = 4m,,, m =1; Do not meet the requirements, to be scrapped;
When c = 3, 3m+ 1 = 8m,,, m = 0.2, which does not meet the requirements, shall be scrapped;
When c = 4, 3m+ 1 = 16m,,, m =113, otherwise it will be discarded;
……………………
It can be seen that the number that can overturn the angular ancient conjecture is only in the range of 1 or below, so no number can overturn this conjecture, so this conjecture is correct.
[Edit this paragraph] Error analysis
I don't agree with the following so-called proof:
"We assume an odd number m, and when he performs an operation, it becomes 3m+ 1. If this conjecture is wrong, then there is (3m+ 1)/2 c = m, and m is not equal to 1. Let's try:
When c = 1, 3m+ 1 = 2m,,, m =- 1, if not, discard it;
When c = 2, 3m+ 1 = 4m,,, m =1; Do not meet the requirements, to be scrapped;
When c = 3, 3m+ 1 = 8m,,, m = 0.2, which does not meet the requirements, shall be scrapped;
When c = 4, 3m+ 1 = 16m,,, m =113, otherwise it will be discarded;
. . . . . .
It can be seen that the number that can overturn the angular ancient conjecture is only in the range of 1 or below, so no number can overturn this conjecture, so this conjecture is correct. "
You should know that the equation (3m+ 1)/2 c = m is different. Although both M's are odd numbers, this M is not another M! The above is nothing more than saying that an odd number multiplied by 3 plus 1 must be divisible by the n power of 2. Of course, how big n is depends on the actual situation. However, this statement is absolutely wrong! You can try if you don't believe me. If you substitute any odd number m on the left, most of the m on the right is different from that on the left. This proof is also obviously inconsistent. An odd number m was assumed, but the results of M = 0.2 and m =113 were obtained later. Are these so-called odd numbers? You can't even tell two M's apart, let alone prove it. Don't make such low-level mistakes again, it is true to be down to earth.
A Generalization of Corner-Valley Conjecture
Corner valley conjecture is also called Syracuse conjecture. One of them is the Cratz issue, which is briefly discussed below:
Since 1950s, such a strange and interesting mathematical problem has been widely circulated in the international mathematics field: given a natural number X at will, if it is even, it will be converted into x/2, if it is odd, it will be converted into 3x+ 1. After that, we will continue to transform the number. For example, if x=52, we can get 26, 13, 40 in turn.
(4,2, 1). Try other natural numbers and you will get the same result. This is called the Syracuse conjecture.
The above transformation is actually an iteration of the following function.
{x/2 (x is an even number)
c(x)= 1
3x+ 1 (x is an odd number)
The question is, starting from any natural number, can we finally get the cycle (4,2, 1) or equivalently, 1 through finite iterations of function C? It is said that Cratz spoke at an international congress of mathematicians held in 1950, so many people called it the Cratz problem. But later, many people found the same problem independently, so since then, perhaps to avoid the controversy over the ownership of the problem, many documents have called it 3x+ 1 problem.
The attraction of Cratz problem is that once the power of 2 appears in the process of C iteration, the problem will be solved, and there are infinitely many powers of 2. People think that as long as the iterative process lasts long enough, the problem will be solved in a positive form. It is this belief that leads to the upsurge of "3x+ 1 problem" wherever the problem goes, and both universities and research institutions are involved in this problem to varying degrees.
Tami Shenfu of the University of Tokyo in Japan tested the natural number of 240, which is about 1 1000 billion. 1992, G.T. Levins and M. Vermeulen have tested the natural number of 5.6 *10/3. Problems that even primary school students can understand are difficult for many great mathematicians in the 20th century. The famous scholar R.K.Guy even titled it "Don't try to solve these problems" when introducing this world problem. After decades of exploration and research, people seem to accept the statement of the great mathematician P Erdos: "Mathematics is not mature enough to solve such problems!" It is suggested that the 3x+ 1 problem is the next Fermat problem.
The following is my preliminary research result on the Cratz issue, but I found a little rule, which is far from being solved.
Cratz's proposition: Let n∈N, and
F(n)= n/2 (if n is even) or 3n+ 1 (if n is odd).
F 1(n) means f (n), F2 (n) = f (n), ... fk (n) = f (... female college students ...).
Then there is a finite positive integer m∈N, so fm(n)= 1. (hereinafter, n/2 is called even transformation, 3n+ 1 is called odd transformation, and the even transformation is called full transformation first).
The Proof of Cratz's Proposition
Lemma 1: If n=2m, then fm(n)= 1 (m∈N).
It is proved that the proposition holds when m= 1, f(n)=f(2)=2/2= 1, and if m=k, then fk+1(n) = f.
=f(2)=2/2= 1。
Lemma 2: If n =1+4+42+43+...+4k = (4k+1-1)/(4-1) (k ∈ n), then there is f (n).
Prove: Prove obvious, omit.
Lemma 3: If n = 2m (4k+1-1)/(4-1) (m ∈ n), there is fm+2k+3(n)= 1.
Proof: ellipsis.
Theorem 1: the set O={X|X=2k- 1, k∈N} is closed for the transformation f(X).
It is proved that for any natural number n, if n=2m, FM (n) =1; For n=2k, after several even transformations, it will inevitably become an odd number. Let's consider the case of odd number, that is, the case of set O. For odd number, the odd number must be transformed first, and then the even number must be transformed, so for odd number, the full transformation must be carried out.
k 1 2 3 4 5 6 7 8 9 1 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 20 2 1 22 23 24 25 26 27 28
0 2k- 1 1 3 5 7 9 1 1 1 3 1 5 1 9 2 1 23 25 27 29 3 1 33 35 37 39 4 1 43 45 47 49 5 1 53 53
1 3k- 1 2 5 8 1 1 1 4 1 7 20 23 26 29 32 35 38 4 1 44 47 50 53 56 59 62 65 68 7 1 74 77 80 83 86 89 92 95 98 106538
2 3k-2 1 4 7 10 13 16 19 22 25 28 3 1 34 37 40 43 46 49 52 55 58 6 1 64 67 70 73 76
3 3k- 1 2 5 8 1 1 14 17 20 23 26 29 32 35 38
4 3k-2 1 4 7 10 13 16 19
5 3k- 1 2 5 8
6 3k-2 1 4
7 3k- 1 2
8 3k-2 1
The first line (2k- 1) is transformed into the second line (3 (2k- 1)/2 = 3k- 1, which is actually equal to the first line plus a k, where the odd number is 5, 1 1.
Theorem 2: Any odd natural number will become 1 after several transformations.
Prove:
We can see that odd numbers are converted into 3k- 1 type numbers, half of 3k- 1 type odd numbers are still converted into 3k- 1 type odd numbers, half of other 3k- 1 type even numbers are converted into 3k-2 type odd numbers, and 3k-2 type odd numbers are converted into 3k-/kloc-0.
Next, we only study the properties of odd numbers after full transformation, because other even numbers will return to the ranks of odd numbers after several even transformations.
First of all, we prove that after several complete transformations, odd numbers will inevitably become even numbers at a certain step.
Let 2a0- 1 be the odd number we want to study, and it will become 3a0- 1 after complete transformation. Let it be odd and equal to 2a 1- 1, and 2a 1- 1 becomes 3a 1-65438 after full transformation. 3A2- 1 = 2A3- 1, ... 3AK- 1 = 2AK- 1, so A 1 = (3/2) A0, A2 = (3/2).
So finally ak=(3/2)ka0. To make ak an integer, A0 = 2kn, and (n is an odd number). So ak=3kn. After many complete transformations from 2a0 to 1, the process is as follows:
2k+ 1n- 1->； 3 * 2kn- 1->； 32 * 2k- 1n- 1->； 33 * 2k-2n- 1->； ...-& gt； 3k+ 1n- 1 (even number).
Then we prove that the odd number that becomes even after complete transformation must be greater than the odd number that is obtained after several even transformations.
Let 3k+ 1n- 1=2mh (h is an odd number), and we will prove that h < 2*3kn- 1:
h =(2 * 3kn- 1+3kn)/2m & lt； 2*3kn- 1, so that A = 3kn, B = 2m- 1, there is 2ab >；; A+b, this is obvious.
Definition: In the following, we will call the above process of transforming from an odd number to another odd number and then to a continuous even number a transformation chain.
Then we prove that the odd number obtained by a transformation chain cannot be any intermediate result in the transformation chain, including the first odd number.
If B(n) represents the number of transformations of an odd number n and m is the other odd numbers encountered for the first time after the transformation of n, then there are
Theorem 3: B(n)=k+ 1+B(m), where k is a nonnegative integer satisfying 3n+ 1=2km.
Proof: N is transformed into odd M by odd transformation and K-even transformation, and it is proved.
For example, b (15) = 2+b (23) = 2+2+b (35) = 2+2+b (53) = 2+2+5+1+b (5) = 2+2.
Primitive craton
In 1930s, when Cratz was still in college, influenced by some famous mathematicians, he became interested in number theory functions, so he studied the iteration of functions.
In the notebook of July 1932, he studied such a function:
F(x)= 2x/3 (if x is divisible by 3 or (4x- 1)/3 (if x is divisible by 3, 1) or (4x+ 1)/3 (if x is divisible by 3, 2).
Then f (1) = 1, f (2) = 3, f (3) = 2, f (4) = 5, f (5) = 7, f (6) = 4, f (7) = 9, f (8) =
1 2 3 4 5 6 7 8 9 ...
1 3 2 5 7 4 9 1 1 6 ...
Therefore, it is observed that the F iteration with x = 2,3 produces cycles (2,3).
F-iterative generation cycle (5, 7, 9, 6, 4) with x=4, 5, 6, 7, 9.
The next step is to iterate x=8. Cratz is in trouble here. He is not sure whether this iteration will form a cycle, nor does he know whether iterating all natural numbers will produce other cycles except the above two cycles. Later generations will call this issue the original Cratz issue. Now people are more interested in its inverse problem:
G(x)= 3x/2 (if x is an even number) or (3x+ 1)/4 (if x is divided by 4, 1) or (3x- 1)/4 (if x is divided by 4, 3).
It is not difficult to prove that G(x) is exactly the inverse of the original Cratz function F(x). What will be the result of iteration for any positive integer x and g?
After calculation, the following four cycles are obtained:
( 1),(2,3),(4,6,9,7,5),(44,66,99,74, 1 1 1,83,62,93,70, 105,79,59).
Because G iteration and F iteration are reciprocal, we know that F iteration should also have cycles (59, 79, 105, 70, 93, 62, 83,1,74, 99, 66, 44).
Can there be other loops in G iteration? In order to find other cycles, people thought of the following ingenious methods:
Because of G iteration, the last term is 3/2 (when the current term is even) or about 3/4 (when the current term is odd) of the previous term. For example, if there is a loop in the G iteration, the T term at of the iteration is repeated with the S term as (t).
as/as- 1，as- 1/as-2，...at+ 1/at
Or equal to 3/2, or close to 3/22, so
1 = as/at = as/as- 1 * as- 1/as-2 *...at+ 1/at≈3m/2n
Where m = s-t, m
That is 2n≈3m.
log22n≈log23m
So n/m≈log23
That is to say, in order to find out the repeated items (that is, there are cycles), the asymptotic score n/m of log23 is required, and m may be the number of numbers contained in a cycle, that is, the length of the cycle.
After log23 is expanded into a continued fraction, you can get the following progressive scores with different defects:
log23≈2/ 1，3/2，8/5， 19/ 12，65/4 1，84/53，485/306， 1054/665，24727/ 1560 1， ...
The asymptotic score of 2/ 1 means 3 1≈22, and the period length should be 1. Actually, there is a cycle with the length of 1 (1).
The asymptotic fraction of 3/2 means 32≈23, and the cycle length should be 2. Actually, there is only one circle (2, 3) of length 2.
The asymptotic score of 8/5 means 35≈28, and the cycle length should be 5. In fact, there are only cycles of length 5 (4, 6, 9, 7, 5).
The asymptotic score of 19/ 12 indicates that 3 12≈2 19 and the period length should be 12. In fact, there is only a period (44, 66, ... 59) with a length of 12.
The consistency between the denominators of these four progressive fractions and the actual cycle length gives people some inspiration and confidence, prompting people to continue to consider whether there is a cycle with the length of 4 1, 53,306,665, 1560 1 ... Unfortunately, it has been proved that the length is 4 1. Then, will there be a cycle with the length of 665, 1560 1? ...
What cycles can F iteration and G iteration have? People are trying to explore!
[Edit this paragraph] The depth expansion of the corner and valley conjecture
Given a positive integer n, if n is divisible by a, it becomes n/a, and if it is divisible, it is multiplied by b plus c (that is, bn+c). Repeat this operation, after a limited number of steps, can you definitely get D? There are only three answers to this question: 1, not necessarily 2, not necessarily 3, not necessarily all.
The following is all about a certain capital.
A = B = C = D = M。
Two a=m b= 1 c=- 1 d=0.
Three a=m b=c=d= 1
Four A = two B = two M- 1 C =- 1 D = 1
Above (m> 1)
Five a = 2 b = 2m-1c =1d =1
6 A = 2 B = C = D = 2M- 1
M above is an arbitrary natural number.
The simplest example:
a=b=c=d=2
a=2 b= 1 c= 1 d= 1
a=2 b= 1 c=- 1 d=0
There are only five original questions. When m=2, it is said that many people in China will prove that the original problem is only a very small part.
All the above data are true, and there is not a counterexample. This question is very short, but it implies very rich mathematical ideas ... there are many things to be used. Those theorems and formulas are perfect and can express very common mathematical laws. This is a mathematical problem, not a guess. This topic focuses on cultivating students' independent thinking ability and reverse thinking. ...
Actually, this question is very simple.
I don't know if this is a holistic approach.
The first step in the overall proof of the above situation:
Firstly, a 2 yuan function is constructed, which reveals a secret: all natural numbers divisible by A are converted into natural numbers f(x, y) that are not divisible by A..
Five a = 2 b = 2m-1c =1d =1
Decomposition of natural numbers by mathematical induction and division ... Prove:
(2^(mn)- 1)/(2^n- 1)=e
When m and n are natural numbers, e is odd.
m= 1 A 1=( 1)
m=2 A2=( 1，5)
m=3 A3=( 1，9， 1 1)
m=4 A4=( 1， 17， 19，23)
m=5 A5=( 1，33，35，37，39)
m=6 A6=( 1，65，67，7 1，73，79)
...
...
...
All terms in the general term formula of the combined infinite sequence A () cannot be divisible by the m power of 2-1.
This combination sequence is very simple, just the first item of countless arithmetic progression. ....