Sorry guys, for taking up space. I should have been learning with my mouth closed.
The Millennium Prize Problems are seven problems in mathematics that were stated by the Clay Mathematics Institute in 2000. The problems are Birch and Swinnerton-Dyer conjecture, Hodge conjecture, Navier–Stokes existence and smoothness, P versus NP problem, Poincaré conjecture, Riemann hypothesis, and Yang–Mills existence and mass gap. A correct solution to any of the problems results in a US $1M prize (sometimes called a Millennium Prize) being awarded by the institute. The only solved problem is the Poincaré conjecture, which was solved by Grigori Perelman in 2003.
I wrote another vbscript that varies a number from 1 to 113,382 (see below)
It processes each value in that range to determine how many loops it takes to reach 1 and appends the result to a text file.
It also keeps track of the maximum loop count as it goes.
The max count was 353 when the variable value was 106,239.
When the variable hit 113,383, it caused an overflow during the calculations when an intermediate value reached 827,370,449 and it tried to multiply it by 3...
Vbscript long values range from -2,147,483,168 to 2,147,483,647.
The output file size was 1.35MB.
EDIT:
I tweaked the script again to range from 1 to 262,144 (256K) and to trap/count overflow errors.
There were 23 overflow errors.
Excluding those, the highest count was 442 for number 230,631.
You know I always thought Mathematics was exacting, it has anomalies, voids, spaces that are unexplained, that's something.
I got my B.A. in Mathematics - there are various abstract pieces, like abstract geometry where all parallel lines intersect and abstract algebra where A times B is NOT equal to B times A, etc
Thank you for the education fellas, the lack of a good foundation in math, defines anything I can do in programming. I regret that I didn't "STAY IN SCHOOL" and get that education. I would enjoy this hobby a lot more if I could do the math.
This conjecture is one example of simple math, and how it achieves a consistent answer, when the process could be so different from one number to the next. Example: The number 4444=33 steps, 4445=33 steps but 4446=183 steps. No rhyme or reason though 4446 is an even number and at first glance I would think, all you had to was devide by two to eventually achieve the answer of one.
Sure am glad Ron posted this, and for his help in the understanding. Thanks Duane for the neat little spin on it, I would have been bored in a half hour doing this on paper, likewise with a calculator. And thanks Heater for the explanations, it takes me and my dusty brain a little while to catch up sometimes. Your a good teacher, for the patient way of explaining something without blowing my mind with the technical.
Count your blessings, MikeDYur. Sixteen GrandKidDays is a gift from the Gods.
Oh no Tom, only seven grandkids, not sure there is the energy in my wife and I for sixteen, as a matter of fact we don't. We seem to be watching them more lately, and they are surly a blessing from above, but they take a lot out of you, thank heaven to for the recovery time.
Mike, I hope you noticed there's a delay in the code. If you want the program to run faster you can comment out the "waitcnt(clkfreq / 4 + cnt)" line.
I didn't specifically look for one, but I was sure the Propeller could spit this out as fast as it could be displayed. I may try a binary display of the answers on one of those dot matrix displays.with an incremented repeat on the input, that should make the LEDs dance, give that retro computer look and have a good reason for it.
{Collatz}
CON
_clkmode = xtal1 + pll16x 'Standard clock mode
_xinfreq = 5_000_000 '* crystal frequency = 80 MHz
VAR
long Command 'command to PASM cog, initial value
long MyParm[6] 'passing addresses, etc to pasm cog
byte Cog 'keeps track of cog number (+1)
long Overflow '<>0 says overflow
long Iterations
long seed
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)
MyParm[0] := @Command 'initial value, then zeroed
MyParm[1] := @Iterations 'iteration count
MyParm[2] := @Overflow
cog := cognew(@PCog, @MyParm) 'start up the output cog
pst.str(string("Cog started: "))
pst.dec(cog)
pst.newline
seed := 1
repeat
Command := seed 'give cog something to chew on
repeat while (Command <> 0) 'wait for it
pst.str(string("Seed: "))
pst.dec(seed)
If (Overflow == 0)
pst.str(string(" Iterations: "))
pst.dec(Iterations)
else
pst.str(string("Failure: Out of range with "))
pst.dec(Iterations)
pst.str(string(" iterations."))
repeat 'die for now
seed++
pst.newline
waitcnt(clkfreq/1000 + cnt)
DAT
PCog org 0 '
mov AdPar,Par 'get the address of input parameters
rdlong AdCommand, AdPar 'command word
add AdPar, #4
rdlong AdIter, AdPar 'number of iterations
add AdPar, #4
rdlong AdErr, AdPar 'error flag '
or dira, mask0 'instrumentation
or dira, mask1
or dira, Mask2
top andn outa, mask0
rdlong work, AdCommand wz 'wait for a command
if_z jmp #top 'busy wait
or outa, mask0
mov current, work 'get current value
mov trials, #0 'no iterations yet
Loop add trials, #1
cmp current, #1 wz 'see if done
if_Z jmp #done
test current, #1 wz 'test even/odd
if_NZ jmp #ProcOdd 'go do odd case
or outa, mask1
shr current, #1 'divide by two
andn outa, mask1
jmp #loop
ProcOdd or outa, mask2
mov work, current 'odd case
add current, work 'multiply by two
add current, work 'and three
andn outa, mask2 '
add current, #1 'add 1
test current, 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
mask0 long 1
mask1 long 2
mask2 long 4
AdPar res
AdCommand res
AdIter res
AdErr res
Trials res
Current res
work res
Tom, if you get a chance sometime could you post this as a spin document, I either have to type this in (4.2wpm) or reformat the copied text. (confusing with pasm). Code block just dosn't migrate well from phone to computer.
Never mind that VB nonsense. Sometimes you just have to love Python. How about 64K bit long numbers, about 20000 decimal digits:
$ cat collatz.py
from random import randint
# A 64Kbit long number
n = randint(pow(2, 65534), pow(2, 65535))
print n
steps = 0
while n > 1 :
#print n
if n & 1 :
n = (n << 1) + n + 1
else :
n = n >> 1
steps += 1
print "Steps", steps
$ time python collatz.py
9213189413433.....
................. a big lot of digits .......
335451721599033877974368
Steps 473026
real 0m1.321s
user 0m1.265s
sys 0m0.015s
Here is Spin/PASM Version that works with 64bit intermediate results.
It shows also the correct result for 670,617,279, with 986 steps.
The Spin code only shows results that are bigger then the previous, so just let it run until it reaches the max positve 32bit value, then the last line shown is the one with the most iterations. This should take about an hour (not tried so far).
After RUN it expects that you type in the start value then return.
CON
_clkmode = xtal1 + pll16x
_xinfreq = 5_000_000
OBJ
term : "Parallax Serial Terminal"
VAR
long start, iter
long imax
PUB Main
term.start(115200)
iter := 1
cognew(@Asm,@iter)
waitcnt(clkfreq*3 + cnt)
term.str(string(13,"start with: "))
start := term.DecIn #> 2
repeat
iter := 0
repeat until iter
if iter > imax
term.str(string(13,"Process: "))
term.dec(start)
term.str(string(" = Iterations: "))
term.dec(iter)
imax := iter
waitcnt(clkfreq/5 + cnt)
start++
until start == posx
term.str(string(13,"done"))
DAT
org 0
Asm rdlong t0,par wz 'wait for value written
if_nz jmp #Asm
mov p1,par
sub p1,#4
rdlong L0,p1 'get value from Spin vars
mov L1,#0
neg cntr,#1 'init cntr
Loop add cntr,#1
cmp L0,#1 wz
if_z cmp L1,#0 wz
if_z jmp #done
test L0,#1 wc 'Odd or Even?
if_c jmp #Odd
shr L1,#1 wc 'Even
rcr L0,#1 '/2
jmp #Loop
Odd mov t0,L0 'Odd
mov t1,L1
add L0,L0 wc '*2
addx L1,L1
add L0,t0 wc '+ *1
addx L1,t1
add L0,#1 wc '+1
addx L1,#0
jmp #Loop
done wrlong cntr,par 'write result to iter var
jmp #Asm
t0 res 1
t1 res 1
L0 res 1
L1 res 1
cntr res 1
p1 res 1
Ariba, Your program shows results in an interesting way, I ran it last evening, couldn't hold my eyes open after about an hour. Went to bed and left laptop and QuickStart running, laptop went in to screensaver and stopped progress. Restarted from number 2 this morning, it has been over an hour now and the Propeller is still working hard. I really like how you showed maximum iterations, it could use a working indicator though, I guess the most universal would be something on the PST, as there are substantial durations in processing the bigger numbers.
Never mind that VB nonsense. Sometimes you just have to love Python.
...
I wouldn't call VB (or vbscript) nonsense - they are powerful, especially when it comes to running and interacting with activex modules like Internet Explorer, Excel, MS Access databases, etc.
However, I downloaded the Python 3.5.2 64-bit Windows version and ran your code for the number 9780657631 and got 1132 steps - the correct answer.
It certainly was fast and handles larger numbers that vb. Apparently there are some syntax differences with the version you are using - "print" requires parenthesis...
Just my little jape Ron. "non-sense" in the context of this thread is about the inability of VB to handle huge numbers where as Python does it with ease. As you see.
I'm no great fan of Python. What with it not having any standardization. As you see the syntax has changed from version 2 to version 3, or whatever versions it was, breaking stuff. For example "print" is no longer built into the language syntax but provided as a "print()" library function now. Also I hate the white space block delimiting thing. And why does a basically line based language need ":" after "if" statements and such. Even Spin got that right.
VB does not appeal to me. It does not work outside of Windows. It also is not a standardized language.
VB in the browser, activex, is a really bad idea for many reasons. Luckily Microsoft have seen the error of their ways and do not support activex in their new Edge browser. As for interacting with databases that is easy enough in most languages.
Turns out that the big number support in Python is not so hot. I forget the limit now but eventually things get too big. If you really need that then you need to turn to a big number library. At that point the only reason I can think of for using Python goes away.
This should take about an hour (not tried so far).
I'm determined to wait this out Ariba, last process 169941673 = 953, it is still going to be awhile if 670617279 with 986 iterations, is the last process before overflow. I certainly understand the time involved, considering the size of the number and steps involved.
Use anything long enough and you start to get annoyed by all the down sides and limitations. Then you are convinced you can design a better language. If you are skillful enough you do so.
That's why programming languages grow like weeds.
Not only programming languages but languages for humans. See the history of the Volapük language, which had a million speakers at one point, and how that soon fragmented into chaos. https://en.wikipedia.org/wiki/Volapük
VB is more like Latin. Back in the day if your were in the church you learned Latin. If not you did not. The VB church is MS and Windows. It's not about language merits. It's about power and money.
VB does not appeal to me. It does not work outside of Windows.
VB6 works just fine in Linux under Wine. You do need to snag a copy of the one .dll it needs which has been included with Windows since Win2K. As for that dot-net nonsense, it's an abomination and who cares where it might or might not work.
Couldn't stay up for the conclusion, need more excitement for that. Too busy checking this on paper, get back with the results in two months. As long as ink and paper hold out.
I have been looking at the numbering sequence in binary rather than base 10 and using binary math methods.
N*3 + 1
can be re-written in binary as ...
(N*4 - N) +1 EDIT: N*2+N+1 works also
...or....
LEFT shift by 2 , subtract the original number, add 1.
Anyway, the KEY in the result always distilling to a "1" may be better viewed from a binary approach.
EVEN RULE ) An EVEN number is repeatedly right shifted until it becomes ODD ... this is a simple divide by two ... if that ODD number happens to be a 1 we stop, if it's not a 1 then we apply the rule for an ODD number.
ODD RULE) An ODD number is left shifted twice ... this is a simple multiply by four ... This produces a temporary even number ... subtracting the original ODD number from the temp number produces a temporary odd number ... adding a ONE ... produces a result that will always EVEN.
The 'BIAS' towards always distilling to a value of 1 is a derivative from the EVEN rule and driven towards a 1 with the most weight when the EVEN number result is a power of 2.
It's this power of 2 that is the key here .... taking that aside, simply put ... if the number is EVEN the rule produces an ODD, if the number is ODD the rule produces an EVEN. However there is an underlying bias that if that EVEN number happens to be a power of 2 then the resulting number will ALWAYS be a "1".
Comments
I wrote another vbscript that varies a number from 1 to 113,382 (see below)
It processes each value in that range to determine how many loops it takes to reach 1 and appends the result to a text file.
It also keeps track of the maximum loop count as it goes.
The max count was 353 when the variable value was 106,239.
When the variable hit 113,383, it caused an overflow during the calculations when an intermediate value reached 827,370,449 and it tried to multiply it by 3...
Vbscript long values range from -2,147,483,168 to 2,147,483,647.
The output file size was 1.35MB.
EDIT:
I tweaked the script again to range from 1 to 262,144 (256K) and to trap/count overflow errors.
There were 23 overflow errors.
Excluding those, the highest count was 442 for number 230,631.
Why is that spooky? Dividing 666 by 2 gives 333 - everything is identical after that...
That will happen with any two numbers where one is twice the other!!
I got my B.A. in Mathematics - there are various abstract pieces, like abstract geometry where all parallel lines intersect and abstract algebra where A times B is NOT equal to B times A, etc
That does not mean there aren't things we are to dumb to have worked out yet. See Millennium Prize problems for example.
That does not mean there aren't mathematical statements that we cannot prove to be true or false in principle. See Gödel: https://en.wikipedia.org/wiki/Gödel's_incompleteness_theorems
That does not mean that:
1 + 2 + 3 + 4 + 5 ... = -1/12
is not true. For some definition of infinite sum.
Heck, the differential calculus manages to divide 0 by 0 and get a sensible result!
This conjecture is one example of simple math, and how it achieves a consistent answer, when the process could be so different from one number to the next. Example: The number 4444=33 steps, 4445=33 steps but 4446=183 steps. No rhyme or reason though 4446 is an even number and at first glance I would think, all you had to was devide by two to eventually achieve the answer of one.
Sure am glad Ron posted this, and for his help in the understanding. Thanks Duane for the neat little spin on it, I would have been bored in a half hour doing this on paper, likewise with a calculator. And thanks Heater for the explanations, it takes me and my dusty brain a little while to catch up sometimes. Your a good teacher, for the patient way of explaining something without blowing my mind with the technical.
Oh no Tom, only seven grandkids, not sure there is the energy in my wife and I for sixteen, as a matter of fact we don't. We seem to be watching them more lately, and they are surly a blessing from above, but they take a lot out of you, thank heaven to for the recovery time.
Mike, I hope you noticed there's a delay in the code. If you want the program to run faster you can comment out the "waitcnt(clkfreq / 4 + cnt)" line.
I didn't specifically look for one, but I was sure the Propeller could spit this out as fast as it could be displayed. I may try a binary display of the answers on one of those dot matrix displays.with an incremented repeat on the input, that should make the LEDs dance, give that retro computer look and have a good reason for it.
Thanks for the HU.
MikeY
{Collatz} CON _clkmode = xtal1 + pll16x 'Standard clock mode _xinfreq = 5_000_000 '* crystal frequency = 80 MHz VAR long Command 'command to PASM cog, initial value long MyParm[6] 'passing addresses, etc to pasm cog byte Cog 'keeps track of cog number (+1) long Overflow '<>0 says overflow long Iterations long seed 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) MyParm[0] := @Command 'initial value, then zeroed MyParm[1] := @Iterations 'iteration count MyParm[2] := @Overflow cog := cognew(@PCog, @MyParm) 'start up the output cog pst.str(string("Cog started: ")) pst.dec(cog) pst.newline seed := 1 repeat Command := seed 'give cog something to chew on repeat while (Command <> 0) 'wait for it pst.str(string("Seed: ")) pst.dec(seed) If (Overflow == 0) pst.str(string(" Iterations: ")) pst.dec(Iterations) else pst.str(string("Failure: Out of range with ")) pst.dec(Iterations) pst.str(string(" iterations.")) repeat 'die for now seed++ pst.newline waitcnt(clkfreq/1000 + cnt) DAT PCog org 0 ' mov AdPar,Par 'get the address of input parameters rdlong AdCommand, AdPar 'command word add AdPar, #4 rdlong AdIter, AdPar 'number of iterations add AdPar, #4 rdlong AdErr, AdPar 'error flag ' or dira, mask0 'instrumentation or dira, mask1 or dira, Mask2 top andn outa, mask0 rdlong work, AdCommand wz 'wait for a command if_z jmp #top 'busy wait or outa, mask0 mov current, work 'get current value mov trials, #0 'no iterations yet Loop add trials, #1 cmp current, #1 wz 'see if done if_Z jmp #done test current, #1 wz 'test even/odd if_NZ jmp #ProcOdd 'go do odd case or outa, mask1 shr current, #1 'divide by two andn outa, mask1 jmp #loop ProcOdd or outa, mask2 mov work, current 'odd case add current, work 'multiply by two add current, work 'and three andn outa, mask2 ' add current, #1 'add 1 test current, 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 mask0 long 1 mask1 long 2 mask2 long 4 AdPar res AdCommand res AdIter res AdErr res Trials res Current res work resThanks MikeY
-Phil
That's pretty dang cool, there's a visable pattern of same iterations here. You guy's are going to crack this with the Propeller.
EDIT: BTW, if this thread has taught me anything it's, always use positive numbers, you always end up with something.
$ cat collatz.py from random import randint # A 64Kbit long number n = randint(pow(2, 65534), pow(2, 65535)) print n steps = 0 while n > 1 : #print n if n & 1 : n = (n << 1) + n + 1 else : n = n >> 1 steps += 1 print "Steps", stepsPropeller should be able to handle this.
It shows also the correct result for 670,617,279, with 986 steps.
The Spin code only shows results that are bigger then the previous, so just let it run until it reaches the max positve 32bit value, then the last line shown is the one with the most iterations. This should take about an hour (not tried so far).
After RUN it expects that you type in the start value then return.
CON _clkmode = xtal1 + pll16x _xinfreq = 5_000_000 OBJ term : "Parallax Serial Terminal" VAR long start, iter long imax PUB Main term.start(115200) iter := 1 cognew(@Asm,@iter) waitcnt(clkfreq*3 + cnt) term.str(string(13,"start with: ")) start := term.DecIn #> 2 repeat iter := 0 repeat until iter if iter > imax term.str(string(13,"Process: ")) term.dec(start) term.str(string(" = Iterations: ")) term.dec(iter) imax := iter waitcnt(clkfreq/5 + cnt) start++ until start == posx term.str(string(13,"done")) DAT org 0 Asm rdlong t0,par wz 'wait for value written if_nz jmp #Asm mov p1,par sub p1,#4 rdlong L0,p1 'get value from Spin vars mov L1,#0 neg cntr,#1 'init cntr Loop add cntr,#1 cmp L0,#1 wz if_z cmp L1,#0 wz if_z jmp #done test L0,#1 wc 'Odd or Even? if_c jmp #Odd shr L1,#1 wc 'Even rcr L0,#1 '/2 jmp #Loop Odd mov t0,L0 'Odd mov t1,L1 add L0,L0 wc '*2 addx L1,L1 add L0,t0 wc '+ *1 addx L1,t1 add L0,#1 wc '+1 addx L1,#0 jmp #Loop done wrlong cntr,par 'write result to iter var jmp #Asm t0 res 1 t1 res 1 L0 res 1 L1 res 1 cntr res 1 p1 res 1Just my 2 cents.
MikeY
I wouldn't call VB (or vbscript) nonsense - they are powerful, especially when it comes to running and interacting with activex modules like Internet Explorer, Excel, MS Access databases, etc.
However, I downloaded the Python 3.5.2 64-bit Windows version and ran your code for the number 9780657631 and got 1132 steps - the correct answer.
It certainly was fast and handles larger numbers that vb. Apparently there are some syntax differences with the version you are using - "print" requires parenthesis...
I'm no great fan of Python. What with it not having any standardization. As you see the syntax has changed from version 2 to version 3, or whatever versions it was, breaking stuff. For example "print" is no longer built into the language syntax but provided as a "print()" library function now. Also I hate the white space block delimiting thing. And why does a basically line based language need ":" after "if" statements and such. Even Spin got that right.
VB does not appeal to me. It does not work outside of Windows. It also is not a standardized language.
VB in the browser, activex, is a really bad idea for many reasons. Luckily Microsoft have seen the error of their ways and do not support activex in their new Edge browser. As for interacting with databases that is easy enough in most languages.
Turns out that the big number support in Python is not so hot. I forget the limit now but eventually things get too big. If you really need that then you need to turn to a big number library. At that point the only reason I can think of for using Python goes away.
I'm determined to wait this out Ariba, last process 169941673 = 953, it is still going to be awhile if 670617279 with 986 iterations, is the last process before overflow. I certainly understand the time involved, considering the size of the number and steps involved.
Use anything long enough and you start to get annoyed by all the down sides and limitations. Then you are convinced you can design a better language. If you are skillful enough you do so.
That's why programming languages grow like weeds.
Not only programming languages but languages for humans. See the history of the Volapük language, which had a million speakers at one point, and how that soon fragmented into chaos. https://en.wikipedia.org/wiki/Volapük
VB is more like Latin. Back in the day if your were in the church you learned Latin. If not you did not. The VB church is MS and Windows. It's not about language merits. It's about power and money.
VB6 works just fine in Linux under Wine. You do need to snag a copy of the one .dll it needs which has been included with Windows since Win2K. As for that dot-net nonsense, it's an abomination and who cares where it might or might not work.
N*3 + 1
can be re-written in binary as ...
(N*4 - N) +1
EDIT: N*2+N+1 works also
...or....
LEFT shift by 2 , subtract the original number, add 1.
Anyway, the KEY in the result always distilling to a "1" may be better viewed from a binary approach.
EVEN RULE ) An EVEN number is repeatedly right shifted until it becomes ODD ... this is a simple divide by two ... if that ODD number happens to be a 1 we stop, if it's not a 1 then we apply the rule for an ODD number.
ODD RULE) An ODD number is left shifted twice ... this is a simple multiply by four ... This produces a temporary even number ... subtracting the original ODD number from the temp number produces a temporary odd number ... adding a ONE ... produces a result that will always EVEN.
The 'BIAS' towards always distilling to a value of 1 is a derivative from the EVEN rule and driven towards a 1 with the most weight when the EVEN number result is a power of 2.
It's this power of 2 that is the key here .... taking that aside, simply put ... if the number is EVEN the rule produces an ODD, if the number is ODD the rule produces an EVEN. However there is an underlying bias that if that EVEN number happens to be a power of 2 then the resulting number will ALWAYS be a "1".