July 2005 - mathfun@mailman.xmission.com

[math-fun] Re: Packing circles into a finite rectangle
by James Propp 09 Feb '06

09 Feb '06

>> If you have circles of radii 1/1, 1/2, 1/3, ..., 1/n for all n >= 1, >> then their total area is finite, although the sum of their radii is >> infinite. >> >> Can one fit these circles into a finite-sized rectangle? > > yes, they will fit inside a 1 x (11/6) rectangle for example. put each > circle inside a square, and then pack the squares like this: > http://www.stetson.edu/~efriedma/harmonic/ It is apparently still unknown whether one can pack squares of sides-lengths 1/1, 1/2, 1/3, etc. into a 1-by-(pi squared over six) rectangle. See Clive Tooth's web-page www.pisquaredoversix.force9.co.uk/Tiling.htm for an example of how one might get started. I asked Clive for background on this tiling, and he kindly forwarded to me copies of some relevant sci.math postings from last year (one by Clive himself and one by David Cantrell): ************************************************************************** From: "The Last Danish Pastry" <TheLastDanishPas...(a)yahoo.com> Newsgroups: sci.math Subject: Packing squares into a 1 x Zeta[2] rectangle Date: Sun, 14 Mar 2004 13:41:34 -0000 Since the sum of the reciprocals of the squares of the positive integers is pi^2/6, the question arises as to whether squares with sides 1, 1/2, 1/3, etc can be packed into a rectangle of size 1 by pi^2/6. A picture of such a packing appears at http://www.pisquaredoversix.force9.co.uk/Tiling.htm I know of no proof that such a packing is possible or impossible. A program which I wrote has recently packed the first one million such squares into such a rectangle. I wrote the program in Mathematica and it uses exact arithmetic throughout. The algorithm is simple: The program maintains a list of rectangles. Each member of this list is itself a list containing exactly two members: the short side of a rectangle followed by the long side of the rectangle. The program does not store the position or orientation of any rectangle. The list is stored in ascending short side order. Initially the list contains one entry: {1, pi^2/6}. The program inserts the squares in decreasing size order, starting with the 1x1 square. At each stage, to insert the square with side 1/n, the program finds the rectangle with the shortest short side which will accommodate the square. [In the case that there are two or more such rectangles with equal short sides, the program will pick the youngest one.] Suppose that this rectangle is a x b, where 1/n<=a<b. The program deletes this rectangle from the list and inserts two new rectangles (b-1/n) x a and (a-1/n) x 1/n into the list. - If any side of one of these new rectangles is zero, the rectangle is not inserted. - Each new rectangle is stored in {short side, long side} form. Thus, the list of rectangles grows by one per inserted square, except in the rare cases in which a rectangle of exactly the right width is found. A trivial optimisation, which took me a long time to notice, is that if the number of squares to be inserted is decided at the beginning, as N, say, then any rectangles narrower than 1/N can be discarded as soon as they appear. This has a dramatic effect on the memory requirements and running time of the program. In the case of N=10^6 the maximum length of the rectangle list is only 7,493 which occurs just after inserting the square with side 1/55,205. Thereafter the length of the list slowly decreases. After inserting the last square, with side 10^-6, there are just 7 rectangles in the list. Their dimensions are, roughly: 0.000001000264 x 0.000371508565 [1,000,000] 0.000001000289 x 0.000006561855 [ 999,736] 0.000001000332 x 0.000011950546 [ 999,710] 0.000001000424 x 0.000099911008 [ 999,668] 0.000001001705 x 0.000013366392 [ 999,575] 0.000001001771 x 0.000555285230 [ 998,297] 0.000621399972 x 0.000621402936 [ 998,232] The number in square brackets is the square insertion step on which the rectangle was created. Note that each rectangle, except the last, has a short side just exceeding 10^-6. The last one is huge in comparison to the others. Also, it is almost square, having an aspect ratio of about 1.00000477 . The exact size of that last rectangle may be expressed as: (pi^2/6 - ShortNumerator/ShortDenominator) by (LongNumerator/LongDenominator) Where ShortNumerator = 88148577597184641314023698687804198322622003067950 90277185502203375757868045576236778623499141581835 91095283100445795053089253938670874859361703421694 93589311823604254188777249571387340885945805010588 59158565482204748239750452173829861295626045336259 37611823762149119593932203343599960000593198902456 62151237628335467123582313067030461952701063806541 09667253352708582423851542412389977650553557102776 48867766805593783542952432276691372915179943637567 30921614687225494242879103415386639772227105415075 60643644416702161056703911777435451470868967261015 03285333687384626370723064421360623232628962182637 33785897530162588640506103091960735379749803817168 27337105343328553249474140253583305664128829433056 13496001065570446619534699711595669897241621797339 93388113729020710706312912651983440135427698863738 63455691221381048718834049233446561869585869886892 11066449759482338440176987851999633382542943944743 83052271691048660471857179765488027759900589960305 37378583137068870187987573969424873832345344118539 33368635075465276924658419905001027235726511505469 90353609271920928926254763071708700239940565565014 69168650106503612867362486635886531701170797485510 99375741498187773039269448405524049571692907463933 52292512770766034352574830725344567781634199947344 39128864912738319438009565992988317045941602472518 84296172734535520954249457165155850357846464984168 55299222999724423825677947429849212042460805178788 23214473791347512926915739195451188103089711423995 69891250713418835019305494967439261535807066257765 86799633983386818438909781178910531233498247023179 22489232680161587870238609995903489290522620579734 27913072409961919211050524749783993630732833119534 51221464170732847284504244076797981093088600479209 053071348915420741889 ShortDenominator = 53608160645434703140761211994317971700783074368336 23325975705041657962199994733358382994458318582660 77598233503372093023408990096331259105144227503324 99931830157705570560424971647310855286927378535483 51519419895212616165032657829920140448566211296935 08925318960134998789890442610040864611429495599467 55671385275409484022080990210675967224987014208598 03335236373663242927780013944648864149878730486125 39041613975393755631755935261748017063478349180906 68435262002209072815068783227098957825899390123056 87116154057047656878878907753207321889684985791605 16008019019744195226005265347943729214648741668979 90732236259531674523664568538104488968273268732774 74645971065348455713992347183400863276778739619943 89625588842652615699820699583835957017913827580111 39619239553717364061586421301662144411944880262864 13395969932087668263688142360819354641427777701996 11575083489100468980371536759296335301136691198138 39559100156995546068054947710363960181181289364408 47219039882502818687162480694856587042340603392188 93192097190331493671006154660882637398429894947140 66724834302759980279336075917538263518035481261929 09959571761983813160895335069812335369906345916646 57307263315174319702690110108769119880417800559541 00846379467033278426493445187132240090150811316237 11870955392306082427560405688265993364931620972062 42335013731582665984021398103261291575096750373611 78793366106368150944101270721191063173365978409196 32419016511795819355629216137822167151147383280072 17692953976640188298210375720290857531988737370969 01207985676688854219832216404101906724620701738590 65777947161752685898547108814129100143613045915161 23374032620084188029394058765229087587568694264890 44233796349785411756140522085279648064146173069741 478636801148014080000 LongNumerator = 86047691660315035868968439680618750650385496662337 69341618423224868557176707904056350747739644607152 19341301092244142985694427567208621603825424715808 50112490209730250303812592410205852634552809617406 54471220118615832220663814127702644186714156802514 89272173167125109946591599082250813475432136844437 68434150604827750301142594110541508119955806775639 48463821703879298880841441517861092382325647927555 17115984413353561811152746794319549286695056542231 75370181749913246697604501180515750468588947850814 96706860842334628047016110265861987131951269186913 55908484624794372227266755207694315503681976948427 59732973255837108405693520922709400140190847636749 60091554508265275883766083172672994896381234279724 35485615485280999872894822261731570552709443192476 07685741096374165452217373319152585412622236248087 75856424918727148070254116048744362672852782317829 99207549345144244124571110563211160343448412194752 79110755652853486307738886342254777707077572587992 29405091182393418319601369763056120887765700618802 27139753549245993550447831136020976532760818138519 98216552674127086312240961717818956038535226187300 43026597993187644795910836481706823332909020130603 09729716420449811214331443400182398534278484763571 27904525989212662382850630094162630962359551947273 97311922973034069310043168935737831265241199089047 46559558404697050977201086017144902884602248144108 71005578441670661613107026657746377160408235952122 70087369832576028781964223879066392055590320740847 64872057694761838719127407266757016871496087930551 58594303661605591550655979493954945142285417155556 97061447617516531128930865552526142619566789459050 16802730874016347300046435875463493515247956092289 80788952041557673741641666771939979618817508420910 11050430185421809507580791626321726210797393934779 33362836600904869583181 LongDenominator = 13847326202197605511604348541676281864027795818043 31494335574789145450920249049910013265993162156505 60831474662540178414423726822350848233301461067293 21368995360010230519749558542277057071473577106811 23548536664652068929533780687547853336157369555086 86435599910456774645119837370840414802536199558214 07527909448749766750406409444125057733978666254122 19353807926168688488715863115960118447262678159252 66974533884810419996115934738184899912380787401311 77856867483197701324817440576351765023155329523060 68640715686158929369832278778842403496825357945180 51999476544062632945516973292520225337991834072383 82846228280041100692245330583478338241014202245803 30323143236417275386997321382053499979484896390576 45426647084624716067636294896758072966317096343334 28169063530634898773783098553798071542939121086910 08006721058240228461124891602875033925435245224172 90909661066024272174911721070106393261965722571136 18608587173321485889447514408382277645342459166650 66976600733716756193252940889415454560334136529577 70915746535414564177067690689656587269581203051464 54295311030944948219808305598301111195229732416082 42817235468158091436079088616794858652804473035517 82817817155337872004025893330437425894039012377193 76447539452009335637045807403996380650616246802471 05691575600545667349590304669247493320414626833379 52612693846867728391114410877249463229225980473996 60123182871902607011087292407939606651288648107916 20645836880002779839862309998364888537462475216562 83515669632032306317521726424095159019732485843596 26389117354057755490411586373128011034072899097872 57238596906896860163242623358201011919041838989031 36072177994374094882330699298066695784371692394667 11940033790850742395135563324255474227834715815498 61014376098413906103604397447388393432391565219123 065068758213935671227536000 -- Clive Tooth http://www.clivetooth.dk ************************************************************************** Subject: Re: Packing squares into a 1 x Zeta[2] rectangle From: David W. Cantrell <DWCantr...(a)sigmaxi.org> Date: 18 Mar 2004 16:31:52 GMT Newsgroups: sci.math "The Last Danish Pastry" <TheLastDanishPas...(a)yahoo.com> wrote: > Since the sum of the reciprocals of the squares of the positive integers > is pi^2/6, the question arises as to whether squares with sides 1, 1/2, > 1/3, etc can be packed into a rectangle of size 1 by pi^2/6. > > A picture of such a packing appears at > http://www.pisquaredoversix.force9.co.uk/Tiling.htm > > I know of no proof that such a packing is possible or impossible. [snip] It would be good if people interested in this thread were aware of some of the history of this problem. To that end: _Unsolved Problems in Geometry_ by Croft, Falconer and Guy (Springer-Verlag, 1991) "D5. Packing unequal rectangles and squares in a square." (pp. 112-113) mentions a question similar to the one considered in this thread. D5 caused me, in 1996, to consider several packing problems of this sort. I found simple algorithms, which I implemented in Mathematica, which seemed to pack rectangles of decreasing size "perfectly". The algorithms worked for classic problems, such as packing the rectangles 1/n by 1/(n+1) into the unit square, as well as for interesting new packing problems. I did not publish my results then, hoping first to prove that the algorithms were adequate for packing all of the rectangles. In November 1999, spurred by Clive Tooth, I posted to sci.math a brief description of what I had done. See both parts of "Packing Rectangles of Decreasing Size" at <http://mathforum.org/discuss/sci.math/a/t/241167>. (Readers may also be interested in looking at the packing algorithm which Clive had used back then.) Unbeknownst to me in 1999, an algorithm for such packings had appeared previously in the literature: An Algorithm for Packing Squares, Marc M. Paulhus, _J. Combin. Theory Ser. A_ 82 (1997) 147-157. His algorithm is somewhat different from any of the algorithms which I had used (but I wonder if perhaps it is the same as Clive's current algorithm). For packing squares of side lengths 1/2, 1/3, 1/4,... into a rectangle 1/2 by 2(pi^2/6 - 1), Paulhus gives two rules: "Rule 1. Always place the next square in the corner of the smallest width rectangle into which it will fit." "Rule 2. After placing a square into the corner of a rectangle, always cut the remaining area into two rectangular pieces by cutting from the free corner of the square tot the longer side of the original rectangle." For older references, see those cited by Paulhus. The most recent articles known to me concerning such packings -- but again, I may not be up-to-date with the literature -- are the following: Perfect Square Packings, Adam Chalcraft, _J. Combin. Theory Ser. A_ 92 (2000) 158-172. Compactness Theorems for Geometric Packings, Greg Martin, <http://arxiv.org/PS_cache/math/pdf/0005/0005054.pdf>. Perfect Packings of Squares Using the Stack-Pack Strategy, Johan Wastlund, <www.mai.liu.se/~jowas/dcg.ps <http://www.mai.liu.se/~jowas/dcg.ps>>. Thoughtful comments are welcome. Regards, David W. Cantrell ************************************************************************** (Clive tells me that there's more discussion of this problem in sci.math, though I haven't checked.) Jim Propp

4 3

[math-fun] a conjecture based on Euler pol. and the Fermat's little theorem.
by Simon Plouffe 08 Feb '06

08 Feb '06

hello everybody, I had this idea one night a while ago, if k = n^2 - n + 41 and if 2^(k-1) = 1 mod k then k is prime. It seems to work all the time, I verified for n up to 500,000,000. In other words : n^2 - n + 41 is never a 2-psp, a pseudo-prime in base 2 (that is the conjecture). There is another one too : if k = n^2 + 3 and if 2^(k-1) = 1 mod k then k is prime. I tried to construct an argument about the factorization of n^2 - n + 41 and 2-psp's but failed to see any convincing details. I have other values that seems to work also like k = n^2 + 163 (only 1 fail), another counter example is 103*n^2 - 3945*n + 34831 when n = 2400371 it does satisfy the little fermat theorem but the number is composite : 5315987*111635707. and that polynomial (103*n^2..) is known to produce a lot of primes. Based on this I launched a series of computations but (as you may know), it all comes back to the fact that the little fermat theorem produces primes very often and if we combine it with a simple g.f. like the Euler polynomial, chances are that it will produce many primes. Even by knowing this, the best probable prime I could find is about 35000 digits. 1) I could not find any reference about this. 2) So far n^2 + 3 and the Euler pol. always produces primes and avoid the 2-psp's elegantly. 3) Maybe there is alink between class numbers and the little fermat theorem but I can't see it. My question is do you see any connections ? Simon Plouffe

2 1

[math-fun] Found in the IHP cellar! 2/2
by Christian Boyer 21 Nov '05

21 Nov '05

---- FAUQUEMBERGUE computations And I have the chance to have discovered, again in the cellar of the Institut Henri Poincaré, the original handwritten computations on Mersenne numbers M101, M103, and M109 as sent by Fauquembergue to André Gérardin. http://www.utm.edu/research/primes/mersenne/LukeMirror/lit/lit_008s.htm These computations done in 1913-1914 were... false, as found by Robinson 40 years later: http://www.utm.edu/research/primes/mersenne/LukeMirror/lit/lit_024s.htm Within the huge number of handwritten 0s and 1s, the game would be to locate the first line where the error occurs! I can send .JPG photos to interested people. Christian.

1 1

[math-fun] Sudoku, minimal number of clues
by Gary McGuire 06 Sep '05

06 Sep '05

I have been spending way too much time on sudoku. There are a few interesting questions around, but most have been solved. There is one remaining big open question: What is the fewest number of clues a sudoku can have? The current record is 17. Here is an example of a puzzle with 17 clues. . 9 8 . . . . . . . . . . 7 . . . . . . . . 1 5 . . . -------+-------+------- 1 . . . . . . . . . . . 2 . . . . 9 . . . 9 . 6 . 8 2 -------+-------+------- . . . . . . . 3 . 5 . 1 . . . . . . . . . 4 . . . 2 . (It is convention that a sudoku puzzle has a unique solution. If there are multiple solutions then the puzzle is not valid. An embarrassing such puzzle was carved into a hillside in England by Sky TV to promote their new sudoku tv show. See http://www.sudoku.org.uk/blunder.htm Also the 3rd puzzle printed by the Daily Telegraph had multiple solutions. Their setter had only just learned the puzzle and hadn't perfected his program yet.) Say you want to construct a sudoku with 16 clues. (This has been discussed on lots of internet chat sites.) Start with a given completed sudoku grid. Then you might look for sets like the following: 1 2 . ... ... . . . ... ... . . . ... ... 2 . 1 ... ... . . . ... ... . . . ... ... . 1 2 ... ... . . . ... ... . . . ... ... It's clear that 1 and 2 can be interchanged IN THESE 6 CELLS ONLY and we still have a valid completed grid. Conclusion: in any sudoku puzzle with this completed grid as the answer, one of these 6 numbers must be a clue. Call a set like this an unavoidable set, or a fated set, or something. The size of a fated set can vary, there are some obvious ones with 4 elements: 12. ... ... ... ... ... ... ... ... 21. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... Of course not every grid has an unavoidable set like this one. If a set of clues does not intersect every fated set, it cannot be used as a set of clues for a sudoku puzzle. So, for a given grid, we want all its fated sets and then we want to search for a set of size 16 that intersects all the fated sets. If we find one, we may also need to check that the puzzle is solvable from these clues, I'm not sure about this bit. Clearly we would like to choose the grid so that it has relatively few fated sets. What types of grids have this property? Are there clever ways to search for the set of size 16? Is this approach feasible? This may be related to the automorphism groups of sudokus, and also to the matrix arising from the dancing links method. I will post a bit about these in other messages. This is already too long. Gary McGuire

4 3

[math-fun] clarification, trapezohedra
by R. William Gosper 08 Aug '05

08 Aug '05

I said, Recall the odd (mod 3) squarefree sequence d(k) = 0 1 2 1 0 1 2 0 2 1 0 2 0 1 2 1 0 1 2 0 1 0 2 1 2 0 2 1 0 ... defined as the left-to-right alternating sum of the nonzero trits of k. In *balanced* ternary. (Thanks, Neil!) Theorem: if any trapezohedron be scaled to inscribe in a sphere, its faces are "right kites", i.e., they have two square vertices. Mathworld's trapezohedron article just lists areas and volumes of a few special cases (scaled inconsistently). For an n-trapezohedron inscribed in a spheroid with polar radius a, equatorial radius b, 2 2 2 2 2 2 8 c (b c - b + 2 a ) 2 sqrt(c (a c + b )) s = sqrt(4 a - ----------------------), S = ---------------------, 2 c + 1 (c + 1) 2 2 2 %pi 8 b sqrt(b c + a c) sin(---) n a b c n inradius = ------------------, area = ---------------------------------, 2 2 2 2 sqrt(b c + a c) (c + 1) 2 %pi 8 a b c sin(---) n n 2 b sqrt(c) volume = -------------------, tradius = -----------, 2 c + 1 3 (c + 1) 2 2 2 2 2 2 (c + 1) ((2 - 2 c) S - s ) (c + 1) ((c - 1) S - c s ) sqrt(---------------------------) sqrt(-----------------------------) (1 - c) (2 c - 1) (c - 1) c (2 c - 1) a = ---------------------------------, b = -----------------------------------, 2 2 2 2 %pi 2 b cos(-----) + a c n angles = [acos(--------------------), 2 2 a c + b 2 2 (b - a ) sqrt(1 - c) sqrt(c) acos(-----------------------------------------), 2 2 2 2 sqrt(a c + b ) sqrt(2 b c + a (1 - c)) 2 2 2 2 b c - a (1 - c) %pi - acos(--------------------)], 2 2 2 b c + a (1 - c) 2 3/2 b c --------------------------- + a 2 2 sqrt(a c + b ) + a sqrt(c) apex_solid_angle = 2 acos(-------------------------------) n, 2 2 sqrt(b c + a ) 2 2 %pi 2 girdpt_solid_angle = acos(((a cos(-----) + b c) n 4 2 %pi 4 2 2 2 (a cos(-----) + b c - 2 a b c (2 c + 1)) n 2 2 2 3/2 2 2 + 4 a (b - a ) sqrt(1 - c) c (c + 1) sqrt(a c + b ) 2 2 2 2 3 sqrt(2 b c + a (1 - c)))/(b c + a ) ), c + 1 natural_a = --------------------------------------------, %pi 2 sqrt(2) sqrt(1 - c) sqrt(2 c + 1) sin(---) n c + 1 natural_b = ------------------, %pi 4 sqrt(c) sin(---) n where s:=short side, S:=long side, c:=cos(%pi/n), tradius := the "tubular" or girth radius, and natural_a and natural_b are the spheroid radii of the trapezohedron which is the dual of the antiprism with unit edges. The face angle order is [apex, upper girdle, lower girdle]. Note vanishing cosine of upper girdle when a=b. Maybe somebody can simplify the girdle vertex solid angle. When a=b, it boils all the way down to acos(1 - 2 c). (This all started when I added prisms, pyramids, etc. to Macsyma's rather meager PLOT_3D_FIGURE for a geomety lesson.) --rwg PS, while the cube is the only regularhedron whose vertex solid angle is a rational fraction (1/8) of the sphere, the tetrahedral and octahedral vertex solid angles are 2 atan(sqrt(2)/5) and 4 atan(sqrt(2)/4). Since 3 atan(sqrt(2)/4) + 2 atan(sqrt(2)/5) = pi/2, six octahedra and eight tetrahdra come together at each vertex in the octahedral-tetrahedral tessellation of 3-space. This is a (rather lame) example of a pi arctan formula a la Machin's, but with sqrt(rational) series multipliers, which are considered kosher in the game of maximizing digits/term of hypergeometric pi series. So, with sqrts, (but not surds), can we beat Machin?

1 4

[math-fun] ossification
by Richard Schroeppel 29 Jul '05

29 Jul '05

rwg> PPS, did RSA200 protect any squeamish ossifrage type sentiments? I don't know of any. At one time RSA was offering prizes for each 10-digit advance, and they had a list up to 500 digits or so. They restructured the prizes, and I think the prize for RSA200 was withdrawn. But I'm repeating third hand "information". Season to taste. Rich rcs(a)cs.arizona.edu

1 0

[math-fun] Sudoku Guessing
by Ken Roberts 27 Jul '05

27 Jul '05

In the example below, I don't really see an essential difference between the method described, and algebra. Suppose one is asked to determine x, knowing that (x + 3)*2 + x + (x + 5) = (25 - 2) Disguised as a suitable word problem - eg, "The twins and their older brother and younger sister have their birthdays on the same day of the year. Julia is three years younger than Wilma; Sam is two years older than Grace. This year, from a box of 25 birthday candles, almost half the candles were needed for the cupcakes for the twins. After all four cupcakes were decorated only two candles were left over. How old is Julia?" First there is interpretation, involving cultural norms. Then trial and error will determine the various ages. Or, one can use "algebra" aka "magic" to write symbols that disguise the guessing. When pressed, the mystic says "I supposed that, whatever Julia's age was,..." To which the questioner will say, "Oh, you guessed!" And the mystic replies, "No guessing was involved!" and starts to mumble about unknowns, formulas, laws of distribution, association and transposition, and maybe redundant information or integer solutions... Bottom line: The following snippet of reasoning, if embedded in some suitable calculus which starts with "a" as a symbol and cranks thru to determine "f"=9, would not be described as "guessing". We only call it guessing if we have to substitute "1" for "a" at an intermediate stage because our calculus is weak. > If a=1 then b=5, c=8, f=9 > If a=9 then d=2, e=8, f=9 > Therefore, no matter what, f=9. So the challenge is to devise a suitable methodology. That is what seems appealing in the sudoku problems. [from prior messages] > > Here's another almost completed example: > > > > 193 852 746 > > 854 763 912 > > 672 419 853 > > > > 938 147 625 > > 246 ... 371 > > 517 236 489 > > > > 78. 6.. .34 > > 465 3.. .97 > > 32. .74 .68 > > > > This is easily completed by making a guess. But I cannot see any > > way to complete it without making a guess. > > This gets into the territory where people argue about what > "making a guess" means (which is the cultural phenomenon > that I thought was interesting enough to start the sudoku > thread in the first place). If you naively write down which > numbers are possible in each square, you get, among > others: > > . . . | . . . | . . . > . . . | . . . | . . . > . . . | . . . | . . . > --------------+------------------+------------ > . . . | . . . | . . . > . . . | . f:8,9 c:5,8 | . . . > . . . | . . . | . . . > --------------+------------------+------------ > . . a:1,9 | . d:2,9 b:1,5 | . . . > . . . | . e:2,8 . | . . . > . . . | . . . | . . . > > The sudoku technique called "forcing chains" uses > the following reasoning: > > If a=1 then b=5, c=8, f=9 > If a=9 then d=2, e=8, f=9 > Therefore, no matter what, f=9. > > I understand that people have developed coloring methods > which make this type of deductive step easy to spot. But > there is still, er, "lively debate" over whether this counts as > guess work -- you certainly do assume something which in > the end turns out to be false, though from just the information > above, you can't tell which assumption is the bad one.

2 1

[math-fun] sudoku, k-SAT, dancing links
by Gary McGuire 27 Jul '05

27 Jul '05

Victor wrote >Well, It's certainly possible to solve a Sudoku puzzle without trial >and error and guessing. Here's the proof: you can pose the solution >of Sudoku as a problem in satisfiability (SAT): ............ >You can solve any solvable SAT problem via resolution (which is like >Gaussian elimination), and back substitution. This doesn't involve >any guesswork. However, it could be exponential (since resolving on a >variable can create a large number of new clauses). Could it be exponential because it is searching and backtracking? Creating a large number of new clauses sounds a bit like searching through a tree. I wonder is this somehow equivalent to using the 729x324 matrix which people have discussed. It puts sudoku into the framework of a "covering" problem: Given a matrix of 0's and 1's, we want to find some rows that together have exactly one 1 in each column. In other words, their sum is the vector of all 1's. Here is how to construct the matrix for sudoku: The rows are indexed by pairs (d,(x,y)), where d is a digit and (x,y) are the coordinates of a cell. The columns are in four groups, each group having 81 columns. The first group have labels (d,x), where d is a digit and x labels a row of the puzzle. The second group have labels (d,y), where d is a digit and y labels a column of the puzzle. The third group have labels (d,b), where d is a digit and b labels a box of the puzzle. The fourth group have labels (x,y). where (x,y) are the coordinates of a cell. In row (d,(x,y)) we place a 1 in the columns labelled (d,x), (d,y), (d,b) where b is the box containing the cell (x,y), and (x,y). Each row has four 1's. This gives a 729x324 matrix, which I think deserves the name The Sudoku Matrix. (Of course we can do this for n^2 x n^2 sudoku.) Here's the point: A valid completed sudoku grid corresponds to a set of 81 rows which "cover" in the sense that they collectively have exactly one 1 in each column. A puzzle may be described by a set of rows which extends uniquely to a set of 81 rows which cover. Solving the puzzle is finding the rest of the rows. (If we drop the 81 columns corresponding to the boxes then we have the ordinary Latin squares completion problem.) One way to efficiently search for a solution in covering problems is by a backtracking method of Knuth which he calls "dancing links," mentioned in an earlier post. See addendum at http://spivey.oriel.ox.ac.uk/mike/comp2005/results.html Solving the puzzle via the matrix puts deductions like "only two numbers can go in this cell" and "this number can only go in these two cells" on the same footing, and makes any distinction between them artificial. >I'm not saying that this is the best way to do it though! However, if >you wish to do it this way, it is certainly best to first do >resolution on the subset of 1-clauses and 2-clauses (which is very >fast -- there is a linear time algorithm for this). This corresponds >to making the standard initial deductions. What would correspond to using trial and error? I'm impressed that your program solved that puzzle in a fraction of a second. Could it be tweaked to somehow rate the difficulty of a puzzle? Gary McGuire

1 0

[math-fun] sudoku trial and error, NP-completeness
by Gary McGuire 26 Jul '05

26 Jul '05

If you want a hard sudoku try . . . | . . 3 | . 6 . . . . | . . . | . 1 . . 9 7 | 5 . . | . 8 . ---------------------- . . . | . 9 . | 2 . . . . 8 | . 7 . | 4 . . . . 3 | . 6 . | . . . ---------------------- . 1 . | . . 2 | 8 9 . . 4 . | . . . | . . . . 5 . | 1 . . | . . . I believe that this one cannot be solved without trial and error (aka guesswork). Here's another almost completed example: 193 852 746 854 763 912 672 419 853 938 147 625 246 ... 371 517 236 489 78. 6.. .34 465 3.. .97 32. .74 .68 This is easily completed by making a guess. But I cannot see any way to complete it without making a guess. There is much discussion about whether every sudoku can be solved without resorting to trial and error. I think the above examples show that some sudokus require guesswork, but that's not a proof. None of the puzzles given in newspapers will require guesswork, but there are several levels of difficulty beyond what you find in published newspapers and books. Somebody on a forum quoted the NP-completeness result as being a proof that sudokus requiring guesswork exist. Solving sudoku is NP-complete, as has been mentioned before (see the wikipedia entry). The argument goes that an NP-complete problem requires a non-deterministic algorithm, which is one that has to make a random choice somewhere. This random choice is the guess. Is this a valid argument? I don't know enough about NP-completeness. Gary McGuire

3 3

[math-fun] Comet, RSA200, Prime Gaps, Sudoku, Count Down, Dull Semigroups
by Richard Schroeppel 22 Jul '05

22 Jul '05

A bunch of things. --Rich ----- Comet: Did anyone else see the comet impact? I was out watching for it the night of July 3. I had my binoculars pointed at the right area, but had picked out the wrong dot as "the comet". I saw one bright flash, lasting perhaps a second, with no obvious center - the whole field flashed. The time was right, within a minute or so. ----- RSA200: [For some reason, this wasn't on the NMBRTHRY list?] The (old) challenge number RSA200 (a 200 digit number) has been factored by F. Bahr, M. Boehm, J. Franke, T. Kleinjung, P. Montgomery, and H. te Riele. Calendar time was about 18 months, Dec 2003 - May 2005. The total work was roughly 75 PC-years on a 2GHz machine. The linear algebra used a cluster of 80 machines. They have since made further improvements to the Lattice Sieve. Sieving is a random-access use of the memory, and it must be tweaked to make the best use of cache and TLB. Google/Wikipedia for RSA200 or RSA-200. Discrete logs are lagging behind, at 130 digits. Joux & Lecier used a 16-processor cluster of 1GHz Alphas for 3 weeks (about 1 GHz PC-year). Individual logs take a few hours. ----- Recent progress related to the twin-prime problem: >From the prime number theorem, the average gap between primes is log(Prime). Goldston, Motohashi, Pintz, and Yildirim have shown that the ratio Gap(Prime(i))/log(Prime(i)) has lim inf = 0. This is a far cry from the "lim inf Gap = 2" required for settling twin primes, but it is progress. http://www.maa.org/news/052505twinprimes.html http://www.aimath.org/preprints.html. ----- Sudoku: Until the 17-clue example from yesterday, I was wondering what all the fuss was about. The 17er actually requires some more interesting reasoning, but no trial. I used things like "these two cells must be {3,4} in some order", and subtracted them from larger sets. Also "since these two are {3,4} (or {4,3}), and they are in the same row, I can exclude 3&4 from other cells in the row". The main work is scanning the array looking for an application of one of the simple rules like "this 3x3 box must have a 7 somewhere, and all but one of the empty cells is excluded by having a 7 elsewhere in an intersecting row or column". The popularity of the game means there are lots of folks who like a kind of mathematical reasoning. Dan's Latin Square estimate deflator should have a coefficient of 2, not 8. D_4 includes horizontal and vertical reflection, already counted in the row & column permutations. Diagonal flipping remains, giving the coefficient 2. There are Latin Cubes! Addition mod N gives a Latin Hypercube of any dimension. ----- Book recommendation: Count Down, by Steve Olson. He follows the US team (6 high schoolers) at the 2001 Math Olympiad. I found the book intersting for the side topics: He examines the rarity of women in the contest. He looks seriously at the very idea of competing, and how it applies to the Olympiad. Apparently mathematics is held in higher regard in other countries. And there's a chapter about Ultimate Frisbee. The Olympiad problems and solutions are sketched. ----- Associative-Commutative Crossover at 406: Fix an integer N. Consider all the N^N^2 binary operations defined on N elements. Are there more Commutative operations (with symmetric operation tables), or Associative operations (semigroups)? Likely answer: For N<=405, commutatives win; for larger N, semigroups. A quick look at OIES shows Commutativity getting off to an impressive early lead over Associativity. (The story's the same if we count tables instead of culling isomorphs.) Semigroups (fron N=0; sans isomorphs & anti-isomorphs): A001423: 1,1,4,18,126,1160,15973,836021,1843120128 Commutatives (from N=0; sans isomorphs): A001425: 1,1,4,129,43968,254429900,30468670170912, 91267244789189735259,8048575431238519331999571800, 24051927835861852500932966021650993560, 2755731922430783367615449408031031255131879354330 Note to NJAS: I think the sequence database is missing abelian semigroups of order 8, 221805. (From the Order 8 paper by Satoh &al.) The trick: For large N, the number of abelian tables is N^(N*(N+1)/2). [Divide by ~N! to discount isomorphs, but it doesn't change the gross order.] Very roughly, (N^N^2)^.5. The semigroups are dominated by the Dull Semigroups, which satisfy the equation A(BC)=(DE)F, or equivalently, XYZ=0. The multiplication table has an L-shaped swath of 0s at the top and left edge; the remaining portion of the table consists of random values <= the thickness of the L. The L that gives the most semigroups solves N = L (2 logL + 1), roughly L ~= N / (2logN). This gives (again very roughly) (N^N^2)^1 tables. Empirically, most semigroups are Dull: 85% of the 7s, and 99% of the 8s. I had a proof of this once, but can't recall it. (Usually a bad sign.) Since 1 > .5, the Semigroups must eventually overtake the Abelians. I wrote a Lisp function to do the estimates. I assumed the crossover would be around N=12, and was surprised it was so large. The crossing is sharp, and isomorphisms don't change it. Rules like Mid-Quartile-Swap, (AB)(CD) = (AC)(BD), one of the Average axioms, have even more tables than the semigroups. They have a sub-population of Dull-4 tables, where any product of four things, in any grouping, equals 0. These tables have an outer L of 0s, like the semigroups, and then an inner L with values <= outer-L-thickness, and then a lower-right square region with values <= outer+inner-L-thickness. These outnumber Dull Semigroups. In fact, because it has no top-level singleton, the MQS rule has an even larger set of Dullish tables, where the 0-region is only a small square in the upper-left corner, and the less-restricted values occupy a big lower-right L. For any Rule where each side has 2 or more operations, (like the ternary Defective Distributive Law for Majority, AB.CDE = ABC.ABD.E), Dull-ness will be a consideration, and will likely dominate the numbers. As the number of operations in the Rule is increased, more nested Ls are added, and the Dulls increase. Dullness can be somewhat counteracted by Commutativity, and is vanquished by Idempotence, or any rule with a singleton on one side. <the end of Dullness>

2 1