March 2008 - mathfun@mailman.xmission.com

[math-fun] Smallest magic squares of powers
by Christian Boyer 01 Sep '08

01 Sep '08

Oct 7th, 2007: the smallest known magic square of 4th powers is now a 44x44 square constructed by Jaroslaw Wroblewski (Poland) and Hugo Pfoertner (Germany). Jaroslaw built the semi-magic square in June, then Hugo needed a very impressive computing job of 3 months, on 57 processors of a SGI computer http://www.sgi.com/products/remarketed/origin3000/, in order to find two magic diagonals in this square! A big progress, because the previous smallest known was a 243x243 square, coming from the 243x243 tetramagic square of Pan Fengchu (China). The best known results, and their first authors, are now: Magic square Smallest known ------------ --------------- Of squares 4x4 (Euler, 1770) Of cubes 9x9 (Boyer, 2006) Of 4th powers 44x44 (Wroblewski-Pfoertner, 2007) Of 5th powers 729x729 (from the pentamagic square of Li Wen, 2003) ON ANY POWER, WE DO NOT KNOW WHAT THE SMALLEST POSSIBLE MAGIC SQUARE IS! For example, as you know, we still do not know if a 3x3 magic square of squares is possible... 4x4, 5x5, 6x6, 7x7, and 8x8 magic squares of cubes are unknown... And the problem of the diagonals is extremely difficult, as proved by the impressive computing search of Hugo. It remains a big gap between the smallest known magic and semi-magic squares (=with or without magic diagonals) of 4th powers: 44x44 versus 4x4... Here is the 4x4 semi-magic square of 4th powers (Morgenstern-Boyer, 2006): 14101^4 938^4 931^4 37762^4 35866^4 20881^4 21038^4 13393^4 24806^4 30191^4 30418^4 9263^4 413^4 32026^4 31787^4 1106^4 Christian.

2 2

[math-fun] Morpion Solitaire
by Christian Boyer 06 Jun '08

06 Jun '08

An easy game: Only paper and pencil needed. A game for one player. And an open game: Who will improve the current world records??? Here is my new website dedicated to "Morpion Solitaire": www.morpionsolitaire.com Fully bilingual, English/French. Feel free to report any error, or any missing information. As you can read in the "Origin" page, any new information on the origin of this game will be welcomed. Some other questions. Is it possible to do best than the two grids given in "Other 5"? Or worst than my very bad grids at the end of the "Limits" page? Christian.

1 2

[math-fun] Space-filling curves
by Jason 08 Apr '08

08 Apr '08

I think I have a new integer sequence for the OEIS (although please tell me if it seems insufficiently interesting). But first, a question: Is there a standard way to encode the cardinal directions as integers? I picked mine since it's both the standard clockwise N,E,S,W and because in this particular case it encodes the first three directions as 1,2,3. Encode up=1, right=2, down=3, left=4. The sequence is the directions of travel of a Hilbert curve as it leaves the origin. I rather arbitrarily used this as the shape of the second iteration. Here again, maybe someone can tell me if there's a more conventional form. p m l k o n i j b c h g a d e f ^ Given these two conventions, the sequence would begin: 1,2,3,2,2,1,4,1,2,1,4,4,3,4,1,... [a->b c d e f g h i j k l m n o p] Can somebody point me at the right vocabulary for thinking about the mappings of 1234 to NESW? It's rather arbitrary, and if your compass is rotated from mine so that you think 2341=NESW, 3412=NESW and 4123=NESW, you'll still get a Hilbert curve, but if you use 1324=NESW, your lines won't connect when you use my sequence. So, there's a relationship inherent in those rotations such that 3=-1 and 2=-4, and that makes me think that group theory ought to be involved. What about sequences of symbols which are totally, er, unrelated? Unordered? That is, assume I have a sequence a,b,c,b,b,d,a that I consider equivalent to the set of all sequences f(a),f(b),f(c),f(b),f(b),f(d),f(a) in which f() is a bijection from {a,b,c,d}->{a,b,c,d}. (In other words, totally arbitrarily chosen symbols.) Would it make sense to want an Online Encyclopedia of such sequences in which the symbols don't have a relationship like the integers do? Or is there a way to canonicalize such sequences so that we can express them uniquely as integers? Perhaps we could force the convention that the symbols must be numbered in order, so that 1 is always the first number to appear in the sequence and that the next non-1 symbol must be 2, etc.? (Sorry if this is an excessivly elementary subject to be asking about)

3 2

Re: [math-fun] Fraction of indivisible numbers
by Fred lunnon 02 Apr '08

02 Apr '08

On 3/30/08, Steve Witham <sw(a)tiac.net> wrote: > oo > ------ > | | 1 > | | 1 - ----- > | | f(i) > i = 1 > > > f(i) = i + 1 > (1/2) (2/3) (3/4) (4/5)... = 0 > > f(i) = (i+1)^2 > (1/4) (8/9) (15/16) (24/25) ... = 0 > > Is the result always zero when f(i) is a positive polynomial of i? > The last equation should apparently read (3/4) (8/9) (15/16) (24/25) ... = 1/2 So no, the product is not always zero --- in fact, taking logarithms and approximating the log by its Taylor expansion log(1-x) = -x + ... , the product is actually nonzero for degree > 1 --- unless one of the factors vanishes "accidentally" because f(i) - 1 happens to have a positive integer root. > f(i) = i'th prime > (1/2) (2/3) (4/5) (6/7) (10/11) (12/13) ... = 0 > > (The fraction of counting numbers that aren't divisible by any prime.) > Does that equation have a name? > > f(i) = 2^i > (1/2) (3/4) (7/8) (15/16) ... ~= 0.288788095087 > This number turns up as the probability that a large random binary matrix is nonsingular. I don't know of a closed form for it --- does anybody else? > Is the result always > 0 when f(i) = k^i and k > 1? > Yes, by the same reasoning as before. > If so, does this put the primes between polynomials and exponentials? > No. A classic result of number theory says that the i-th prime equals i/log(i) (very roughly) --- this is the "Prime Number Theorem", see Hardy & Wright "Introduction to the Theory of Numbers" for a detailed account [and no doubt Wikipedia for a quick 'n' dirty summary]. Fred Lunnon

4 4

[math-fun] New (to me) proof of divergence of the harmonic series
by Joshua Zucker 01 Apr '08

01 Apr '08

Up until now, I only knew a couple of standard proofs that the harmonic series diverges: 1) 1 + 1/2 + (1/3 + 1/4) + (1/5 + ... + 1/8) + ... > 1/2 + 1/2 + 1/2 + 1/2 + ... 2) integral(1/x) = ln x I think that's about it ... But then I saw this very very cool proof idea in what was otherwise a mostly weak book of philosophy of mathematics ( http://www.amazon.com/How-Mathematicians-Think-Contradiction-Mathematics/dp… if you are interested ) and I think it could be said something like this: Suppose it converges. Then let H = 1 + 1/2 + 1/3 + 1/4 + 1/5 + ... so 1/2 H = 1/2 + 1/4 + 1/6 + 1/8 + ... and, subtracting, H - 1/2 H = 1 + 1/3 + 1/5 + ... Finally comparing term-for-term, it's clear that 1/2 H > 1/2 H, contradiction, QED. Does anyone have an early citation for this proof, or know who might have thought it up? Byers doesn't give any citation for the idea in his book. Are there any major holes in the proof that need to be filled, or is this basically a good outline? (Since we assume convergence to get the contradiction, I think the manipulations in the middle are OK, right?) Thanks, --Joshua Zucker

6 5

[math-fun] Fraction of indivisible numbers
by Steve Witham 30 Mar '08

30 Mar '08

oo ------ | | 1 | | 1 - ----- | | f(i) i = 1 f(i) = i + 1 (1/2) (2/3) (3/4) (4/5)... = 0 f(i) = (i+1)^2 (1/4) (8/9) (15/16) (24/25) ... = 0 Is the result always zero when f(i) is a positive polynomial of i? f(i) = i'th prime (1/2) (2/3) (4/5) (6/7) (10/11) (12/13) ... = 0 (The fraction of counting numbers that aren't divisible by any prime.) Does that equation have a name? f(i) = 2^i (1/2) (3/4) (7/8) (15/16) ... ~= 0.288788095087 Is the result always > 0 when f(i) = k^i and k > 1? If so, does this put the primes between polynomials and exponentials? --Steve

2 2

Re: [math-fun] distinct distances
by Dean Hickerson 29 Mar '08

29 Mar '08

Joshua Zucker wrote: > I got an interesting problem lately and neither I nor the proposer > know the solution. Perhaps it is an open question? ... > Examples (all in 2-D): ... > For n points, the regular n-gon gives floor(n/2) different distances, > and I conjecture that is the fewest possible distinct distances (based > on not much evidence!), but in general that arrangement is not unique For large n you can get fewer distances by using n points from the integer lattice. E.g. if n=m^2, use an m by m array of points. The number of distinct distances equals the number of distinct numbers of the form x^2+y^2 with 0 <= x < m, 0 <= y < m, and x and y not both 0. (Subtract 1 from the terms of A047800 in the OEIS.) This is less than the number of sums of 2 squares up to 2m^2, which grows like C m^2/sqrt(log(m)); see: http://mathworld.wolfram.com/Landau-RamanujanConstant.html The smallest square number n for which this construction gives fewer distances than a regular n-gon is n=144; a 12x12 grid has only 70 distinct distances. But there are probably smaller values of n for which the n-gon is not optimal; maybe taking a circular chunk of the integer lattice would work better. Or maybe a lattice made of equilateral triangles is better than the square lattice. No doubt this is well-known to someone. P.S.: According to p. 42 of "Lectures on Discrete Geometry" by Jiri Matousek, the best known upper bound on the number of distinct distances is C n/sqrt(log(n)) (as shown above) and the best known lower bound is C n^0.863. See: http://books.google.com/books?id=0N5RVe5lKQUC&printsec=frontcover Apparently Erdos offered $500 for a proof or disproof that the upper bound is best possible. See "Uniformity of distance in the plane (I)" in: http://www.math.niu.edu/~rusin/known-math/93_back/prizes.erd Dean Hickerson dean(a)math.ucdavis.edu

2 1

[math-fun] distinct distances
by Joshua Zucker 29 Mar '08

29 Mar '08

Hi math-funsters, I got an interesting problem lately and neither I nor the proposer know the solution. Perhaps it is an open question? Given n points in d dimensions with k different pairwise distances, how can you tell if there are 0, a finite number, or an infinite number of possible arrangements of the points up to similarity? And if the answer is a finite number, how many arrangements are there? Any special cases that you can help me out with would be nice too. I'm particularly interested in knowing the minimum value of k for each n. Examples (all in 2-D): For 3 points, with 1 different distance you have only 1 arrangement, the equilateral triangle. With 2 different distances you get the infinite family of isosceles triangles. For 4 points, you must have at least 2 different distances, and I think there are exactly 6 distinct arrangements but I don't have a proof. For 5 points, the regular pentagon works to give exactly 2 distinct distances, and I'm pretty sure that's unique. For n points, the regular n-gon gives floor(n/2) different distances, and I conjecture that is the fewest possible distinct distances (based on not much evidence!), but in general that arrangement is not unique (e.g. for n = 7 the regular heptagon works but so does the regular hexagon plus the point in the middle, and maybe there are lots more possible arrangements. How many?). (And if my floor(n/2) conjecture is correct, we should add something about this to the relevant entry in OEIS, and if it's not correct, sounds like a great sequence to me!) This problem was suggested to me as the basis of a problem set for http://jrmathfestival.org ... and I think it'll make a great one. The festival (of which I am the director) has funding for people who write problem sets, and also for those of you in the SF Bay area who would like to spend a day at Google or Pixar, you can sit down with some kids (grades 6-12) and work on a problem set with them (and we can also pay you some token amount to thank you for volunteering, but not nearly enough to make it worth the time if you don't already like helping kids work on interesting problems). If you are interested, let me know and I'll send you some sample problem sets. Thanks, --Joshua Zucker

2 1

[math-fun] NPR: The End of the Math Wars?
by Henry Baker 28 Mar '08

28 Mar '08

FYI -- NPR's "On Point" discussed math education yesterday. You can listen or download the 45 minute podcast: http://www.onpointradio.org/shows/2008/03/20080327_a_main.asp http://www.wbur.org/listen/podcasts/onpoint.xml The End of the Math Wars? Aired: Thursday, March 27, 2008 10-11AM ET By guest host Jane Clayson Here's a headline you may have missed: a truce has been declared in the great American "Math War." For 20-odd years, mathematicians, parents, and teachers have been arguing over the best way to teach your children math. Well, a national panel formed by President Bush two years ago has just issued its findings, and is pushing schools to go back to the basics -- memorization, multiplication tables, and less so-called "fuzzy math." This hour, On Point: we ask experts if it all adds up -- and with their help, we do your kids' math homework. Â·John Hechinger, education reporter for The Wall Street Journal Â· Mary Eich, a former math teacher, she is the K-8 math coordinator for the Newton, Massachusetts, public schools Â· Wilfried Schmid, professor of mathematics at Harvard University and a member of the National Mathematics Advisory Panel, which recently released its report Â· Joseph Rosenstein, professor of mathematics at Rutgers University and director of the New Jersey Mathematics and Science Education Coalition

1 0

[math-fun] Dan A. is being modest
by Lee Sallows 24 Mar '08

24 Mar '08

Phosphor. Lee Sallows At 10:09 PM 3/23/2008 -0700, you wrote: >Okay, here's another one in the same vein: > >Find an 8-letter (Scrabble-eligible) word >whose first hslf is the same as its second half, >except that the 4th letter immediately follows, >alphabetically, the 8th letter. > >Additional hint: it's something that glows. > >No fair using software to solve it! > >--Dan

1 0