File: /Volumes/HOME/s/local/lib/python2.5/site-packages/sage/graphs/graph_database.py Source Code (starting at line 566): def CompleteBipartiteGraph(self, n1, n2): """ Returns a Complete Bipartite Graph sized n1+n2, with each of the nodes [0,(n1-1)] connected to each of the nodes [n1,(n2-1)] and vice versa. A Complete Bipartite Graph is a graph with its vertices partitioned into two groups, V1 and V2. Each v in V1 is connected to every v in V2, and vice versa. PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, each complete bipartite graph will be displayed with the first n1 nodes on the top row (at y=1) from left to right. The remaining n2 nodes appear at y=0, also from left to right. The shorter row (partition with fewer nodes) is stretched to the same length as the longer row, unless the shorter row has 1 node; in which case it is centered. The x values in the plot are in domain [0,max{n1,n2}]. In the Complete Bipartite graph, there is a visual difference in using the spring-layout algorithm vs. the position dictionary used in this constructor. The position dictionary flattens the graph and separates the partitioned nodes, making it clear which nodes an edge is connected to. The Complete Bipartite graph plotted with the spring-layout algorithm tends to center the nodes in n1 (see spring_med in examples below), thus overlapping its nodes and edges, making it typically hard to decipher. Filling the position dictionary in advance adds O(n) to the constructor. Feel free to race the constructors below in the examples section. The much larger difference is the time added by the spring-layout algorithm when plotting. (Also shown in the example below). The spring model is typically described as O(n^3), as appears to be the case in the NetworkX source code. EXAMPLES: # The following examples require NetworkX (to use default) sage: import networkx as NX # Compare the constructors (results will vary) sage.: time n = NX.complete_bipartite_graph(389,157); spring_big = Graph(n) # CPU time: 9.28 s, Wall time: 11.02 s sage.: time posdict_big = graphs.CompleteBipartiteGraph(389,157) # CPU time: 10.72 s, Wall time: 13.84 s # Compare the plotting speeds (results will vary) sage: n = NX.complete_bipartite_graph(11,17) sage: spring_med = Graph(n) sage: posdict_med = graphs.CompleteBipartiteGraph(11,17) # Notice here how the spring-layout tends to center the nodes of n1 sage.: time spring_med.show() # CPU time: 3.84 s, Wall time: 4.49 s sage.: time posdict_med.show() # CPU time: 0.96 s, Wall time: 1.14 s # View many Complete Bipartite graphs with a SAGE Graphics Array # With this constructor (i.e., the position dictionary filled) sage: g = [] sage: j = [] sage: for i in range(9): ... k = graphs.CompleteBipartiteGraph(i+1,4) ... g.append(k) ... sage: for i in range(3): ... n = [] ... for m in range(3): ... n.append(g[3*i + m].plot(node_size=50, with_labels=False)) ... j.append(n) ... sage: G = sage.plot.plot.GraphicsArray(j) sage.: G.show() # Compared to plotting with the spring-layout algorithm sage: g = [] sage: j = [] sage: for i in range(9): ... spr = NX.complete_bipartite_graph(i+1,4) ... k = Graph(spr) ... g.append(k) ... sage: for i in range(3): ... n = [] ... for m in range(3): ... n.append(g[3*i + m].plot(node_size=50, with_labels=False)) ... j.append(n) ... sage: G = sage.plot.plot.GraphicsArray(j) sage.: G.show() """ pos_dict = {} c1 = 1 # scaling factor for top row c2 = 1 # scaling factor for bottom row c3 = 0 # pad to center if top row has 1 node c4 = 0 # pad to center if bottom row has 1 node if n1 > n2: if n2 == 1: c4 = (n1-1)/2 else: c2 = ((n1-1)/(n2-1)) elif n2 > n1: if n1 == 1: c3 = (n2-1)/2 else: c1 = ((n2-1)/(n1-1)) for i in range(n1): x = c1*i + c3 y = 1 pos_dict[i] = [x,y] for i in range(n1+n2)[n1:]: x = c2*(i-n1) + c4 y = 0 pos_dict[i] = [x,y] G = NX.complete_bipartite_graph(n1,n2) return graph.Graph(G, pos=pos_dict, name="Complete bipartite graph on %d vertices"%(n1+n2))

File: /Users/was/s/local/lib/python/site-packages/sage/rings/bernoulli_mod_p.pyx Source Code (starting at line 202): def bernoulli_mod_p(int p): r""" Returns the bernoulli numbers $B_0, B_2, ... B_{p-3}$ modulo $p$. INPUT: p -- integer, a prime OUTPUT: list -- Bernoulli numbers modulo $p$ as a list of integers [B(0), B(2), ... B(p-3)]. ALGORITHM: Described in accompanying latex file. PERFORMANCE: Should be complexity $O(p \log p)$. EXAMPLES: Check the results against PARI's C-library implemention (that computes exact rationals) for $p = 37$: sage: bernoulli_mod_p(37) [1, 31, 16, 15, 16, 4, 17, 32, 22, 31, 15, 15, 17, 12, 29, 2, 0, 2] sage: [bernoulli(n) % 37 for n in xrange(0, 36, 2)] [1, 31, 16, 15, 16, 4, 17, 32, 22, 31, 15, 15, 17, 12, 29, 2, 0, 2] Boundary case: sage: bernoulli_mod_p(3) [1] AUTHOR: -- David Harvey (2006-08-06) """ if p <= 2: raise ValueError, "p (=%s) must be a prime >= 3"%p if not sage.libs.pari.gen.pari(p).isprime(): raise ValueError, "p (=%s) must be a prime"%p ntl.set_modulus(ntl.ZZ(p)) cdef int g, gSqr, gInv, gInvSqr, isOdd g = sage.rings.arith.primitive_root(p) gInv = arith_int.c_inverse_mod_int(g, p) gSqr = ((<llong> g) * g) % p gInvSqr = ((<llong> gInv) * gInv) % p isOdd = ((p-1)/2) % 2 # STEP 1: compute the polynomials G(X) and J(X) # These hold g^{i-1} and g^{-i} at the beginning of each iteration cdef llong gPower, gPowerInv gPower = gInv gPowerInv = 1 # "constant" is (g-1)/2 mod p cdef int constant if g % 2: constant = (g-1)/2 else: constant = (g+p-1)/2 # fudge holds g^{i^2}, fudgeInv holds g^{-i^2} cdef int fudge, fudgeInv fudge = fudgeInv = 1 cdef ntl_ZZ_pX G, J G = ntl.ZZ_pX() J = ntl.ZZ_pX() G.preallocate_space((p-1)/2) J.preallocate_space((p-1)/2) cdef int i cdef llong temp, h for i from 0 <= i < (p-1)/2: # compute h = h(g^i)/g^i (h(x) is as in latex notes) temp = g * gPower h = ((p + constant - (temp / p)) * gPowerInv) % p gPower = temp % p gPowerInv = (gPowerInv * gInv) % p # store the coefficient g^{i^2} h(g^i)/g^i G.setitem_from_int(i, <int> ((h * fudge) % p)) # store the coefficient g^{-i^2} J.setitem_from_int(i, fudgeInv) # update fudge and fudgeInv fudge = (((fudge * gPower) % p) * ((gPower * g) % p)) % p fudgeInv = (((fudgeInv * gPowerInv) % p) * ((gPowerInv * g) % p)) % p J.setitem_from_int(0, 0) # STEP 2: multiply the polynomials cdef ntl_ZZ_pX product product = G * J # STEP 3: assemble the result cdef int gSqrPower, value output = [1] gSqrPower = gSqr fudge = g for i from 1 <= i < (p-1)/2: value = product.getitem_as_int(i + (p-1)/2) if isOdd: value = (G.getitem_as_int(i) + product.getitem_as_int(i) - value + p) % p else: value = (G.getitem_as_int(i) + product.getitem_as_int(i) + value) % p value = (((4 * i * (<llong> fudge)) % p) * (<llong> value)) % p value = ((<llong> value) * (arith_int.c_inverse_mod_int(1 - gSqrPower, p))) % p output.append(value) gSqrPower = ((<llong> gSqrPower) * g) % p fudge = ((<llong> fudge) * gSqrPower) % p gSqrPower = ((<llong> gSqrPower) * g) % p return output

Factor Tree Worksheet

This worksheet uses the SAGE Notebook to illustrate integer factorization as a product of primes using the ``factor trees'' that students learn about in school.

rOU?# Worksheet '' (2006-12-04 at 13:45) sage: E.name() '_sage_[7]'rPU5# Worksheet '' (2006-12-04 at 13:45) sage: E.Rank() 1rQU<# Worksheet '' (2006-12-04 at 13:45) sage: a = maple('2+3') rRU.# Worksheet '' (2006-12-04 at 13:45) sage: a 5rSU=# Worksheet '' (2006-12-04 at 13:46) sage: a = maple('2007') rTU1# Worksheet '' (2006-12-04 at 13:46) sage: a 2007rUUF# Worksheet '' (2006-12-04 at 13:46) sage: a.ifactor() ``(3)^2*``(223)rVU;# Worksheet '' (2006-12-04 at 13:46) sage: a.name() 'sage1'rWUV# Worksheet '' (2006-12-04 at 13:47) sage: for i in range(5): ... print i 0 1 2 3 4rXUY# Worksheet 'graph' (2006-12-04 at 14:09) sage: g = graphs.CompleteBipartiteGraph(5,100) rYU8# Worksheet 'graph' (2006-12-04 at 14:09) sage: show(g) rZU{# Worksheet 'graph' (2006-12-04 at 14:16) sage: g Traceback (most recent call last): ... NameError: name 'g' is not definedr[UY# Worksheet 'graph' (2006-12-04 at 14:16) sage: g = graphs.CompleteBipartiteGraph(5,100) r\Uz# Worksheet 'graph' (2006-12-04 at 14:16) sage: g Complete bipartite graph on 105 vertices: a simple graph on 105 verticesr]UB# Worksheet 'graph' (2006-12-04 at 14:16) sage: g.save('mygraph') r^UW# Worksheet 'graph' (2006-12-04 at 14:18) sage: P = plot(sin, 0, 10, rgbcolor=(1,1,0)) r_Ud# Worksheet 'graph' (2006-12-04 at 14:18) sage: P Graphics object consisting of 1 graphics primitiver`U9# Worksheet 'graph' (2006-12-04 at 14:18) sage: P.show() raUY# Worksheet 'graph' (2006-12-04 at 14:18) sage: P = plot(sin, 0, 10, rgbcolor=(0,0.5,0)) rbUd# Worksheet 'graph' (2006-12-04 at 14:18) sage: P Graphics object consisting of 1 graphics primitivercU9# Worksheet 'graph' (2006-12-04 at 14:18) sage: P.show() rdUf# Worksheet 'graph' (2006-12-04 at 14:18) sage: P = plot(sin, 0, 10, rgbcolor=(0,0.5,0), thickness=5) reUd# Worksheet 'graph' (2006-12-04 at 14:18) sage: P Graphics object consisting of 1 graphics primitiverfU9# Worksheet 'graph' (2006-12-04 at 14:18) sage: P.show() rgU™# Worksheet 'graph' (2006-12-04 at 14:25) sage: bernoulli(100) -94598037819122125295227433069493721872702841533066936133385696204311395415197247711/33330rhUJ# Worksheet 'graph' (2006-12-04 at 14:25) sage: E = EllipticCurve('389a') riUG# Worksheet 'graph' (2006-12-04 at 14:25) sage: L = E.Lseries_zeros(2) rjUL# Worksheet 'graph' (2006-12-04 at 14:25) sage: L [0.000000000, 0.000000000]rkUG# Worksheet 'graph' (2006-12-04 at 14:25) sage: L = E.Lseries_zeros(5) rlUp# Worksheet 'graph' (2006-12-04 at 14:26) sage: L [0.000000000, 0.000000000, 2.87609907, 4.41689608, 5.79340263]rmU~# Worksheet 'graph' (2006-12-04 at 14:27) sage: time b = bernoulli(1000, algorithm='gap') CPU time: 0.06 s, Wall time: 4.59 srnU~# Worksheet 'graph' (2006-12-04 at 14:27) sage: time b = bernoulli(1000, algorithm='gap') CPU time: 0.01 s, Wall time: 0.01 sroU~# Worksheet 'graph' (2006-12-04 at 14:27) sage: time b = bernoulli(1002, algorithm='gap') CPU time: 0.02 s, Wall time: 0.03 srpU€# Worksheet 'graph' (2006-12-04 at 14:28) sage: time b = bernoulli(10000, algorithm='pari') CPU time: 0.44 s, Wall time: 0.48 srqU€# Worksheet 'graph' (2006-12-04 at 14:28) sage: time b = bernoulli(10000, algorithm='pari') CPU time: 0.24 s, Wall time: 0.27 srrU€# Worksheet 'graph' (2006-12-04 at 14:28) sage: time b = bernoulli(10000, algorithm='pari') CPU time: 0.24 s, Wall time: 0.26 srsU€# Worksheet 'graph' (2006-12-04 at 14:28) sage: time b = bernoulli(10000, algorithm='pari') CPU time: 0.24 s, Wall time: 0.26 srtU0# Worksheet '' (2007-01-05 at 09:53) sage: 2+3 5ruU0# Worksheet '' (2007-01-05 at 09:53) sage: 2+5 7rvTþ# Worksheet 'factor' (2007-01-05 at 09:54) sage: %hideall sage: #auto sage: sage: # The source code to draw factorization trees... sage: sage: import random sage: sage: def factor_tree(n, font=10): ... rows = [] ... v = [(n,None,0)] ... ftree(rows, v, 0, factor(n)) ... return draw_ftree(rows, font) ... sage: sage: def ftree(rows, v, i, F): ... if len(v) > 0: ... # add a row to g at the ith level. ... rows.append(v) ... w = [] ... for i in range(len(v)): ... k, _,_ = v[i] ... if k is None or is_prime(k): ... w.append((None,None,None)) ... else: ... d = random.choice(divisors(k)[1:-1]) ... w.append((d,k,i)) ... e = k//d ... if e == 1: ... w.append((None,None)) ... else: ... w.append((e,k,i)) ... if len(w) > len(v): ... ftree(rows, w, i+1, F) ... sage: sage: sage: def draw_ftree(rows,font): ... g = Graphics() ... for i in range(len(rows)): ... cur = rows[i] ... for j in range(len(cur)): ... e, f, k = cur[j] ... if not e is None: ... if is_prime(e): ... c = (1,0,0) ... else: ... c = (0,0,.4) ... g += text(str(e), (j*2-len(cur),-i), fontsize=font, rgbcolor=c) ... if not k is None and not f is None: ... g += line([(j*2-len(cur),-i), (k*2-len(rows[i-1]),-i+1)], alpha=0.4, thickness=1) ... return g ... sage: sage: def factor_trees(n, cols=4, rows=3, font=10): ... return graphics_array([[factor_tree(n,font) for _ in range(cols)] for _ in range(rows)]) CPU time: 0.00 s, Wall time: 0.00 srwUŽ# Worksheet 'factor' (2007-01-05 at 09:54) sage: F = factor_trees(300000000, rows=1, cols=1, font=8) sage: F.show(axes=False, figsize=[10,6]) rxUš# Worksheet 'factor' (2007-01-05 at 09:54) sage: F = factor_tree(prod(primes(40))) sage: F.show(xmin=-3,xmax=7,ymin=-5,ymax=0.5,figsize=[8,2],axes=False) ryUk# Worksheet 'factor' (2007-01-05 at 09:54) sage: show(factor_trees(1200,cols=3,rows=3),axes=False,dpi=100) rzUY# Worksheet 'qsieve' (2007-01-05 at 09:55) sage: n = next_prime(10^21)*next_prime(10^22) r{U•# Worksheet 'qsieve' (2007-01-05 at 09:55) sage: time factor(n) 1000000000000000000117 * 10000000000000000000009 CPU time: 0.53 s, Wall time: 0.78 sr|Uœ# Worksheet 'qsieve' (2007-01-05 at 09:55) sage: time qsieve(n) ([1000000000000000000117, 10000000000000000000009], '') CPU time: 0.00 s, Wall time: 0.53 sr}UY# Worksheet 'qsieve' (2007-01-05 at 09:55) sage: n = next_prime(10^22)*next_prime(10^24) r~U˜# Worksheet 'qsieve' (2007-01-05 at 09:55) sage: time factor(n) 10000000000000000000009 * 1000000000000000000000007 CPU time: 0.95 s, Wall time: 1.51 srUŸ# Worksheet 'qsieve' (2007-01-05 at 09:55) sage: time qsieve(n) ([10000000000000000000009, 1000000000000000000000007], '') CPU time: 0.01 s, Wall time: 0.81 sr€UY# Worksheet 'qsieve' (2007-01-05 at 09:55) sage: n = next_prime(10^24)*next_prime(10^26) rUœ# Worksheet 'qsieve' (2007-01-05 at 09:55) sage: time factor(n) 1000000000000000000000007 * 100000000000000000000000067 CPU time: 2.30 s, Wall time: 3.65 sr‚U£# Worksheet 'qsieve' (2007-01-05 at 09:55) sage: time qsieve(n) ([1000000000000000000000007, 100000000000000000000000067], '') CPU time: 0.01 s, Wall time: 2.08 srƒU°# Worksheet 'qsieve' (2007-01-05 at 09:55) sage: qsieve(n, time=True) ([1000000000000000000000007, 100000000000000000000000067], '2.55 real 1.46 user 0.01 sys')r„UY# Worksheet 'qsieve' (2007-01-05 at 09:56) sage: n = next_prime(10^25)*next_prime(10^27) r…Už# Worksheet 'qsieve' (2007-01-05 at 09:56) sage: time factor(n) 10000000000000000000000013 * 1000000000000000000000000103 CPU time: 3.60 s, Wall time: 5.46 sr†Uœ# Worksheet 'qsieve' (2007-01-05 at 09:56) sage: n = next_prime(10^25)*next_prime(10^27) sage: print n 10000000000000000000000014030000000000000000000001339r‡U²# Worksheet 'qsieve' (2007-01-05 at 09:56) sage: qsieve(n, time=True) ([10000000000000000000000013, 1000000000000000000000000103], '2.71 real 2.06 user 0.01 sys')rˆUÐ# Worksheet 'qsieve' (2007-01-05 at 09:56) sage: F, t = qsieve(n, time=True) sage: print F sage: print t [10000000000000000000000013, 1000000000000000000000000103] 2.73 real 2.06 user 0.01 sysr‰Už# Worksheet 'qsieve' (2007-01-05 at 09:56) sage: n = next_prime(10^26)*next_prime(10^28) sage: print n 1000000000000000000000000703100000000000000000000022177rŠU # Worksheet 'qsieve' (2007-01-05 at 09:56) sage: time factor(n) 100000000000000000000000067 * 10000000000000000000000000331 CPU time: 5.33 s, Wall time: 8.05 sr‹UÒ# Worksheet 'qsieve' (2007-01-05 at 09:56) sage: F, t = qsieve(n, time=True) sage: print F sage: print t [100000000000000000000000067, 10000000000000000000000000331] 4.96 real 3.46 user 0.02 sysrŒU¡# Worksheet 'qsieve' (2007-01-05 at 09:58) sage: n = next_prime(10^27)*next_prime(10^30) sage: print n 1000000000000000000000000103057000000000000000000000005871rU¥# Worksheet 'qsieve' (2007-01-05 at 09:58) sage: time factor(n) 1000000000000000000000000103 * 1000000000000000000000000000057 CPU time: 12.82 s, Wall time: 19.37 srŽUÖ# Worksheet 'qsieve' (2007-01-05 at 09:59) sage: F, t = qsieve(n, time=True) sage: print F sage: print t [1000000000000000000000000103, 1000000000000000000000000000057] 12.09 real 8.88 user 0.06 sysrU¤# Worksheet 'qsieve' (2007-01-05 at 09:59) sage: n = next_prime(10^29)*next_prime(10^31) sage: print n 1000000000000000000000000003193300000000000000000000000010527rU¨# Worksheet 'qsieve' (2007-01-05 at 10:00) sage: time factor(n) 100000000000000000000000000319 * 10000000000000000000000000000033 CPU time: 27.28 s, Wall time: 41.15 sr‘UÙ# Worksheet 'qsieve' (2007-01-05 at 10:00) sage: F, t = qsieve(n, time=True) sage: print F sage: print t [100000000000000000000000000319, 10000000000000000000000000000033] 22.45 real 15.22 user 0.11 sysr’U¬# Worksheet 'qsieve' (2007-01-05 at 10:19) sage: n = next_prime(10^33)*next_prime(10^35) sage: print n 100000000000000000000000000000006169000000000000000000000000000004209r“U©# Worksheet 'qsieve' (2007-01-05 at 10:21) sage: n = next_prime(10^32)*next_prime(10^33) sage: print n 100000000000000000000000000000055100000000000000000000000000002989r”UÞ# Worksheet 'qsieve' (2007-01-05 at 10:22) sage: F, t = qsieve(n, time=True) sage: print F sage: print t [100000000000000000000000000000049, 1000000000000000000000000000000061] 80.95 real 45.56 user 0.49 sysr•U# Worksheet 'qsieve' (2007-01-05 at 10:24) sage: time factor(n) 100000000000000000000000000000049 * 1000000000000000000000000000000061 CPU time: 64.23 s, Wall time: 87.90 sr–UW# Worksheet 'qsieve' (2007-01-05 at 10:41) sage: q = qsieve(n, time=True, block=False) r—UL# Worksheet 'qsieve' (2007-01-05 at 10:41) sage: q Proper factors so far: []r˜U?# Worksheet 'qsieve' (2007-01-05 at 10:41) sage: q.done() Falser™U6# Worksheet 'qsieve' (2007-01-05 at 10:41) sage: 2+2 4ršT# Worksheet 'qsieve' (2007-01-05 at 10:41) sage: q.log() 'Input number to factor [ >=40 decimal digits]: 100000000000000000000000000000055100000000000000000000000000002989\r\n\r\n\r\n\r\n100 relations, 9 partials.\r\n1260 curves.\r\n200 relations, 15 partials.\r\n2520 curves.\r\n300 relations, 25 partials.\r\n400 relations, 38 partials.\r\n3780 curves.\r\n500 relations, 46 partials.\r\n600 relations, 55 partials.\r\n5040 curves.\r\n700 relations, 61 partials.\r\n6300 curves.\r\n800 relations, 70 partials.\r\n900...r›T# Worksheet 'qsieve' (2007-01-05 at 10:41) sage: print q.log() Input number to factor [ >=40 decimal digits]: 100000000000000000000000000000055100000000000000000000000000002989 100 relations, 9 partials. 1260 curves. 200 relations, 15 partials. 2520 curves. 300 relations, 25 partials. 400 relations, 38 partials. 3780 curves. 500 relations, 46 partials. 600 relations, 55 partials. 5040 curves. 700 relations, 61 partials. 6300 curves. 800 relations, 70 partials. 900 relations, 81 partials. 7560 curves. 1000 relations...rœU?# Worksheet 'qsieve' (2007-01-05 at 10:45) sage: q.done() FalserU?# Worksheet 'qsieve' (2007-01-05 at 10:45) sage: q.done() FalseržUL# Worksheet 'qsieve' (2007-01-05 at 10:45) sage: q Proper factors so far: []rŸT# Worksheet 'qsieve' (2007-01-05 at 10:46) sage: print q.log() Input number to factor [ >=40 decimal digits]: 100000000000000000000000000000055100000000000000000000000000002989 100 relations, 9 partials. 1260 curves. 200 relations, 15 partials. 2520 curves. 300 relations, 25 partials. 400 relations, 38 partials. 3780 curves. 500 relations, 46 partials. 600 relations, 55 partials. 5040 curves. 700 relations, 61 partials. 6300 curves. 800 relations, 70 partials. 900 relations, 81 partials. 7560 curves. 1000 relations...r T# Worksheet 'qsieve' (2007-01-05 at 10:46) sage: print q.log() Input number to factor [ >=40 decimal digits]: 100000000000000000000000000000055100000000000000000000000000002989 100 relations, 9 partials. 1260 curves. 200 relations, 15 partials. 2520 curves. 300 relations, 25 partials. 400 relations, 38 partials. 3780 curves. 500 relations, 46 partials. 600 relations, 55 partials. 5040 curves. 700 relations, 61 partials. 6300 curves. 800 relations, 70 partials. 900 relations, 81 partials. 7560 curves. 1000 relations...r¡U¡# Worksheet 'qsieve' (2007-01-05 at 10:46) sage: q.stop() Traceback (most recent call last): ... AttributeError: qsieve_nonblock instance has no attribute 'stop'r¢U²# Worksheet 'qsieve' (2007-01-05 at 10:46) sage: q.quit() Traceback (most recent call last): ... pexpect.ExceptionPexpect: close() could not terminate the child using terminate()r£U:# Worksheet 'qsieve' (2007-01-05 at 10:46) sage: q.quit() r¤U;# Worksheet 'qsieve' (2007-01-05 at 10:46) sage: q ([], '')r¥Tþ# Worksheet 'factor' (2007-01-05 at 14:27) sage: %hideall sage: #auto sage: sage: # The source code to draw factorization trees... sage: sage: import random sage: sage: def factor_tree(n, font=10): ... rows = [] ... v = [(n,None,0)] ... ftree(rows, v, 0, factor(n)) ... return draw_ftree(rows, font) ... sage: sage: def ftree(rows, v, i, F): ... if len(v) > 0: ... # add a row to g at the ith level. ... rows.append(v) ... w = [] ... for i in range(len(v)): ... k, _,_ = v[i] ... if k is None or is_prime(k): ... w.append((None,None,None)) ... else: ... d = random.choice(divisors(k)[1:-1]) ... w.append((d,k,i)) ... e = k//d ... if e == 1: ... w.append((None,None)) ... else: ... w.append((e,k,i)) ... if len(w) > len(v): ... ftree(rows, w, i+1, F) ... sage: sage: sage: def draw_ftree(rows,font): ... g = Graphics() ... for i in range(len(rows)): ... cur = rows[i] ... for j in range(len(cur)): ... e, f, k = cur[j] ... if not e is None: ... if is_prime(e): ... c = (1,0,0) ... else: ... c = (0,0,.4) ... g += text(str(e), (j*2-len(cur),-i), fontsize=font, rgbcolor=c) ... if not k is None and not f is None: ... g += line([(j*2-len(cur),-i), (k*2-len(rows[i-1]),-i+1)], alpha=0.4, thickness=1) ... return g ... sage: sage: def factor_trees(n, cols=4, rows=3, font=10): ... return graphics_array([[factor_tree(n,font) for _ in range(cols)] for _ in range(rows)]) CPU time: 0.00 s, Wall time: 0.00 sr¦U‰# Worksheet 'factor' (2007-01-05 at 14:28) sage: F = factor_trees(2007, rows=1, cols=1, font=8) sage: F.show(axes=False, figsize=[10,6]) r§UŽ# Worksheet 'bernoull_mod' (2007-01-05 at 14:28) sage: bernoulli_mod_p(37) [1, 31, 16, 15, 16, 4, 17, 32, 22, 31, 15, 15, 17, 12, 29, 2, 0, 2]r¨U¡# Worksheet 'bernoull_mod' (2007-01-05 at 14:29) sage: time v=bernoulli_mod_p(10^4) Traceback (most recent call last): ... ValueError: p (=10000) must be a primer©U„# Worksheet 'bernoull_mod' (2007-01-05 at 14:29) sage: time v=bernoulli_mod_p(next_prime(10^4)) CPU time: 0.06 s, Wall time: 0.17 srªU„# Worksheet 'bernoull_mod' (2007-01-05 at 14:29) sage: time v=bernoulli_mod_p(next_prime(10^5)) CPU time: 0.75 s, Wall time: 0.78 sr«U0# Worksheet '' (2007-01-05 at 14:32) sage: 2+3 5r¬U0# Worksheet '' (2007-01-05 at 14:32) sage: 2+5 7rUP# Worksheet '' (2007-01-05 at 14:33) sage: E = magma.EllipticCurve([1,2,3,4,5]) r®UÉ# Worksheet '' (2007-01-05 at 14:33) sage: %sh sage: ps ax |grep magma 687 p4 S+ 0:00.00 grep magma 682 p5 Ss+ 0:01.65 /Users/was/local/magma/magma.exe -n /Users/was/talks/2007-01-05-msrr¯U‚# Worksheet '' (2007-01-05 at 14:33) sage: E Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 4*x + 5 over Rational Fieldr°U_# Worksheet '' (2007-01-05 at 14:33) sage: type(E) r±UW# Worksheet '' (2007-01-05 at 14:34) sage: E.TorsionSubgroup() Abelian Group of order 1r²UD# Worksheet '' (2007-01-05 at 14:34) sage: magma.eval('2^10') '1024'r³U;# Worksheet '' (2007-01-05 at 14:35) sage: a = magma(-5/6) r´U1# Worksheet '' (2007-01-05 at 14:35) sage: a -5/6rµU5# Worksheet '' (2007-01-05 at 14:35) sage: b = gp(a) r¶U1# Worksheet '' (2007-01-05 at 14:35) sage: b -5/6r·U6# Worksheet '' (2007-01-05 at 14:36) sage: s = str(a) r¸U3# Worksheet '' (2007-01-05 at 14:36) sage: s '-5/6'r¹U<# Worksheet '' (2007-01-05 at 14:36) sage: sage_eval(s) -5/6rºU7# Worksheet 'boothby' (2007-01-05 at 14:40) sage: 2+2 4r»U[# Worksheet 'boothby' (2007-01-05 at 14:44) sage: A = MatrixSpace(ZZ,100).random_element() r¼U\# Worksheet 'boothby2' (2007-01-05 at 14:45) sage: A = MatrixSpace(ZZ,100).random_element() r½U[# Worksheet 'boothby2' (2007-01-05 at 14:45) sage: A = MatrixSpace(ZZ,10).random_element() r¾Uç# Worksheet 'boothby2' (2007-01-05 at 14:45) sage: %time sage: A.characteristic_polynomial() x^10 + 8*x^9 + 7*x^8 - 19*x^7 + 179*x^6 + 1177*x^5 + 5281*x^4 + 17998*x^3 + 303*x^2 + 80998*x - 59474 CPU time: 0.02 s, Wall time: 0.11 sr¿U[# Worksheet 'boothby2' (2007-01-05 at 14:46) sage: A = MatrixSpace(ZZ,20).random_element() rÀTº# Worksheet 'boothby2' (2007-01-05 at 14:46) sage: %time sage: A.characteristic_polynomial() x^20 - 8*x^19 + 6*x^18 - 214*x^17 + 1793*x^16 - 5075*x^15 + 48929*x^14 + 18144*x^13 - 3503664*x^12 + 21816786*x^11 - 128077072*x^10 + 204941895*x^9 - 575326349*x^8 + 153952082*x^7 + 50348199867*x^6 - 179830544090*x^5 + 653932820298*x^4 - 4414556160025*x^3 + 10322875513858*x^2 - 13965115307613*x + 39642628772487 CPU time: 0.13 s, Wall time: 0.14 srÁUÆ# Worksheet 'boothby2' (2007-01-05 at 14:48) sage: A.view() Traceback (most recent call last): ... AttributeError: 'sage.matrix.matrix_integer_dense.Matrix_integer_de' object has no attribute 'view'rÂUÆ# Worksheet 'boothby2' (2007-01-05 at 14:48) sage: A.show() Traceback (most recent call last): ... AttributeError: 'sage.matrix.matrix_integer_dense.Matrix_integer_de' object has no attribute 'show'rÃT # Worksheet 'boothby2' (2007-01-05 at 14:48) sage: show(A)

\left(\begin{array}{rrrrrrrrrrrrrrrrrrrr} 2&-2&-1&-2&2&-1&-2&2&-2&1&-1&-2&1&2&-2&1&1&1&-1&2\\ -1&1&-1&1&1&-2&2&2&-1&-1&-1&-1&1&2&-1&-1&-1&2&2&-2\\ 1&-2&1&2&-1&-1&-2&1&-1&-1&1&1&-2&-2&2&2&1&-2&2&-1\\ -1&2&2&-2&1&2&2&1&-1&2&-1&-2&-1&1&-2&-2&1&-2&-2&-2\\ -1&2&-2&1&2&2&-2&-2&-2&-1&-1&-1&-2&2&-2&1&1&1&1&-1\\ 2&-2&-1&-1&2&1&2&-1&-2&-1&1&1&-2&1&-1&-1&-1&2&-2&-2\\ -2&2&-2&-2&2&2&2&1&-1&-1&1&-2&-1&-2&-1&-2&2&2&1&1\\ -1&-2&2&-2&1&-1&2&-1&1&2&...rÄTù# Worksheet 'boothby2' (2007-01-05 at 14:49) sage: %time sage: show(A.characteristic_polynomial())

x^{20} - 8x^{19} + 6x^{18} - 214x^{17} + 1793x^{16} - 5075x^{15} + 48929x^{14} + 18144x^{13} - 3503664x^{12} + 21816786x^{11} - 128077072x^{10} + 204941895x^{9} - 575326349x^{8} + 153952082x^{7} + 50348199867x^{6} - 179830544090x^{5} + 653932820298x^{4} - 4414556160025x^{3} + 10322875513858x^{2} - 13965115307613x + 39642628772487

CPU time: 0.00 s, Wall time: 0.00 srÅTÔ# Worksheet 'boothby2' (2007-01-05 at 14:49) sage: %time sage: latex(A.characteristic_polynomial()) x^{20} - 8x^{19} + 6x^{18} - 214x^{17} + 1793x^{16} - 5075x^{15} + 48929x^{14} + 18144x^{13} - 3503664x^{12} + 21816786x^{11} - 128077072x^{10} + 204941895x^{9} - 575326349x^{8} + 153952082x^{7} + 50348199867x^{6} - 179830544090x^{5} + 653932820298x^{4} - 4414556160025x^{3} + 10322875513858x^{2} - 13965115307613x + 39642628772487 CPU time: 0.00 s, Wall time: 0.00 srÆU[# Worksheet 'boothby2' (2007-01-05 at 14:52) sage: A = MatrixSpace(ZZ,20).random_element() rÇTº# Worksheet 'boothby2' (2007-01-05 at 14:52) sage: %time sage: A.characteristic_polynomial() x^20 + x^19 - 48*x^18 - 248*x^17 + 4281*x^16 - 6925*x^15 - 48119*x^14 - 707292*x^13 + 6241051*x^12 + 10172390*x^11 - 121169427*x^10 - 296266733*x^9 + 1505434256*x^8 + 3541680905*x^7 - 3496581918*x^6 - 191335962487*x^5 + 377854814060*x^4 + 1684293041404*x^3 - 12520145979924*x^2 - 8695150961834*x + 50834179507692 CPU time: 0.12 s, Wall time: 0.19 srÈUŒ# Worksheet 'boothby2' (2007-01-05 at 14:52) sage: %time sage: a = latex(A.characteristic_polynomial()) CPU time: 0.00 s, Wall time: 0.00 srÉU.# Worksheet 'boothby2' (2007-01-05 at 14:52) rÊU.# Worksheet 'boothby2' (2007-01-05 at 14:52) rËU.# Worksheet 'boothby2' (2007-01-05 at 14:52) rÌUw# Worksheet 'boothby2' (2007-01-05 at 14:53) sage: plot(sin, 0,2*pi) Graphics object consisting of 1 graphics primitiverÍUL# Worksheet 'boothby2' (2007-01-05 at 14:54) sage: plot(sin, 0,2*pi).show() rÎU:# Worksheet 'boothby2' (2007-01-05 at 14:54) sage: save A rÏU:# Worksheet 'boothby3' (2007-01-05 at 14:54) sage: load a rÐU:# Worksheet 'boothby3' (2007-01-05 at 14:54) sage: load A rÑU?# Worksheet 'boothby3' (2007-01-05 at 14:55) sage: A.height() 2rÒeU_Notebook__defaultsrÓ}rÔ(Ucell_output_colorrÕU#0000EErÖUmax_history_lengthr×MôUcell_input_colorrØU#0000000rÙUword_wrap_colsrÚKPuU_Notebook__worksheet_dirrÛUsage_notebook/worksheetsrÜU_Notebook__history_countrÝKU_Notebook__log_serverrÞ‰U_Notebook__filenamerßUsage_notebook/nb.sobjràU_Notebook__default_worksheetrá(horâ}rã(h U _scratch_räh ]rå(horæ}rç(hUhjâh‰jUhKhU*sage_notebook/worksheets/_scratch_/cells/0rèhUh‰h Kjjh'‰ubahÜ‰jP}réhÝU"sage_notebook/worksheets/_scratch_rêhç]rëhéKhïhhëˆhìU _scratch_rìhíU1165187727.127047ríhóU 11G3BJNEUV/PkrîhðKhòNubU_Notebook__server_logrï]rðU_Notebook__next_worksheet_idrñK U_Notebook__kill_idleròKU_Notebook__systemróNU_Notebook__show_debugrô‰U_Notebook__dirrõU sage_notebookröU_Notebook__authr÷U:U_Notebook__colorrøNU_Notebook__object_dirrùUsage_notebook/objectsrúU_default_filenamerûU5/Users/was/talks/2007-01-05-msr/sage_notebook/nb.sobjrüU_Notebook__splashpagerýˆub.