Differences between revisions 11 and 65 (spanning 54 versions)
⇤ ← Revision 11 as of 2009-02-06 04:19:02 →
Size: 30130
Editor: TimothyClemans
Comment:
← Revision 65 as of 2019-11-14 20:52:33 → ⇥
Size: 48344
Editor: chapoton
Comment: no xrange
Deletions are marked like this. Additions are marked like this.
Line 4: Line 4:

== Divisibility Poset ==
by William Stein
{{{#!sagecell
@interact
def _(n=(5..100)):
    Poset(([1..n], lambda x, y: y%x == 0) ).show()
}}}

{{attachment:divposet.png}}
Line 7: Line 18:
{{{ {{{#!sagecell
Line 40: Line 51:
                    g += line([(j*2-len(cur),-i), ((k*2)-len(rows[i-1]),-i+1)],                      g += line([(j*2-len(cur),-i), ((k*2)-len(rows[i-1]),-i+1)],
Line 61: Line 72:
{{{ {{{#!sagecell
Line 75: Line 86:
{{{ {{{#!sagecell
Line 83: Line 94:
== Prime Spiral - Square == == Prime Spiral - Square FIXME ==
Line 85: Line 96:
{{{ {{{#!sagecell
Line 90: Line 101:
    REFERENCES:      REFERENCES:
Line 95: Line 106:
        Weisstein, Eric W. "Prime-Generating Polynomial." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html          Weisstein, Eric W. "Prime-Generating Polynomial." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html
Line 103: Line 114:
        elif y<0 and -x >= y and y<x: return 4*(y+1)^2 -11*(y+1) + (start+7) +x 
        else: print 'NaN'

    #Takes in an n and the start value of the spiral and gives its (x,y) coordinate 		         elif y<0 and -x >= y and y<x: return 4*(y+1)^2 -11*(y+1) + (start+7) +x
        else: print('NaN')

    #Takes in an n and the start value of the spiral and gives its (x,y) coordinate
Line 108: Line 119:
        num = num - start +1          num = num - start +1
Line 110: Line 121:
        top = ceil(sqrt(num))             top = ceil(sqrt(num))
Line 115: Line 126:
            else:              else:
Line 122: Line 133:
            else:              else:
Line 129: Line 140:
    if start < 1 or end <=start: print "invalid start or end value"
    if n > end: print "WARNING: n is larger than the end value"		     if start < 1 or end <=start: print("invalid start or end value")
    if n > end: print("WARNING: n is larger than the end value")
Line 134: Line 145:
        N = M.copy()         N = copy(M)
Line 138: Line 149:
 
    #These functions return an int based on where the t is located in the spiral 
    #These functions return an int based on where the t is located in the spiral
Line 151: Line 162:
    if n !=0: x_cord, y_cord = find_xy(n, start) #Overrides the user given x and y coordinates      if n !=0: x_cord, y_cord = find_xy(n, start) #Overrides the user given x and y coordinates
Line 159: Line 170:
    
Line 161: Line 172:
    #print x_cord, y_cord
 if show_lines: 
        for t in [(-size-1)..size+1]: 		     if show_lines:
        for t in [(-size-1)..size+1]:
Line 165: Line 175:
            if m.is_pseudoprime(): main_list.add(m)              if m.is_pseudoprime(): main_list.add(m)
Line 170: Line 180:
    #This for loop changes the matrix by spiraling out from the center and changing each entry as it goes. It is faster than the find_xy function above.      #This for loop changes the matrix by spiraling out from the center and changing each entry as it goes. It is faster than the find_xy function above.
Line 172: Line 182:
        #print x, "=x y=", y, " num =", num
Line 175: Line 184:
            else: x-=1              else: x-=1
Line 177: Line 186:
        
        elif county < overcount: 
        elif county < overcount:
Line 180: Line 189:
            else: y-=1              else: y-=1
Line 182: Line 191:
        else:          else:
Line 188: Line 197:
    
        if not invert and num in main_list: 
        if not invert and num in main_list:
Line 196: Line 205:
    
    if n != 0: 
        print '(to go from x,y coords to an n, reset by setting n=0)'
    if n != 0:
        print('(to go from x,y coords to an n, reset by setting n=0)')
Line 200: Line 209:
        #print 'if n =', n, 'then (x,y) =', (x_cord, y_cord)

    print '(x,y) =', (x_cord, y_cord), '<=> n =', find_n(x_cord, y_cord, start)
    print ' '
    print "SW/NE line"
    if -y_cord<x_cord: print '4*t^2 + 2*t +', -x_cord+y_cord+start
    else: print '4*t^2 + 2*t +', +x_cord-y_cord+start

    print "NW/SE line"
    if x_cord<y_cord: print '4*t^2 +', -x_cord-y_cord+start
    else: print '4*t^2 + 4*t +', +x_cord+y_cord+start
    print('(x,y) =', (x_cord, y_cord), '<=> n =', find_n(x_cord, y_cord, start))
    print(' ')
    print("SW/NE line")
    if -y_cord<x_cord: print('4*t^2 + 2*t +', -x_cord+y_cord+start)
    else: print('4*t^2 + 2*t +', +x_cord-y_cord+start)

    print("NW/SE line")
    if x_cord<y_cord: print('4*t^2 +', -x_cord-y_cord+start)
    else: print('4*t^2 + 4*t +', +x_cord+y_cord+start)
Line 213: Line 221:
    else:      else:
Line 222: Line 230:
{{{
@interact
def polar_prime_spiral(start=1, end=2000, show_factors = false, highlight_primes = false, show_curves=true, n = 0): 

    #For more information about the factors in the spiral, visit http://www.dcs.gla.ac.uk/~jhw/spirals/index.html by John Williamson. 

    if start < 1 or end <=start: print "invalid start or end value"
    if n > end: print "WARNING: n is greater than end value"		 {{{#!sagecell
@interact
def polar_prime_spiral(start=1, end=2000, show_factors = false, highlight_primes = false, show_curves=true, n = 0):

    #For more information about the factors in the spiral, visit http://www.dcs.gla.ac.uk/~jhw/spirals/index.html by John Williamson.

    if start < 1 or end <=start: print("invalid start or end value")
    if n > end: print("WARNING: n is greater than end value")
Line 232: Line 240:
    
Line 240: Line 248:
        R = points(list2, alpha = .1) #Faded Composites 
    else: 		         R = points(list2, alpha = .1) #Faded Composites
    else:
Line 248: Line 256:
        R=points(list2, hue = .1, pointsize = p_size) 
    		         R=points(list2, hue = .1, pointsize = p_size)
Line 251: Line 259:
        print 'n =', factor(n)
        		         print('n = {}'.format(factor(n)))
Line 259: Line 267:
        Q = plot(W1+W2+W3+W4, alpha = .1)                   Q = plot(W1+W2+W3+W4, alpha = .1)
Line 262: Line 270:
        if show_curves:          if show_curves:
Line 267: Line 275:
            if n > (floor(sqrt(n)))^2 and n <= (floor(sqrt(n)))^2 + floor(sqrt(n)):              if n > (floor(sqrt(n)))^2 and n <= (floor(sqrt(n)))^2 + floor(sqrt(n)):
Line 270: Line 278:
            else:              else:
Line 273: Line 281:
            print 'Pink Curve: n^2 +', c
            print 'Green Curve: n^2 + n +', c2
            def g(m): return (a*m^2+b*m+c); 		             print('Pink Curve: n^2 +', c)
            print('Green Curve: n^2 + n +', c2)
            def g(m): return (a*m^2+b*m+c);
Line 281: Line 289:
            c= c2;              c= c2;
Line 296: Line 304:
{{{
j = 0
@interact
def _(N=[1..100], k=selector([2,4,..,12],nrows=1), prec=(3..40), 		 {{{#!sagecell
@interact
def _(N=[1..100], k=selector([2,4,..,12],nrows=1), prec=(3..40),
Line 302: Line 309:
    print j; global j; j += 1
    print M; print '\n'*3
    print "Computing basis...\n\n"		     print(M)
    print('\n' * 3)
    print("Computing basis...\n\n")
Line 306: Line 313:
         print "Space has dimension 0"          print("Space has dimension 0")
Line 308: Line 315:
        prec = max(prec, M.dimension()+1)         prec = max(prec, M.dimension() + 1)
Line 311: Line 318:
    print "\n\n\nDone computing basis."     print("\n\n\nDone computing basis.")
Line 319: Line 326:
{{{ {{{#!sagecell
Line 324: Line 331:
    print A.cuspidal_subgroup()     print(A.cuspidal_subgroup())
Line 332: Line 339:
{{{ {{{#!sagecell
Line 340: Line 347:
    G = Graph(T, multiedges=True, loops=not three_d)     G = DiGraph(T, multiedges=not three_d)
    if three_d:
        G.remove_loops()
Line 353: Line 362:
== Quadratic Residue Table == == Quadratic Residue Table FIXME ==
Line 355: Line 364:
{{{ {{{#!sagecell
Line 406: Line 415:
== Cubic Residue Table == == Cubic Residue Table FIXME ==
Line 408: Line 417:
{{{ {{{#!sagecell
Line 426: Line 435:
    if Mod(a,3)!=0 and Mod(b,3)==0:
        return True
    else:
        return False		     return Mod(a,3)!=0 and Mod(b,3)==0
Line 464: Line 470:
        MP += line([(i,0),(i,r)], rgbcolor='black')          MP += line([(i,0),(i,r)], rgbcolor='black')
Line 492: Line 498:
{{{ {{{#!sagecell
Line 541: Line 547:
    S = circle((0,0),1,rgbcolor='yellow')  \
    + line([e_pt,e_gs_pt], rgbcolor='red', thickness=4) \
    + line([f_pt,f_gs_pt], rgbcolor='blue', thickness=3) \
    + line([ef_pt,ef_gs_pt], rgbcolor='purple',thickness=2) \
    + point(e_pt,pointsize=50, rgbcolor='red')  \
    + point(f_pt,pointsize=50, rgbcolor='blue') \
    + point(ef_pt,pointsize=50,rgbcolor='purple') \
    + point(f_gs_pt,pointsize=75, rgbcolor='black') \
    + point(e_gs_pt,pointsize=75, rgbcolor='black') \
    + point(ef_gs_pt,pointsize=75, rgbcolor='black') \
    + point(js_pt,pointsize=100,rgbcolor='green')		     S = circle((0,0),1,rgbcolor='yellow')
    S += line([e_pt,e_gs_pt], rgbcolor='red', thickness=4)
    S += line([f_pt,f_gs_pt], rgbcolor='blue', thickness=3)
    S += line([ef_pt,ef_gs_pt], rgbcolor='purple',thickness=2)
    S += point(e_pt,pointsize=50, rgbcolor='red')
    S += point(f_pt,pointsize=50, rgbcolor='blue')
    S += point(ef_pt,pointsize=50,rgbcolor='purple')
    S += point(f_gs_pt,pointsize=75, rgbcolor='black')
    S += point(e_gs_pt,pointsize=75, rgbcolor='black')
    S += point(ef_gs_pt,pointsize=75, rgbcolor='black')
    S += point(js_pt,pointsize=100,rgbcolor='green')
Line 553: Line 559:
        S += text('$J(%s,%s) = %s$'%(latex2(e),latex2(f),latex(js)), \         S += text('$J(%s,%s) = %s$'%(latex2(e),latex2(f),latex(js)),
Line 572: Line 578:
{{{ {{{#!sagecell
Line 621: Line 627:
    S = circle((0,0),1,rgbcolor='yellow')  \
    + line([e_pt,e_gs_pt], rgbcolor='red', thickness=4) \
    + line([f_pt,f_gs_pt], rgbcolor='blue', thickness=3) \
    + line([ef_pt,ef_gs_pt], rgbcolor='purple',thickness=2) \
    + point(e_pt,pointsize=50, rgbcolor='red')  \
    + point(f_pt,pointsize=50, rgbcolor='blue') \
    + point(ef_pt,pointsize=50,rgbcolor='purple') \
    + point(f_gs_pt,pointsize=75, rgbcolor='black') \
    + point(e_gs_pt,pointsize=75, rgbcolor='black') \
    + point(ef_gs_pt,pointsize=75, rgbcolor='black') \
    + point(js_pt,pointsize=100,rgbcolor='green')		     S = circle((0,0),1,rgbcolor='yellow')
    S += line([e_pt,e_gs_pt], rgbcolor='red', thickness=4)
    S += line([f_pt,f_gs_pt], rgbcolor='blue', thickness=3)
    S += line([ef_pt,ef_gs_pt], rgbcolor='purple',thickness=2)
    S += point(e_pt,pointsize=50, rgbcolor='red')
    S += point(f_pt,pointsize=50, rgbcolor='blue')
    S += point(ef_pt,pointsize=50,rgbcolor='purple')
    S += point(f_gs_pt,pointsize=75, rgbcolor='black')
    S += point(e_gs_pt,pointsize=75, rgbcolor='black')
    S += point(ef_gs_pt,pointsize=75, rgbcolor='black')
    S += point(js_pt,pointsize=100,rgbcolor='green')
Line 633: Line 639:
        S += text('$J(%s,%s) = %s$'%(latex2(e),latex2(f),latex(js)), \         S += text('$J(%s,%s) = %s$'%(latex2(e),latex2(f),latex(js)),
Line 645: Line 651:
        ga[i].save('j%d.PNG'%i,figsize=4,aspect_ratio=1, \         ga[i].save('j%d.png'%i,figsize=4,aspect_ratio=1,
Line 651: Line 657:
    html('<table bgcolor=lightgrey cellpadding=2>')     s='<table bgcolor=lightgrey cellpadding=2>'
Line 653: Line 659:
        html('<tr><td align="center"><img src="cell://j%d.PNG"></td>'%(2*i))
        html('<td align="center"><img src="cell://j%d.PNG"></td></tr>'%(2*i+1))
    html('</table>')
}}}		         s+='<tr><td align="center"><img src="cell://j%d.png"></td>'%(2*i)
        s+='<td align="center"><img src="cell://j%d.png"></td></tr>'%(2*i+1)
    s+='</table>'
    html(s)}}}
Line 664: Line 670:
{{{ {{{#!sagecell
Line 670: Line 676:
    else:      else:
Line 677: Line 683:

def line_from_curve_points(E,P,Q,style='-',rgb=(1,0,0),length=25):
 """
 P,Q two points on an elliptic curve.
 Output is a graphic representation of the straight line intersecting with P,Q.
 """
 # The function tangent to P=Q on E
 if P == Q:
  if P[2]==0:
   return line([(1,-length),(1,length)],linestyle=style,rgbcolor=rgb)
  else:
   # Compute slope of the curve E in P
   l=-(3*P[0]^2 + 2*E.a2()*P[0] + E.a4() - E.a1()*P[1])/((-2)*P[1] - E.a1()*P[0] - E.a3())
   f(x) = l * (x - P[0]) + P[1]
   return plot(f(x),-length,length,linestyle=style,rgbcolor=rgb)
 # Trivial case of P != R where P=O or R=O then we get the vertical line from the other point
 elif P[2] == 0:
  return line([(Q[0],-length),(Q[0],length)],linestyle=style,rgbcolor=rgb)
 elif Q[2] == 0:
  return line([(P[0],-length),(P[0],length)],linestyle=style,rgbcolor=rgb)
 # Non trivial case where P != R
 else:
  # Case where x_1 = x_2 return vertical line evaluated in Q
  if P[0] == Q[0]:
   return line([(P[0],-length),(P[0],length)],linestyle=style,rgbcolor=rgb)

  #Case where x_1 != x_2 return line trough P,R evaluated in Q"
  l=(Q[1]-P[1])/(Q[0]-P[0])
  f(x) = l * (x - P[0]) + P[1]
  return plot(f(x),-length,length,linestyle=style,rgbcolor=rgb)
Line 679: Line 716:
 curve = E.plot(rgbcolor = (0,0,1),xmin=25,xmax=25,plot_points=300)  curve = E.plot(rgbcolor = (0,0,1),xmin=-5,xmax=5,plot_points=300)
Line 705: Line 742:

def line_from_curve_points(E,P,Q,style='-',rgb=(1,0,0),length=25):
 """
 P,Q two points on an elliptic curve.
 Output is a graphic representation of the straight line intersecting with P,Q.
 """
 # The function tangent to P=Q on E
 if P == Q:
  if P[2]==0:
   return line([(1,-length),(1,length)],linestyle=style,rgbcolor=rgb)
  else:
   # Compute slope of the curve E in P
   l=-(3*P[0]^2 + 2*E.a2()*P[0] + E.a4() - E.a1()*P[1])/((-2)*P[1] - E.a1()*P[0] - E.a3())
   f(x) = l * (x - P[0]) + P[1]
   return plot(f(x),-length,length,linestyle=style,rgbcolor=rgb)
 # Trivial case of P != R where P=O or R=O then we get the vertical line from the other point
 elif P[2] == 0:
  return line([(Q[0],-length),(Q[0],length)],linestyle=style,rgbcolor=rgb)
 elif Q[2] == 0:
  return line([(P[0],-length),(P[0],length)],linestyle=style,rgbcolor=rgb)
 # Non trivial case where P != R
 else:
  # Case where x_1 = x_2 return vertical line evaluated in Q
  if P[0] == Q[0]:
   return line([(P[0],-length),(P[0],length)],linestyle=style,rgbcolor=rgb)
  
  #Case where x_1 != x_2 return line trough P,R evaluated in Q"
  l=(Q[1]-P[1])/(Q[0]-P[0])
  f(x) = l * (x - P[0]) + P[1]
  return plot(f(x),-length,length,linestyle=style,rgbcolor=rgb)
Line 740: Line 747:
{{{ {{{#!sagecell
Line 745: Line 752:
    print "p = %s"%p
    show(E.change_ring(GF(p)).plot(),xmin=0,ymin=0)		     print("p = %s" % p)
    show(E.change_ring(GF(p)).plot(), xmin=0, ymin=0)
Line 755: Line 762:
{{{ {{{#!sagecell
Line 769: Line 776:
    print """
<html>		     html("""
Line 794: Line 800:
</ol></html>
    """ % (bits, p, g, a, g, a, p, (g^a), b, g, b, p, (g^b), (g^b), a, p, 
       (g^ b)^a, g^a, b, p, (g^a)^b)		 </ol>
    """ % (bits, p, g, a, g, a, p, (g^a), b, g, b, p, (g^b), (g^b), a, p,
       (g^ b)^a, g^a, b, p, (g^a)^b))
Line 806: Line 812:
{{{
@interact
def _(number=e, ymax=selector([None,5,20,..,400],nrows=2), clr=Color('purple'), prec=[500,1000,..,5000]):
    c = list(continued_fraction(RealField(prec)(number))); print c		 {{{#!sagecell
@interact
def _(number=e, ymax=selector([5,20,..,400],nrows=2), clr=Color('purple'), prec=[500,1000,..,5000]):
    c = list(continued_fraction(RealField(prec)(number))); print(c)
Line 816: Line 822:
{{{ {{{#!sagecell
Line 837: Line 843:
{{{
L = [[-0.5, 2.0^(x/100.0) - 1 + sqrt(3.0)/2] for x in xrange(1000, -1, -1)]
R = [[0.5, 2.0^(x/100.0) - 1 + sqrt(3.0)/2] for x in xrange(1000)]
xes = [x/1000.0 for x in xrange(-500,501,1)]		 {{{#!sagecell
L = [[-0.5, 2.0^(x/100.0) - 1 + sqrt(3.0)/2] for x in range(1000, -1, -1)]
R = [[0.5, 2.0^(x/100.0) - 1 + sqrt(3.0)/2] for x in range(1000)]
xes = [x/1000.0 for x in range(-500,501,1)]
Line 845: Line 851:
def _(gen = selector(['t+1', 't-1', '-1/t'], nrows=1)): def _(gen = selector(['t+1', 't-1', '-1/t'], buttons=True,nrows=1)):
Line 863: Line 869:

= Multiple Zeta Values =
by Akhilesh P.
== Computing Multiple Zeta values ==
=== Word Input ===
{{{#!sagecell
R=RealField(10)
@interact
def _( weight=(5,(2..100))):
 n=weight
 a=[0 for i in range(n-1)]
 a.append(1)
 @interact
 def _(v=('word', input_grid(1, n, default=[a], to_value=lambda x: vector(flatten(x)))), accuracy=(100..100000)):
  D=accuracy
  a=[v[i] for i in range(len(v))]
  DD=int(3.321928*D)+int(R(log(3.321928*D))/R(log(10)))+4
  RIF=RealIntervalField(DD)
  def Li(word):
        n=int(DD*log(10)/log(2))+1
        B=[]
        L=[]
        S=[]
        count=-1
        k=len(word)
        for i in range(k):
                B.append(RIF('0'))
                L.append(RIF('0'))
                if(word[i]==1 and i<k-1):
                        S.append(RIF('0'))
                        count=count+1
        T=RIF('1')
        for m in range(n):
                T=T/2
                B[k-1]=RIF('1')/(m+1)
                j=count
                for i in range(k-2,-1,-1):
                        if(word[i]==0):
                                B[i]=B[i+1]/(m+1)
                        elif(word[i]==1):
                                B[i]=S[j]/(m+1)
                                S[j]=S[j]+B[i+1]
                                j=j-1
                        L[i]=T*B[i]+L[i]
                L[k-1]=T*B[k-1]+L[k-1]
        return(L)
  def dual(a):
        b=list()
        b=a
        b=b[::-1]
        for i in range(len(b)):
                b[i]=1-b[i]
        return(b)
  def zeta(a):
        b=dual(a)
        l1=Li(a)+[1]
        l2=Li(b)+[1]
        Z=RIF('0')
        for i in range(len(l1)):
                Z=Z+l1[i]*l2[len(a)-i]
        return(Z)
  u=zeta(a)
  RIF=RealIntervalField(int(3.321928*D))
  u=u/1
  print(u)
}}}
{{attachment:akhi1.png}}
=== Composition Input ===
{{{#!sagecell
R=RealField(10)
@interact
def _( Depth=(5,(2..100))):
 n=Depth
 a=[2]
 a=a+[1 for i in range(n-1)]
 @interact
 def _(v=('Composition', input_grid(1, n, default=[a], to_value=lambda x: vector(flatten(x)))), accuracy=(100..100000)):
  D=accuracy
  a=[v[i] for i in range(len(v))]
  def comptobin(a):
        word=[]
        for i in range(len(a)):
                word=word+[0]*(a[i]-1)+[1]
        return(word)
  a=comptobin(a)
  DD=int(3.321928*D)+int(R(log(3.321928*D))/R(log(10)))+4
  RIF=RealIntervalField(DD)
  def Li(word):
        n=int(DD*log(10)/log(2))+1
        B=[]
        L=[]
        S=[]
        count=-1
        k=len(word)
        for i in range(k):
                B.append(RIF('0'))
                L.append(RIF('0'))
                if(word[i]==1 and i<k-1):
                        S.append(RIF('0'))
                        count=count+1
        T=RIF('1')
        for m in range(n):
                T=T/2
                B[k-1]=RIF('1')/(m+1)
                j=count
                for i in range(k-2,-1,-1):
                        if(word[i]==0):
                                B[i]=B[i+1]/(m+1)
                        elif(word[i]==1):
                                B[i]=S[j]/(m+1)
                                S[j]=S[j]+B[i+1]
                                j=j-1
                        L[i]=T*B[i]+L[i]
                L[k-1]=T*B[k-1]+L[k-1]
        return(L)
  def dual(a):
        b=list()
        b=a
        b=b[::-1]
        for i in range(len(b)):
                b[i]=1-b[i]
        return(b)
  def zeta(a):
        b=dual(a)
        l1=Li(a)+[1]
        l2=Li(b)+[1]
        Z=RIF('0')
        for i in range(len(l1)):
                Z=Z+l1[i]*l2[len(a)-i]
        return(Z)
  u=zeta(a)
  RIF=RealIntervalField(int(3.321928*D))
  u=u/1
  print(u)
}}}
{{attachment:akhi5.png}}
== Program to Compute Integer Relation between Multiple Zeta Values ==
{{{#!sagecell
from mpmath import *
print("Enter the number of composition")
@interact
def _( n=(5,(2..100))):
 a=[]
 for i in range(n):
        a.append([i+2,1])
 print("In each box Enter composition as an array")
 @interact
 def _(v=('Compositions', input_box( default=a, to_value=lambda x: vector(flatten(x)))), accuracy=(100..100000)):
  D=accuracy
  R=RealField(10)
  a=v
  def comptobin(a):
        word=[]
        for i in range(len(a)):
                word=word+[0]*(a[i]-1)+[1]
        return(word)
  DD=int(D)+int(R(log(3.321928*D))/R(log(10)))+4
  RIF=RealIntervalField(DD)
  mp.dps=DD
  def Li(word):
        n=int(DD*log(10)/log(2))+1
        B=[]
        L=[]
        S=[]
        count=-1
        k=len(word)
        for i in range(k):
                B.append(mpf('0'))
                L.append(mpf('0'))
                if(word[i]==1 and i<k-1):
                        S.append(mpf('0'))
                        count=count+1
        T=mpf('1')
        for m in range(n):
                T=T/2
                B[k-1]=mpf('1')/(m+1)
                j=count
                for i in range(k-2,-1,-1):
                        if(word[i]==0):
                                B[i]=B[i+1]/(m+1)
                        elif(word[i]==1):
                                B[i]=S[j]/(m+1)
                                S[j]=S[j]+B[i+1]
                                j=j-1
                        L[i]=T*B[i]+L[i]
                L[k-1]=T*B[k-1]+L[k-1]
        return(L)
  def dual(a):
        b=list()
        b=a
        b=b[::-1]
        for i in range(len(b)):
                b[i]=1-b[i]
        return(b)
  def zeta(a):
        b=dual(a)
        l1=Li(a)+[1]
        l2=Li(b)+[1]
        Z=mpf('0')
        for i in range(len(l1)):
                Z=Z+l1[i]*l2[len(a)-i]
        return(Z)
  zet=[]
  for i in range(n):
        zet.append((zeta(comptobin(a[i]))))
  mp.dps=D
  for i in range(n):
        zet[i]=zet[i]/1
        print("zeta(", a[i], ")=", zet[i])
  u=pslq(zet,tol=10**-D,maxcoeff=100,maxsteps=10000)
  print("the Intger Relation between the above zeta values given by the vector")
  print(u)
}}}
{{attachment:akhi10.png}}
== Word to composition ==
{{{#!sagecell
@interact
def _( weight=(7,(2..100))):
 n=weight
 a=[0 for i in range(n-1)]
 a.append(1)
 @interact
 def _(v=('word', input_grid(1, n, default=[a], to_value=lambda x: vector(flatten(x))))):
  a=[v[i] for i in range(len(v))]
  def bintocomp(a):
 b=[]
 count=1
 for j in range(len(a)):
  if(a[j]==0):
   count=count+1
  else:
   b.append(count)
   count=1
 return(b)
  print("Composition is {}".format(bintocomp(a)))
}}}

{{attachment:akhi2.png}}
== Composition to Word ==
{{{#!sagecell
@interact
def _( Depth=(7,(1..100))):
 n=Depth
 a=[]
 a.append(2)
 a=a+[1 for i in range(1,n)]
 @interact
 def _(v=('composition', input_grid(1, n, default=[a], to_value=lambda x: vector(flatten(x))))):
  a=[v[i] for i in range(len(v))]
  def comptobin(a):
 word=[]
 for i in range(len(a)):
  word=word+[0]*(a[i]-1)+[1]
 return(word)

  print("Word is {}".format(comptobin(a)))
}}}

{{attachment:akhi3.png}}
== Dual of a Word ==
{{{#!sagecell
@interact
def _( weight=(7,(2..100))):
 n=weight
 a=[0 for i in range(n-1)]
 a.append(1)
 @interact
 def _(v=('word', input_grid(1, n, default=[a], to_value=lambda x: vector(flatten(x))))):
  a=[v[i] for i in range(len(v))]
  def dual(a):
 b=list()
 b=a
 b=b[::-1]
 for i in range(len(b)):
  b[i]=1-b[i]
 return(b)

  print("Dual word is {}"?format(dual(a)))
}}}

{{attachment:akhi4.png}}


== Shuffle product of two Words ==
{{{#!sagecell
@interact
def _( w1=(2,(2..100)), w2=(2,(2..100))):
 a=[0]
 b=[0 for i in range(w2-1)]
 a=a+[1 for i in range(1,w1)]
 b=b+[1]
 import itertools
 #this program gives the list of all binary words of weight n and depth k
 @interact
 def _(v1=('word1', input_grid(1, w1, default=[a], to_value=lambda x: vector(flatten(x)))), v2=('word2', input_grid(1, w2, default=[b], to_value=lambda x: vector(flatten(x))))):
  a=[v1[i] for i in range(len(v1))]
  b=[v2[i] for i in range(len(v2))]
  def kbits(n, k):
    result = []
    for bits in itertools.combinations(range(n), k):
        s = ['0'] * n
        for bit in bits:
            s[bit] = '1'
        result.append(''.join(s))
    return result
  def sort(a,l,m):
        b=[]
        n=len(a)
        for i in range(n):
                b.append(a[i])
        for j in range(l-1,-1,-1):
                k=0
                for t in range(m+1):
                        for i in range(n):
                                if(a[i][j]== t):
                                        b[k]=a[i]
                                        k=k+1
                for i in range(n):
                        a[i]=b[i]
        return(a)
  def count(a):
        n=len(a)
        b=[]
        b.append(a[0])
        m=[]
        m.append(1)
        c=0
        for i in range(1,n):
                if(a[i]==a[i-1]):
                        m[c]=m[c]+1
                else:
                        b.append(a[i])
                        m.append(1)
                        c=c+1
        return(b,m)
  def shuffle(a,b):
        r=len(a)
        s=len(b)
        # Generating an array of strings containing all combinations of weight r+s and depth s
        M=kbits(r+s,s)
        n=len(M)
        a1= []
        for i in range(n):
                a1.append(list(M[i]))
        # The zeroes are replaced by the entries of a and the ones by the entries of b
        a2= []
        for i in range(n):
                a2.append([])
                count0=0
                count1=0
                for j in range(s+r):
                        if(a1[i][j]=='0'):
                                a2[i].append(a[count0])
                                count0=count0+1
                        if(a1[i][j]=='1'):
                                a2[i].append(b[count1])
                                count1=count1+1
        # Reordering in lexicographic order the entries of a2: this is done by first reordering them according to the last digit, then the next to last digit, etc
        a3=sort(a2,r+s,max(a+b+[0]))
        # Getting the same list without repetitions and with multiplicities
        a4=count(a3)
        return(a4)
  c=shuffle(a,b)
  for i in range(len(c[0])-1):
    print(c[1][i],"*",c[0][i] ,"+ ")
  print(c[1][len(c[0])-1],"*",c[0][len(c[0])-1])


}}}
{{attachment:akhi6.png}}
== Shuffle Regularization at 0 ==
{{{#!sagecell
@interact
def _( w=(2,(2..100))):
 a=[0]
 a=a+[1 for i in range(1,w)]
 import itertools
 #this program gives the list of all binary words of weight n and depth k
 @interact
 def _(v=('word', input_grid(1, w, default=[a], to_value=lambda x: vector(flatten(x))))):
  a=[v[i] for i in range(len(v))]
  def kbits(n, k):
    result = []
    for bits in itertools.combinations(range(n), k):
        s = ['0'] * n
        for bit in bits:
            s[bit] = '1'
        result.append(''.join(s))
    return result
  def sort(a,l,m):
 b=[]
 n=len(a)
 for i in range(n):
  b.append(a[i])
 for j in range(l-1,-1,-1):
  k=0
  for t in range(m+1):
   for i in range(n):
    if(a[i][j]== t):
     b[k]=a[i]
     k=k+1
  for i in range(n):
   a[i]=b[i]
 return(a)

  def sort1(a,l,m):
 b=[]
 b.append([])
 b.append([])
 n=len(a[0])
 for i in range(n):
  b[0].append(a[0][i])
  b[1].append(a[1][i])
 for j in range(l-1,-1,-1):
  k=0
  for t in range(m+1):
   for i in range(n):
    if(a[0][i][j]== t):
     b[0][k]=a[0][i]
     b[1][k]=a[1][i]
     k=k+1
  for i in range(n):
   a[0][i]=b[0][i]
   a[1][i]=b[1][i]
 return(a)

  def count(a):
 n=len(a)
 b=[]
 b.append(a[0])
 m=[]
 m.append(1)
 c=0
 for i in range(1,n):
  if(a[i]==a[i-1]):
   m[c]=m[c]+1
  else:
   b.append(a[i])
   m.append(1)
   c=c+1
 return(b,m)


  def count1(a):
 n=len(a[0])
 b=[]
 b.append([])
 b.append([])
 b[0].append(a[0][0])
 b[1].append(a[1][0])
 c=0
 for i in range(1,n):
  if(a[0][i]==a[0][i-1]):
   b[1][c]=b[1][c]+a[1][i]
  else:
   b[0].append(a[0][i])
   b[1].append(a[1][i])
   c=c+1

 return(b)
  def shuffle(a,b):
        r=len(a)
        s=len(b)
        # Generating an array of strings containing all combinations of weight r+s and depth s
        M=kbits(r+s,s)
        n=len(M)
        a1= []
        for i in range(n):
                a1.append(list(M[i]))
        # The zeroes are replaced by the entries of a and the ones by the entries of b
        a2= []
        for i in range(n):
                a2.append([])
                count0=0
                count1=0
                for j in range(s+r):
                        if(a1[i][j]=='0'):
                                a2[i].append(a[count0])
                                count0=count0+1
                        if(a1[i][j]=='1'):
                                a2[i].append(b[count1])
                                count1=count1+1
        # Reordering in lexicographic order the entries of a2: this is done by first reordering them according to the last digit, then the next to last digit, etc
        a3=sort(a2,r+s,max(a+b+[0]))
        # Getting the same list without repetitions and with multiplicities
        a4=count(a3)
        return(a4)
  def Regshuf0(a):
        r=[]
        r.append([])
        r.append([])
        t=0
        c=1
        for i in range(len(a)+1):
                if(t==0):
                        b=shuffle(a[:len(a)-i],a[len(a)-i:])
                        for j in range(len(b[0])):
                                r[0].append(b[0][j])
                                r[1].append(b[1][j]*c)
                        c=-c
                        if(i<len(a)):
                                if(a[len(a)-1-i]==1):
                                        t=1
        r=sort1(r,len(a),max(a+[0]))
        r=count1(r)
        rg=[]
        rg.append([])
        rg.append([])
        for i in range(len(r[0])):
                if(r[1][i] is not 0):
                        rg[0].append(r[0][i])
                        rg[1].append(r[1][i])
        return(rg)
  c = Regshuf0(a)
  for i in range(len(c[0])-1):
    if(c[1][i] != 0):
      print(c[1][i],"*",c[0][i] ,"+ ")
  if(c[1][len(c[0])-1] != 0):
    print(c[1][len(c[0])-1],"*",c[0][len(c[0])-1])


}}}
{{attachment:akhi7.png}}
== Shuffle Regularization at 1 ==
{{{#!sagecell
@interact
def _( w=(2,(2..20))):
 a=[0]
 a=a+[1 for i in range(1,w)]
 import itertools
 #this program gives the list of all binary words of weight n and depth k
 @interact
 def _(v=('word', input_grid(1, w, default=[a], to_value=lambda x: vector(flatten(x))))):
  a=[v[i] for i in range(len(v))]
  def kbits(n, k):
    result = []
    for bits in itertools.combinations(range(n), k):
        s = ['0'] * n
        for bit in bits:
            s[bit] = '1'
        result.append(''.join(s))
    return result
  def sort(a,l,m):
 b=[]
 n=len(a)
 for i in range(n):
  b.append(a[i])
 for j in range(l-1,-1,-1):
  k=0
  for t in range(m+1):
   for i in range(n):
    if(a[i][j]== t):
     b[k]=a[i]
     k=k+1
  for i in range(n):
   a[i]=b[i]
 return(a)

  def sort1(a,l,m):
 b=[]
 b.append([])
 b.append([])
 n=len(a[0])
 for i in range(n):
  b[0].append(a[0][i])
  b[1].append(a[1][i])
 for j in range(l-1,-1,-1):
  k=0
  for t in range(m+1):
   for i in range(n):
    if(a[0][i][j]== t):
     b[0][k]=a[0][i]
     b[1][k]=a[1][i]
     k=k+1
  for i in range(n):
   a[0][i]=b[0][i]
   a[1][i]=b[1][i]
 return(a)

  def count(a):
 n=len(a)
 b=[]
 b.append(a[0])
 m=[]
 m.append(1)
 c=0
 for i in range(1,n):
  if(a[i]==a[i-1]):
   m[c]=m[c]+1
  else:
   b.append(a[i])
   m.append(1)
   c=c+1
 return(b,m)


  def count1(a):
 n=len(a[0])
 b=[]
 b.append([])
 b.append([])
 b[0].append(a[0][0])
 b[1].append(a[1][0])
 c=0
 for i in range(1,n):
  if(a[0][i]==a[0][i-1]):
   b[1][c]=b[1][c]+a[1][i]
  else:
   b[0].append(a[0][i])
   b[1].append(a[1][i])
   c=c+1

 return(b)
  def shuffle(a,b):
        r=len(a)
        s=len(b)
        # Generating an array of strings containing all combinations of weight r+s and depth s
        M=kbits(r+s,s)
        n=len(M)
        a1= []
        for i in range(n):
                a1.append(list(M[i]))
        # The zeroes are replaced by the entries of a and the ones by the entries of b
        a2= []
        for i in range(n):
                a2.append([])
                count0=0
                count1=0
                for j in range(s+r):
                        if(a1[i][j]=='0'):
                                a2[i].append(a[count0])
                                count0=count0+1
                        if(a1[i][j]=='1'):
                                a2[i].append(b[count1])
                                count1=count1+1
        # Reordering in lexicographic order the entries of a2: this is done by first reordering them according to the last digit, then the next to last digit, etc
        a3=sort(a2,r+s,max(a+b+[0]))
        # Getting the same list without repetitions and with multiplicities
        a4=count(a3)
        return(a4)
  def Regshuf1(a):
 r=[]
 r.append([])
 r.append([])
 t=0
 c=1
 for i in range(len(a)+1):
  if(t==0):
   b=shuffle(a[:i],a[i:])
   for j in range(len(b[0])):
    r[0].append(b[0][j])
    r[1].append(b[1][j]*c)
   c=-c
   if(i<len(a)):
    if(a[i]==0):
     t=1
 r=sort1(r,len(a),max(a+[0]))
 r=count1(r)
 rg=[]
 rg.append([])
 rg.append([])
 for i in range(len(r[0])):
  if(r[1][i] is not 0):
   rg[0].append(r[0][i])
   rg[1].append(r[1][i])
 return(rg)
  c = Regshuf1(a)
  for i in range(len(c[0])-1):
    if(c[1][i] != 0):
      print(c[1][i],"*",c[0][i] ,"+ ")
  if(c[1][len(c[0])-1] != 0):
    print(c[1][len(c[0])-1],"*",c[0][len(c[0])-1])


}}}
{{attachment:akhi8.png}}

Contents

  1. Integer Factorization
    1. Divisibility Poset
    2. Factor Trees
    3. Factoring an Integer
  2. Prime Numbers
    1. Illustrating the prime number theorem
    2. Prime Spiral - Square FIXME
    3. Prime Spiral - Polar
  3. Modular Forms
    1. Computing modular forms
    2. Computing the cuspidal subgroup
    3. A Charpoly and Hecke Operator Graph
  4. Modular Arithmetic
    1. Quadratic Residue Table FIXME
    2. Cubic Residue Table FIXME
  5. Cyclotomic Fields
    1. Gauss and Jacobi Sums in Complex Plane
    2. Exhaustive Jacobi Plotter
  6. Elliptic Curves
    1. Adding points on an elliptic curve
    2. Plotting an elliptic curve over a finite field
  7. Cryptography
    1. The Diffie-Hellman Key Exchange Protocol
  8. Other
    1. Continued Fraction Plotter
    2. Computing Generalized Bernoulli Numbers
    3. Fundamental Domains of SL_2(ZZ)
  9. Multiple Zeta Values
    1. Computing Multiple Zeta values
      1. Word Input
      2. Composition Input
    2. Program to Compute Integer Relation between Multiple Zeta Values
    3. Word to composition
    4. Composition to Word
    5. Dual of a Word
    6. Shuffle product of two Words
    7. Shuffle Regularization at 0
    8. Shuffle Regularization at 1

Integer Factorization

Divisibility Poset

by William Stein

divposet.png

Factor Trees

by William Stein

factortree.png

More complicated demonstration using Mathematica: http://demonstrations.wolfram.com/FactorTrees/

Factoring an Integer

by Timothy Clemans

Sage implementation of the Mathematica demonstration of the same name. http://demonstrations.wolfram.com/FactoringAnInteger/

Prime Numbers

Illustrating the prime number theorem

by William Stein

primes.png

Prime Spiral - Square FIXME

by David Runde

SquareSpiral.PNG

Prime Spiral - Polar

by David Runde

PolarSpiral.PNG

Modular Forms

Computing modular forms

by William Stein

modformbasis.png

Computing the cuspidal subgroup

by William Stein

cuspgroup.png

A Charpoly and Hecke Operator Graph

by William Stein

heckegraph.png

Modular Arithmetic

Quadratic Residue Table FIXME

by Emily Kirkman

quadres.png

quadresbig.png

Cubic Residue Table FIXME

by Emily Kirkman

cubres.png

Cyclotomic Fields

Gauss and Jacobi Sums in Complex Plane

by Emily Kirkman

jacobising.png

Exhaustive Jacobi Plotter

by Emily Kirkman

jacobiexh.png

Elliptic Curves

Adding points on an elliptic curve

by David Møller Hansen

PointAddEllipticCurve.png

Plotting an elliptic curve over a finite field

ellffplot.png

Cryptography

The Diffie-Hellman Key Exchange Protocol

by Timothy Clemans and William Stein

dh.png

Other

Continued Fraction Plotter

by William Stein

contfracplot.png

Computing Generalized Bernoulli Numbers

by William Stein (Sage-2.10.3)

bernoulli.png

Fundamental Domains of SL_2(ZZ)

by Robert Miller

fund_domain.png

Multiple Zeta Values

by Akhilesh P.

Computing Multiple Zeta values

Word Input

akhi1.png

Composition Input

akhi5.png

Program to Compute Integer Relation between Multiple Zeta Values

akhi10.png

Word to composition

akhi2.png

Composition to Word

akhi3.png

Dual of a Word

akhi4.png

Shuffle product of two Words

akhi6.png

Shuffle Regularization at 0

akhi7.png

Shuffle Regularization at 1

akhi8.png

interact/number_theory (last edited 2020-06-14 09:10:48 by chapoton)