From: tr.17687@z991.linuxsc.com   
      
   Thomas Koenig  writes:   
      
   > 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?   
      
   Amusing.  I predict that ultimately it will be a waste of   
   effort because the Collatz conjecture is true even though   
   currently unproven.  Also it seems likely that no mathematical   
   insights will result from any sort of brute force approach to   
   disprove it, even if the "brute force" scheme is selective.   
      
   If anyone is interested in looking into questions regarding the   
   Collatz conjecture, I suggest considering a generalization   
      
      f[k](n) = n/2 if n is even, 3n+k if n is odd, for an fixed odd k   
      
   Empirically you should quickly find   
      
      There is always a cycle starting at k.  (Duh!)   
      
      There is only one cycle if k is a power of 3.  (This result   
      follows from the Collatz conjecture.)   
      
      If k is not a power of 3, there are always at least two cycles,   
      and can be more.   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)