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

Ron Czapala · 2016-08-10 15:13

http://www.popularmechanics.com/technology/news/a22246/simple-problem-that-still-stumps-mathematicians/

Part of the beauty of mathematics is that seemingly simple patterns lead to much more complicated questions and theories. The Collatz conjecture, which is the subject of a new video from YouTube channel Numberphile, is the perfect example of a simple problem that even the greatest mathematical minds in the world haven't been able to solve.

The essence of the question is simple. We have an interesting pattern: If you take a positive integer, and then divide by 2 if it is even, or multiply by 3 and add 1 if it is odd, then repeat this process with the resulting number, eventually you will end up with the number 1. Professor David Eisenbud of the University of California, Berkeley, demonstrates this process, also known as the hailstone sequence, using the number 7 in the video.

Heater. · 2016-08-10 15:32

I watched that yesterday. Love numberphile.

KeithE · 2016-08-10 15:42

And the obligatory: https://xkcd.com/710/

MikeDYur · 2016-08-10 16:12

It's tricks like this that get kids interested in math.

erco · 2016-08-11 01:12

This math wizard conjures his baffling manner of sorcery on Youtube.

Pick a number. Now subtract your number. You have....................... ZERO!

localroger · 2016-08-11 01:46

I'm sure Inter-Universal Teichmuller Theory will make short work of this.

Ron Czapala · 2016-08-11 13:28

localroger wrote: »

I'm sure Inter-Universal Teichmuller Theory will make short work of this.

It's been around since 1937 with no solution yet...

The longest progression for any initial starting number less than 100 million is 63,728,127, which has 949 steps. For starting numbers less than 1 billion it is 670,617,279, with 986 steps, and for numbers less than 10 billion it is 9,780,657,631, with 1132 steps

https://en.wikipedia.org/wiki/Collatz_conjecture

http://io9.gizmodo.com/5813673/the-easiest-math-conjecture-it-took-74-years-to-prove (NOT)

MikeDYur · 2016-08-11 15:27

It would be fun to watch the Propeller do the math on the PST, slowed down to see what's happening.

Ron Czapala · 2016-08-11 15:51

I wrote a little vbscript to do the job, but it overflows with large numbers...

Save it as a .vbs file and double-click it to run.

Option Explicit

Dim val1, cntr, result, idata

  val1 = inputbox("Enter starting number",  "The Collatz Conjecture")
  val1 = CLng(val1)
  cntr = 0
  idata = val1	
  do
    if val1 = 1 then
      exit do
    end if
    result = clng(val1 Mod 2)
    if result = 0 then
      val1 = val1 / 2
    else
      val1 = (val1 * 3) + 1   
    end if
    cntr = cntr + 1
    idata = idata & "," & val1    
  loop
  msgbox idata,,cntr & " Loops"

MikeDYur · 2016-08-11 16:14

Great start, Thanks Ron.

I may have been able to come up with something like this but, it might have taken awhile. I don't have any problem setting up pst, I want to make it kid friendly, and they can check their progress.

MikeY

Duane Degn · 2016-08-11 16:55

Edit: I made a mistake. I'll post it again in a couple minutes.

Duane Degn · 2016-08-11 17:00

MikeDYur wrote: »

It would be fun to watch the Propeller do the math on the PST, slowed down to see what's happening.

Try this program.

CON
  _clkmode = xtal1 + pll16x
  _xinfreq = 5_000_000

  BAUD = 115200
  QUOTE = 34
  UPPERLIMIT = posx / 3 - 1  ' I'm not sure if this is a low enough value.
  
OBJ

   Pst: "Parallax Serial Terminal"
   
PUB Main | stepCount

  Pst.Start(BAUD)

  repeat
    waitcnt(clkfreq / 2 + cnt)
    result := Pst.RxCount
    Pst.Str(string(11, 13, "Press any key to begin."))
  until result

  Pst.RxFlush
  
  repeat
    stepCount := 0
    Pst.Str(string(11, 13, 11, 13, "Collatz Conjecture"))
    Pst.Str(string(11, 13, 11, 13, "Enter a positive interger between ", QUOTE, "1", QUOTE, " and ", QUOTE))
    Pst.Dec(UPPERLIMIT)
    Pst.Str(string(QUOTE, "."))   
    result := Pst.DecIn
    Pst.Str(string(11, 13, "You entered ", QUOTE))
    Pst.Dec(result)
    Pst.Str(string(QUOTE, "."))
    if CheckForInputError(result)
      next ' start loop from beginning
    repeat while result <> 1
      Pst.Str(string(11, 13, "Step # "))
      Pst.Dec(++stepCount)
      Pst.Str(string(": The value ", QUOTE))
      Pst.Dec(result)
      Pst.Str(string(QUOTE, " is "))
      result := CheckType(result)
      waitcnt(clkfreq / 4 + cnt) 
     
    Pst.Str(string(13, 11, "The value 1 was reached in "))
    Pst.Dec(stepCount)
    Pst.Str(string(" steps."))
 
PUB CheckType(value)

  
  if value & 1 ' odd
    result := value * 3 + 1
    Pst.Str(string("odd. Mulitplying by 3 and adding 1"))     
  else
    result := value / 2
    Pst.Str(string("even. Dividing by 2"))

  Pst.Str(string(" which equals "))
  Pst.Dec(result)
  Pst.Char(".")

PUB CheckForInputError(value)

  if value < 1 or value > UPPERLIMIT
    Pst.Str(string(11, 13, "The value ", QUOTE))
    Pst.Dec(value)
    Pst.Str(string(QUOTE, " is not a valid entry."))
    result := true     ' "true" is also -1 or $FFFFFFFF or %11111111111111111111111111111111 (32 bits of all ones)

Here's the output when 7 is used as the input.

Press any key to begin.

Collatz Conjecture

Enter a positive interger between "1" and "715827881".
You entered "7".
Step # 1: The value "7" is odd. Mulitplying by 3 and adding 1 which equals 22.
Step # 2: The value "22" is even. Dividing by 2 which equals 11.
Step # 3: The value "11" is odd. Mulitplying by 3 and adding 1 which equals 34.
Step # 4: The value "34" is even. Dividing by 2 which equals 17.
Step # 5: The value "17" is odd. Mulitplying by 3 and adding 1 which equals 52.
Step # 6: The value "52" is even. Dividing by 2 which equals 26.
Step # 7: The value "26" is even. Dividing by 2 which equals 13.
Step # 8: The value "13" is odd. Mulitplying by 3 and adding 1 which equals 40.
Step # 9: The value "40" is even. Dividing by 2 which equals 20.
Step # 10: The value "20" is even. Dividing by 2 which equals 10.
Step # 11: The value "10" is even. Dividing by 2 which equals 5.
Step # 12: The value "5" is odd. Mulitplying by 3 and adding 1 which equals 16.
Step # 13: The value "16" is even. Dividing by 2 which equals 8.
Step # 14: The value "8" is even. Dividing by 2 which equals 4.
Step # 15: The value "4" is even. Dividing by 2 which equals 2.
Step # 16: The value "2" is even. Dividing by 2 which equals 1.
The value 1 was reached in 16 steps.

Collatz Conjecture

Enter a positive interger between "1" and "715827881".

Edit: I didn't set "stepCount" to zero with each new number being tested. The embedded code is fixed but I need to attach the fixed code to a different post. I can't change which files are attached in an edit. See post below for fixed program.

Heater. · 2016-08-11 17:24

Clearly we need to do this in binary. Just hold your number as an array of longs.

Divide by 2 is only a shift down by one of all the bits in the array.

Mull by 3 and is only a shift up by one of all the bits then add the original number. Long by long, rippling the carry up.

Add 1 is easy.

Testing that you have hit 1 is easy.

This enables us to work with numbers of hundreds or thousands of bits. Depends how long you want to wait for it to run.

The intermediate steps could be easily displayed in hexadecimal.

Converting those big numbers to decimal display is a bit more tricky.

Ron Czapala · 2016-08-11 17:31

Duane Degn wrote: »

MikeDYur wrote: »

It would be fun to watch the Propeller do the math on the PST, slowed down to see what's happening.

Try this program.

UPPERLIMIT = posx / 3 - 1 ' I'm not sure if this is a low enough value.

I doubt that this limit will work because the intermediate calculation results can go way higher (and lower) than the starting value before coming back down to 1.

e.g.

63728124
31864062
15932031
47796094
23898047
71694142
35847071
107541214
53770607
161311822
80655911
241967734
120983867
362951602
181475801
544427404
272213702
136106851
408320554
204160277
612480832
306240416
153120208
76560104
38280052
19140026
9570013
28710040
14355020
7177510
3588755
10766266
5383133
16149400
8074700
4037350
2018675
6056026
3028013
9084040
4542020
2271010
1135505
3406516
1703258
851629
2554888
1277444
638722
319361
958084
479042
239521
718564
359282
179641
538924
269462
134731
404194
202097
606292
303146
151573
454720
227360
113680
56840
28420
14210
7105
21316
10658
5329
15988
7994
3997
11992
5996
2998
1499
4498
2249
6748
3374
1687
5062
2531
7594
3797
11392
5696
2848
1424
712
356
178
89
268
134
67
202
101
304
152
76
38
19
58
29
88
44
22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1

Duane Degn · 2016-08-11 18:20

I agree, the "UPPERLIMIT" value I used isn't a safe number. I'm writing a program to find the lowest start value which will cause a 32-bit overflow (a signed 32-bit number like those used in the Propeller).

I've attached the fixed code which is embedded in an earlier post. I forgot to clear the "stepCount" variable.

Heater. · 2016-08-11 18:38

Perhaps if you could determine the UPPERLIMT prior to running the code you might get a Fields medal.

(Only for those under 40 years of age)

MikeDYur · 2016-08-11 18:52

Ron,
I haven't got past checking for odd or even numbers, It will take a bit to catch up with the thread. I take it back, I can read VB and understand what's going on in your script. Don't think I could write one though.

EDIT: That cool Duane, I wish I could put something together that quick. I need examples most of the time.

We are going to be watching four of the grandkids for four days in a couple of weeks, three of them can do this math, should keep them busy for an hour or two.

Thanks guys.

Heater. · 2016-08-11 19:07

Duane Degn,

I think one should check for overflow on every "n*3" and then "+ 1" operation.

After all the user could input $10000000 which would go to 1 very fast but is much bigger than your UPPERLIMIT.

Heater. · 2016-08-11 19:08

MikeDYur ,

We are going to be watching four of the grandkids for four days in a couple of weeks, three of them can do this math, should keep them busy for an hour or two.

That is cruel and unusual punishment

Phil Pilgrim (PhiPi) · 2016-08-11 19:11

You only need to compare odd results to the upper limit. Even results always diminish.

-Phil

MikeDYur · 2016-08-11 19:18

Heater. wrote: »

That is cruel and unusual punishment

You are so right, they might put the prop though it for an hour maybe.

Ron Czapala · 2016-08-11 19:26

Here is an updated vbscript - it creates a text file called Collatz.txt on your desktop with the results...

Option Explicit

Dim fso, WshShell, ts, outFile, desktop
Dim val1, cntr, result, idata

  Set fso = CreateObject("Scripting.FileSystemObject")
  set WshShell = WScript.CreateObject("Wscript.Shell")

  desktop = WshShell.SpecialFolders("Desktop")
  outFile = fso.BuildPath(desktop, "Collatz.txt")

  val1 = inputbox("Enter starting number",  "The Collatz Conjecture")
  if val1 = "" then
    wscript.quit  
  end if

  set ts = fso.CreateTextFile(outFile, True, False)
  val1 = CLng(val1)
  if val1 < 1 then
    msgbox "Value must be > 0", vbcritical, "Error" 
    wscript.quit
  end if
  ts.writeline "-> " & val1
  cntr = 0
  idata = val1	
  do
    if val1 = 1 then
      exit do
    end if
    result = clng(val1 Mod 2)
    if result = 0 then
      val1 = val1 / 2
    else
      val1 = (val1 * 3) + 1   
    end if
    cntr = cntr + 1
    ts.writeline cntr & ". " & val1
    idata = idata & "," & val1    
  loop
  msgbox idata,vbinformation,cntr & " Loops " & outFile
  ts.close  
  set fso = nothing

MikeDYur · 2016-08-11 19:29

This could definitely use some paper, eight digits got me 183 steps. A lot more fun to watch the Propeller do the math.

Heater. · 2016-08-11 19:33

Phil,

You only need to compare odd results to the upper limit. Even results always diminish.

That's what I said Phil.

Except one can optimize that by checking that by checking "n*3" by UPPERLIMIT - 1 such that the "+1" will never fail.

MikeDYur · 2016-08-11 19:52

Sombody have an explanation why 600 produces 17 steps, and 601 is done in 56. Just one number different, It is amazing.

EDIT: 603 took 69 steps, 604 took 17 again, it seems odd numbers take three times the steps.

Heater. · 2016-08-11 19:59

MikeDYur,

Like I said, if one could answer such questions one would probably have proved or disproved the conjecture. Thus becoming a Fields medal winner.

Ron Czapala · 2016-08-11 20:00

deleted

Heater. · 2016-08-11 20:17

I don't see anything related to the current topic on that link Ron.

Heater. · 2016-08-11 20:19

Ah, sorry Ron, that link is in your sig. The thin dotted line separating post content from the sig did not show up on this crappy laptop screen.

tomcrawford · 2016-08-11 20:20

MikeDYur wrote: »

We are going to be watching four of the grandkids for four days in a couple of weeks, three of them can do this math, should keep them busy for an hour or two.

Thanks guys.

Count your blessings, MikeDYur. Sixteen GrandKidDays is a gift from the Gods.

MikeDYur · 2016-08-11 20:21

24684 came up with 263,

Heater, I missed your comment above,

Mr. Lothar Collatz is a brain to come up with it, and it's just simple math.

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

Comments