From: already5chosen@yahoo.com
On Sun, 15 Feb 2026 03:58:28 -0500
Robert Finch wrote:
> On 2026-02-14 4:57 a.m., Thomas Koenig wrote:
> > Some people are throwing large amounts of computing power at trying
> > to disprove the Collatz conjecture. Graphics cards have sped this
> > up enormously.
> >
> > (A reminder, if any is needed: From a starting number n, the
> > transformation, recursively applied,
> >
> >
> > f(n) = 3*n+1, if n is odd; =n/2 if n is even.
> >
> > is conjectured to always reach 1 for any positive integer 1).
> >
> > All the work is done on general-purpose hardware, which has many
> > capabilities that are not needed, and consume area and power that
> > special-purpose hardware would not need. Also, the hardware
> > is limited to 64-bit integers, and the range of tested numbers
> > is now up to 2^71, so
> >
> > What could specialized hardware look like?
> >
> > The central part could be a unit which is handed a block of numbers
> > to check, for example a range of 2^32 numbers. The current records
> > for number of iterations and maximum number reached would also be
> > stored in that unit.
> >
> > In that unit, the calculaiton would be performed by a combination
> > of adder and shifter. The input would always be odd (so the last
> > bit could be dropped), and it would calculate (3*n+1)>>ctz(3*n+1).
> >
> > The adder would compute (3*n+1)/2, and would be specialzed 128-bit
> > adder. Why specialized? The logic is far less complex than a
> > general-purpose adder. For example, a two-bit adder has the formula
> >
> > y1 = (!a1&a0) | (!c_in&a1&!a0);
> > y0 = (c_in&!a1&!a0) | (!c_in&a1&!a0) | (a1&a0);
> >
> > and its propagate and generate bits are
> >
> > p = (a1);
> > g = (a1&a0);
> >
> > The maximum number of trailing zeros after the (3*n+1)/2 step is
> > three and can be determined cheaply from bits <3:1> of the input,
> > so the input to the shifter (two levels only) can be provided
> > in parallel. The machine would be designed that adding and
> > shifting can be done in a single cycle.
> >
> > The number of iterations would be tracked; if larger than a prevous
> > record, the calculation would terminate with a corresponding signal
> > to the outside world.
> >
> > Also, each cycle, the result from the previous round would be
> > compared against the input value. If it is lower, the next number
> > would be chosen. Finally, the number reached would be checked
> > against the previous, pre-set maximum, with would also signal to
> > the outside world.
> >
> > Which numbers to chose? It is well known that only certain
> > numbers with remainders modulo 2^n are interesting. The number
> > can be seen on OEIS A076227. For example, modulo 2^10, only 64
> > numbers are "interesting", or 6.25% (but only eight bits would
> > be needed to store them because the last two are always one).
> > Modulo 2^16 would be 734 numbers, or 3.22%, so this would cut the
> > amount of numbers to be checked by half. One would use a small ROM,
> > I presume. The number of bits would be a tradeoff between area and
> > amount of compuation. My current guess would be that 2^10 could
> > be a sweet spot. One third of the numbers would further be
> > excluded by checking for divisiblity by three.
> >
> > The problem is embarassingly parallel. One could chose a size so
> > each parcel is calculated in a few seconds or even minutes. to avoid
> > having to avoid a large amount of communication with the outside.
> >
> > Because all units would be working all the time, and if one has
> > a smaller unit one could simply build more of them, I suspect that
> > power would be the main limiting factor. An adder design that
> > might not be very fast, but uses lower power, low voltage and low
> > frequency would be beneficial.
> >
> > Comments?
> >
> I wonder how difficult it would be to implement a parallel tester in
> an FPGA. It looks simple enough and there are hundreds of DSP blocks
> available to use. Could test in blocks of hundreds of numbers at a
> time. Running at 100 MHz * 200 tests at a time = how long to get to
> 2^71?
>
I am not totally sure what exactly you are asking, but if you are
asking about how much time it takes at that rate to do 2**71 iterations
then the answer is ~3743 years.
But you probably already figured it out yourself.
Of course, brute force demonstration of correction of conjecture for all
numbers in range 1 to 2**71 will take more steps than 2**71. And it
is unknown how much more.
> I wonder if the calculation can be broken down further. Numbers are
> all just defined by rules. I wonder if some calculus may apply. Limit
> of function approaches one for a finite number of steps. There may be
> a whole range of algorithms, is there one for the number two? Then
> the number three?
>
> Occasionally I have made useless machinery. Great puzzle work. Made
> the game of life in hardware.
>
--- SoupGate-Win32 v1.05
* Origin: you cannot sedate... all the things you hate (1:229/2)
|
