### Collatz.BC - The 3x+1 or hailstones problem

## Here we'll be using the modified rules of
##   Odd  -> (3x+1)/2
##   Even -> x/2
## ...as otherwise the usual odd step (3x+1) is always followed by
## the even step. This way each rule has a 50/50 distribtion.

# Generate the next hailstone 5 -> (3*5+1)/2 = 8; 8 -> 8/2 = 4; 
define cz_next(x) {
  auto os;if(x<=1)return(1)
  os=scale;scale=0;x/=1
  if(x%2)x=3*x+1;x/=2
  scale=os
  return(x)
}

# Take a guess at the previous hailstone - since in some cases there are
# two choices, this function always chooses the lower option.
# e.g. 5 comes from both 3 [(3*(3)+1)/2] and 10 [10/2]
# - this function chooses 3.
define cz_prev(x) {
  auto os;if(x<=1)return(1)
  os=scale;scale=0;x/=1
  x=2*x-1;if(x%3){x+=1}else{x/=3}
  scale=os
  return(x)
}

# Determine the hailstone chain length to 1
# e.g. [5 -> 8 -> 4 -> 2 -> 1] = 4 steps
define cz_chlen(x) {
  auto os,c;if(x<=1)return(0)
  os=scale;scale=0;x/=1
  c=0
  while(x!=1){
    c+=1
    if(x%2)x=3*x+1;x/=2
  }
  scale=os
  return(c)
}

# Add the values of all the hailstones in a chain.
# [5 -> 8 -> 4 -> 2 -> 1] => 5 + 8 + 4 + 2 + 1 = 20
define cz_chsum(x) {
  auto os,s;if(x<=1)return(0)
  os=scale;scale=0;x/=1
  s=x
  while(x!=1){
    if(x%2)x=3*x+1;x/=2
    s+=x
  }
  scale=os
  return(s)
}

# Print the whole hailstone chain of numbers from x
define cz_chain(x) {
  auto os;if(x<=1)return(0)
  os=scale;scale=0;x/=1
  while(x!=1){
    x
    if(x%2)x=3*x+1;x/=2
  }
  scale=os
  return(1)
}

# Find the highest 'altitude' that the hailstone chain for x reaches
define cz_chmax(x) {
  auto os,m;if(x<=1)return(0)
  os=scale;scale=0;x/=1
  m=0
  while(x!=1){
    if(x>m)m=x
    if(x%2)x=3*x+1;x/=2
  }
  scale=os
  return(m)
}

# Generate a binary number representing a hailstone choice path
define cz_8tp(x) { # 8-tree path
# all numbers lead back to 8, this function maps the path as a binary
# number with the bit representing 8 as most significant.
# (8) = 1, (5 -> 8) = 10, (16 -> 8) = 11, (10 -> 5 -> 8) = 101, etc
  auto os,p,t;if(x<4)return(0)
  os=scale;scale=0;x/=1
  p=0;t=1
  while(x!=8){
    if(x%2){x=(3*x+1)/2}else{x/=2;p+=t}
    t*=2
  }
  p+=t
  scale=os
  return(p)
}

# Generate a hailstone from its path's binary number
define cz_i8tp(p) { # convert an 8-tree path back into a number
  auto os,msb,x;if(p<1)return(0)
  os=scale;scale=0;p/=1
  msb=1;while(msb<=p)msb*=2;msb/=2
  x=8;p-=msb;msb/=2
  while(msb){
    while(msb>p){scale=os;x=(2*x-1)/3;scale=0; msb/=2}
    if(msb){scale=os;x*=2;scale=0; p-=msb;msb/=2}
  }
  p=x/1;if(p==x)x=p # remove zeroes after dp if there are any
  scale=os
  return(x)
}