This project uses FPGAs to test the 3n+1 conjecture for a large range of numbers.
| Project status | |
|---|---|
| Verified numbers up to | 101×254
= 1.81×1018 |
| Counterexamples found | 0 |
| FPGA days used | 4196 |
| Last update | 2013-04-12 |
The 3n+1 conjecture
Start with a positive integer. If the number is even, divide by two, otherwise multiply by three and add one. Keep doing this, and you will end up at 1. For example: 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
The 3n+1 conjecture, also known as Collatz conjecture predicts that this procedure will always reach 1, no matter which number you start with. It works for every number that has ever been tried. Still, no mathematical proof of the conjecture is known; so it's not certain that this really works for all numbers.
Testing the conjecture with FPGAs
An FPGA is a programmable digital chip. For this project, I'm using four Xilinx Spartan‑3E1600 FPGAs. The boards are linked by a serial bus. One of the boards is connected to a PC through Ethernet.
Testing the 3n+1 conjecture is simple: try all numbers in increasing order and verify that the sequences all reach 1. If the conjecture is true, this process can go on forever. On the other hand, if the conjecture is false, this process will eventually find a sequence which does not reach 1.
The FPGA communicates with a PC to get an assignment for a block of 234 starting numbers. It tests the range in about 3.3 seconds and sends results back to the PC.
| Performance of one FPGA | ||
|---|---|---|
| Numbers per block | 234 | |
| Time needed per block | 3.3 | seconds |
| Speed | 5.1×109 | num/second |
| Power consumption | 4 | Watt |
| Energy efficiency | 1.2×109 | num/Joule |
Note: speed = rate of expansion of the tested range, including numbers that are not actually tested because of optimizations.
The digital design in the FPGA consists of 32 parallel iterators. Each iterator works independently through a block of starting numbers. The clock frequency is 80 MHz. On every tick of that clock, the iterators compute the next number of a sequence, either n/2, or (3n+1)/2.
It is not really necessary to follow every sequence until it gets to 1. Many numbers can be skipped because simple mathematics shows that they will eventually reach 1. Such optimizations were invented by others and shamelessly copied by me. See my article 3n+1 iteration: FPGA vs CPU for a better description.
The following optimizations are used:
- The operations 3n+1 followed by n/2 are computed in one (3n+1)/2 step;
- A sequence stops when it reaches a number smaller than its starting number;
- Even starting numbers are not tested;
- Starting numbers N ≡ 2 mod 3 are not tested;
- Starting numbers are not tested if their least significant 24 bits indicate that the sequence stops within 24 steps.
Records
The stopping time of N, abbreviated as σ(N), is the number of steps needed to go from N to a number smaller than N. A σ-record occurs when σ(N) is larger than any σ of a smaller starting number.
The maximum excursion of N is the largest number that occurs anywhere in the sequence from N to 1. An excursion record occurs when the maximum excursion of N is larger than any maximum excursion of a smaller starting number.
While verifying that all sequences lead to 1, the FPGA also looks for σ-records and excursion records. These records are useful for comparing results against other 3n+1 projects. When a new record is found, the range is recomputed in software on a PC to find the exact starting number where the record occurred.
Results
Status: Verified numbers up to 101×254 (Apr 2013).
The tables below report the records found with my FPGA setup. These numbers agree with results reported by others for the same range.
| N | σ record |
|---|---|
| 3 | 4 |
| 7 | 7 |
| 27 | 59 |
| 703 | 81 |
| 10 087 | 105 |
| 35 655 | 135 |
| 270 271 | 164 |
| 362 343 | 165 |
| 381 727 | 173 |
| 626 331 | 176 |
| 1 027 431 | 183 |
| 1 126 015 | 224 |
| 8 088 063 | 246 |
| 13 421 671 | 287 |
| 20 638 335 | 292 |
| 26 716 671 | 298 |
| 56 924 955 | 308 |
| 63 728 127 | 376 |
| 217 740 015 | 395 |
| 1 200 991 791 | 398 |
| 1 827 397 567 | 433 |
| 2 788 008 987 | 447 |
| 12 235 060 455 | 547 |
| 898 696 369 947 | 550 |
| 2 081 751 768 559 | 606 |
| 13 179 928 405 231 | 688 |
| 31 835 572 457 967 | 712 |
| 70 665 924 117 439 | 722 |
| 739 448 869 367 967 | 728 |
| 1 008 932 249 296 231 | 886 |
| 118 303 688 851 791 519 | 902 |
| 180 352 746 940 718 527 | 966 |
| 1 236 472 189 813 512 351 | 990 |
| N | excursion record |
|---|---|
| 3 | 8 |
| 7 | 26 |
| 15 | 80 |
| 27 | 4 616 |
| 255 | 6 560 |
| 447 | 19 682 |
| 639 | 20 762 |
| 703 | 125 252 |
| 1 819 | 638 468 |
| 4 255 | 3 405 068 |
| 4 591 | 4 076 810 |
| 9 663 | 13 557 212 |
| 20 895 | 25 071 632 |
| 26 623 | 53 179 010 |
| 31 911 | 60 506 432 |
| 60 975 | 296 639 576 |
| 77 671 | 785 412 368 |
| 113 383 | 1 241 055 674 |
| 138 367 | 1 399 161 680 |
| 159 487 | 8 601 188 876 |
| 270 271 | 12 324 038 948 |
| 665 215 | 26 241 642 656 |
| 704 511 | 28 495 741 760 |
| 1 042 431 | 45 119 577 824 |
| 1 212 415 | 69 823 368 404 |
| 1 441 407 | 75 814 787 186 |
| 1 875 711 | 77 952 174 848 |
| 1 988 859 | 78 457 189 112 |
| 2 643 183 | 95 229 909 242 |
| 2 684 647 | 176 308 906 472 |
| 3 041 127 | 311 358 950 810 |
| 3 873 535 | 429 277 584 788 |
| 4 637 979 | 659 401 147 466 |
| 5 656 191 | 1 206 246 808 304 |
| 6 416 623 | 2 399 998 472 684 |
| 6 631 675 | 30 171 305 459 816 |
| 19 638 399 | 153 148 462 601 876 |
| 38 595 583 | 237 318 849 425 546 |
| 80 049 391 | 1 092 571 914 585 050 |
| 120 080 895 | 1 638 950 788 059 290 |
| 210 964 383 | 3 202 398 580 560 632 |
| 319 804 831 | 707 118 223 359 971 240 |
| 1 410 123 943 | 3 562 942 561 397 226 080 |
| 8 528 817 511 | 9 072 297 468 678 299 012 |
| 12 327 829 503 | 10 361 199 457 202 525 864 |
| 23 035 537 407 | 34 419 078 320 774 113 520 |
| 45 871 962 271 | 41 170 824 451 011 417 002 |
| 51 739 336 447 | 57 319 808 570 806 999 220 |
| 59 152 641 055 | 75 749 682 531 195 100 772 |
| 59 436 135 663 | 102 868 194 685 920 926 084 |
| 70 141 259 775 | 210 483 556 894 194 914 852 |
| 77 566 362 559 | 458 306 514 538 433 899 928 |
| 110 243 094 271 | 686 226 824 783 134 190 180 |
| 204 430 613 247 | 707 630 396 504 827 495 544 |
| 231 913 730 799 | 1 095 171 911 941 437 256 778 |
| 272 025 660 543 | 10 974 241 817 835 208 981 874 |
| 446 559 217 279 | 19 766 638 455 389 030 190 536 |
| 567 839 862 631 | 50 270 086 612 792 993 117 994 |
| 871 673 828 443 | 200 279 370 410 625 061 016 864 |
| 2 674 309 547 647 | 385 209 974 924 871 186 526 136 |
| 3 716 509 988 199 | 103 968 231 672 274 974 522 437 732 |
| 9 016 346 070 511 | 126 114 763 591 721 667 597 212 096 |
| 64 848 224 337 147 | 637 053 460 104 079 232 893 133 864 |
| 116 050 121 715 711 | 1 265 292 033 916 892 480 613 118 196 |
| 201 321 227 677 935 | 2 636 975 512 088 803 001 946 985 208 |
| 265 078 413 377 535 | 2 857 204 078 078 966 555 847 716 826 |
| 291 732 129 855 135 | 3 537 558 936 133 726 760 243 328 464 |
| 394 491 988 532 895 | 6 054 282 113 227 445 504 606 919 650 |
| 406 738 920 960 667 | 12 800 696 705 021 228 411 442 619 682 |
| 613 450 176 662 511 | 22 881 441 742 972 862 145 992 619 776 |
| 737 482 236 053 119 | 37 684 665 798 782 446 690 107 505 928 |
| 1 254 251 874 774 375 | 1 823 036 311 464 280 263 720 932 141 024 |
| 5 323 048 232 813 247 | 1 964 730 439 297 455 725 829 478 995 944 |
| 8 562 235 014 026 655 | 13 471 057 008 351 679 202 003 944 688 336 |
| 10 709 980 568 908 647 | 175 294 593 968 539 094 415 936 960 141 122 |
| 49 163 256 101 584 231 | 301 753 104 069 007 668 258 074 264 675 786 |
| 82 450 591 202 377 887 | 875 612 750 096 198 197 075 499 421 245 450 |
| 93 264 792 503 458 119 | 2 115 362 774 686 865 777 485 863 406 680 032 |
| 172 545 331 199 510 631 | 2 118 089 541 282 012 618 909 185 268 056 780 |
| 212 581 558 780 141 311 | 2 176 718 166 004 315 761 101 410 771 585 688 |
| 255 875 336 134 000 063 | 2 415 428 612 584 587 115 646 993 931 986 234 |
| 484 549 993 128 097 215 | 4 332 751 846 533 208 436 890 106 993 276 834 |
| 562 380 758 422 254 271 | 6 718 947 974 962 862 349 115 040 884 231 904 |
| 628 226 286 374 752 923 | 31 268 160 888 027 375 005 205 169 043 314 754 |
| 891 563 131 061 253 151 | 140 246 903 347 442 029 303 138 585 287 425 762 |
| 1 038 743 969 413 717 663 | 159 695 671 984 678 120 932 209 599 662 553 676 |
Project history
In 2006, while writing 3n+1 iteration: FPGA vs CPU, I used a Digilent Spartan-3-200 board. It used 4 parallel iterators at 50 MHz, verifying 0.4×109 numbers per second. It ran for nearly a year before I discovered a timing error in the design. Digital circuits with timing violations are unreliable, therefore I could not trust the results of the computation.
In 2007, I switched to a Trenz Spartan-3-1000 micromodule. It used 16 iterators at 60 MHz, verifying 1.9×109 numbers per second. After it had run for two years, I found yet another mistake in the timing. Again I had to throw away the results, fix the design and restart the run. The corrected design ran for 9 months, verifying all numbers up to 3.6×1016.
In 2010, I restarted from scratch with four Digilent Spartan-3E-1600 boards. Each board runs 32 parallel iterators at 80 MHz. The 4 boards together verify 20×109 numbers per second. I have been very careful this time to avoid any more timing mistakes. The new run started on February 8, 2010.
Related projects
Gary T. Leavens and Mike Vermeulen (1992) report records and other statistics for all starting numbers up to 5.6×1013.
Eric Roosendaal verified convergence of all numbers up to 260 (1.2×1018) and lists the corresponding excursion records.
Thomás Oliveira e Silva verified convergence of all numbers up to 20×258 (5.7×1018) and computed σ-records and excursion records.