orangesquid (os) wrote,
orangesquid
os

seeing a base-prime binary tree

I know this requires python2 or higher as well as bash3 or higher. Not sure about the other requirements, but my system has python-2.6.6, sage-4.6.1, graphviz-2.26.3, and bash-4.1.7(2)-release.

Here's baseprime-bintree as converted with the standard
sed "s/&/&amp;/g;s/</\&lt;/g;s/>/\&gt;/g"
for a livejournal non-autoformat post.
#!/bin/bash
if [ $# -lt 1 -o $1 -lt 3 ]; then
  echo "usage: $0 nrows [args to pass to dot/neato...]"
  echo "where nrows >= 3"
  echo "typical dot args: -Tpng -o binarytree.png"
  exit 1
else
  rows=$1
  shift
fi
treedata=$(sage -c 'execfile("BCLIB-sage");'\
'print("Result",[[[[0,0],[],1]]]+'\
'map(lambda k:map(lambda x:[[k,x],'\
'bpnorm(bptree([k,x])),bp2num(bpnorm(bptree([k,x])))],'\
'range(2^(k-1))),range(1,'"$rows"')))' | 
  fgrep "'Result'"|cut -d, -f2-|cut -d')' -f1)
expanded=$(echo "a=$treedata
"'print [["coord%s rep%s val:%d stop" % (p,q,r) for p,q,r in x] for x in a]'|
  python)
halfparsed=$(
  sed "s/'coord/\\n&/g;s/stop'/&\\n/g;s/[:[]/ &/g" <<< "$expanded"|
    sed -n "s/, /,/g;/stop'/p")
nodes=$(
  awk '{
        gsub(/,/,".",$2);
        gsub(/[][]/,"",$2);
        print "  " $2 " [label=\"" $4 $6 "\"];"}' <<<"$halfparsed")
gv1=$(echo -e 'digraph tree {\n  node [shape=box];\n  0.0 -> 1.0;')
gv2=$(
  r=2
  while [ $r -lt $rows ]; do
    cols=$(dc -e "2 $[ $r - 1 ] ^ p")
    c=0
    x=0
    while [ $c -lt $cols ]; do
      echo "  $[ $r - 1].$(dc -e "0 k $c 2 / p") -> $r.$c"\
";"
#change previous line to the following to try attach-points for digraph
#"$(if [ $x -eq 0 ]; then echo ':ne'; else echo ':nw' ; fi);"
#in truth, it is harder to read, because the arrows curve and overlap---
#something I plan to fix
      c=$[ $c + 1 ]
      x=$[ 1 - $x ]
    done
    r=$[ $r + 1 ]
  done
)
(echo "$gv1";echo "$gv2";echo "$nodes";echo "}")|dot "$@"
# see these for potential output tuning with graphviz 2.28:
# http://stackoverflow.com/questions/10902745/
#          enforcing-horizontal-node-ordering-in-a-dot-tree
# https://mailman.research.att.com/pipermail/
#           graphviz-interest/2010q2/007101.html
# the Ganser tree.gv script can be modified to work with graphviz 2.26.3
# by removing the second BEG_G section and changing TV_postfwd to TV_fwd
# in the first BEG_G section, but the output is not wide enough to
# prevent the nodes from overlapping (when I get a chance, I'll fix it)
# for now, the tree output is still pretty good, because it's a balanced
# and complete tree from the second row down
# this is how you might call the Ganser tree.gv script (if stored as
# ganser-tree.gv):
#(echo "$gv1";echo "$gv2";echo "$nodes";echo "}")|dot|
#  gvpr -c -fganser-tree.gv|neato -n "$@"



And here's BCLIB-sage converted the same way:

# load with execfile(path)

def basep(n):
    a=[]
    if n>=2:
        f=factor(n)
        r=prime_range(1,f[len(f)-1][0]+1)
        o=0
        for i in range(len(r)):
####            print(i,r[i],o,f[o][0],f[o][1])
            if f[o][0]==r[i]:
                a.append(f[o][1])
                o=o+1
            else:
                a.append(0)
    return a

def bp2num(a):
    if(len(a)):
        p=[2]
        while len(p)<len(a):
            print("Expand:",p,p[len(p)-1])
            print(prime_range(power(p[len(p)-1],2)))
            p=prime_range(power(p[len(p)-1],2))
            print("p is now",p,len(p))
        p=filter(lambda x:x<=p[len(a)-1],p)
        n=prod(map(power,p,a))
    else:
        n=1
    return n

# basepthrunine = map(basep,range(1,10))
# onethrunine = map(lambda n:bp2num(basep(n)),range(1,10))

def revlist(p):
    q=[]
    for k in range(len(p)):
        q.append(p[len(p)-1-k])
    return q

def bpnorm(p):
    q=[]
    n=0
    for k in range(len(p)):
        e = p[len(p)-1-k]
        if e:
            n=1
        if n:
            q.append(e)
    return revlist(q)

def squid(a,b):
    w=len(a)+len(b)-1
    z=map(lambda x:0,range(w))
    for r in range(len(b)):
        y=map(lambda x:0 if x<r or x-r>=len(a) else b[r]*a[x-r],range(w))
        z=map(lambda a,b:a+b,z,y)
    return bpnorm(z)

def bpconj(a):
    if(len(a)):
        if(a[0]):
            c=[0,a[0]-1]+a[1:]
        else:
            c=[a[1]+1]+a[2:]
    else:
        c=[]
    return c

def bptree(z):
    r=z[0]
    c=z[1]
    p=[1,0]
    o = map(lambda x:0,range(r))
    for k in range(r):
        print("@",k,":")
        m = floor(c / 2);
        m = m * 2
        m = c - m
        if m > 0:
            print("R");
            o[r - k - 1] = 0
            c = floor((c - 1) / 2)
        else:
            print("L");
            o[r - k - 1] = 1
            c = floor(c / 2)
        print(",c:=",c)
        print(p)
    for j in range(2, r + 1):
        p.append(0);
    print(o)
    for k in range(len(o)):
        print("op",k,o[k])
        if o[k] > 0:
            p[1] = p[1] + 1
        else:
            print("n",p[0])
            print(p)
            for j in range(p[0], 0, -1):
                print("j",j,p[j])
                p[j + 1] = p[j]
            p[1] = 0
            p[0] = p[0] + 1
        print(p)
    return p[1:]

def inbptree(p):
    g = 1
    o = []
    while g>0:
        if len(p)==1 and p[0]==0:
            p=[]
        if len(p)>0:
            if p[0] > 0:
                p[0] = p[0] - 1
                o.append(1)
            else:
                for k in range(len(p)-1):
                    p[k] = p[k + 1]
                p = p[0:len(p)-1]
                o.append(0)
        else:
            g=0
    r=0
    c=0
    for k in range(len(o)-1,-1,-1):
        if o[k]>0:
            r=r+1
            c=c*2
        else:
            r=r+1
            c=c*2+1
    return (r,c)



Here's the output from ./baseprime-bintree 6 -Tpng -obinarytree.png


binary tree(view full size)

Tags: baseprime, math, primes
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments