May 2005 - mathfun@mailman.xmission.com

[math-fun] more challenge sequences needed
by N. J. A. Sloane 25 May '05

25 May '05

To Seqfans, Mathfun: the people who are planning the contest (I should probably not have described them as French, although my contact has a French email address - they could be anywhere in the world) replied that none of the sequences that I gave them were suitable. Either they failed to meet some of the requirements for a good challenge, or else they were too close to problems that had been used in previous challenges. So they are still looking for a good sequence to extend. Something like the Hadamard determinant problem or the Golomb ruler problem would be perfect, but these have already been used. Here are the constraints on the problem: 1) It must be NP-complete 2) It must be simple to describe 3) It should not have been widely explored 4) A solution must be easy to check (= it doesn't require a lot of computation to check) 5) It has to be computed from N=8 to at most 64 Further suggestions would be welcomed! Neil

4 3

RE: [math-fun] more challenge sequences needed
by dasimov＠earthlink.net 25 May '05

25 May '05

I'm not sure how to tell what's NP-complete. But what about determining the sequence emerging from a recent math-fun discussion: B(n) = [# of subsets of the n nth roots of unity that sum to 0], up to isometry. (A naive brute-force check would involve > 2^n / #(D_n) = 2^(n-1) / n sums for each n.) --Dan

1 0

RE: [math-fun] Re: Challenge sequences
by dasimov＠earthlink.net 25 May '05

25 May '05

Don Reble writes: << > And it scarcely seems credible that the next number would be 67, Generating a bunch of random boolean 8x8's, I've gotten every determinant from 0 to 32, and 34, 35, 36, 42. 73 different values, when you count the negative ones. Sorry to Dan and Mr. Heegner. >> Hey, that would be great -- another prime. --Dan

1 0

RE: [math-fun] Challenge sequences
by dasimov＠earthlink.net 25 May '05

25 May '05

AMong Neil's Challenge Sesquences, I find this one in particular fascinating: << Suggestion #6: Similar problems dealing with the spectrum of determinants: http://www.research.att.com/projects/OEIS?Anum=A089472 Sequence: 2,3,5,7,11,19,43 Name: Number of different values taken by the determinant of a real (0,1)-matrix of order n. >> To state the obvious, these are all prime. Q1: Is there any reason to think they might all be prime? ------------------------------------------------------------------------- If we allow a 0x0 matrix, then (as the empty sum) the only determinant is 0. In which case the known sequence becomes 1,2,3,5,7,11,19,43 Q2: Can it be just a coincidence that 1,2,3,7,11,19,43, (all but the fourth term, 5, of A089472) are the first 10 of the 12 "Heegner numbers" (A003173): 1,2,3,7,11,19,43,67,163 ? (As many know, 1,2,3,7,11,19,43,67,163 are the integers d > 0 for which the field Q(sqrt(-d))'s ring of algebraic integers enjoys unique factorization.) --Dan

3 2

[math-fun] Challenge sequences
by N. J. A. Sloane 24 May '05

24 May '05

To math-fun, I was asked by a group of programmers in France to suggest a sequence that they could attack as a team effort. They imposed several conditions that I found hard to satisfy, so I asked the sequence-fan mailing list for help. This resulted in the following list of "challenge sequences", which I sent to France, and post here just for fun. Presumably these people will select one of them to work on. NJAS ------------------------------------------------------- Suggestion #1: From: "Rainer Rosenthal" <r.rosenthal(a)web.de> In the German newsgroup de.sci.mathematik we discussed "Perfect Rulers" and there were some enhancements for http://www.research.att.com/projects/OEIS?Anum=A004137 some weeks ago. Let them compute A004137(n) from scratch. They will enjoy (I hope). And the OEIS will be glad :-) ----------------------------------------------------------- Suggestion #2: From: Don Reble <djr(a)nk.ca> I suggest A006945, although it does not satisfy all of the conditions that were listed. ----------------------------------------------------------- From: "Pfoertner, Hugo" <Hugo.Pfoertner(a)muc.mtu.de> Suggestion #3: Confirm Daren Casella's results for The Snake or Coil in the Box Problem: http://www.research.att.com/projects/OEIS?Anum=A000937 2,4,6,8,14,26,48 Name: Length of longest simple cycle without chords in the n-dimensional hypercube graph. Also called n-coil or closed n-snake-in-the-box problem. After 48, lower bounds on the next terms are 96,180,344,630,1236. - Darren Casella (artdeco42(AT)yahoo.com) Mar 04 2005 http://www.research.att.com/projects/OEIS?Anum=A099155 Sequence: 1,2,4,7,13,26,50 Name: Maximum length of a simple path with no chords in the n-dimensional hypercube, also known as snake-in-the-box problem. After 50, lower bounds on the next terms are 97,186,358,680,1260. - Darren Casella (artdeco42(AT)yahoo.com) Mar 04 2005 ----------- Suggestion #4: Find an extension of http://www.research.att.com/projects/OEIS?Anum=A087725 Sequence: 0,6,31,80 Name: Maximum number of moves required for the n X n generalization of Sam Loyd's Fifteen Puzzle. As a "warm-up" for this the research group could complete http://www.research.att.com/projects/OEIS?Anum=A089484 Sequence: 1,2,4,10,24,54,107,212,446,946,1948,3938,7808,15544,30821, 60842,119000,231844,447342,859744 Name: Number of configurations of Sam Loyd's sliding block 15-puzzle that require a minimum of n moves to be reached, starting with the empty square in one of the corners. and the related http://www.research.att.com/projects/OEIS?Anum=A090164 and http://www.research.att.com/projects/OEIS?Anum=A090165 ----------- Suggestion #5: http://www.research.att.com/projects/OEIS?Anum=A085000 Sequence: 1,10,412,40800,6839492,1865999570 Name: Maximal determinant of an n X n matrix using the integers 1 to n^2. I have spent more than 2 years of CPU time to get a current lower bound for a(7)>=762140212575 and much less time for a(8)>=440857916120379 ------------ Suggestion #6: Similar problems dealing with the spectrum of determinants: http://www.research.att.com/projects/OEIS?Anum=A089472 Sequence: 2,3,5,7,11,19,43 Name: Number of different values taken by the determinant of a real (0,1)-matrix of order n. and some of the sequences cross-linked in A089472. -------------------------------------------------------- Suggestion #7: From: Ralf Stephan <ralf(a)ark.in-berlin.de> Permanents of matrices would be a good choice. For example, A087983. (There are many related sequences that need extending and have not been studied hardly at all. Search for the word permanent in the OEIS) -------------------------------------------------------- Suggestion #8: From: Ed Pegg Jr <edp(a)wolfram.com> ID Number: A081287 URL: http://www.research.att.com/projects/OEIS?Anum=A081287 Sequence: 0,1,1,5,5,8,14,6,15,20,7,17,17,20,25,16,9,30,21,20,33 Name: Excess area when consecutive squares of size 1 to n are packed into the smallest possible rectangle. References R. M. Kurchan (editor), Puzzle Fun, Number 18 (December 1997), pp. 9-10. Links: Ed Pegg Jr, Packing squares http://www.maa.org/editorial/mathgames/mathgames_12_01_03.html See also: Cf. A038666. Does it ever go back down to zero? I'll pay $100 for a solution to that. The best known solution for 1-24 is http://www.mathpuzzle.com/24sqB.gif ------------------------------------------------------------------

1 0

[math-fun] Holyhedron
by David Wilson 23 May '05

23 May '05

In Mathworld's Holyhedron article, Vinson's holyhedron is stated to have around 54,000,000 faces. I believe this would have been an early estimate. The exact number is apparently 78,585,627 faces according to http://www.maa.org/mathland/mathtrek_6_19_00.html, which was apparently taken from Vinson's preprint, according to the references. I also found a claim of a 492-face holyhedron at http://www.plunk.org/~hatch/Holyhedron/. This should be much more easily verifiable than Vinson's monster. - David W. Wilson "Truth is just truth -- You can't have opinions about the truth." - Peter Schickele, from P.D.Q. Bach's oratorio "The Seasonings"

1 0

[math-fun] Re: Packing squares into a 1 x Zeta[2] rectangle
by James Propp 21 May '05

21 May '05

>Conjecture: Given an open set O that for each n >=1 can >contain disjoint open squares of sides 1, 1/2, 1/3,...,1/n , >then O can contain disjoint squares of all sides 1/n, n >= 1 >simultaneously. If O is bounded, then the closure of O can contain disjoint squares of all sides 1/n, n >= 1. Proof: For all n, form the infinite sequence of points (p(n,1),p(n,2), p(n,3),...), where for k <= n, p(n,k) is the center of the square of side 1/k in the nth partial packing. (It won't matter how we define p(n,k) for k>n.) By compactness, we can find a subsequence of partial packings such that all coordinates converge. This gives the desired packing of all the squares in the closure of O. Jim Propp

4 3

[math-fun] Re RH
by N. J. A. Sloane 20 May '05

20 May '05

there's no truth to the rumor that Andrew Odlyzko has settled the RH. NJAS

2 1

Re: [math-fun] pi^2/6 packing problem
by Richard Schroeppel 20 May '05

20 May '05

Dan asked ... > Hmm, what about other rectangles also with area pi^2/6 ? > For example the pi/sqrt(6) x pi/sqrt(6) square. and I replied ... No, you need one edge of the rectangle to be at least 1.5, if the squares are placed othogonally. It looks even worse if they're rotated 45 degrees. But pi/2 x pi/3 looks like a possibility. This was too optimistic: With orthogonal placement, any packable rectangle must have a larger dimension >= 1 + 1/3 +1/4 = 1.58333... or smaller dimension >= 1/2 + 1/3 + 1/4 = 1.08333... But pi/2 x pi/3 is 1.5707... x 1.047..., which fails both criteria. It doesn't look like rotating any of the squares helps, but I haven't done the arithmetic to check this. Perhaps things go the other way: Maybe only the 1 x pi^2/6 rectangle works. Rich

3 2

RE: [math-fun] planar partitions
by Schroeppel, Richard 19 May '05

19 May '05

I came across an interesting paper by Christian Krattenthaler, called Advanced Determinant Calculus: A Complement, at http://arxiv.org/abs/math.CO/0503507 He evaluates a bunch of determinants, but in passing he generalizes one of Gosper's pi formulas, and gets into planar partitions and cutting up hexagons. He mentions en passant that there's an algorithm for computing the Nth *decimal* digit of pi without computing the first N-1 digits, by Fabrice Bellard, using Gosper's formula. Rich -----Original Message----- From: math-fun-bounces+rschroe=sandia.gov(a)mailman.xmission.com on behalf of Richard Schroeppel Sent: Wed 5/18/2005 1:04 AM To: math-fun(a)mailman.xmission.com Subject: Re: [math-fun] hexagons, sequences, omino This is from Dylan Thurston. --Rich ----- Date: Wed, 18 May 2005 01:18:25 -0400 Reply-To: dpt(a)math.harvard.edu From: dpt(a)lotus.bostoncoop.net (Dylan Thurston) Subject: Re: [math-fun] hexagons, sequences, omino On Tue, May 17, 2005 at 08:50:52AM -0600, Schroeppel, Richard wrote: > Scott asks ... > > Is there a nice general formula or a good approximation for the number > > of nondecreasing sequences in N^k, for integers N and k ? > > For an exact formula: > The 1D case is already answered, a quotient of factorials. > Based on experiments done long long ago, at an Institute far far away, > the 2D case seems to be a product of something like the 1D answers. > Strict vs. non-strict vs. semi-strict perturbs the formulas slightly. The 2D case is actually a well-known problem, called "plane partitions"; it's equivalent to counting lozenge tilings of a hexagon. (A 'lozenge' is a 60-120-60-120 rhombus obtained by gluing two triangles.) You have an rectangular array of numbers, non-decreasing in the rows and columns. Above each square, make a stack of cubes with height given by the number in that square. Add in two walls and the floor of the room. Tilt the whole construction and balance it on one corner; looking at it from the corner, you get a lozenge tiling of a hexagon. (Recall that if you look at a cube from a corner you see a hexagon.) There are many different symmetry classes of such tilings. Many have nice counts. > This also worked for rectangles, MxN. But I couldn't find a similar > answer for the 3D case. I always figured there was a tie-in with linear > and planar partitions having a nice generating function, while cubic > partitions don't seem to have one. Other people have noticed this too; I haven't heard a convincing explanation why this should be true. Peace, Dylan _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0