Tool to test the Collatz conjecture (or Hailstone or 3n+1) and variants that divide a number by 2 if it is even and else multiply it by 3 and add 1.
Collatz Conjecture - dCode
Tag(s) : Mathematics, Fun/Miscellaneous
dCode is free and its tools are a valuable help in games, maths, geocaching, puzzles and problems to solve every day!
A suggestion ? a feedback ? a bug ? an idea ? Write to dCode!
The Collatz Conjecture (or Syracuse Conjecture), also known as the 3n+1 problem, states that applying the 3n+1 algorithm to any positive integer will always end up with the number 1.
Take a number number $ n $ (non-zero positive integer), if $ n $ is even, divide it by $ 2 $, else multiply by $ 3 $ and add $ 1 $. Start again by giving $ n $ the value of the result previously obtained.
Mathematically the algorithm is defined by the function $ f $: $$ f_{3n+1}(n) = \begin{cases}{ \frac{n}{2}} & {\text{if }}n \equiv 0 \mod{2} \\ 3n+1 & {\text{if }} n \equiv 1 \mod{2} \end{cases} $$
Example: $ n=10 $, $ 10 $ is even, divide it by $ 2 $ and get $ 5 $,
$ 5 $ is odd, multiply it by $ 3 $ and add $ 1 $ to get $ 16 $,
Continue the sequence to get $ 8 $, $ 4 $, $ 2 $ and $ 1 $.
When the value $ 1 $ is obtained, continuation is generally considered complete, because the algorithm renders in an infinite loop of 4, 2, 1, 4, 2, 1, 4, 2, 1.
The sequence is generally considered to be finished at 1, because otherwise the following numbers are 4, 2, 1, 4, 2, 1, 4, 2, 1 which are repeated endlessly.
Some numbers have surprising sequences (called trajectories) like 27, 255, 447, 639 or 703.
If the number $ n $ is odd, then multiplying it by $ 3 $ and adding $ 1 $ necessarily makes it even, the next step is necessarily a division by 2.
The compressed (or shortened) version merges the $ 3x+1 $ and $ x/2 $ calculations into a single step $ (3x+1)/2 $
No, nobody has found a number for which it does not work but nobody has found any mathematical proof that the conjecture is always true.
This is why the conjecture is also called the Syracuse problem or the Collatz problem and it is not a theorem.
Anyone finding a number that does not end at 1 will then have solved the conjecture by proving it to be false.
No, there have been some real advances recently but the Syracuse conjecture remains unsolved despite dozens of pseudo-scientists who have claimed to have a proof.
A number never appears twice in the sequence.
Any sequence ends with a series of powers of 2.
An odd number is always followed by an even number.
The numbers 5 and 32 give the same result.
There are several ways to program source code for the 3x+1 algorithm:// Javascript
function step(n) {
if (n%2 == 0) return n/2;
return 3*n+1;
}
function collatz(n) {
var nb = 1;
while (n != 1) {
n = step(n);
nb++;
}
return nb;
}// Python
def collatz(x):
while x != 1:
if x % 2 > 0:
x =((3 * x) + 1)
list_.append(x)
else:
x = (x / 2)
list_.append(x)
return list_
The Collatz conjecture/problem is also known as
— 3n+1 conjecture (or 3x+1)
— Hailstone conjecture
— Ulam conjecture
— Kakutani's problem
— Thwaites conjecture
— Hasse's algorithm
— Syracuse problem
— HOTPO (Half Or Triple Plus One)
The name Syracuse comes from the Syracuse University, a city in the state of New York in the United States.
This table is for numbers until 1000 (total time/iterations => numbers)
0 | 1 |
---|---|
1 | 2 |
2 | 4 |
3 | 8 |
4 | 16 |
5 | 5, 32 |
6 | 10, 64 |
7 | 3, 20, 21, 128 |
8 | 6, 40, 42, 256 |
9 | 12, 13, 80, 84, 85, 512 |
10 | 24, 26, 160, 168, 170 |
11 | 48, 52, 53, 320, 336, 340, 341 |
12 | 17, 96, 104, 106, 113, 640, 672, 680, 682 |
13 | 34, 35, 192, 208, 212, 213, 226, 227 |
14 | 11, 68, 69, 70, 75, 384, 416, 424, 426, 452, 453, 454 |
15 | 22, 23, 136, 138, 140, 141, 150, 151, 768, 832, 848, 852, 853, 904, 906, 908, 909 |
16 | 7, 44, 45, 46, 272, 276, 277, 280, 282, 300, 301, 302 |
17 | 14, 15, 88, 90, 92, 93, 544, 552, 554, 560, 564, 565, 600, 602, 604, 605 |
18 | 28, 29, 30, 176, 180, 181, 184, 186, 201 |
19 | 9, 56, 58, 60, 61, 352, 360, 362, 368, 369, 372, 373, 401, 402, 403 |
20 | 18, 19, 112, 116, 117, 120, 122, 704, 720, 724, 725, 736, 738, 739, 744, 746, 753, 802, 803, 804, 805, 806 |
21 | 36, 37, 38, 224, 232, 234, 240, 241, 244, 245, 267 |
22 | 72, 74, 76, 77, 81, 448, 464, 468, 469, 480, 482, 483, 488, 490, 497, 534, 535, 537 |
23 | 25, 144, 148, 149, 152, 154, 162, 163, 896, 928, 936, 938, 960, 964, 965, 966, 976, 980, 981, 985, 994, 995 |
24 | 49, 50, 51, 288, 296, 298, 304, 308, 309, 321, 324, 325, 326, 331 |
25 | 98, 99, 100, 101, 102, 576, 592, 596, 597, 608, 616, 618, 625, 642, 643, 648, 650, 652, 653, 662, 663, 713, 715 |
26 | 33, 196, 197, 198, 200, 202, 204, 205, 217 |
27 | 65, 66, 67, 392, 394, 396, 397, 400, 404, 405, 408, 410, 433, 434, 435, 441, 475 |
28 | 130, 131, 132, 133, 134, 784, 788, 789, 792, 794, 800, 808, 810, 816, 820, 821, 833, 857, 866, 867, 868, 869, 870, 875, 882, 883, 950, 951, 953, 955 |
29 | 43, 260, 261, 262, 264, 266, 268, 269, 273, 289 |
30 | 86, 87, 89, 520, 522, 524, 525, 528, 529, 532, 533, 536, 538, 546, 547, 555, 571, 577, 578, 579, 583, 633, 635 |
31 | 172, 173, 174, 177, 178, 179 |
32 | 57, 59, 344, 346, 348, 349, 354, 355, 356, 357, 358, 385, 423 |
33 | 114, 115, 118, 119, 688, 692, 693, 696, 698, 705, 708, 709, 710, 712, 714, 716, 717, 729, 761, 769, 770, 771, 777, 846, 847 |
34 | 39, 228, 229, 230, 236, 237, 238 |
35 | 78, 79, 456, 458, 460, 461, 465, 472, 473, 474, 476, 477, 507, 513 |
36 | 153, 156, 157, 158, 912, 916, 917, 920, 922, 930, 931, 943, 944, 945, 946, 947, 948, 949, 952, 954, 971, 987 |
37 | 305, 306, 307, 312, 314, 315, 316, 317 |
38 | 105, 610, 611, 612, 613, 614, 624, 628, 629, 630, 631, 632, 634, 647, 683, 687 |
39 | 203, 209, 210, 211 |
40 | 406, 407, 409, 418, 419, 420, 421, 422, 431, 455 |
41 | 135, 139, 812, 813, 814, 817, 818, 819, 827, 836, 837, 838, 840, 841, 842, 843, 844, 845, 862, 863, 910, 911 |
42 | 270, 271, 278, 279, 281, 287, 303 |
43 | 540, 541, 542, 545, 551, 556, 557, 558, 561, 562, 563, 574, 575, 606, 607 |
44 | 185, 187, 191 |
45 | 361, 363, 367, 370, 371, 374, 375, 382, 383 |
46 | 123, 127, 721, 722, 723, 726, 727, 734, 735, 740, 741, 742, 747, 748, 749, 750, 764, 765, 766, 809, 891 |
47 | 246, 247, 249, 254, 255 |
48 | 481, 489, 492, 493, 494, 498, 499, 508, 509, 510, 539 |
49 | 169, 961, 962, 963, 969, 978, 979, 984, 986, 988, 989, 996, 997, 998, 999 |
50 | 329, 338, 339, 359 |
51 | 641, 657, 658, 659, 665, 676, 677, 678, 718, 719 |
52 | 219, 225, 239 |
53 | 427, 438, 439, 443, 450, 451, 478, 479 |
54 | 159, 854, 855, 876, 877, 878, 886, 887, 900, 901, 902, 907, 956, 957, 958 |
55 | 295, 318, 319 |
56 | 569, 585, 590, 591, 601, 636, 637, 638 |
58 | 379, 393, 425 |
59 | 758, 759, 767, 779, 786, 787, 801, 849, 850, 851 |
60 | 283 |
61 | 505, 511, 519, 566, 567 |
63 | 377 |
64 | 673, 679, 681, 699, 711, 754, 755 |
65 | 251 |
66 | 502, 503 |
67 | 167, 897, 905, 923 |
68 | 334, 335 |
69 | 111, 603, 615, 668, 669, 670 |
70 | 222, 223 |
71 | 444, 445, 446 |
72 | 799, 807, 888, 890, 892, 893 |
73 | 297 |
74 | 593, 594, 595 |
76 | 395 |
77 | 790, 791, 793 |
78 | 263 |
79 | 526, 527 |
80 | 175 |
81 | 350, 351 |
82 | 700, 701, 702 |
83 | 233 |
84 | 466, 467 |
85 | 155, 839, 932, 933, 934, 939 |
86 | 310, 311 |
87 | 103, 559, 620, 621, 622 |
88 | 206, 207 |
89 | 412, 413, 414 |
90 | 137, 745, 824, 826, 828, 829 |
91 | 274, 275 |
92 | 91, 548, 549, 550 |
93 | 182, 183, 993 |
94 | 364, 365, 366 |
95 | 121, 671, 728, 730, 732, 733, 743 |
96 | 242, 243 |
97 | 447, 484, 485, 486, 495 |
98 | 161, 894, 895, 968, 970, 972, 973, 977, 990, 991 |
99 | 322, 323 |
100 | 107, 644, 645, 646, 651 |
101 | 214, 215 |
102 | 71, 428, 429, 430 |
103 | 142, 143, 795, 856, 858, 860, 861 |
104 | 47, 284, 285, 286 |
105 | 94, 95, 568, 570, 572, 573 |
106 | 31, 188, 189, 190 |
107 | 62, 63, 376, 378, 380, 381 |
108 | 124, 125, 126, 752, 756, 757, 760, 762 |
109 | 41, 248, 250, 252, 253 |
110 | 82, 83, 496, 500, 501, 504, 506 |
111 | 27, 164, 165, 166, 992, 1000 |
112 | 54, 55, 328, 330, 332, 333, 337 |
113 | 108, 109, 110, 656, 660, 661, 664, 666, 674, 675 |
114 | 216, 218, 220, 221 |
115 | 73, 432, 436, 437, 440, 442, 449 |
116 | 145, 146, 147, 864, 872, 874, 880, 881, 884, 885, 898, 899, 903, 927 |
117 | 290, 291, 292, 293, 294, 299 |
118 | 97, 580, 581, 582, 584, 586, 587, 588, 589, 598, 599 |
119 | 193, 194, 195, 199 |
120 | 386, 387, 388, 389, 390, 391, 398, 399 |
121 | 129, 772, 773, 774, 776, 778, 780, 781, 782, 783, 785, 796, 797, 798 |
122 | 257, 258, 259, 265 |
123 | 514, 515, 516, 517, 518, 521, 523, 530, 531 |
124 | 171 |
125 | 342, 343, 345, 347, 353 |
126 | 684, 685, 686, 689, 690, 691, 694, 695, 697, 706, 707 |
127 | 231, 235 |
128 | 457, 459, 462, 463, 470, 471 |
129 | 913, 914, 915, 918, 919, 921, 924, 925, 926, 929, 935, 940, 941, 942, 959 |
130 | 313 |
131 | 609, 617, 619, 623, 626, 627, 639 |
133 | 411, 415, 417 |
134 | 811, 815, 822, 823, 825, 830, 831, 834, 835 |
136 | 543, 553 |
139 | 731, 737, 751 |
141 | 487, 491 |
142 | 967, 974, 975, 982, 983 |
143 | 327 |
144 | 649, 654, 655, 667 |
147 | 859, 865, 873, 879, 889 |
152 | 763, 775 |
170 | 703 |
173 | 937 |
178 | 871 |
This table shows numbers until 1000 (max number reached => numbers)
1 | 1 |
---|---|
2 | 2 |
4 | 4 |
8 | 8 |
16 | 3, 5, 6, 10, 12, 16 |
20 | 20 |
24 | 24 |
32 | 32 |
40 | 13, 26, 40 |
48 | 48 |
52 | 7, 9, 11, 14, 17, 18, 22, 28, 34, 36, 44, 52 |
56 | 56 |
64 | 21, 42, 64 |
68 | 68 |
72 | 72 |
80 | 80 |
84 | 84 |
88 | 19, 25, 29, 38, 50, 58, 76, 88 |
96 | 96 |
100 | 33, 66, 100 |
104 | 104 |
112 | 37, 74, 112 |
116 | 116 |
128 | 128 |
132 | 132 |
136 | 45, 90, 136 |
144 | 144 |
148 | 49, 98, 148 |
152 | 152 |
160 | 15, 23, 30, 35, 46, 53, 60, 70, 92, 106, 120, 140, 160 |
168 | 168 |
176 | 176 |
180 | 180 |
184 | 61, 122, 184 |
192 | 192 |
196 | 43, 57, 65, 86, 114, 130, 172, 196 |
200 | 200 |
208 | 69, 138, 208 |
212 | 212 |
224 | 224 |
228 | 228 |
232 | 51, 77, 102, 154, 204, 232 |
240 | 240 |
244 | 81, 162, 244 |
256 | 85, 170, 256 |
260 | 260 |
264 | 264 |
272 | 272 |
276 | 276 |
280 | 93, 186, 280 |
288 | 288 |
296 | 296 |
304 | 39, 59, 67, 78, 89, 101, 118, 134, 156, 178, 202, 236, 268, 304 |
308 | 308 |
312 | 312 |
320 | 320 |
324 | 324 |
336 | 336 |
340 | 75, 113, 150, 226, 300, 340 |
344 | 344 |
352 | 117, 234, 352 |
356 | 356 |
360 | 360 |
368 | 368 |
372 | 372 |
384 | 384 |
392 | 392 |
400 | 133, 266, 400 |
404 | 404 |
408 | 408 |
416 | 416 |
424 | 141, 282, 424 |
448 | 99, 149, 198, 298, 396, 448 |
452 | 452 |
456 | 456 |
464 | 464 |
468 | 468 |
472 | 157, 314, 472 |
480 | 480 |
488 | 488 |
512 | 512 |
520 | 115, 153, 173, 230, 306, 346, 460, 520 |
528 | 528 |
532 | 177, 354, 532 |
536 | 536 |
544 | 181, 362, 544 |
552 | 552 |
560 | 560 |
564 | 564 |
576 | 576 |
592 | 87, 131, 174, 197, 262, 348, 394, 524, 592 |
596 | 596 |
600 | 600 |
608 | 608 |
612 | 612 |
616 | 205, 410, 616 |
624 | 624 |
628 | 123, 139, 185, 209, 246, 278, 370, 418, 492, 556, 628 |
640 | 213, 426, 640 |
648 | 648 |
672 | 672 |
680 | 680 |
688 | 229, 458, 688 |
692 | 692 |
696 | 696 |
704 | 704 |
708 | 708 |
712 | 237, 474, 712 |
720 | 720 |
724 | 241, 482, 724 |
736 | 163, 217, 245, 326, 434, 490, 652, 736 |
740 | 740 |
744 | 744 |
768 | 768 |
784 | 261, 522, 784 |
788 | 788 |
792 | 792 |
800 | 800 |
808 | 79, 105, 119, 158, 179, 210, 238, 269, 316, 358, 420, 476, 538, 632, 716, 808 |
816 | 816 |
820 | 273, 546, 820 |
832 | 277, 554, 832 |
836 | 836 |
840 | 840 |
848 | 848 |
852 | 852 |
868 | 289, 578, 868 |
896 | 896 |
904 | 301, 602, 904 |
912 | 912 |
916 | 135, 203, 270, 305, 406, 540, 610, 812, 916 |
920 | 920 |
928 | 309, 618, 928 |
936 | 936 |
944 | 944 |
948 | 948 |
952 | 187, 211, 249, 281, 317, 374, 422, 498, 562, 634, 748, 844, 952 |
960 | 960 |
964 | 321, 642, 964 |
976 | 325, 650, 976 |
980 | 980 |
984 | 984 |
996 | 996 |
1024 | 151, 201, 227, 302, 341, 402, 454, 604, 682, 804, 908 |
1048 | 349, 698 |
1072 | 357, 714 |
1108 | 369, 738 |
1120 | 373, 746 |
1156 | 385, 770 |
1192 | 397, 794 |
1204 | 267, 401, 534, 802 |
1216 | 405, 810 |
1264 | 421, 842 |
1300 | 433, 866 |
1360 | 453, 906 |
1384 | 307, 409, 461, 614, 818, 922 |
1396 | 465, 930 |
1408 | 469, 938 |
1432 | 477, 954 |
1480 | 493, 986 |
1492 | 331, 441, 497, 662, 882, 994 |
1540 | 513 |
1576 | 525 |
1588 | 529 |
1600 | 315, 355, 473, 533, 630, 710, 946 |
1624 | 541 |
1636 | 363, 545, 726 |
1672 | 219, 247, 329, 371, 438, 494, 557, 658, 742, 876, 988 |
1684 | 561 |
1696 | 565 |
1732 | 577 |
1792 | 597 |
1816 | 403, 537, 605, 806 |
1840 | 613 |
1876 | 625 |
1888 | 279, 419, 558, 629, 838 |
1960 | 435, 653, 870 |
1972 | 657 |
2080 | 693 |
2116 | 705 |
2128 | 709 |
2152 | 717 |
2164 | 721 |
2176 | 483, 725, 966 |
2224 | 741 |
2248 | 295, 393, 443, 499, 590, 665, 749, 786, 886, 998 |
2260 | 753 |
2308 | 769 |
2368 | 789 |
2416 | 805 |
2440 | 813 |
2452 | 817 |
2464 | 547, 729, 821 |
2500 | 555, 833 |
2512 | 837 |
2536 | 375, 563, 750, 845 |
2560 | 853 |
2608 | 579, 869 |
2632 | 877 |
2728 | 909 |
2752 | 271, 361, 379, 407, 427, 481, 505, 542, 569, 611, 641, 673, 722, 758, 814, 854, 897, 917, 962 |
2836 | 945 |
2848 | 949 |
2884 | 961 |
2896 | 507, 571, 643, 761, 857, 965 |
2944 | 981 |
2968 | 439, 585, 659, 878, 989 |
2992 | 997 |
3076 | 303, 455, 606, 683, 910 |
3220 | 423, 635, 715, 846, 953 |
3256 | 723 |
3328 | 739, 985 |
3472 | 771 |
3508 | 519, 779 |
3544 | 699, 787 |
3616 | 475, 535, 633, 713, 803, 950 |
3688 | 819 |
3796 | 843 |
3904 | 867 |
3940 | 583, 777, 875 |
3976 | 883 |
4192 | 367, 489, 551, 734, 827, 931, 978 |
4264 | 631, 747, 841, 947 |
4336 | 963 |
4372 | 127, 169, 191, 225, 254, 287, 338, 339, 382, 431, 450, 451, 508, 509, 574, 601, 647, 676, 677, 678, 764, 765, 801, 862, 900, 901, 902, 971 |
4408 | 979 |
4480 | 663, 995 |
4804 | 711 |
4840 | 955 |
4912 | 727, 969 |
5128 | 759 |
5776 | 855 |
5812 | 603, 679, 905 |
5992 | 591, 887 |
6424 | 951 |
6964 | 687 |
7504 | 987 |
8080 | 559, 745, 839, 993 |
8584 | 847, 891 |
9232 | 27, 31, 41, 47, 54, 55, 62, 63, 71, 73, 82, 83, 91, 94, 95, 97, 103, 107, 108, 109, 110, 111, 121, 124, 125, 126, 129, 137, 142, 143, 145, 146, 147, 155, 159, 161, 164, 165, 166, 167, 171, 175, 182, 183, 188, 189, 190, 193, 194, 195, 199, 206, 207, 214, 215, 216, 218, 220, 221, 222, 223, 231, 233, 235, 239, 242, 243, 248, 250, 251, 252, 253, 257, 258, 259, 263, 265, 274, 275, 283, 284, 285, 286, 290, 291, 292, 293, 294, 297, 299, 310, 311, 313, 318, 319, 322, 323, 327, 328, 330, 332, 333, 334, 335, 337, 342, 343, 345, 347, 350, 351, 353, 359, 364, 365, 366, 376, 377, 378, 380, 381, 386, 387, 388, 389, 390, 391, 395, 398, 399, 411, 412, 413, 414, 415, 417, 425, 428, 429, 430, 432, 436, 437, 440, 442, 444, 445, 446, 449, 457, 459, 462, 463, 466, 467, 470, 471, 478, 479, 484, 485, 486, 487, 491, 496, 500, 501, 502, 503, 504, 506, 514, 515, 516, 517, 518, 521, 523, 526, 527, 530, 531, 539, 543, 548, 549, 550, 553, 566, 567, 568, 570, 572, 573, 580, 581, 582, 584, 586, 587, 588, 589, 593, 594, 595, 598, 599, 607, 609, 617, 619, 620, 621, 622, 623, 626, 627, 636, 637, 638, 644, 645, 646, 649, 651, 654, 655, 656, 660, 661, 664, 666, 668, 669, 670, 674, 675, 684, 685, 686, 689, 690, 691, 694, 695, 697, 700, 701, 702, 706, 707, 718, 719, 728, 730, 731, 732, 733, 737, 752, 754, 755, 756, 757, 760, 762, 763, 772, 773, 774, 775, 776, 778, 780, 781, 782, 783, 785, 790, 791, 793, 796, 797, 798, 809, 811, 815, 822, 823, 824, 825, 826, 828, 829, 830, 834, 835, 849, 850, 851, 856, 858, 859, 860, 861, 864, 865, 872, 873, 874, 880, 881, 884, 885, 888, 890, 892, 893, 898, 899, 903, 911, 913, 914, 915, 918, 919, 921, 924, 925, 926, 929, 932, 933, 934, 935, 939, 940, 941, 942, 956, 957, 958, 967, 968, 970, 972, 973, 974, 977, 982, 983, 992, 1000 |
9556 | 943 |
9880 | 975 |
10024 | 879 |
10528 | 615, 923 |
11176 | 735 |
11392 | 999 |
12148 | 799 |
13120 | 255, 383, 510, 575, 766, 863, 907 |
14308 | 495, 743, 990 |
15064 | 991 |
15856 | 927 |
18952 | 831 |
21688 | 667, 751, 889 |
39364 | 447, 511, 671, 681, 767, 795, 807, 894, 895 |
41524 | 639, 959 |
190996 | 871 |
250504 | 703, 937 |
The table above shows altitudes up to 250504 for numbers up to 1000. But there are infinite numbers that go higher.
For any given number N (very large N), then the odd number closest to N will have an even greater elevation.
Formulated in 1937 by Lothar Collatz (german mathematician), it remains unsolved: nobody has been able to prove this conjecture always ends with 1.
dCode retains ownership of the "Collatz Conjecture" source code. Except explicit open source licence (indicated Creative Commons / free), the "Collatz Conjecture" algorithm, the applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, breaker, translator), or the "Collatz Conjecture" functions (calculate, convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (Python, Java, PHP, C#, Javascript, Matlab, etc.) and all data download, script, or API access for "Collatz Conjecture" are not public, same for offline use on PC, mobile, tablet, iPhone or Android app!
Reminder : dCode is free to use.
The copy-paste of the page "Collatz Conjecture" or any of its results, is allowed (even for commercial purposes) as long as you credit dCode!
Exporting results as a .csv or .txt file is free by clicking on the export icon
Cite as source (bibliography):
Collatz Conjecture on dCode.fr [online website], retrieved on 2024-12-02,