- mathfun@mailman.xmission.com - mailman.xmission.com

Re: [math-fun] New Mersenne prime, exponent 30,402,457
by Daniel Asimov 30 Dec '05

30 Dec '05

Rich wrote: << There's a new Mersenne prime, 2 ^ 30,402,457 - 1. 9.2 million digits. More details at www.mersenne.org. >> I'm curious if people are searching for new Mersenne primes just for the fun of the hunt, or if there is a deeper reason, such as to gather evidence bearing on some conjecture(s) about them (or evidence for potentially formulating some conjecture about them). Question: Is it known that there exist infinitely many Mersenne primes? If not, what is the evidence for and against? --Dan

2 1

[math-fun] trolls
by Schroeppel, Richard 30 Dec '05

30 Dec '05

Global warming trolls, including replies, will earn the offender 30 days moderation. Sit on your hands. Rich

1 0

[math-fun] minimum area convex lattice polygons - results
by Chris Landauer 30 Dec '05

30 Dec '05

file systematic-results.txt results from systematic searches (with various programs, as, aq, ai, ao, af, and ae, co and ce) and from the dynamic programming approach (with various programs phalf, pmap, pndx, pvrt) best systematic for even n min min min longest max edge running n area perim edge bound used now later 04 1 4 1 50 06 3 8 2 50 08 7 12 2 50 10 14 18 3 50 12 24 24 3 50 14 40 30 3 50 16 59 36 3 50 18 87 44 4 50 20 121 52 4 50 22 164 62 5 50 24 210 72 5 50 26 274 80 5 50 28 345 90 5 50 30 430 98 5 50 32 523 108 5 40 34 632 118 5 30 36 749 128 5 20 38 890 138 5 18 40 1039 148 5 18 42 1222 162 7 16 44 1412 176 7 16 46 1620 192 7 14 48 1838 208 8 14 50 2088 218 8 14 52 2357 234 8 14 54 2651 244 8 14 56 2953 260 8 14 58 3278 278 9 12 14 60 3612 296 9 12 14 62 4020 308 9 12 14 64 4439 322 9 12 14 66 4902 334 9 12 14 68 5387 348 9 12 14 70 5898 362 9 12 14 72 6418 376 9 12 14 74 6974 390 9 12 14 76 7557 404 9 12 14 78 8182 420 9 12 14 80 8835 434 9 12 14 82 9512 450 9 12 14 84 10218 464 9 13 14 86 10984 482 9 13 14 88 11759 500 9 13 14 90 12635 516 9 13 14 92 13525 532 9 13 14 94 14448 550 9 13 14 96 15399 568 9 13 14 98 16415 588 10 13 14 100 17473 608 10 13 14 best systematic for odd n min min min longest edge bound running n area perim edge max used now later 03 0.5 4 2 50 05 2.5 8 2 50 07 6.5 12 3 50 09 10.5 16 3 50 11 21.5 22 3 50 13 32.5 28 4 50 15 51.5 34 4 40 17 75.5 42 5 30 19 106.5 50 5 20 21 144.5 60 5 18 20 23 193.5 66 5 16 20 25 248.5 76 5 14 20 27 312.5 88 7 14 20 29 391.5 96 7 14 20 31 483.5 106 7 14 20 33 588.5 120 7 14 18 35 704.5 124 6 14 18 37 835.5 136 7 14 18 39 977.5 146 7 14 16 41 1139.5 156 7 14 16 43 1325.5 168 7 14 15 45 1525.5 182 7 14 16 47 1746.5 196 7 14 16 49 1984.5 212 8 14 51 2244.5 228 9 14 53 2522.5 246 9 14 55 2811.5 258 9 14 57 3121.5 276 9 12 14 59 3495.5 282 9 12 14 61 3865.5 302 9 12 14 63 4273.5 314 9 12 14 65 4713.5 326 9 12 14 67 5178.5 340 9 12 14 69 5669.5 350 9 12 14 71 6179.5 368 9 12 14 73 6729.5 382 9 12 14 75 7307.5 394 9 12 14 77 7905.5 408 9 12 14 79 8536.5 426 9 12 14 81 9215.5 442 9 12 14 83 9916.5 458 9 12 14 85 10660.5 474 9 13 14 87 11450.5 492 10 13 14 89 12263.5 510 10 13 14 91 13141.5 528 11 13 14 93 14052.5 546 11 13 14 95 14996.5 562 10 13 14 97 15979.5 578 11 13 14 99 17009.5 602 11 13 14 end of file systematic-results.txt

5 4

[math-fun] New Mersenne prime, exponent 30,402,457
by Schroeppel, Richard 30 Dec '05

30 Dec '05

There's a new Mersenne prime, 2 ^ 30,402,457 - 1. 9.2 million digits. More details at www.mersenne.org. Rich

4 3

[math-fun] Re: copy (fwd)
by Richard Guy 30 Dec '05

30 Dec '05

Perhaps I shdve sent this to others than Neil. R. ---------- Forwarded message ---------- Date: Fri, 30 Dec 2005 13:21:33 -0700 (MST) From: Richard Guy <rkg(a)cpsc.ucalgary.ca> To: N. J. A. Sloane <njas(a)research.att.com> Subject: Re: copy It may be that the 38th is the last one to be certain (that there are no smaller others). Later: I've just cribbed the following from the status page of GIMPS. Evidently there is still some chance of finding another before what is suspected to be the 40th. R. All exponents below 11,145,000 have been tested and double-checked. All exponents below 16,693,000 have been tested at least once. Countdown to testing all exponents below M(20996011) once: 448 Countdown to testing all exponents below M(24036583) once: 2,337 Countdown to testing all exponents below M(25964951) once: 6,286 Countdown to testing all exponents below M(30402457) once: 43,294 Countdown to proving M(13466917) is the 39th Mersenne Prime: 128 Countdown to proving M(20996011) is the 40th Mersenne Prime: 128,672 Countdown to proving M(24036583) is the 41st Mersenne Prime: 193,946 Countdown to proving M(25964951) is the 42nd Mersenne Prime: 235,460 Countdown to proving M(30402457) is the 43rd Mersenne Prime: 332,615 On Fri, 30 Dec 2005, N. J. A. Sloane wrote: > sorry Richard , I meant to copy this to you. > > Richard Guy said: > n 31 32 33 34 35 36 37 > M 216091 756839 859433 1257787 1398269 2976221 3021377 > g 31.6 34.8 35.1 36.1 36.4 38.3 38.3 > > n 38 39 40 41 42 43 > M 6972593 13466917 20996011 24036583 25964951 30402457 > g 40.5 42.2 43.2 43.7 43.9 44.3 > > Me: In the entry A000043 I have a comment that says that 13466917 IS > the > 39-th Mersenne prime. But is it really known that 20996011 is the > 40th? > In other words, how far has the exhaustive search been taken? > > I looked at the GIMPS page but could not (easily) see the answer. > > Neil

1 0

Re: [math-fun] Boolean synthesis request from Knuth
by Henry Baker 30 Dec '05

30 Dec '05

I've always been curious about the feedback/loops restriction. Does anyone know how much things can be improved for boolean _functions_ that are implemented with feedback and/or loops? I suspect that latency can't be improved, but I suspect that the # of gates can be improved over the no feedback/loop version. (To be clear, I'm thinking about implementing functions using circuits that might have state, but the initial state is irrelevant to the output. For example, a boolean circuit might utilize some sort of hash table lookup to implement an initial guess that is verified before being output. In this case, the (mean) latency could be improved over the no-state version.) At 05:00 PM 12/29/2005, Schroeppel, Richard wrote: >The allowed gates are two-input And and two-input Xor; also, Nots >may be used freely, and don't count against the total. As usual, >the circuits must be DAGs (no feedback or loops), and circuit >depth doesn't matter.

2 1

[math-fun] minimum area convex lattice polygons - explanations
by Chris Landauer 29 Dec '05

29 Dec '05

file announce.txt announcement of search results changed 16:10-11:25 PST, 23 December 2005 at argus changed 11:05-11:15 PST, 23 December 2005 at argus changed 10:20-10:30 PST, 23 December 2005 at argus created 00:00-01:10 PST, 23 December 2005 at argus 0. Abstract 1. Problem 1.1. Complication SL(2,z) 2. Approach 2.1. Edge Length Bound 2.2. Polygon Ordering 2.3. Corners 2.4. Algorithm 3. Simplifications 3.1. Fractions 3.2. Even Theorem and Odd Heuristic 3.3. Normalization 4. More Complications: Margin 5. More Algorithms: Random 6. New Algorithms 6.1. Dynamic Programming 6.2. Current State 7. Results 0. Abstract This note describes my progress and results on the minimum area convex lattice polygon problem. My programs have results up to n=100, with some confidence. I have realized that this note is fairly cryptic as an explanation, and yet it is still too long. More details are available 8-). 1. Problem To find the minimum area convex lattice polygons with n sides for small n (polygon = convex lattice polygon in the rest of this note). 1.1. Complication SL(2,Z) Since SL(2,Z) preserves area, all SL(2,Z) images of a minimum area polygon are also minimum area polygons. That means that there are infinitely many different minimum area polygons for each n. 2. Approach 2.1. Edge Length Bound I addressed the SL(2,Z) problem by running searches with an imposed maximum edge length bound b to reduce the search to a finite number of possibilities. This means that my results tell us almost nothing about how many SL(2,Z)-classes of minimum area polygons there are, since there is no theorem about class representatives with small maximum edge length (in many but not all small cases, my programs found more than one such class). 2.2. Polygon Ordering My programs use an ordering among the polygons first by smaller area, then by same area and smaller perimeter, and finally by same area and perimeter and smaller maximum edge length. Note that the ordering of polygons by area is different from the ordering by perimeter. It frequently occurs that the minimum area polygons do not have the minimum perimeter. So a minimum polygon has minimum area among polygons with n sides, but also minimum perimeter among the polygons with minimum area, and also minimum maximum edge length among the polygons with minimum area and perimeter. There is no assumption that a minimum polygon is unique. 2.3. Corners My programs always consider polygons as enumerated from the vertex with the least y value (and the one with the least x value if there are two least y values), in a counter-clockwise order. This means that the angle of the oriented edge vector is increasing from at least 0 to just under 2*pi. Each edge can be identified as belonging to a corner, representing the number of pi/2 clockwise rotations required to change the oriented edge vector into one that moves up (positive y) and to the right (non-negative x). This is the same as the first quadrant, modulo the boundary rules just mentioned. 2.4. Algorithm The first algorithm I wrote attempted to move an edge around in the lattice and keep adding new edges with larger angle. It was good enough to extend the results up to n=17 or so, but quickly ran out of steam. 3. Simplifications Other hints and messages on math-fun led me to two important simplifications and a potential simplification that I could not use (though it took me a long time to figure that out). 3.1. Fractions An edge of a minimum area polygon has no interior lattice points, so the edge coordinates are relatively prime. We can identify each corner0 edge with a fraction n/d, where 0<=n, 1<=d, gcd(n,d) = 1, and we decided to use the L1 length, so our edge length bound is n+d < b (it is a historical artifact that the inequality is strict). The number nf of such fractions is easy to count nf(1) = 0; nf(b+1) = nf(b) + phi(b), so nf(b) = sum(1<=d<=b-1) phi(d), which we give as a small table here b nf(b) 1 0 2 1 3 2 4 4 5 6 6 10 7 12 8 18 9 22 10 28 11 32 12 42 3.2. Even Theorem and Odd Heuristic Somebody mentioned on math-fun a theorem that for n even, there were always edge-symmetric minimum area polygons. That means, in my corner terminology, that corner2 is the negative of corner0 and corner3 is the negative of corner1. I also noticed that for odd n up to about 21, there were always minimum area polygons with corner0 plus corner1 being almost half the sides, so I assumed that in all subsequent searches. Using this restriction also ignores many potential SL(2,Z)-classes of minimum polygons. 3.3. Normalization If the polygon start vertex (least y value, and least x value if there are two least y values) is moved to the origin, then there are elements of SL(2,Z) that will move the next vertex to (1, 0), so we could make the assumption that the first edge is [1, 0]. The reason my programs can't use that assumption is that there is no control over the maximum edge length of the resulting polygon. Omitting that assumption made the searches much longer, but did occasionally find better polygons. 4. More Complications: Margin Because my programs use an edge length bound, my original strategy was to gradually increase it until no better polygons are found. However, the following peculiar phenomenon occurs: for n=27, 29, 31, 33, with edge bound 6, my programs found minimum polygons with maximum edge length of 5. For the same n, with edge bound 7, the same minimum polygons were found, so I thought that the programs were done with those cases. However, when the program was run with edge bound 8, better polygons were found for all of these n, with maximum edge length of 7. So the concept of margin now becomes important as a measure of confidence. The margin of a result is the difference between the edge length bound and the maximum edge length found for a minimum polygon. The peculiar phenomenon shows that margin 2 is not enough. This phenomenon has not occurred for any other n, and my programs are currently working on extending the results to margin 4 or 5. 5. More Algorithms: Random The backtrack programs take a long time (the last one currently running has used over 1600 hours of cpu time so far, and we expect it to use about 2000), so I rewrote the backtracking algorithm into a random program, that would make a random next choice instead of the next available choice. In large cases, the random found several polygons better than any of the systematic searches had. 6. New Algorithms This was the state of affairs for almost two years, as I occasionally posted some partial results to math-fun (without a lot of confidence in the larger values). These program were running almost continuously on between two and six of my fast computers (high-end commodity Intel PCs running FreeBSD 5.4, all between 3GHz and 3.6GHz, each with 4GB of memory and at least 1TB of disk space) and a few others, for the entire two years, stopped only two or three times by city power failures, usually for less than a day (my multiple UPS arrangement made the dozen or so shorter power blips during that time irrelevant). 6.1. Dynamic Programming In October, after some data mining of the program performance parameters (I always collect these for medium and large programs, if only to know or at least predict when they might finish), I finally hit upon a useful improvement of the backtracking program. I realized that my programs were finding all the same partial polygons, over and over again, and that if they could save them, it would greatly speed up the execution. Well, the tradeoff here was between the Scylla of more time than there is (heat death of the universe pales in comparison) and the Charybdis of more space than I have (I only have 8TB of disk space at home), and after several explorations that ran up against each extreme (the predictive models I made using the performance parameter measurements were part of this assessment; I didn't have to wait for it to happen 8-)), I finally found the obvious: I use dynamic programming to build p-maps (sequences of p edges that could be part of a polygon), p-halves (sequences of p edges that could be half of a polygon), and polygons. The dynamic programming approach leads to much faster systematic searches. In two months, I have confirmed all my previous results from the previous two years up to n=99 (and improved some that had margin 1), superseded all previous random program results, and extended the margin to at least 3 for all even n up to 100, all odd n up to 87. The dynamic programming approach also leads to a possible explanation of the half-size heuristic: if the area of half a polygon grows much faster than linearly, then the best combined area is nearly split evenly among the parts (don't take this argument too seriously; it needs some background definitions to be more precise, and it is still not a proof). 6.2. Current State My programs have computed results for all n up to 100, currently with margin at least 3 for all n, except 91, 93, 97, 99 (which have margin 2). The programs are currently running to extend the margin to at least 4 for all n up to 100 (with the same four exceptions), and to extend the results up to n=112 with b=14, which should give margin at least 2 for that range (the largest maximum edge length for n<=100 is 11, and I expect to see 12 a few times for odd n<=112; I hope not to see any 12's for even n or any 13's at all). These runs are either simply confirmatory (for n <= 100) or speculative (for n > 100), so I thought I'd share what I have. 7. Results This table contains my current results. The ``max edge bound used'' shows the largest edge bound used in a completed systematic search for the given n, so it can be used to compute the margin for that n. The ``running now'' heading is for cases that will run when program scripts that are already started get to them. end of file announce.txt

1 0

[math-fun] Boolean synthesis request from Knuth
by Schroeppel, Richard 29 Dec '05

29 Dec '05

Don Knuth has been studying Boolean Synthesis as part of writing Volume 7 of his opus. He would like solutions to the following puzzle. There are about 600K different boolean functions of 5 variables. (The inputs are 5 independent bits, and the output is 1 bit. Inputs may be permuted or negated, and the output negated, are all counted as the same function.) Under Knuth's metric (B2), all but ~100 of these functions can be computed by circuits with <= 10 gates. He's found circuits with 11 gates for most of the remaining functions, but there are 7 holdout functions. He's got 12-gate syntheses for the holdouts, but is hoping that there are 11-gate circuits. We don't know any good methods for proving the impossibility of 11-gate circuits. The best we know how to do is to run a program that generates all 11-gate ciruits, which is too much computing work right now. The allowed gates are two-input And and two-input Xor; also, Nots may be used freely, and don't count against the total. As usual, the circuits must be DAGs (no feedback or loops), and circuit depth doesn't matter. The seven functions are defined by 32-cell truth tables. The hex values are the 32-bit numbers 01bcda86 067ab314 067abc17 06b5d398 166eb583 1698ac5b 169ae443 Example: the truth table for 01bcda86 is -------x x-xxxx-- xx-xx-x- x----xx- This isn't a Karnaugh map with gray-coded coordinates; the coordinates are simply sequential binary numbers. So input variable A is true in the bottom two rows of the table, variable B is true in rows 2 and 4, variable C is true in the right half of the table, D is true in columns 3,4,7,8, and E is true in columns 2,4,6,8. My first cut at synthesizing 1698ac5b by hand has 16 gates; I'm out of practice. There's a December 5 version of Knuth's "Boolean Basics" at http://www-cs-faculty.stanford.edu/~knuth/fasc0b.ps.gz but I wasn't able to view the postscript. He's promised an updated version with the circuit search programs "soon", probably in a few days. Rich

1 0

[math-fun] The new OEIS search page!!!!!
by N. J. A. Sloane 29 Dec '05

29 Dec '05

There is a new lookup page under development - please try http://www.research.att.com/~njas/nsequences/index.html This will eventually (maybe quite soon) replace the existing lookup page http://www.research.att.com/~njas/sequences/index.html Click the Advanced Search button to get instructions: this points to the URL http://www.research.att.com/~njas/nsequences/index2.html Note that you can now search for multiple things like 1,2,3,4,5 "partial sums" author:njas keyword:nice It is also very fast. Please report any problems to njas. Several things still need to be fixed (the Demo pages and the Index files, in particular) Thanks to Russ Cox, who spent countless hours writing the new programs. Some of the ideas were contributed by Alex Healy, and David Applegate played a key role in getting them running on the local machine. Neil

2 1

[math-fun] Family of fractal sequences
by Kerry Mitchell 28 Dec '05

28 Dec '05

Just submitted to OEIS: Let A be the sequence A114729 (1, 1, 1, 2, 3, 2, 2, 1, 1, 1, 2, 3, 4, 4, 3, 3, 2, 2, 1, 1, ...), B be the sequence A114730 (1, 1, 2, 2, 1, 1, 1, 2, 3, 4, 3, 3, 2, 2, 1, 1, 1, 2, 3, 4, ...), and C be the sequence A114731 (1, 2, 1, 1, 1, 2, 3, 3, 2, 2, 1, 1, 1, 2, 3, 4, 5, 4, 4, 3, ...). Let D be the sequence A114732 (1, 2, 3, 1, 1, 2, 3, 4, 5, 6, 4, 2, 1, 2, 3, 4, 5, 6, 7, 8, ...), E be the sequence A114733 (1, 2, 1, 2, 3, 4, 5, 3, 1, 1, 2, 3, 4, 5, 6, 7, 8, 6, 4, 2, ...), and F be the sequence A114734 (1, 1, 2, 3, 4, 2, 1, 2, 3, 4, 5, 6, 7, 5, 3, 1, 1, 2, 3, 4, ...). Then: - A upper trims to B - B upper trims to C - C upper trims to A - A lower trims to C - B lower trims to A - C lower trims to B - D counts the number of times each element of A occurs - E counts the number of times each element of B occurs - F counts the number of times each element of C occurs - A counts the number of times each element of D occurs - B counts the number of times each element of E occurs - C counts the number of times each element of F occurs - D lower trims to E - E lower trims to F - F lower trims to D - D upper trims to F - E upper trims to D - F upper trims to E Kerry

1 0