(skip navigation)

Computing 3n+1 with an FPGA

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

XKCD Comic

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

Picture of FPGA boards

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
34
77
2759
70381
10 087105
35 655135
270 271164
362 343165
381 727173
626 331176
1 027 431183
1 126 015224
8 088 063246
13 421 671287
20 638 335292
26 716 671298
56 924 955308
63 728 127376
217 740 015395
1 200 991 791398
1 827 397 567433
2 788 008 987447
12 235 060 455547
898 696 369 947550
2 081 751 768 559606
13 179 928 405 231688
31 835 572 457 967712
70 665 924 117 439722
739 448 869 367 967728
1 008 932 249 296 231886
118 303 688 851 791 519902
180 352 746 940 718 527966
1 236 472 189 813 512 351990

Nexcursion record
38
726
1580
274 616
2556 560
44719 682
63920 762
703125 252
1 819638 468
4 2553 405 068
4 5914 076 810
9 66313 557 212
20 89525 071 632
26 62353 179 010
31 91160 506 432
60 975296 639 576
77 671785 412 368
113 3831 241 055 674
138 3671 399 161 680
159 4878 601 188 876
270 27112 324 038 948
665 21526 241 642 656
704 51128 495 741 760
1 042 43145 119 577 824
1 212 41569 823 368 404
1 441 40775 814 787 186
1 875 71177 952 174 848
1 988 85978 457 189 112
2 643 18395 229 909 242
2 684 647176 308 906 472
3 041 127311 358 950 810
3 873 535429 277 584 788
4 637 979659 401 147 466
5 656 1911 206 246 808 304
6 416 6232 399 998 472 684
6 631 67530 171 305 459 816
19 638 399153 148 462 601 876
38 595 583237 318 849 425 546
80 049 3911 092 571 914 585 050
120 080 8951 638 950 788 059 290
210 964 3833 202 398 580 560 632
319 804 831707 118 223 359 971 240
1 410 123 9433 562 942 561 397 226 080
8 528 817 5119 072 297 468 678 299 012
12 327 829 50310 361 199 457 202 525 864
23 035 537 40734 419 078 320 774 113 520
45 871 962 27141 170 824 451 011 417 002
51 739 336 44757 319 808 570 806 999 220
59 152 641 05575 749 682 531 195 100 772
59 436 135 663102 868 194 685 920 926 084
70 141 259 775210 483 556 894 194 914 852
77 566 362 559458 306 514 538 433 899 928
110 243 094 271686 226 824 783 134 190 180
204 430 613 247707 630 396 504 827 495 544
231 913 730 7991 095 171 911 941 437 256 778
272 025 660 54310 974 241 817 835 208 981 874
446 559 217 27919 766 638 455 389 030 190 536
567 839 862 63150 270 086 612 792 993 117 994
871 673 828 443200 279 370 410 625 061 016 864
2 674 309 547 647385 209 974 924 871 186 526 136
3 716 509 988 199103 968 231 672 274 974 522 437 732
9 016 346 070 511126 114 763 591 721 667 597 212 096
64 848 224 337 147637 053 460 104 079 232 893 133 864
116 050 121 715 7111 265 292 033 916 892 480 613 118 196
201 321 227 677 9352 636 975 512 088 803 001 946 985 208
265 078 413 377 5352 857 204 078 078 966 555 847 716 826
291 732 129 855 1353 537 558 936 133 726 760 243 328 464
394 491 988 532 8956 054 282 113 227 445 504 606 919 650
406 738 920 960 66712 800 696 705 021 228 411 442 619 682
613 450 176 662 51122 881 441 742 972 862 145 992 619 776
737 482 236 053 11937 684 665 798 782 446 690 107 505 928
1 254 251 874 774 3751 823 036 311 464 280 263 720 932 141 024
5 323 048 232 813 2471 964 730 439 297 455 725 829 478 995 944
8 562 235 014 026 65513 471 057 008 351 679 202 003 944 688 336
10 709 980 568 908 647175 294 593 968 539 094 415 936 960 141 122
49 163 256 101 584 231301 753 104 069 007 668 258 074 264 675 786
82 450 591 202 377 887875 612 750 096 198 197 075 499 421 245 450
93 264 792 503 458 1192 115 362 774 686 865 777 485 863 406 680 032
172 545 331 199 510 6312 118 089 541 282 012 618 909 185 268 056 780
212 581 558 780 141 3112 176 718 166 004 315 761 101 410 771 585 688
255 875 336 134 000 0632 415 428 612 584 587 115 646 993 931 986 234
484 549 993 128 097 2154 332 751 846 533 208 436 890 106 993 276 834
562 380 758 422 254 2716 718 947 974 962 862 349 115 040 884 231 904
628 226 286 374 752 92331 268 160 888 027 375 005 205 169 043 314 754
891 563 131 061 253 151140 246 903 347 442 029 303 138 585 287 425 762
1 038 743 969 413 717 663159 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.