November 2005 - mathfun@mailman.xmission.com

[math-fun] sudoku; wrinkles
by Schroeppel, Richard 14 Nov '05

14 Nov '05

A Sudoku question for the experts: Suppose I generate a random Sudoku puzzle: Select a completed sudoku at random from the gazillion or so distinct sudokus. Then delete entries at random, stopping when nothing further can be removed without making the problem ambiguous. [This is a poor man's substitute for selecting a truly random minimal puzzle, which I suspect is much harder to do.] How hard, on average, is the resulting Sudoku? Are there very difficult Sudokus? Everything I've seen can be solved with at worst "single guessing", where a branch is tried and one of the possibilities leads to a quick contradiction without sub-guessing, or both branches lead to a same-forced- value. I.e., if the correct "cell to branch on" is selected, one of the branches dies and no recursion is necessary. ---- A challenge for numerical topology: Most materials -- cloth, paper, tape, plastic sheet, wood, metal, can stretch or shrink a bit in order to fit together. Even glass is slightly flexible. People who work with these materials for a living -- tailors, carpenters, ... -- have an intuitive feeling for how much their medium can stretch, bend, or twist, and what manipulations are required to make the pieces fit. Here's the challenge: Come up with a theory of making things fit -- a theory of wrinkles, shims, pleats, and all the other myriad tricks, fiddles, and adjustments that the subject experts know. Rich

2 1

RE: [math-fun] ??? maple, mathematica, matlab ???
by Pacher Christoph 14 Nov '05

14 Nov '05

Hi, I can only compare Mathematica and Matlab/Octave. In short: for pure mathematics only Mathematica. for applied mathematics it depends. ;-) Syntax: Matlab is a programming language like C or Fortran with extensions to matrix computations. You can quite easily write big simulation programs. Mathematica is more list-oriented, I would call it. The syntax of Mathematica is more complicated. If you are interested in symbolics: only Mathematica is worth considering (it offers an incredible amount of built-in functions from nearly all fields of mathematics. you will need some time to get into using it. if you do complicated things, it is worth it). Regarding numerics: For a long time it was said that Mathematica is not as efficient in doing numerics as Matlab, sometimes with a factor of 100 or so less. I think this changed a lot in the last versions when Mma integrated LAPACK routines. The debug possibilities of Mathematica are not good in my oppinion. If you just want to test the syntax of Matlab, you can go for the open source GNU clone Octave http://www.octave.org. The plotting capabilities of Octave are not sufficient in my oppinion (only command line interface, no zooming...). Here you would need Matlab. If we have more info what you would actually like to do with the program we could give you more help. bye Christoph

3 2

[math-fun] dilog(1/2), log(2)
by Thomas Baruchel 14 Nov '05

14 Nov '05

Hi, this is my first message on math-fun. The following thing is very easy to prove, but quite nice to look at: when computing the product (which in fact is a continued fraction), [0 4] [x^4/n^2 2^n*(1-(n*x)-(n*x)^2+(n*x)^5] [1 0] . prod(n=1,k, [1 0 ] ) then the quotient of the two terms in the left column (after an even number of multiplications) or in the right column (after an odd number of multiplications) converges to: dilog(1/2) x^4 + log(2) x^5 + O(x^6) Here is the Pari/GP code: m=matrix(2,2,i,j,(i!=j)*j^2+O(x^6)); for(n=1,100, m0=matrix(2,2); m0[2,1]=1; m0[1,1]=x^4/n^2; m0[1,2]=2^n*(1-(n*x)-(n*x)^2+(n*x)^5); m=m*m0); m[1,1]/m[2,1] Regards, -- Thomas Baruchel Home Page: http://baruchel.free.fr/~thomas/

1 0

RE: [math-fun] sudoku
by dasimov＠earthlink.net 13 Nov '05

13 Nov '05

Rich wrote (decontextualized) << How hard, on average, is the resulting Sudoku? Here's another question, perhaps easier to answer: What is the smallest number of filled squares that can uniquely determine an extension filling all 81 squares? --Dan (Or was this already answered here and I missed it?)

2 1

Re: [math-fun] sudoku; wrinkles
by Sterten＠aol.com 12 Nov '05

12 Nov '05

Rich wrote: >A Sudoku question for the experts: > >Suppose I generate a random Sudoku puzzle: Select a completed >sudoku at random from the gazillion or so distinct sudokus. >Then delete entries at random, stopping when nothing further >can be removed without making the problem ambiguous. [This is >a poor man's substitute for selecting a truly random minimal >puzzle, which I suspect is much harder to do.] this algo should generate a truly random minimal sudoku: (1) start with an empty grid (2) add a clue with random value 1..9 into one of the 81 cells chosen at random (3) if the resulting puzzle has no solution then goto (1) (4) if the resulting puzzle has more than one solution goto (2) (5) if the puzzle is not minimal then goto (1) (6) print the sudoku it's not so fast as your method. >How hard, on average, is the resulting Sudoku? 84 is the average number of placements = backtracking steps which my solver needs to process such a puzzle. Average number of clues is 24.4. 42% can be solved by the basic techniques "naked single,hidden single" , In that case 81-c placements are made, where c is the number of initially given clues. >Are there very difficult Sudokus? Everything I've seen can be >solved with at worst "single guessing", where a branch is tried >and one of the possibilities leads to a quick contradiction >without sub-guessing, or both branches lead to a same-forced- >value. I.e., if the correct "cell to branch on" is selected, >one of the branches dies and no recursion is necessary. Some rare sudokus require sub-guessing, but level-2-guessing is probably always sufficient. Probably all sudokus can be solved with 2 "magic cells", that is there exist 2 further clues which when added allow a solution with the basic techniques. Here are lists of hard sudokus: http://magictour.free.fr/top95 http://magictour.free.fr/top1234 http://magictour.free.fr/top44 the last one is for 16*16 sudokus. You can rate them by the number of solver-placements with http://magictour.free.fr/suexrate.exe -Guenter.

1 0

[math-fun] RSA640 factored
by Schroeppel, Richard 10 Nov '05

10 Nov '05

The 640-bit number RSA640 was factored last week. This is somewhat anticlimactic, since the 200 digit number RSA200 was factored in May. For some reason, this group doesn't post announcements on the NMBRTHRY list. The total work looks like roughly 30 years of 2.2GHz Opterons. This would nominally be 66 Gips-years, but I don't know either the parallelism of the Opteron, or the average number of clocks per instruction. Rich ---------- http://mathworld.wolfram.com/news/2005-11-08/rsa-640/ includes a bit of history http://www.crypto-world.com/announcements/rsa640.txt From: "Jens Franke" Date: Fri, 04 Nov 2005 16:53:08 +0100 We have factored RSA640 by GNFS. The factors are 16347336458092538484431338838650908598417836700330\ 92312181110852389333100104508151212118167511579 and 19008712816648221131268515739354139754718967899685\ 15493666638539088027103802104498957191261465571 We did lattice sieving for most special q between 28e7 and 77e7 using factor base bounds of 28e7 on the algebraic side and 15e7 on the rational side. The bounds for large primes were 2^34. This produced 166e7 relations. After removing duplicates 143e7 relations remained. A filter job produced a matrix with 36e6 rows and columns, having 74e8 non-zero entries. This was solved by Block-Lanczos. Sieving has been done on 80 2.2 GHz Opteron CPUs and took 3 months. The matrix step was performed on a cluster of 80 2.2 GHz Opterons connected via a Gigabit network and took about 1.5 months. Calendar time for the factorization (without polynomial selection) was 5 months. More details will be given later. F. Bahr, M. Boehm, J. Franke, T. Kleinjung

1 0

[math-fun] NYTimes: 'Innovative' Math, but Can You Count?
by Henry Baker 09 Nov '05

09 Nov '05

FYI -- http://www.nytimes.com/2005/11/09/education/08education.html The New York Times November 9, 2005 ON EDUCATION 'Innovative' Math, but Can You Count? By SAMUEL G. FREEDMAN PENFIELD, N.Y. LAST spring, when he was only a sophomore, Jim Munch received a plaque honoring him as top scorer on the high school math team here. He went on to earn the highest mark possible, a 5, on an Advanced Placement exam in calculus. His ambition is to become a theoretical mathematician. So Jim might have seemed the veritable symbol for the new math curriculum installed over the last seven years in this ambitious, educated suburb of Rochester. Since seventh grade, he had been taking the "constructivist" or "inquiry" program, so named because it emphasizes pupils' constructing their own knowledge through a process of reasoning. Jim, however, placed the credit elsewhere. His parents, an engineer and an educator, covertly tutored him in traditional math. Several teachers, in the privacy of their own classrooms, contravened the official curriculum to teach the problem-solving formulas that constructivist math denigrates as mindless memorization. "My whole experience in math the last few years has been a struggle against the program," Jim said recently. "Whatever I've achieved, I've achieved in spite of it. Kids do not do better learning math themselves. There's a reason we go to school, which is that there's someone smarter than us with something to teach us." Such experiences and emotions have burst into public discussion and no small amount of rancor in the last eight months in Penfield. This community of 35,000 has become one of the most obvious fronts in the nationwide math wars, which have flared from California to Pittsburgh to the former District 2 on the Upper East Side of Manhattan, pitting progressives against traditionalists, with nothing less than America's educational and economic competitiveness at stake. In these places and others, groups of parents have condemned constructivist math for playing down such basic computational tools as borrowing, carrying, place value, algorithms, multiplication tables and long division, while often introducing calculators into the classroom as early as first or second grade. Such criticism has run headlong into the celebration of constructivism by the National Council of Teachers of Mathematics and such leading teacher-training institutions as the Bank Street College of Education. The strife has taken on a particular intensity here in Penfield, perhaps, because the town includes an unusually large share of engineers and scientists, because of the proximity of companies like Xerox, Kodak and Bausch & Lomb. Skilled themselves in math, they have refused to accept the premise that innovation means improvement, and in their own households they have seen evidence to the contrary. For Joe Hoover, the epiphany came two years ago when he took his daughter, Kathryn, then in sixth grade, to lunch at McDonald's and realized she could not compute the correct change for their meal from a $20 bill. For Claudia Lioy, it was seeing her daughter, Iris, then in third grade, plodding through a multiplication problem by counting 23 groups of four apples. When Mrs. Lioy pleaded with Iris's teacher simply to show the class a times table, the teacher replied, "But that's drill-and-kill." For Ben Lee, it was having his teenage daughter, Olivia trying to answer probability problems by a method called "guess and check" - until he pulled out his own 10th-grade math book to instruct her about the appropriate formula. "I don't mind having kids appreciate what they learn," said Mr. Lee, an engineer who now works as a purchasing agent for Kodak. "But it's crazy to make a kid spend a night trying to solve a problem with these rudimentary and feeble tools." By last spring, these parents had discovered one another and their common exasperation with constructivist math. Jim Munch's father, Bill, a software developer at Kodak, drew up a petition asking the Penfield schools to offer pupils the option of taking traditional math. Nearly 700 residents signed it. Last June, the Board of Education turned down the request. Not surprising, school officials here paint a wildly different picture of the new math curriculum than do the critical parents. They point to a slip in Penfield's scores on standardized math tests and Regents exams in the late 1990's as a catalyst for changing the program. They also note that since the introduction of the constructivist curriculums - Investigations for elementary school, Connected Math for junior high, Core Plus for high school - those scores have risen gradually but steadily. In a broad sense, Penfield can be a hard place to make the indictment against constructivism stick. The high school sends 90 percent of its graduates to two-year or four-year colleges, and the mean SAT score stands at 1117 (with 562 on math). In the battle of anecdotes, school officials assembled their own array of parents to praise the new curriculum when this columnist visited Penfield last week. Susan Gray, the superintendent, attributed the criticism of the math program to "helicopter parents" who are accustomed to being deeply involved in all aspects of their children's lives. "Because the pedagogy has changed, the parents who knew the old ways didn't know how to help their children," she said. "They didn't have the knowledge and skills to support their children at home. There's a security in memorization of math facts, and that security is gone now." YET many of the dissident parents have extensive math backgrounds and thus the ability to criticize the curriculum. It is also true that most of them tolerated the constructivist program for its first several years, until bitter experience drove them into rebellion. Mary Rapp, the assistant superintendent, acknowledged the legitimacy of some complaints. In response, she said, Penfield has begun supplementing the constructivist classes with lessons in computation. Nearly 300 pupils in the district are now receiving remedial classes. A group of teachers worked last summer to revise the math syllabus in the high school in a somewhat more conventional direction. As a result, the district has had to petition the state for a postponement in the Math A Regents exam, from early 2006 to June. Still, in the math wars, tweaking around the edges does not settle the issue. The dispute is fundamental. To its advocates, constructivist math applies the subject to the real world, builds critical thinking and rescues classes from numbing repetition. But to those parents in Penfield and elsewhere - who have children in junior high unable to do long division or multiply two-column numbers, who pay for private tutors or sessions at traditionalist learning centers like Kumon, who wonder why there are so many calculators and so few textbooks - the words of a recent graduate to the Board of Education ring tragically true. "My biggest fear about going to college," Samantha Meek said at a meeting last spring, "is attending introductory math courses How am I going to be able to explain to my professors that I do not understand what they are talking about, that I do not have the same math background as the rest of the students, and that I cannot do mental math and can barely do it with pencil and paper?" E-mail: sgfreedman(a)nytimes.com

1 0

Re: [math-fun] Sudoku variant: dichotomy problem
by Sterten＠aol.com 08 Nov '05

08 Nov '05

see also: _http://www.sudoku.com/forums/viewtopic.php?t=2151&sid=10cdd4ba0ee77a3bfb0f… 1af4b09d0_ (http://www.sudoku.com/forums/viewtopic.php?t=2151&sid=10cdd4ba0ee77a3bfb0fa…)

1 0

[math-fun] Super/mirror palindromes ?
by Henry Baker 08 Nov '05

08 Nov '05

I was looking at an exit sign last night that was made of clear glass, so the words EXIT appeared on both sides, but unfortunately, the letters were backwards on the reverse. Are there any interesting "super/mirror" palindromes that read the same from both front & rear? They could only use the following letters A,H,I,M,O,T,U,V,W,X,Y. Is there a name for such palindromes?

6 5

[math-fun] Sudoku variant: dichotomy problem
by dasimov＠earthlink.net 08 Nov '05

08 Nov '05

So I was thinking about sudoku and realized that I'm not fond of the asymmetry of the 3 kinds of groups of 9 boxes that must each contain all the digits. Just rows & columns would be fine, but the 9 3x3 squares of boxes don't seem to fit in well. So I wondered if something could be done with a 4-dimensional tic-tac-toe board T -- with #(T) = 3^4, like sudoku. The most obvious groups of 9 cubes seem to be the "coordinate 2-planes": Just specify 2 of the 4 coordinates of points in T, letting the other two range over their 9 combinations; there are 54 such 2-planes in T. To make this as sudokitudinous as possible, the only problem remaining is to choose -- in a symmetrical fashion -- 27 among these 54 2-planes. ***It's tricky to find a symmetrical way to choose 27 out of the 54 2-planes!*** The best ways to do this all seem unsatisfactory, in that they don't have S_4 or even A_4 symmetry w.r.t. the coordinates x1, x2, x3, x4. Ideas? --Dan

1 0