December 2003 - mathfun@mailman.xmission.com

Re: [math-fun] convex lattice 11-gon of minimum area
by Dan Hoey 16 Dec '03

16 Dec '03

Chris Landauer wrote: [...] > Now the program just uses a simple radius bounded backtracking > search for the points in the polygon, with some special processing > near the end. Once the area of the polygon determined by the current set of points exceeds your bound, you can cut off the search. Perhaps it's obvious that you already do this, since you can run the search at all. How about this: Start by picking the vertex V most distant from the origin. All convex polygons with area A and including {O, V} must lie between the two lines parallel to OV at a distance of 2A/|V|. That will probably be only about 4A points. I'm trying to figure out what to do with SL(2,Z). Suppose all points of the polygon lie within a rectangle M1 <= x <= M2 and 0 <= y <= N <= M2-M1. Under what circumstances will the map (x,y) -> x-y,y) or (x,y) -> (x+y,y) reduce the value of M2-M1? If M2-M1 goes below N, we can transpose and try again. Can this be made to map to a polygon with a small radius bound? What gets me is that Jamie Simpson apparently proved that the minimum must be at least 39/2. Is this something that can be pushed with computation? Dan

1 0

Re: [math-fun] convex lattice 11-gon of minimum area?
by Chris Landauer 15 Dec '03

15 Dec '03

hihi, all - i have found hundreds of 11-gons with area 21.5, with a computer program that looks at ones with longest edge at most 10 (in a few seconds), and thousands more, but none of smaller area, when the allowed edge lengths go up as high as 50 (in a lotta seconds: 13843.496u 18.417s), on commodity pcs with freebsd and linux (varying from 1.8GHz to 2.4GHz intel Pentium style machines) i've also looked at some larger polygons, to get some upper bounds on the minimum area, including (n = number of edges of polygon) (rad = maximum edge length, manhattan distance) (min = minimum area found) (number = number found with that same minimum area) (times = how long it took user cpu seconds, system cpu seconds, elapsed time, cpu % (2.2GHz celeron, 512MB main memory, running FreeBSD 5.1) (10ms clock tick, so that small times are unreliable) (. = same value as previous row) n rad min number times 10 20 14 203 57.200u 1.069s 1:03.54 91.6% . . . . 57.230u 0.835s 1:02.48 92.9% . . . . 55.306u 0.070s 1:00.19 91.9% . 30 . 430 261.873u 0.312s 4:41.90 93.0% . . . . 262.131u 0.328s 4:41.75 93.1% . 40 . 728 788.353u 1.101s 14:12.05 92.6% . . . . 788.329u 1.085s 14:08.73 93.0% . 50 . 1129 1920.953u 2.920s 34:41.34 92.4% 11 10 21.5 233 22.820u 0.000s 0:23.39 97.5% . 20 . 872 395.410u 0.010s 6:45.57 97.4% . . . . 394.030u 0.020s 6:45.59 97.1% . 30 . 1809 1823.860u 0.010s 31:12.17 97.4% . 40 . 3034 5403.410u 0.060s 1:32:29.02 97.3% . 50 . 4689 12985.860u 0.040s 3:42:13.26 97.3% 12 10 24 15 39.460u 0.010s 0:40.57 97.2% . 20 . 53 698.810u 0.000s 11:56.81 97.4% . . . . 695.760u 0.030s 11:54.40 97.3% . 30 . 112 3210.980u 0.030s 54:56.88 97.3% . 40 . 188 9484.200u 0.400s 2:42:30.10 97.2% 13 10 32.5 55 205.140u 0.010s 3:30.58 97.4% . 20 . 207 3964.860u 0.340s 1:07:50.53 97.4% . . . . 3946.270u 0.000s 1:07:31.88 97.3% . 30 . 423 18152.870u 1.390s 5:11:07.84 97.2% 14 10 40 68 709.800u 0.050s 12:09.59 97.2% . 20 . 248 14871.960u 0.080s 4:14:06.26 97.5% . . . . 14788.790u 1.100s 4:13:29.98 97.2% 15 10 51.5 121 3606.580u 0.000s 1:01:43.25 97.3% . 20 . 482 85559.430u 0.710s 24:22:23.00 97.5% 16 10 59 16 9207.270u 0.390s 2:37:48.86 97.2% 17 10 75.5 72 55945.880u 1.020s 15:56:06.60 97.5% 18 10 87 51 169100.770u 3.070s 48:08:23.04 97.5% 19 10 ?? ?? a long, long, time 8-) it will perhaps finish thursday, if i don't use the machine for anything else anyway, i obviously need a new program - i'm looking at something that will more quickly enumerate lattice points in wedges (the program is a simple backtracker that enumerates the points in the wedge between the line of the previous edge and the line towards the original point, centered at the current point - my program does this now by enumerating the entire lattice spiral and checking bounds, which isn't so bad as it might seem, since early on in the search, the wedges are fairly wide, and the spiral search is easy and fast enough - i want to switch over to a more direct enumeration at the end when the wedges are not very wide and other constraints can be applied) i imagine that it should be encouraging for the lower bound minded among you that the best value found for the minimum area is found already when the radius bound is 10 (and only n=17, among those with n<= 18, even needed to use a radius bound as much as 5 - that is, for each n<=18 except n=17, there was a polygon, with the minimal area that the program found for any bound i tried, with maximum edge length <= 4, but for n=17, they all had maximum edge lengths at least 5) it would be significantly helpful if there were a theorem upper bounding the smallest maximum edge length for a minimum area (convex lattice) n-gon (one for which the bound was a function of n that is not too large) - then this radius bounded search could be used to determine the precise minimum area more later, cal Chris Landauer Aerospace Integration Science Center The Aerospace Corporation cal(a)aero.org

7 6

[math-fun] convex lattice 11-gon of minimum area?
by Steven Finch 14 Dec '03

14 Dec '03

Hello! >From Neil Sloane's sequences A063984 and A070911, I infer that the convex lattice 11-gon of minimum area is not yet known. This is remarkable, since the answer is known for 12-gons, 13-gons and 14-gons! Does anyone know about any recent progress toward a solution? Jamie Simpson proved in 1990 that the minimum area must be 19.5, 20, 20.5, 21 or 21.5. By a convex lattice n-gon, I mean a polygon whose n vertices are points on the integer lattice Z^2 and whose interior angles are strictly less than pi. Thank you, Steve Finch http://pauillac.inria.fr/algo/bsolve/ _________________________________________________________________ Tired of slow downloads and busy signals? Get a high-speed Internet connection! Comparison-shop your local high-speed providers here. https://broadband.msn.com

2 1

[math-fun] A test for primality using elliptic curves
by victor＠idaccr.org 11 Dec '03

11 Dec '03

Math funsters might be interested in "An Elliptic Curve test for Mersenne Primes" by Benedict Gross. http://abel.math.harvard.edu/~gross/preprints/Mersenne.pdf In a talk this afternoon Dick (his nickname) mentioned that he is going to use it to check the primality of the newest Mersenne prime. Victor

1 0

[math-fun] Early wishes
by Marc LeBrun 11 Dec '03

11 Dec '03

Happy [ 1 2 3 4 ] [ ] [ 2 2 3 4 ] Permanent [ ] [ 3 3 3 4 ] [ ] [ 4 4 4 4 ] everyone! Also (capriciously and perhaps unreliably extracted from the OEIS): Distinct distances to integer lattice points in a ball of radius 49 (A047809) 5-tuples of distinct integers from {1,2,...,23} with no common pair-wise factors (A015698) n(7n-1)/2, for n=24 (A022264) Terms in fourteenth derivative of f(f(f(x))) (A022811) Partitions of 35 whose least part is even 3n^2 - 7n + 6, for n=27 (A027599) Partitions of 26 into parts not of the kind 21k, 21k+9 or 21k-9 (A035987) Partitions of 43 into parts not congruent to 2 or 3 mod 5 (A036820) Integer lattice points enclosed by right half-plane and circle with radius (0,0)-to-(25,25) (A049728) Partitionings of factorials into 58 factorials (A061889) Power of 2 (the 20th such) whose reversed decimal digits give a prime (A057708) Multiple of 3 (the 43rd such) whose decimal digits are all even (A061811) "Eban" integer (the 22nd such)--ie whose English name does not contain the letter "E" (A006933) ...

1 0

[math-fun] Smarandache numbers
by Jon Perry 11 Dec '03

11 Dec '03

New paper at; http://www.users.globalnet.co.uk/~perry/maths/smarandache/smarandache.htm Jon Perry perry(a)globalnet.co.uk http://www.users.globalnet.co.uk/~perry/maths/ http://www.users.globalnet.co.uk/~perry/DIVMenu/ BrainBench MVP for HTML and JavaScript http://www.brainbench.com

1 0

RE: [math-fun] 7.11 puzzle
by Fred W. Helenius 09 Dec '03

09 Dec '03

At 12:51 PM 12/5/03, Rich wrote: >Probably still legal tender for small debts, but I doubt 7-11 >would take them. But it raises an interesting generalization: >Prices are frequently "2 for 1.29". Suppose we ignore the >custom of rounding up (.645 -> .65), and allow (positive) >rationals in the solution. It's not clear to me that the >set of solutions is still finite, and my enumeration methods >would only work if the denominators are bounded. >-----Original Message----- >From: R. William Gosper >To: math-fun(a)mailman.xmission.com >Sent: 12/4/2003 11:19 PM >Subject: Re: [math-fun] 7.11 puzzle > >Are half-cents still legal tender?-) >1.125, 1.28, 3.125, 1.58 There are indeed plenty of rational solutions. Taking all values in cents, we're solving a + b + c + d = 711, abcd = 711000000. Using a known solution, namely the intended (316,150,125,120), as a starting point, fix a = 316 and treat b as a parameter. Then c and d are given by c + d = 395 - b, cd = 2250000/b, and so they are the roots of a quadratic with discriminant D = sqrt((395 - b)^2 - 9000000/b). So a rational solution corresponds to a rational point on the cubic curve b^3 - 790*b^2 + 156025*b - 9000000 = b*D^2. We already know rational points with b = 120,125,150, so we can find more by the chord-and-tangent method. The drawback is that the denominators get large fast. The first two all-positive solutions I find are (316, 1922/13, 4056/31, 46875/403) and (316, 956092840/8367257, 2961126750/20587579, 1329939075/9714443). P.S. There's also a very nice non-positive solution in whole cents: (316,900,-500,-5). -- Fred W. Helenius <fredh(a)ix.netcom.com>

2 1

[math-fun] A crypt() hashing collision
by Thane Plambeck 09 Dec '03

09 Dec '03

>From the paper "Terracrack: Password cracking using TeraFlop and PetaByte Resources" by Tom Perrine and Devin Kowatch, at the San Diego Supercomputing Center. They built up billions of plaintext passwords and looked for crypt() collisions (among other things)... http://security.sdsc.edu/publications/teracrack.pdf > ...we found one "real" collision. By this we mean two words, > that differ in more than just the lower 7 bits of each byte, > which hash to the same value [under crypt()]. This occurs with the words > "$C4U1N3R" and "SEEKETH.", under the salt > "1/". Both words hash to: "ChERhgHoo1o". Thane Plambeck 650 321 4884 office 650 323 4928 fax http://www.plambeck.org

1 0

[math-fun] Balls in Bags
by Jon Perry 08 Dec '03

08 Dec '03

Let there be n balls in a bag. Let k_i be a partition of n such that there are k_1 red balls, k_2 blue balls, etc..., and k_a yellow balls. Give each ball an unique number from 1 to n. What is the probability that a red ball has a number <=j. e.g. consider a bag with 20 balls numbered 1..20, and randomly coloured red (7) and green (13). What is the probability that a red ball is numbered either 1 or 2? Jon Perry perry(a)globalnet.co.uk http://www.users.globalnet.co.uk/~perry/maths/ http://www.users.globalnet.co.uk/~perry/DIVMenu/ BrainBench MVP for HTML and JavaScript http://www.brainbench.com

2 2

[math-fun] Hot & Cold
by Henry Baker 06 Dec '03

06 Dec '03

Does it bother anyone else that hot water is indicated by "red" and cold water is indicated by "blue" ? I can forsee a time when an emissary from an advanced civilization comes to the UN and stays in a better hotel, and scalds himself to death in the shower -- thus causing an intergalactic war.

9 8