Collatz Conjecture Proof
Cody Dianopoulos merlincody@gmail.com Kshitij Kulkarni kkulkarni1997@gmail.com
February 17, 2013
Abstract The Collatz function of a positive integer n is given by n/2 if n is even and 3n + 1 if n is odd. Lothar Collatz proposed in 1937 that repetitive iterations of this function, for any initial number n, will end as 1. For example, starting with n = 6, the iterations of the function are 6 3 10 5168421. To prove the Collatz Conjecture, the Collatz function is examined for the binary representations of n. As opposed to popular trains of thought, a new perspective is introduced viewing the Collatz function as a series of string transformations as opposed to integer transformations. Algorithms are then created to iterate the Collatz function in binary as a string operations, which yield the generalisation that every starting number n can be reduced to 1 through repeated iteration of the Collatz function.
Contents
1 Algorithms 1.1 n/2 . . . . . . . . . 1.2 n/2 (iteratively) . . 1.3 3n+1 . . . . . . . . 1.4 Collatz Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 3 4 6
1
1.1
Algorithms
n/2
Dividing by 2 in binary is equivalent to dividing by 10 in binary because 210 = 102 . To divide an even binary number by 2, the rightmost 0 is removed. In pseudocode, this is: Data: an even, binary number n Result: n/2 remove rightmost 0
public static String collatz1(String b){ if(!b.substring(b.length()-1).equals("0")) throw new IllegalArgumentException("Even numbers only."); return b.substring(0,b.length()-1); } In Java, public static String collatz1(String b){ if(!b.substring(b.length()-1).equals("0")) throw new IllegalArgumentException("Even numbers only."); return b.substring(0,b.length()-1); } Example: 110100 110100 = 11010. In decimal, this can be shown to be correct because 1101002 = 5210 , 110102 = 2610 , and 52/2 = 26.
1.2
n/2 (iteratively)
The Collatz function calls the n/2 algorithm as long as the integer b is even. Thus, the 0s at the end of the number will constantly be taken o. Hence, to iteratively divide by 2, remove the rightmost string of consecutive 0s. In pseudocode, this is: Data: an even, binary number n Result: n/2 (iteratively) while last digit is 0 do remove rightmost 0 end In Java, public static String collatz2(String b){ if(!b.substring(b.length()-1).equals("0")) 3
throw new IllegalArgumentException("Even numbers only."); while(b.substring(b.length()-1).equals("0")) b = b.substring(0,b.length()-1); return b; } $ = 11011 It can be shown that this is $ Example: 110110000 11011$ 0000 correct in this instance because the sequence for 1101100002 = 43210 216 108 54 27 = 110112 .
1.3
3n+1
For a binary string, such as 110011101, to multiply it by 3 would be equivalent to multiplying it by 112 . By the distributive property, thats the same as adding itself plus itself with an extra 0 at the end of it. Adding two binary digits modulo 2 is equivalent to performing the xor function. But, carrying the 1 must also be accounted for in addition. As long as there is a 1 being carried, a 1 will continue to be carried until there is a pair of adjacent 0s. This is shown below, with the carried 1s in the top column: 1 + 1 0 1 1 0 1 1 1 0 0 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 0 1
1 1
So, as a result, the carried 1 interferes with the xor of the adjacent digits and causes the binary negation of the result. From this, we can generalise the algorithm for 3n (which is steps 1-3 below). To add 1 at the end, the carried 1s negate all of the rightmost consecutive 1s and cause the rightmost 0 to become a 1 (step 4 below). 1. From right to left, for each string 00. . . 11, highlight 00. . . . If there are no visible 00 pairs, the leading 0s are used. 2. For each digit in the number, concatenate a string from the binary xor of the digit with the digit to the right of it, retaining the highlight. Note that this includes the xor of the leftmost digit and 0 as well as the rightmost digit and 0. 3. Perform the binary negation of all highlighted digits. 4. Perform the binary negation of the rightmost string of 011. . . 11. The pseudocode is shown below.
Data: an odd, binary number n Result: 3n + 1 n = 00 + n /* the leading 0s s = 0 /* for length constraints for i := 1 to length of b - 2 do s += b substring(i,i+1) b substring(i+1,i+2) end s += 1 for i := length of b - 2 to 0 do if b substring(i,i+2) = 11 then j=i while b substring(j,j+2) do j-end negate s from j to i i=j end end i = length of s - 1 while s substring(i,i+1) = 1 do i-end negate s from i to end of s /* optional: remove leading 0s
*/ */
*/
In Java, public static String collatz3(String b){ if(!b.substring(b.length()-1).equals("1")) throw new IllegalArgumentException("Odd numbers only."); b = "00" + b; // leading 0s String s = "0"; // so s.length() == b.length() for(int i = 1; i < b.length()-1; i++) s += xor(b.substring(i,i+1),b.substring(i+1,i+2)); s += "1"; // because b is odd for(int i = b.length()-2; i >= 0; i--) if(b.substring(i,i+2).equals("11")){ int j = i; while(!b.substring(j,j+2).equals("00")) j--; s = negate(s,j,i); i = j; } 5
int i = s.length()-1; while(s.substring(i,i+1).equals("1")) i--; s = negate(s,i,s.length()); while(s.substring(0,1).equals("0")) // remove leading 0s s = s.substring(1); return s; } Example: 1101100111 001101100111, since two zeros are assumed in front of the number. From right to the left, strings of 11 are found and highlighted until strings of 00 are found. The xor function is iteratively performed on adjacent digits and concatenated to form a new number, the hightlights retained. 001101100111 010110101001. Lastly, the binary negation of each highlighted digit is implemented. 010110101001 101000110101. Finally, to add 1, the rightmost string of 011 . . . 111 is converted to 100 . . . 000: 101000110101 101000110110. So the nal transformation is 1101100111 101000110110. In base 10, it can be shown that the algorithm proved successful: 11011001112 = 87110 , 1010001101102 = 261410 , and 3 (871) + 1 = 2614.
1.4
Collatz Algorithm
This algorithm is a combination of the 3n + 1 and the n/2 algorithms. For an odd number n, 1. From right to left, for each string 00. . . 11, highlight 00. . . . If there are no visible 00 pairs, the leading 0s are used. 2. For each digit in the number, concatenate a string from the binary xor of the digit with the digit to the right of it, retaining the highlight. Note that this includes the xor of the leftmost digit and 0 as well as the rightmost digit and 0. 3. Perform the binary negation of all highlighted digits. 4. Remove the rightmost string of consecutive 1s and convert the rightmost 0 to a 1. For an even number n, the n/2 formula is applied to make n odd, and the algorithm is performed. In pseudocode, this is: In Java, public static String collatz4(String b){ if(b.substring(b.length()-1).equals("0")) 6
Data: an odd, binary number n Result: 3n + 1 n = 00 + n /* the leading 0s s = 0 /* for length constraints for i := 1 to length of b - 2 do s += b substring(i,i+1) b substring(i+1,i+2) end s += 1 for i := length of b - 2 to 0 do if b substring(i,i+2) = 11 then j=i while b substring(j,j+2) do j-end negate s from j to i i=j end end while last digit of s is 1 do remove last digit of s end change last digit of s to 1 /* optional: remove leading 0s
*/ */
*/
b = collatz2(b); b = "00" + b; // leading 0s String s = "0"; // so s.length() == b.length() for(int i = 1; i < b.length()-1; i++) s += xor(b.substring(i,i+1),b.substring(i+1,i+2)); s += "1"; // because b is odd for(int i = b.length()-2; i >= 0; i--) if(b.substring(i,i+2).equals("11")){ int j = i; while(!b.substring(j,j+2).equals("00")) j--; s = negate(s,j,i); i = j; } int i = s.length()-1; while(s.substring(i,i+1).equals("1")){ s = s.substring(0,i); i--; } s = s.substring(0,i) + "1"; while(s.substring(0,1).equals("0")) // remove leading 0s s = s.substring(1); return s; }
