Libraries for bc and dc.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

#### 300 lines 8.6 KiB Raw Permalink Blame History

 `#!/usr/local/bin/bc -l` `### Collatz.BC - The 3x+1 or hailstones problem` `# Global variable` `# The original Collatz iteration has rules:` `# odd x -> 3x+1` `# even x -> x/2` `# The condensed Collatz iteration has rules:` `# odd x -> (3x+1)/2` `# even x -> x/2` `# ...since the usual odd step always produces an even value` `# The odd-only Collatz iteration has rules:` `# odd x -> odd part of 3x+1` `# even x -> odd part of x` `# This var sets the mode of the functions in this library` `# 0 => odd-only Collatz` `# 1 => original Collatz - note that these two entries ...` `# 2 => condensed Collatz - ... match the divisor on the odd step` `collatz_mode_=1` `# sanity check` `define check_collatz_mode_() {` ` auto os;` ` if(collatz_mode_==0||collatz_mode_==1||collatz_mode_==2)return collatz_mode_` ` if(collatz_mode_<0||collatz_mode_>2)collatz_mode_=1` ` if(scale(collatz_mode_)){os=scale;scale=0;collatz_mode_/=1;scale=os}` ` return collatz_mode_` `}` `## Step forwards and back` `# Generate the next hailstone` `define collatz_next_(x) {` ` auto os,t;` ` os=scale;scale=0;x/=1` ` t=x/2;if(x!=t+t)t=3*x+1` ` if(collatz_mode_){` ` if(collatz_mode_==2&&t>x){x=t/2}else{x=t}` ` } else {` ` while(x==t+t||t>x){x=t;t/=2}` ` }` ` scale=os;return x` `}` `define collatz_next(x) {` ` .=check_collatz_mode_()` ` return collatz_next_(x)` `}` `# Take a guess at the previous hailstone - since in some cases there are` `# two choices, this function always chooses the option of lowest magnitude` `define collatz_prev(x) {` ` auto os,a,b,c;` ` os=scale;scale=0;x/=1` ` if(check_collatz_mode_()){` ` a=collatz_mode_*x-1;b=a/3` ` x+=x` ` if(3*b!=a||b==1||b==-1){scale=os;return x}` ` if((b>0)==(b0;i--)if(tape[i]==t){scale=os;return 0}` ` if(tapetop++>max_array_){` ` print "is_collatz: can't calculate; chain too long. assuming true.\n"` ` scale=os;return 1` ` }` ` tape[tapetop]=x=t` ` }` ` return x` `}` `# Print the chain of iterations of x until a loop or 1` `# . was cz_chain` `define collatz_print(x) {` ` auto os,t,i,tape[],tapetop` ` os=scale;scale=0;x/=1` ` x;if(x==0){scale=os;return 0}` ` .=check_collatz_mode_()` ` tapetop=-1` ` while(x!=1&&x!=-1){` ` t = collatz_next_(x)` ` # Search backwards for previous occurrence of t (which is more` ` # likely to be near end of tape since chains lead to loops)` ` for(i=tapetop;i>0;i--)if(tape[i]==t){scale=os;"looping ";return t}` ` if(tapetop++>max_array_){` ` print "collatz_print: can't calculate; chain too long.\n"` ` scale=os;return t` ` }` ` tape[tapetop]=x=t;t` ` }` `}` `# Find the number of smallest magnitude under the Collatz iteration of x` `# . assuming the conjecture is true, this returns 1 for all positive x` `define collatz_root(x) {` ` auto os,t,i,tape[],tapetop` ` os=scale;scale=0;x/=1` ` if(x==0){scale=os;return 0}` ` .=check_collatz_mode_()` ` tapetop=-1` ` while(x!=1&&x!=-1){` ` t = collatz_next_(x)` ` # Search backwards for previous occurrence of t (which is more` ` # likely to be near end of tape since chains lead to loops)` ` for(i=tapetop;i>0;i--)if(tape[i]==t){` ` #go back the other way looking for the lowest absolute value` ` while(++i<=tapetop)if((tape[i]>0)==(tape[i]max_array_){` ` print "collatz_print: can't calculate; chain too long.\n"` ` scale=os;return (x>0)-(x<0)` ` }` ` tape[tapetop]=x=t` ` }` ` return x` `}` `# Returns the loopsize should the iteration become stuck in a loop` `# . assuming the conjecture is true, this returns 3 for the` `# . 4,2,1,4,etc. loop for all positive x.` `define collatz_loopsize(x) {` ` auto os,t,i,tape[],tapetop` ` os=scale;scale=0;x/=1` ` if(x==0){scale=os;return 1}` ` .=check_collatz_mode_()` ` tapetop=-1` ` while(x!=1&&x!=-1){` ` t = collatz_next_(x)` ` # Search backwards for previous occurrence of t (which is more` ` # likely to be near end of tape since chains lead to loops)` ` for(i=tapetop;i>0;i--)if(tape[i]==t){scale=os;return tapetop-i+1}` ` if(tapetop++>max_array_){` ` print "collatz_loopsize: can't calculate; chain too long.\n"` ` scale=os;return 0` ` }` ` tape[tapetop]=x=t` ` }` ` if(collatz_mode_==0)return 1` ` if(collatz_mode_==1)return 3` ` if(collatz_mode_==2)return 2` `}` `# How many iterations to 1 (or loop)?` `define collatz_chainlength(x) {` ` auto os,t,i,c,tape[],tapetop` ` os=scale;scale=0;x/=1` ` if(x==0){scale=os;return 0}` ` .=check_collatz_mode_()` ` tapetop=-1` ` while(x!=1&&x!=-1){` ` .=c++` ` t = collatz_next_(x)` ` # Search backwards for previous occurrence of t (which is more` ` # likely to be near end of tape since chains lead to loops)` ` for(i=tapetop;i>0;i--)if(tape[i]==t){scale=os;return 2-c }# infinity` ` if(tapetop++>max_array_){` ` print "collatz_chainlength: can't calculate; chain too long.\n"` ` scale=os;return -c` ` }` ` tape[tapetop]=x=t` ` }` ` return c` `}` `# Highest point on way to 1 or before being stuck in a loop` `define collatz_magnitude(x) {` ` auto os,t,i,m,tape[],tapetop` ` os=scale;scale=0;x/=1` ` if(x==0){scale=os;return 0}` ` .=check_collatz_mode_()` ` tapetop=-1` ` m=x` ` while(x!=1&&x!=-1){` ` t = collatz_next_(x)` ` if((t>0)==(t>m))m=t` ` # Search backwards for previous occurrence of t (which is more` ` # likely to be near end of tape since chains lead to loops)` ` for(i=tapetop;i>0;i--)if(tape[i]==t){scale=os;return m}` ` if(tapetop++>max_array_){` ` print "collatz_magnitude: can't calculate; chain too long.\n"` ` scale=os;return m` ` }` ` tape[tapetop]=x=t` ` }` ` return m` `}` `# Sum of all values in the iteration` `define collatz_sum(x) {` ` auto os,t,i,s,tape[],tapetop` ` os=scale;scale=0;x/=1` ` if(x==0){scale=os;return 0}` ` .=check_collatz_mode_()` ` tapetop=-1` ` s=x` ` while(x!=1&&x!=-1){` ` t = collatz_next_(x)` ` # Search backwards for previous occurrence of t (which is more` ` # likely to be near end of tape since chains lead to loops)` ` for(i=tapetop;i>0;i--)if(tape[i]==t){scale=os;"infinite ";return 0}` ` if(tapetop++>max_array_){` ` print "collatz_sum: can't calculate; chain too long.\n"` ` scale=os;return s` ` }` ` tape[tapetop]=x=t` ` s+=t` ` }` ` return s` `}` `# is_collatz_sg(x) # set globals by name of above functions` `# All of the above rolled into one.` `# Global variables are set with the same names as the above functions` `# with the exception of global variable collatz_print, which should be` `# set to non-zero if emulation of the collatz_print() function is required` `define is_collatz_sg(x) {` ` auto os,t,i,s,c,m,tape[],tapetop` ` os=scale;scale=0;x/=1` ` if(collatz_print)x` ` if(x==0){` ` collatz_root = 0` ` collatz_loopsize = 1` ` collatz_chainlength = 0` ` collatz_magnitude = 0` ` collatz_sum = 0` ` scale=os;return 0` ` }` ` .=check_collatz_mode_()` ` tapetop=-1` ` s=m=x` ` while(x!=1&&x!=-1){` ` .=c++` ` t = collatz_next_(x)` ` if((t>0)==(t>m))m=t` ` # Search backwards for previous occurrence of t (which is more` ` # likely to be near end of tape since chains lead to loops)` ` for(i=tapetop;i>0;i--)if(tape[i]==t){` ` collatz_loopsize = tapetop-i+1` ` collatz_chainlength = 2-c # Infinite` ` collatz_magnitude = m` ` collatz_sum = 0 # Infinite` ` #go back the other way looking for the lowest absolute value` ` while(++i<=tapetop)if((tape[i]>0)==(tape[i]max_array_){` ` print "is_collatz_sg: can't calculate; chain too long.\n"` ` collatz_root = (x>0)-(x<0)` ` collatz_loopsize = 0` ` collatz_chainlength = -c` ` collatz_magnitude = m` ` collatz_sum = s` ` scale=os;return s` ` }` ` tape[tapetop]=x=t` ` if(collatz_print)x` ` s+=t` ` }` ` collatz_root = x` ` if(collatz_mode_==0) collatz_loopsize = 1` ` if(collatz_mode_==1) collatz_loopsize = 3` ` if(collatz_mode_==2) collatz_loopsize = 2` ` collatz_chainlength = c` ` collatz_magnitude = m` ` collatz_sum = s` ` return x` ```} ``` ``` ```