Picaxe takes on Collatz

[johnlong]

Hi All
The dark cold nights are here so skipping around youtube increases found a video on the Collatz
conjecture, and thought seems a nice little exercise for the picaxe

'The Collatz conjecture in mathematics asks whether repeating certain simple arithmetic operations will eventually transform every positive integer into one
'    If the number is even, divide it by two.
 '   If the number is odd, triple it and add one.
symbol steps=w5
symbol n=w0
symbol value=w6

main:
n=12

sertxd("value of n= ",#n,",")
do 
    steps=steps+1
    if n=1 then
        gosub fin
    elseif bit0=0 then gosub divide 'bit0 dictates if odd or even
    elseif bit0=1 then gosub tripple
    endif
    sertxd(#n,",")
    
loop
divide:'bit0 is even so divide by 2 
    n=n/2
    value=value+1'for resetting n start value
    return
tripple:'bit0 is odd tripple it and add 1
    n=n*3
    n=n+1
    value=value+1
    return
fin:    sertxd(cr,lf)
    sertxd("number of steps before n1= ",#steps,cr,lf)
    sertxd("next value for n= ",#value,cr,lf)
    n=value
    steps=0
    sertxd("value of n= ")
    return
[/code}

love the fact that every string ends in 5,16,8,4,2,1 irrespective of the starting value for n
regards john

 

[Buzby]

Great stuff, just the sort of project I like !.

From Wikipedia, "As of 2020, the conjecture has been checked by computer for all starting values up to 2^68".

It's going to take a Picaxe quite a long time to check any further just using 16 bit integers.

However, the Wikipedia article mentions a Binary Method, which is well suited to bit twiddling algorithms which can work on any length numbers.
It's quite a simple algorithm. It needs two 'registers' of whatever bit length you need to test, a 'left shift', a simple 'adder', some 'right shifts', and a method to detected the final value of 1.

Somehow I think its still going to take years for a Picaxe to check the conjecture past 68 bits.

It's still an unproven conjecture, so maybe it would be worth the wait to get your name in the record books .

Cheers,

Buzby

 

[AllyCat]

Hi,

You ought to at least test for an overflow in the "tripple" subroutine, for example with an IF n > 21845 THEN ... at its start.

It's interesting that the conjecture has been tested "only" to 2^68 which is a number easily stored in even a PICaxe 08M2. The number doesn't even expand very rapidly; a * 3 + 1 (of an odd number) will always produce an even number which is then divided by 2, so two iterations can only increase the value by about 1.5 . The two large integer "numbers" could be, for example, up to 400 bits each, stored in RAM bytes 28 to 127 (@bptr) of an 08M2. That would leave the registers b0 ... b27 and s_w1 to s_w6 for any calculation/housekeeping.

Division by 2 simply Shifts Right each byte by 1 bit, with the LSB of @bptr (before shifting) being added into the MSB of @(bptr-1) after shifting. Multiplication by 3 is simply a Shift-Left , then add the starting number, which again just needs a run through the bytes (e.g @bptrinc) to the "top" of the number, after adding 1 to the LSByte . A single "housekeeping" byte/word can keep track of the maximum size (number of bytes) currently being stored, to avoid unnecessary computation (of bytes containing leading zeros).

If you are only interested in "(dis-)proving" the conjecture (starting from zero), then all "even" numbers can be skipped (because division by 2 will reach a number already encountered/tested) and similarly, an even number produced by a first division by 2 would lead to a number smaller than previously encountered, i.e. n * 3 + 1 / 4 is less than n [EDIT:] each "candidate" number can be abandoned as soon as the computed value becomes lower. However, I've no idea how many consecutive "* 3 + 1" iterations might occur (when dealing with literally billions of billions of numbers) and suspect that a native 64-bit processor running with "Assembler" type code would be much faster than a PICaxe.

Cheers, Alan.