April 2014 - mathfun@mailman.xmission.com

[math-fun] A knight's surprise?
by Fred Lunnon 13 Apr '14

13 Apr '14

Consider the graph whose vertices & edges represent squares & knight moves on a 4x4 chessboard tiling the torus. (1) Find a spatial embedding with the full symmetry of the graph. (2) Deduce that the graph can be embedded (without crossings) on the torus. Fred Lunnon

1 0

[math-fun] Knight distance
by Warren D Smith 13 Apr '14

13 Apr '14

The proof of the Knight distance formula by Das & Chatterji [Pattern Recog Lett 7,4 (1988) 215-226] is not as simple as certain math-funners seem to think it can be. But it is probably correct. They first established formula gave a "metric." This forces: formula gives a lower bound on true knight distance. Albeit they did not actually say that -- when it came time to actually prove this lower bound claim, then they just said "we can easily show" it, without saying how, then claiming details may be found on p.127 of A.Rosenfeld: Digital geometry, chapter 2 of "pictorial languages" Academic Pr 1979. Annoying, but I do not need Rosenfeld to tell me metricness plus validity at small distances forces lower bounding. So then we also need: formula really is metric, and gives upper bound. This they claim to establish by case arguments depending mod 2 and other stuff. They omit about 70% of the cases from the paper, hence do not actually fully prove it. I guess they expect the reader to fill in the missing cases.

1 0

[math-fun] Knight Distance
by Warren D Smith 12 Apr '14

12 Apr '14

This formula works: kd = Function[{ox, oy}, Module[{x = Max[Abs[ox], Abs[oy]], y = Min[Abs[ox], Abs[oy]], p = 0}, p = If[3 x < 2 (x + y), (x + y + 1)/3, (x + 1)/2]; If[Mod[x + y, 2] == 0, p = 2 Floor[(p + 1)/2], p = 2 Floor[p/2] + 1]; If[x == 1 && y == 0, p = 3]; If[x == 2 && y == 2, p = 4]; p]]; Proof: It suffices to verify that kd[0, 0] = 0 and kd[x, y] = 1 + Min[kd[x + 1, y + 2], kd[x + 2, y + 1], ..., kd[x - 2, y - 1]], in which case we are done by induction on the value of kd[x, y]. Both of these are absolutely trivial to verify, although the latter is a messy case-bash (having to special-case squares near the lines 2|x| = |y| and 2|y| = |x|). Sincerely, Adam P. Goucher --uh, well, that was what I was saying, but the devil is in the details ("nasty case bash") i.e. the sentence you used to avoid actually proving it. Meanwhile, E.Clark's tip led me to find the "Encyclopedia of Distances" by Michel Marie Deza, Elena Deza, published by Springer 2009. Amazingly enough, on page 336 it says: The Knight distance... is 3 if (M,m)=(1,0); is 4 if (M,m)=(2,2); otherwise equals max( ceiling(M/2), ceiling((M+m)/3)) + (M+m) - max(ceiling(M/2), ceiling(((M+m)/3)) mod 2 where M>=m>=0. They then define a "(p,q) super knight" or "(p,q)-leaper" which leaps p squares in x or y direction the q squares in orthogonal direction; the usual knight is a (2,1) leaper. For various (p,q) these have been called "Wazir, Ferz, camel, giraffe"... They then say the metric for this has been studied by PP Das & J Mukherjee: Pattern Recognition Letters 11 (1990) 601-604.

2 2

Re: [math-fun] sketched proof of Knight distance formula
by Warren D Smith 12 Apr '14

12 Apr '14

A lower bound on shortest path count of the form polynomial(d) * central binomial coeff may be proved not only for the along-diagonal shortest N-paths at (3k+1, 3k+1), but also for the along axis cases at (4k-1,0). My technique is, essentially, you use the usual minimal path to reach (3k,3k) and (4k,0) plus add one "zig" and one "zag" -- plus in the (4k-1,0) case remove an edge -- so it now reaches (3k+1,3k+1) and (4k-1,0) and still is shortest. The number of ways to insert the zig and the zag, grows quadratically in both the (4k-1,0) and (3k+1,3k+1) cases. In the (4k-1,0) case we also get to remove one edge, which can be done in a linear number of ways. As a result, the shortest path count in this along-axis case indeed wins asymptotically, overwhelming the diagonal case and refuting my flaky conjecture: It grows like a CUBIC times central binomial coefficient, whereas the along-diagonal growth was only QUADRATIC times c.b.c. One should be able to work out exact formulas, or at least more precise lower bounds, for these maximal counts.

5 5

[math-fun] bit-reversal for words of length 3^k, and a hundred E-bucks
by Joerg Arndt 12 Apr '14

12 Apr '14

Before I forget about it: The usual technique is - swapping pairs of single bits - swapping pairs of two bits - swapping pairs of four bits etc. til end. For words of length 3, one just has to swap the first and last bit. For words of length 3, one can do as just said for the length-3 sub-words then swap the first and last runs of 3 bits. Etc., 3^k bits reversed in k steps! Naively doing this with words of length not of the form 3^k leads to deletion of initial ones, BAD! Now one has to truncate masks to avoid losing ones. When you look into it, there is a truly huge amount of possible ways to do the task. Here is a way of reversing words of 2^k-1 bits: 1 bit: nop 3 bits: swap first and last 7 bits: as before for first and last 3 bits (one bits stays in the middle), then swap first and runs of 3 bits. 2^(k+1)-1 bits: as 2^k-1 for the first and last 2^k-1 bits, (one bits stays in the middle), then swap first and runs of 2^k-1 bits. Doing better is (for me, so far) a matter of creativity, the neat routine I gave for 64 bits uses the fact that 64 - 1 is divisible by 9. Here is a strategy for a (slightly different) routine, just as fine as the one I have given: Split the 63 low bits as [27][9][27] <--= [b] means "run of b bits" now use the 3^k idea to reverse all runs of 9 bits (two steps). At the next step, the two runs of 27 are completed (the middle run has to be left alone). At the last step, swap the two 27-bit runs. Done in four steps, or five for 64 bits with just an additional rotation by one. I didn't manage to find anything for 32 bits (neither 31 bits) better than this. I offer 100 Euro for a routine for 32 bits (or 31, your choice) that uses one op less than my routine for 64 (or 63 when you pick 31 above). Best, jj

1 1

[math-fun] knight distance formula (review)
by Warren D Smith 12 Apr '14

12 Apr '14

> I've kind of lost track of this thread. > What exactly is the "Knight distance formula" to be proved? --As C code, where dx=|x1-x2|, dy=|y1-y2|, bi-infinite chess board WDS's algorithm: Ki = max(dx,dy); L1 = dx+dy; if(Ki<3){ //handle exceptional cases where my formula fails if(L1==1){ return(3); } if(L1==4){ return(4); } //omit next line if bi-infinite chessboard: if( (InCorner(a) || InCorner(b)) && dx==1 && dy==1 ){ return(4); } } if(L1 & 1){ //different square colors, so KnightDist=odd F = ( 4+max(2*L1, 3*Ki) ) / 12; F *= 2; F++; //divide rounds downward }else{ //KnightDist=even F = ( 10+max(2*L1, 3*Ki) ) / 12; F *= 2; //divide rounds downward } return(F); Lunnon's equivalent algorithm: if(dx<dy){ X=dy; Y=dx; }else{ X=dx; Y=dy; } if(X<=2){ if(X==1 && Y==0){ return(3); } if(X==2 && Y==2){ return(4); } //omit next line if bi-infinite chessboard: if( (InCorner(a) || InCorner(b)) && X==1 && Y==1 ){ return(4); } } p = X-Y; q = p-Y; if(q<0){ return( p + 2*( (q%3!=0) - q/3 ) ); } return( p - 2*(q/4) ); In both cases the returned value is the minimum number of knight moves needed to reach (x2,y2) starting from (x1,y1). Current status: WDS produced a proof sketch unfortunately depending on a large but simple brute force computation. Lunnon produced a large number of incorrect proofs but now claims to have produced a valid proof which does not need any computer. But WDS still does not agree Lunnon's proof valid. Lunnon & WDS also interested in certain other questions about knight distance, such as how many shortest paths there are, but the validity of these formulas is foundational and needed before we can discuss all those other questions.

1 0

Re: [math-fun] sketched proof of Knight distance formula
by Adam P. Goucher 12 Apr '14

12 Apr '14

This formula works: kd = Function[{ox, oy}, Module[{x = Max[Abs[ox], Abs[oy]], y = Min[Abs[ox], Abs[oy]], p = 0}, p = If[3 x < 2 (x + y), (x + y + 1)/3, (x + 1)/2]; If[Mod[x + y, 2] == 0, p = 2 Floor[(p + 1)/2], p = 2 Floor[p/2] + 1]; If[x == 1 && y == 0, p = 3]; If[x == 2 && y == 2, p = 4]; p]]; Proof: It suffices to verify that kd[0, 0] = 0 and kd[x, y] = 1 + Min[kd[x + 1, y + 2], kd[x + 2, y + 1], ..., kd[x - 2, y - 1]], in which case we are done by induction on the value of kd[x, y]. Both of these are absolutely trivial to verify, although the latter is a messy case-bash (having to special-case squares near the lines 2|x| = |y| and 2|y| = |x|). Sincerely, Adam P. Goucher > ----- Original Message ----- > From: Dan Asimov > Sent: 04/12/14 02:54 PM > To: math-fun > Subject: Re: [math-fun] sketched proof of Knight distance formula > > Let f(K,L) := the smallest number of knight moves {(+-2,+-1),(+-1,+-2)} it takes to get from square (0,0) to square (K,L) on an infinite chessboard. > > WLOG assume K,L > 0. > > Then find an explicit way to express f(K,L), and prove its correctness. > > --Dan > > > On Apr 12, 2014, at 6:18 AM, David Wilson <davidwwilson(a)comcast.net> wrote: > > > I've kind of lost track of this thread. > > What exactly is the "Knight distance formula" to be proved? > > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

[math-fun] knight distance
by Warren D Smith 12 Apr '14

12 Apr '14

As I remarked to Lunnon in email, I still do not accept that he has proved the N-distance formula. Despite him seeming to think he has. But anyhow, I believe the "brute force proof" I sketched does work. Another comment is that, apparently, the shortest path from (0,0) to (x,y) is unique if and only if (x,y) is an integer multiple of (+-1,+-2) or (+-2, +-1). Otherwise, at least 2 paths exist, and if KnightDist>2 then at least 3 exist. Indeed the number of shortest paths (whenever non-unique) appears to be lower bounded by some linearly-growing function of the distance, and this seems tight because NumberOfShortestPaths( 2 + 2*k, k-1 ) = k+1 = KnightDist(2+2*k, k-1) for each k>=0. On the other hand, exponential growth is possible as demonstrated by NumberOfShortestPaths( 3*n, 3*n ) = (2*n)!/(n!)^2 for each n>=0 as one can prove by explicit construction of all paths. Here KnightDist(3*n, 3*n) = 2*n. This grows exponentially with ultimate growth ratio 2 as a function of distance d. It naively appears as though NumberOfShortestPaths( 3*n+1, 3*n+1 ) grows faster, but you can easily prove it ultimately also grows exponentially also with growth factor (in the limit) 2. It is however lower bounded by (2*n+2)*(2*n+1)*(2*n)!/(n!)^2 as I can show by explicit construction of that many paths. Here KnightDist(3*n+1, 3*n+1) = 2*n+2. I conjecture (without great confidence) that this formula is the maximum possible to within a constant factor. If you do not want to take some path, then the next-higher-distance is always 2 greater because of parity. In consequence the "NonUniqueKnightDistance" function, giving the shortest distance in knight moves if your first-choice path is rejected, is equal to the usual KnightDist function, except when (x,y) is an integer multiple of (+-1,+-2) or (+-2, +-1), in which cases add 2 hops.

2 1

[math-fun] [EXTERNAL] Re: Nines in Pi
by Bill Gosper 12 Apr '14

12 Apr '14

-------- Original Message -------- Subject: Re: [math-fun] [EXTERNAL] Re: Nines in Pi Date: 2014-04-11 16:36 From: "Schroeppel, Richard" <rschroe(a)sandia.gov> To: math-fun <math-fun(a)mailman.xmission.com> Cc: "rcs(a)xmission.com" <rcs(a)xmission.com>, "Schroeppel, Richard" < rschroe(a)sandia.gov> Reply-To: math-fun <math-fun(a)mailman.xmission.com> IIRC, the definition of "irrationality measure" M for X uses the expression | X - n/d | > 1/d^M except for a finite number of ds. So the digits n through 7.61n (of pi) can't be all 9s (or all 0s), with only a finite number of exceptional n. <RCS So there are still probably millions of cases of a million 9s in a row. Man, we don't know anything. --rwg RCS>At a symbolic math conference in NYC ~1985, the Chudnovsky's offered a good result for pi^2, perhaps 6 or 7, and remarked that that implied a less good result for pi, perhaps 12-14. Note that the ordinary continued fraction algorithm gives an infinite stream of d when M=2, for any irrational X. So we'd need something a little stronger to address Jim's original question. And (Thue-Seigel-)Roth says that M<2+epsilon for (irrational, real) algebraic X. Rich ________________________________________ From: math-fun-bounces(a)mailman.xmission.com [ math-fun-bounces(a)mailman.xmission.com] on behalf of Michael Kleber [ michael.kleber(a)gmail.com] Sent: Thursday, March 20, 2014 8:20 AM To: math-fun Subject: [EXTERNAL] Re: [math-fun] Nines in Pi The irrationality measure of pi is at most 7.6063 [Salikhov, "On the Irrationality Measure of $\pi$", 2008]. I think that translates into "There are at most finitely many n for which digits n through k*n are all 9's" for some k, but I don't know what k is. But none of this answers Jim's / Dick's question (whose answer is surely "it never happens but we don't have a proof"). --Michael On Thu, Mar 20, 2014 at 9:34 AM, James Propp <jamespropp(a)gmail.com> wrote: > Is it possible that for some n, the n+1st through 2nth digits of pi are all > 9's? > > Dick Hess just gave a wonderful G4G talk which raised this issue. > > Jim > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > -- Forewarned is worth an octopus in the bush.

1 0

[math-fun] Nines in Pi
by James Propp 11 Apr '14

11 Apr '14

Is it possible that for some n, the n+1st through 2nth digits of pi are all 9's? Dick Hess just gave a wonderful G4G talk which raised this issue. Jim

5 4