The Collatz Conjecture Is a Simple Problem That Mathematicians Can't Solve

Heater. · 2016-08-14 06:50

Beau Schwabe,

That much is all clear enough. As I said above this whole thing could be done pretty fast of a Prop using just shift and add in PASM. One could handle numbers has big as will fit into HUB RAM.

It certainly feels like there is a bias towards hitting a power of 2 and then rapidly falling to 1. However it's not yet proven that this is always the case for all numbers. There may well be a number out there for which the process gets stuck in a loop that does not include a power of 2.

Heater. · 2016-08-14 06:52

localroger,

Yes, all kinds of Windows programs work under Wine. I use it for running LTSpice on Linux.

However I'm not about to start programming in a language that requires a virtual machine, emulator or WINE to run my creations.

Beau Schwabe · 2016-08-14 07:29

You just have to handle the large numbers as if you were doing it long hand on paper, but write a program to keep track of the add and carry depending on what BASE you are doing the math operation in.

I had to do something recently like this to convert from 40-BIT binary to a 13 digit BCD and back from a 13 digit BCD to 40-BIT binary as well as ADD SUBTRACT MULTIPLY and DIVIDE ... all using long hand techniques applied within a program.

Heater. · 2016-08-14 08:11

Yep, just hold the numbers as arrays of longs in hub. Write the thing in PASM. Just shift and add operations on the array elements and ripple the carry up and down.

I was thinking that we need space for two huge numbers in order to do the 3n + 1 step, (n << 1) + n + 1. You need to hold the original value and the doubled value so as to add them together, so the limit would be about 260000 bit numbers. But now I have a suspicion on could do that step with just one working copy of the number so the entire 32K HUB could be used, 520000 bit numbers !

Of course it might take a while to run...

MikeDYur · 2016-08-14 12:40

Still going this morning, that's 24 hours. The Propeller should get a prize for completing this.

EDIT: finished processing 670617279 = 986 about twenty minutes ago.

tomcrawford · 2016-08-14 15:57

Turns out Propellor was born to do this. Here is an example of multiple cogs running identical PASM programs. The long pole is the Spin cog that issues numbers and checks the results for a new maximum iterations. This found the 966 (965 depending on how you count them) iteration seed at 537 099 606 in about 17 hours.

{Collatz}

CON
        _clkmode = xtal1 + pll16x    'Standard clock mode 
        _xinfreq = 5_000_000         '* crystal frequency = 80 MHz
        NmbrCogs = 4                  'number of calculator cogs
  
VAR                                       
  long  MyParm[6]                'passing addresses, etc to pasm cog
  byte  Cog       
  long  Command[NmbrCogs]                  'command to PASM
  long  Overflow[NmbrCogs]                 '<>0 says overflow
  long  Iterations[NmbrCogs]
  long  seedLo[Nmbrcogs]
  long  seedHi[NmbrCogs] 
  long  maxit
  long  MasterSeedLo
  long  MasterSeedHi
  byte  symbol
OBJ
  pst      : "parallax serial terminal"

  
PUB main
    pst.Start (115_200)                                   'start up ser terminal
    pst.str(String("hello, world   "))                    'runs in cog 1
    pst.NewLine
    waitcnt(clkfreq/10 + cnt) 

    repeat symbol from 0 to NmbrCogs - 1      
      MyParm[0] := @Command[symbol]               'initial value, then zeroed
      MyParm[1] := @Iterations[symbol]            'iteration count
      MyParm[2] := @Overflow[symbol]
      MyParm[3] := @SeedLo[symbol]
      MyParm[4] := @SeedHi[symbol]
      MyParm[5] := 1 << symbol            'this guy's pin mask    
      cog := cognew(@PCog, @MyParm)       'start up the output cog
      pst.str(string("Cog started:  "))
      pst.dec(cog)
      pst.newline

    MasterSeedLo := 1   'initialize
    MasterSeedHi := 0
    MaxIt := 0

    repeat symbol from 0 to NmbrCogs - 1    'get everybody started
      SeedHi[symbol] := 0
      SeedLo[symbol] := MasterSeedLo++
      Command[symbol] := 1

  repeat  
    repeat symbol from 0 to NmbrCogs - 1
      if(Command[symbol] == 0)   'wait for this guy to become avail
        if (Iterations[symbol] > maxit)    'if his iterations is greater
           pst.newline         
           pst.str(string("Cog: "))
           pst.dec(symbol)
           pst.str(string("  SeedHi: "))
           pst.dec(SeedHi[symbol])
           pst.str(string("  SeedLo: "))
           pst.dec(SeedLo[symbol])
           pst.str(string("  Iterations: "))
           pst.dec(Iterations[symbol])
           maxit := iterations[symbol]

        MasterSeedLo++
        if (MasterSeedLo == 0)
           MasterSeedHi++
        SeedHi[symbol] := MasterSeedHi
        SeedLo[Symbol] := MasterSeedLo
        command[symbol] := 1              'light it off
        
        if ((MasterSeedLo//1_000_000) == 0)
          pst.char(" ")
          pst.dec(MasterSeedLo/1_000_000)
          pst.char(" ")

DAT
PCog    org   0                '
        mov AdPar,Par          'get the address of input parameters
        rdlong AdCommand, AdPar 'command long
        add AdPar, #4
        rdlong AdIter, AdPar  'number of iterations
        add AdPar, #4
        rdlong AdErr, AdPar    'error flag
        add AdPar, #4
        rdlong AdSeedLo, AdPar  'seed low
        add AdPar, #4
        rdlong AdSeedHi, AdPar   'seed high
        add AdPar, #4
        rdlong PinMask, AdPar
        or dira, PinMask     '
                                                   
top     andn outa, PinMask
        rdlong workLo, AdCommand wz  'wait for a command
        if_z jmp #top                   'busy wait
        or outa, PinMask
        rdlong currentLo, AdSeedLo    'get current value
        rdlong currentHi, AdSeedHi
        mov trials, #0               'no iterations yet

Loop    add trials, #1
        cmp currentLo, #1 wz           'see if done
        if_NZ jmp #teo
        cmp currentHi, #0 wz
        if_Z jmp #done
teo     test currentLo, #1 wz          'test even/odd
        if_NZ jmp #ProcOdd            'go do odd case
        mov zero, zero wc              'clear carry           
        rcr currentHi, #1 wc             'divide by two
        rcr currentLo, #1         
        jmp #loop
        
ProcOdd mov workLo, currentLo             'odd case
        mov workHi, CurrentHi
        add currentLo,  workLo wc            'multiply by two
        addx currentHi, WorkHi
        add currentLo, workLo wc            'and three
        addx currentHi, workHi             '
        add currentLo, #1 wc              'add 1
        addx currentHi, #0       
        test currentHi, Bit31 wz        'test overflow
        if_NZ jmp #error                 
        jmp #loop
        
Done    wrlong trials, AdIter         'how many
        wrlong zero, AdErr            'no error
        wrlong zero, adcommand        
        jmp #top                
                                                  
Error   wrlong one, AdErr           'indicate failure
        wrlong trials, AdIter
        wrlong zero, AdCommand        'complete
        jmp #top     

zero        long  0
one         long  1
Bit31       long  $8000_0000
PinMask     res
AdPar       res                                                     
AdCommand   res
AdIter      res
AdErr       res
AdSeedHi    res
AdSeedLo    res
Trials      res
CurrentLo   res
CurrentHi   res
workLo      res
WorkHi      res

It uses double precision for the seed, so can go past the 2**32 limit. I plan to adapt it to a LCD display and let it run for a very long time.

Ron Czapala · 2016-08-14 17:30

MikeDYur wrote: »

Still going this morning, that's 24 hours. The Propeller should get a prize for completing this.

EDIT: finished processing 670617279 = 986 about twenty minutes ago.

Python takes about 2 seconds...

Ditto for 537099606

Processing ALL of the numbers from 1 to one million looking for the number with the most steps to reach 1 took about 32 seconds.

2016-08-14 15:01:11.858442
max 837799 steps 524
2016-08-14 15:01:43.648260

Here is the code:

from datetime import datetime
now = datetime.now()

print (now)
maxsteps = 0
maxval = 0
 
x = 1
while x < 1000000:
  steps = 0
  n = x
  while n > 1 :

    #print (n)
    if n & 1 :
        n = (n << 1) + n + 1
    else :
        n = n >> 1
    steps += 1


  #print (x, " - ", steps)

  if steps > maxsteps :
      maxsteps = steps
      maxval = x
      
  x += 1

now = datetime.now()
print ("max ", maxval, " steps ", maxsteps)
print (now)

Heater. · 2016-08-14 18:46

Yay Javascript, 5 seconds!

Python takes 40 seconds here also.

Note: This is good for integers up to 53 bits wide.

let maxsteps = 0;
let maxval = 0;

let x = 1;
let n;

while (x < 1000000) {
    steps = 0;
    n = x;
    while (n > 1) {
        //print (n)
        if (n & 1)
            n = 3*n + 1;
        else
            n = n / 2;
        steps += 1;
    }

    // console.log (x, " - ", steps);

    if (steps > maxsteps) {
        maxsteps = steps;
        maxval = x;
    }

    x += 1;
}

console.log ("max ", maxval, " steps ", maxsteps);

$ time node collatz.js
max  837799  steps  524

real    0m5.066s
user    0m0.000s
sys     0m0.000s

Ron Czapala · 2016-08-14 20:06

Heater. wrote: »

Yay Javascript, 5 seconds!

...
[/code]

I've never seen a "let" statement in javascript?!?

Here is a web page that runs a javascript function checking 1 to 1 million - faster than 5 seconds on my PC using Chrome

http://ronczap.home.insightbb.com/Collatz.htm

<HTML>
<HEAD>
<TITLECollatz Conjecture</TITLE>
<STYLE>
BODY
{
    SCROLLBAR-ARROW-COLOR: #0066cc;
    BACKGROUND-COLOR: ivory;
    BACKGROUND-REPEAT: repeat;
    SCROLLBAR-DARKSHADOW-COLOR: #fff8dc;
    SCROLLBAR-BASE-COLOR: #e6e6fa;
    FONT-FAMILY: Verdana, Courier, 'MS Sans Serif';
    SCROLLBAR-HIGHLIGHT-COLOR: #fff8dc;
    COLOR: blue;
    SCROLLBAR-SHADOW-COLOR: #e6e6fa;
    FONT-SIZE: 12px;
    SCROLLBAR-TRACK-COLOR: #fffff0
}
H2
{
    FONT-FAMILY: 'Comic Sans MS', Verdana, Courier;
    COLOR: mediumorchid
}
</STYLE>
<script type="text/javascript" language="javascript">

function Collatz(){
  var maxsteps = 0;
  var maxval = 0;

  var x = 1;
  var n;
  var steps;
  
  while (x < 1000000) {
    steps = 0;
    n = x;
    while (n > 1) {
        //print (n)
        if (n & 1)
            n = 3*n + 1;
        else
            n = n / 2;
        steps += 1;
    }
    if (steps > maxsteps) {
      maxsteps = steps;
      maxval = x;
//      alert(maxval + ' ' + maxsteps);
//      document.getElementById("answer").innerText = maxval + ' ' + maxsteps;
    }
    x += 1;
  }
  document.getElementById("answer").innerText = maxval + ' - ' + maxsteps + ' steps';
}
</script>
</HEAD>
<BODY>
<center>
<h2>Collatz Conjecture</h2>
<h3>all numbers between 1 and 1,000,000</h3>

<INPUT type="submit" value="Run Collatz" id=button1 name=button1 onclick="return Collatz()">
<br><br>
Answer: <div style="color:red" id="answer" name="answer">&nbsp;</div>
</center>
</BODY>
</HTML>

Heater. · 2016-08-14 20:30

"let" is a new feature of the Javascript standard ES2015 or ES6 as it was known. All the major browsers support "let" already. Along with a ton of other ES6 features.

Thing about "let" is that unlike "var" it is subject to block scope. Which is nice.

I can't run your code on the same machine, Surface Pro 4, at the moment but on this old Samsung laptop it does complete in about 2 seconds. Which is surprising as this should be an older slower machine.

Heater. · 2016-08-14 21:18

Ron,

Oh my God. I just tried my code and yours on the Surface again under node.js. Sure enough yours runs nearly 3 times faster!

Messing around with it a bit it seems that it's the "let" that slows it down. Changing my "let"s to "vars" gets it up to the same speed as yours.

Ron Czapala · 2016-08-14 22:03

Heater. wrote: »

Ron,

Oh my God. I just tried my code and yours on the Surface again under node.js. Sure enough yours runs nearly 3 times faster!

Messing around with it a bit it seems that it's the "let" that slows it down. Changing my "let"s to "vars" gets it up to the same speed as yours.

It really slows down with ten million too...

Sapphire · 2016-08-14 22:33

This is even faster, up to 70 million. But runs out of memory somewhere above that. Trick is saving the steps from lower computations, so once the value n is below x, just lookup the steps that remain. Around 5 seconds on my Win7 64-bit laptop.

Ron, can you try this on your web page?

var maxsteps = 0;
var maxval = 0;
var s = [];
var x = 1;
var n;

s[x] = 0;  // initialize for x=1

while (x < 70000000) { 
    steps = 0;
    n = x;
    while ((n > 1) && (n >= x)) { 
        if (n & 1)
            n = 3*n + 1;
        else
            n = n / 2;
        steps += 1;
    }
    steps += s[n];
    s[x] = steps;

    if (steps > maxsteps) {
        maxsteps = steps;
        maxval = x;
    }

    x += 1;
}

console.log ("max ", maxval, " steps ", maxsteps);

Ron Czapala · 2016-08-14 23:01

Sapphire wrote: »

This is even faster, up to 70 million. But runs out of memory somewhere above that. Trick is saving the steps from lower computations, so once the value n is below x, just lookup the steps that remain. Around 5 seconds on my Win7 64-bit laptop.

Ron, can you try this on your web page?

It seems to work - gets 63728127 - 949 steps - Guess that's correct.

MikeDYur · 2016-08-15 00:08

tomcrawford wrote: »

I plan to adapt it to a LCD display and let it run for a very long time.

That is the perfect display for this sort of thing, if your using the Parallax 4x20, I would like to see how you will display the relative information. Hope you share. -_-

If Ariba's PASM doesn't finish before bedtime, I may pull the plug. Though I would like to have it finish, I won't know when it did.

Heater. · 2016-08-15 05:20

Sapphire,

Your code runs in 4.9 seconds on my Surface Pro 4.

I can get it down to 2.7 seconds, about 45% faster !

How?

Firstly, declare "steps" at the top. This makes little difference to node.js but...

Secondly, install the new Microsoft build of node.js that uses their chakracore Javascript engine from the Edge browser. https://github.com/nodejs/node-chakracore
(Seems that missing declaration of step makes a big difference to chakra's performance, slowing it to 3.4 seconds)

Pretty amazing.

MikeDYur · 2016-08-15 12:12

Held in a virtual number enigma and not to be released until the proper code is entered, or I just goofed. I let it go for 48 hours and no conclusion. For my files, I think I will add a terminal bell to the process, to let me know things are still working.

MikeDYur · 2016-08-15 13:12

What do I need to run the JS version? it doesn't sound like it's a CPU benchmark, because of what Heater said about an old laptop. I would like to try it on a few computers here. Like HTML files, most of the code is in displaying the page.

Martin_H · 2016-08-15 13:29

For the Forth aficionados:

: odd? dup 1 and ;
: 3n+1 dup 2* + 1 + ;
: collatz(n) odd? if 3n+1 else 2/ then ;
: .n dup . ;
: collatz begin .n dup 1 = invert while collatz(n) repeat cr drop ;
15 collatz
1024 collatz
16385 collatz

15 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1 
1024 512 256 128 64 32 16 8 4 2 1 
16385 49156 24578 12289 36868 18434 9217 27652 13826 6913 20740 10370 5185 15556 7778 3889 11668 5834 2917 8752 4376 2188 1094 547 1642 821 2464 1232 616 308 154 77 232 116 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Heater. · 2016-08-15 13:30

I just saved the HTML above to a file (with .html) extension). Then find it in the file explorer and double click it. Select Chrome to run it in. Boom there is the web page.

Edit: Ah, sorry. If you want to run the .js files then you need node.js to run them: https://nodejs.org/en/

Or use Microsoft's version of node.js
https://github.com/nodejs/node-chakracore
https://github.com/nodejs/node-chakracore/releases

MikeDYur · 2016-08-15 13:49

Thanks Heater, Crome sounds like something I should have anyway but don't. Here's a screenshot of Tom's latest PASM, maybe about fifteen hours into it. Lots of info, wonder how he will cram that on a LCD.

Heater. · 2016-08-15 15:25

Should work as described for Edge or IE. Not that I have tried.

Heater. · 2016-08-15 16:40

I think Martin_H wins the prize for the most obfuscated Collatz program so far.

Is that a program or is the baud rate set wrong on the serial interface?

User Name · 2016-08-15 17:12

I liked Ariba's code so I thought I'd use it to make my own 6-cog version (with the seventh cog doing PST and the eighth cog being the spin boot cog). Right off the bat I realized that even numbers will never increase imax, so you can double the speed of the algorithm by considering only odd starting numbers. That plus six PASM cogs engaged in the search makes a 12x increase in speed. The Prop is not going to beat the i7 in your laptop, but it's not a bad speed improvement over the original Prop code.

mindrobots · 2016-08-15 17:59

If you're fretting over your Python code running slowly, there's always PyPy for a little boost in speed:
(using Ron C's program to 1,000,000 without the datetime captures)

[rapost@c3po python]$ time python collatz.py
max  837799  steps  524

real	1m8.855s
user	1m8.784s
sys	0m0.053s


[rapost@c3po python]$ time pypy3 collatz.py
max  837799  steps  524

real	0m2.262s
user	0m2.242s
sys	0m0.019s

using the JIT compiler on Python can add a boost if you are feeling a bit computationally bound! (Yes, that *IS* Python in 2.26 seconds)

tomcrawford · 2016-08-15 18:08

Mike, most of the info on that screen shot is just printing the number every time it is an even million.

Here is the first try at an LCD version; it needs a number of things done to it but I will be away from my computer for most of the rest of August. I am going to let it run as is during that time.
1. Increment the trial count after testing for "ONE" instead of before, so that it reports the correct number.
2. Print the number of iterations on the same line as the seed: HHBLLLLLLLLLLBIIII, for a total of 18 characters
3. Replace the spin "number Issue_er" with a PASM version; should speed things up by a factor of 3 or 4

It has found that highest one before one billion:

670 617 279 in 985 iterations.

Heater. · 2016-08-15 18:16

mindrobots,

Interesting, how does PyPy fare for the huge number of digits code back in my old post here:

http://forums.parallax.com/discussion/comment/1384963/#Comment_1384963

mindrobots · 2016-08-15 18:50

Heater.,

Here's your big Collatz with a side of PyPy:

[rapost@c3po python]$ time pypy3 big-collatz.py
73121761986832960825125652135550145392070469961663728781282106353340872357945129370313397212971441713875079029815189780467879972636287613195842871254....thar be many digits here...01815293452480070814311034410505
Steps 473522

real	0m1.350s
user	0m1.330s
sys	0m0.020s

Not much difference, actually. (This is on an older I3 laptop)

I also let it chew on 100,000,000 numbers instead of 1,000,000:

[rapost@c3po python]$ time pypy3 collatz.py
max  63728127  steps  949

real	4m52.661s
user	4m52.241s
sys	0m0.294s

I should try 1 billion next to see if it has memory issues

Ron Czapala · 2016-08-15 19:06

User Name wrote: »

I liked Ariba's code so I thought I'd use it to make my own 6-cog version (with the seventh cog doing PST and the eighth cog being the spin boot cog). Right off the bat I realized that even numbers will never increase imax, so you can double the speed of the algorithm by considering only odd starting numbers. That plus six PASM cogs engaged in the search makes a 12x increase in speed. The Prop is not going to beat the i7 in your laptop, but it's not a bad speed improvement over the original Prop code.

I'm not sure why people keep saying even numbers "don't increase" ????

Numbers that a factors of 2 (e.g. 2 4 8 16 32 64 128) go to 1 very quickly because no intermediate values will be odd.

But most even numbers become odd numbers when divided by two and then the intermediate values go UP when multiplied by 3 and then add 1....

Even numbers and factors of two are different animals all together!

Look at the 15 steps for the number 22:
-> 22
1. 11
2. 34
3. 17
4. 52
5. 26
6. 13
7. 40
8. 20
9. 10
10. 5
11. 16
12. 8
13. 4
14. 2
15. 1

However,
This list shows the numbers which bump the maximum step count when ranging from 1 to 1 million
and 18 and 54 are the only even numbers which bump the max
Note: you can see this effect here: http://ronczap.home.insightbb.com/Collatz4.htm - (It run a little slower due to building the list)

2 - 1 steps
3 - 7 steps
6 - 8 steps
7 - 16 steps
9 - 19 steps
18 - 20 steps
25 - 23 steps
27 - 111 steps
54 - 112 steps
73 - 115 steps
97 - 118 steps
129 - 121 steps
171 - 124 steps
231 - 127 steps
313 - 130 steps
327 - 143 steps
649 - 144 steps
703 - 170 steps
871 - 178 steps
1161 - 181 steps
2223 - 182 steps
2463 - 208 steps
2919 - 216 steps
3711 - 237 steps
6171 - 261 steps
10971 - 267 steps
13255 - 275 steps
17647 - 278 steps
23529 - 281 steps
26623 - 307 steps
34239 - 310 steps
35655 - 323 steps
52527 - 339 steps
77031 - 350 steps
106239 - 353 steps
142587 - 374 steps
156159 - 382 steps
216367 - 385 steps
230631 - 442 steps
410011 - 448 steps
511935 - 469 steps
626331 - 508 steps
837799 - 524 steps

MikeDYur · 2016-08-15 19:41

tomcrawford wrote: »

Here is the first try at an LCD version;

Thank you Tom, I can give the PCs a break. Going to get a Propeller setup right now with this.

The Collatz Conjecture Is a Simple Problem That Mathematicians Can't Solve

Comments