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
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

  • 0 comments