[math-fun] Knight-distance metric in chess
Consider a bi-infinite chessboard (Z^2). What is the distance between (x1,y1) and (x2,y2) measured in number of knight-moves? [Incidentally, for a finite hXw chessboard, if min(h,w)>3 the bi-infinite and finite board exhibit the same distances in all cases except if the two squares are the corner of the board and diagonally adjacent to it, in which case the finite board has distance=4 while the bi-infinite board distance is 2.] After some fiddling, I came up with the following CONJECTURE: Define dx = |x1-x2|, dy = |y1-y2|, L1distance = dx + dy, KingDistance = max(dx, dy) F = ( max(2*L1distance, 3*KingDistance) + 4 ) / 6 Then KnightDistance = F rounded to the nearest eligible integer of the correct parity (correct parity: even if source and destination same-colored squares, otherwise odd) (eligible: must be non-negative, and if the two squares differ then must be positive) except for this list: (dx,dy) KnightDistance Formula (1,0) or (0,1) 3 1 (2,2) 4 2 (7,7) 4 6 in which my formula is off by 2. Are there any other exceptions? -- Warren D. Smith http://RangeVoting.org
="Warren D Smith" <warren.wds@gmail.com> What is the distance between (x1,y1) and (x2,y2) measured in number of knight-moves?
Warren, some years ago I put some "knight metric" sequences in the OEIS. Special-cases to compare with your conjecture: dx,dy =... ...n,0: http://oeis.org/A018837 2[ (n+2)/4 ] if n even, 2[ (n+1)/4 ]+1 if n odd (n >= 8) ...n,n: http://oeis.org/A018839 2*ceiling(n/3), n >= 3 Also perhaps of interest is the size of the n-move neighborhood, etc. The OEIS has some references as well. Search on "knight" gives many hits. "Enjoy"! --MLB
On Fri, Mar 28, 2014 at 1:16 PM, Marc LeBrun <mlb@well.com> wrote:
="Warren D Smith" <warren.wds@gmail.com> What is the distance between (x1,y1) and (x2,y2) measured in number of knight-moves?
Warren, some years ago I put some "knight metric" sequences in the OEIS. Special-cases to compare with your conjecture: dx,dy =...
...n,0: http://oeis.org/A018837 2[ (n+2)/4 ] if n even, 2[ (n+1)/4 ]+1 if n odd (n >= 8)
...n,n: http://oeis.org/A018839 2*ceiling(n/3), n >= 3
When I follow that link, I don't get knight distance to (n,n); I get a series purporting to be the series for Squares on infinite chess-board at n moves from center using a {2,3} fairy knight. But this sequence is incorrect; it claims that the answer is For n >= 8, a(n) = 68n - 72. But that can't be right; you can reach any square within distance n by first going to an appropriate square in a (2,6) neighborhood of the initial square, and then zigzagging to the right to get to a square from which you can get to the desired square in a straight line. Each part of this procedure takes a number of steps linear in n, so the total number of squares at n moves from the center must be of order n^2. Andy
Also perhaps of interest is the size of the n-move neighborhood, etc. The OEIS has some references as well. Search on "knight" gives many hits.
"Enjoy"! --MLB
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
The sequence is for squares at exactly that distance, not squares reachable in that distance or less. Thus, it should increase as order n, not n^2. On Fri, Mar 28, 2014 at 11:20 AM, Andy Latto <andy.latto@pobox.com> wrote:
On Fri, Mar 28, 2014 at 1:16 PM, Marc LeBrun <mlb@well.com> wrote:
="Warren D Smith" <warren.wds@gmail.com> What is the distance between (x1,y1) and (x2,y2) measured in number of knight-moves?
Warren, some years ago I put some "knight metric" sequences in the OEIS. Special-cases to compare with your conjecture: dx,dy =...
...n,0: http://oeis.org/A018837 2[ (n+2)/4 ] if n even, 2[ (n+1)/4 ]+1 if n odd (n >= 8)
...n,n: http://oeis.org/A018839 2*ceiling(n/3), n >= 3
When I follow that link, I don't get knight distance to (n,n); I get a series purporting to be the series for
Squares on infinite chess-board at n moves from center using a {2,3} fairy knight.
But this sequence is incorrect; it claims that the answer is For n >= 8, a(n) = 68n - 72. But that can't be right; you can reach any square within distance n by first going to an appropriate square in a (2,6) neighborhood of the initial square, and then zigzagging to the right to get to a square from which you can get to the desired square in a straight line. Each part of this procedure takes a number of steps linear in n, so the total number of squares at n moves from the center must be of order n^2.
Andy
Also perhaps of interest is the size of the n-move neighborhood, etc. The OEIS has some references as well. Search on "knight" gives many hits.
"Enjoy"! --MLB
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
On Fri, Mar 28, 2014 at 2:58 PM, Tom Rokicki <rokicki@gmail.com> wrote:
The sequence is for squares at exactly that distance, not squares reachable in that distance or less. Thus, it should increase as order n, not n^2.
oops, sorry! I should read more carefully. Andy
On Fri, Mar 28, 2014 at 11:20 AM, Andy Latto <andy.latto@pobox.com> wrote:
On Fri, Mar 28, 2014 at 1:16 PM, Marc LeBrun <mlb@well.com> wrote:
="Warren D Smith" <warren.wds@gmail.com> What is the distance between (x1,y1) and (x2,y2) measured in number of knight-moves?
Warren, some years ago I put some "knight metric" sequences in the OEIS. Special-cases to compare with your conjecture: dx,dy =...
...n,0: http://oeis.org/A018837 2[ (n+2)/4 ] if n even, 2[ (n+1)/4 ]+1 if n odd (n >= 8)
...n,n: http://oeis.org/A018839 2*ceiling(n/3), n >= 3
When I follow that link, I don't get knight distance to (n,n); I get a series purporting to be the series for
Squares on infinite chess-board at n moves from center using a {2,3} fairy knight.
But this sequence is incorrect; it claims that the answer is For n >= 8, a(n) = 68n - 72. But that can't be right; you can reach any square within distance n by first going to an appropriate square in a (2,6) neighborhood of the initial square, and then zigzagging to the right to get to a square from which you can get to the desired square in a straight line. Each part of this procedure takes a number of steps linear in n, so the total number of squares at n moves from the center must be of order n^2.
Andy
Also perhaps of interest is the size of the n-move neighborhood, etc. The OEIS has some references as well. Search on "knight" gives many hits.
"Enjoy"! --MLB
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
I searched for this topic on the web, and found remarkably little. Amanda M. Miller, David L. Farnsworth "Counting the Number of Squares Reachable in k Knight's Moves" Open Journal of Discrete Mathematics, 2013, 3, 151-154 http://dx.doi.org/10.4236/ojdm.2013.33027 does what it says on the tin, but disappointingly avoids any attempt at an explicit distance function. http://www.chessbanter.com/rec-games-chess-misc-chess/30866-counting-knight-... --- one of four strangely similar posts --- puffs to almost universal disdain << Fortunately, there's a better way. I'm a fan of obscure chess books, so when I was at a local chess store the other day, the book "Knight Moves" by Charles Alexander caught my eye. In it he describes a relatively simple method, which he calls "Alexander's Technique", to count the minimum number of knight moves it would take a knight to move from any given square to any other square. >> Said tome apparently manages to devote 80 pages to this delicate investigation. http://math.stackexchange.com/questions/104700/minimum-number-of-moves-to-re... is frankly feeble. http://stackoverflow.com/questions/2339101/knights-shortest-path-chess-quest... finally turns up something nontrivial: << Note: This question was asked on SACO 2007 Day 1 http://olympiad.cs.uct.ac.za/old/saco2007/day1_2007.pdf And solutions are here http://olympiad.cs.uct.ac.za/old/saco2007/day1_2007_solutions.pdf >> The problem appears as no. 4 on day 1 of the 2007 SA Mathematical Olympiad, posed by one Harry Wiggins. The proposed solution is not explicitly credited, but might well have been prepared by Tommy Cooper --- its "magic formula" transports the knight from [0,0] to [1,1] in zero moves, by way of one of three errors shoehorned into just two lines! Well, if you want a job done properly, do it yourself. A corrected and tested revision of Wiggins' prestidigitation, together with --- in answer to the enquiry from Warren Smith --- a proof of correctness, will follow in a separate post. Magma program is available on request. Fred Lunnon On 3/28/14, Andy Latto <andy.latto@pobox.com> wrote:
On Fri, Mar 28, 2014 at 2:58 PM, Tom Rokicki <rokicki@gmail.com> wrote:
The sequence is for squares at exactly that distance, not squares reachable in that distance or less. Thus, it should increase as order n, not n^2.
oops, sorry! I should read more carefully.
Andy
On Fri, Mar 28, 2014 at 11:20 AM, Andy Latto <andy.latto@pobox.com> wrote:
On Fri, Mar 28, 2014 at 1:16 PM, Marc LeBrun <mlb@well.com> wrote:
="Warren D Smith" <warren.wds@gmail.com> What is the distance between (x1,y1) and (x2,y2) measured in number of knight-moves?
Warren, some years ago I put some "knight metric" sequences in the OEIS. Special-cases to compare with your conjecture: dx,dy =...
...n,0: http://oeis.org/A018837 2[ (n+2)/4 ] if n even, 2[ (n+1)/4 ]+1 if n odd (n >= 8)
...n,n: http://oeis.org/A018839 2*ceiling(n/3), n >= 3
When I follow that link, I don't get knight distance to (n,n); I get a series purporting to be the series for
Squares on infinite chess-board at n moves from center using a {2,3} fairy knight.
But this sequence is incorrect; it claims that the answer is For n >= 8, a(n) = 68n - 72. But that can't be right; you can reach any square within distance n by first going to an appropriate square in a (2,6) neighborhood of the initial square, and then zigzagging to the right to get to a square from which you can get to the desired square in a straight line. Each part of this procedure takes a number of steps linear in n, so the total number of squares at n moves from the center must be of order n^2.
Andy
Also perhaps of interest is the size of the n-move neighborhood, etc. The OEIS has some references as well. Search on "knight" gives many hits.
"Enjoy"! --MLB
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
//////////////////////////////////////////////////////////////////////////////// Knight's Move Distance Function _______________________________ *Define* [X, Y] := [|x|, |y|] if |x| >= |y| , := [|y|, |x|] otherwise; p := X-Y; q := p-Y; r := 3 if q < 0 , := 4 otherwise; f(x, y) := 3 if [X, Y] = [1, 0] , := 4 if [X, Y] = [2, 2] , := p - 2*Floor(q/r) otherwise; *Lemma* For f(x, y) > 4 in the first octant x >= y >= 0 , f(x, y) = f(x-2, y-1) + 1 . Proof: Note [x', y'] = [x-2, y-1] lies also in the first octant unless x = y . Then correspondingly p' = p-1 , q' = q , r' = r , and via definition f' = f-1 . QED *Theorem* Denoting by d(x, y) knight's move distance from [0, 0] , d(x, y) = f(x, y) . Proof: via symmetry, need consider only the first octant. For f(x, y) > 4 by induction on f : d(x, y) <= d(x-2, y-1) + 1 via definition, = f(x-2, y-1) + 1 via hypothesis, = f(x, y) via lemma; but d(x, y) > f(x-2, y-1) via hypothesis, therefore d(x, y) = f(x, y) . For f(x, y) <= 4 : by inspection of table below, showing d(x, y) = f(x, y) for 0 <= x,y <= 8 . [0 3 2 3 2 3 4 5 4] [3 2 1 2 3 4 3 4 5] [2 1 4 3 2 3 4 5 4] [3 2 3 2 3 4 3 4 5] [2 3 2 3 4 3 4 5 4] [3 4 3 4 3 4 5 4 5] [4 3 4 3 4 5 4 5 6] [5 4 5 4 5 4 5 6 5] [4 5 4 5 4 5 6 5 6] QED *Remark* Above, cell [0, 0] is assumed to lie at board centre; if instead it lay at top left corner, the definition would require another special case: f(x, y) := 4 if [X, Y] = [1, 1] . *Geometry* Cells [x, y] lying at distance c = d(x, y) > 4 form an octagonal annulus, with straight sides comprising four aligned with rook moves (q >= 0 above), and isomorphic to { [x,y] | 3c-4 <= x+y <= 3c & c < x < 2c & x+y = c (mod 2) } ; and four with bishop moves (q < 0 above), isomorphic to { [x,y] | c <= y-x & c <= y+x & 2c-3 <= y <= 2c & x+y = c (mod 2) } . Neglecting cells not having the same parity x+y = c (mod 2) , each annulus disconnects the remainder into regions at distance <= c-2 and >= c+2 respectively. The induction then becomes visually obvious. Fred Lunnon, Maynooth 01/04/14 ////////////////////////////////////////////////////////////////////////////////
In[44]:= Abs[FractionalPart[Exp[Pi*Sqrt[163]]] - 1/2] 525074825281537487 Sqrt[163] Pi Out[44]= -(------------------) + E 2 In[45]:= N[%,17] Out[45]= 0.49999999999925007 In[46]:= Abs[FractionalPart[Exp[Pi*Sqrt[163]]] - 1/2] > .49 Out[46]= False Explanations welcomed. --Dan
Comparison with .49, like N without a second parameter, just uses "machine precision" to evaluate. Since you're playing with values where machine precision doesn't even reach the decimal point, you'll get much worse results than even N[_,0]. In[1]:= x = Abs[FractionalPart[Exp[Pi*Sqrt[163]]] - 1/2]; In[2]:= N[x] Out[2]= -480. In[3]:= N[x,0] Out[3]= 0. In[4]:= N[x,1] Out[4]= 0.5 --Michael On Tue, Apr 1, 2014 at 3:49 PM, Dan Asimov <dasimov@earthlink.net> wrote:
In[44]:= Abs[FractionalPart[Exp[Pi*Sqrt[163]]] - 1/2]
525074825281537487 Sqrt[163] Pi Out[44]= -(------------------) + E 2
In[45]:= N[%,17]
Out[45]= 0.49999999999925007
In[46]:= Abs[FractionalPart[Exp[Pi*Sqrt[163]]] - 1/2] > .49
Out[46]= False
Explanations welcomed.
--Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
OK, I decided to acquiesce to Mathematica's ridiculous demands. (Why should you have to apply AccountingForm[] just to get a number in standard decimal format?) But gripes aside, appended are the numbers N (other than 1237, 1249, 1256, which it seemed to choke on), 1 <= N <= 2000, for which exp(pi*sqrt(N)) is within .01 of an integer. Besides the mysterious number theory explanations for why some are so very close, it's also puzzling why so many more of these are just above an integer than just below one. --Dan ------------------------------------------------------------------------------ In[52]:= g[n_] := Exp[Pi*Sqrt[n]] In[53]:= K[max_] := For[n=1,n<=max,n=n+1,If[N[Abs[FractionalPart[g[n]]-1/2],3] > .49, Print[n," -> ", AccountingForm[N[g[n],70]]], Null]] In[54]:= K[2000] 17 -> 422150.9976756804516223118279935465573938998932276160355506282041005362 18 -> 614551.9928856196354139298276299092637721589143090195364477936836190191 22 -> 2508951.998257424467165529194121687162476410734868206435729660830423741 25 -> 6635623.999341134233266264067099104921836106934150987203247166936354241 37 -> 199148647.9999780465518567665009238753359004336658664318323947056203771 43 -> 884736743.9997774660349066619374620785853768473991271391609175146278345 58 -> 24591257751.99999982221324146957619235526581222761017107146978074727952 59 -> 30197683486.99318226092820317456691819659501730074805447587158906382489 67 -> 147197952743.9999986624542245068292613125786285081833125038167126333713 74 -> 545518122089.9991746788535498566430173362368690907009069646240495704728 103 -> 70292286279654.00194128887588078323607339804118079323350802547781482432 148 -> 39660184000219160.00096667435857524642577260262167893454080881851324518 149 -> 45116546012289599.99183028700036243820106838306889700225231435049418180 163 -> 262537412640768743.9999999999992500725971981856888793538563373369908627 164 -> 296853791705948489.0026726248354647230571999609920977505604998845455156 177 -> 1418556986635586485.996179355249780456304054322609687324822525165865396 205 -> 34268610654606782799.00302588709819877957417711509991955739178349255586 223 -> 236855705574162154847.0034451037730456731334687474109472878887472801644 226 -> 324394960614997599147.0065272185438674490961889863263111309144075035267 232 -> 604729957825300084759.9999921715268564302785946808125512858845316413892 267 -> 19683091854079461001445.99273704076983901658449709887562598444136513736 268 -> 21667237292024856735768.00029203884241295945428349129791564877323635540 326 -> 4309793301730386363005719.996011651626851524869273743200857493473875733 386 -> 639355180631208421212174016.9976698325078231117287843106768301634122745 522 -> 14871070263238043663567627879007.99984872648279481477388379523706422285 566 -> 288099755064053264917867975825573.9938983115610667783462631133127007347 638 -> 28994858898043231996779771804797161.99237293954516048470864023572454327 652 -> 68925893036109279891085639286943768.00000000016373864420923460757232906 719 -> 3842614373539548891490294277805829192.999987249566012187563270183657068 790 -> 223070667213077889794379623183838336437.9920551177281967668330417762103 792 -> 249433117287892229255125388685911710805.9960973230079997367491007072130 928 -> 365698321891389219219142531076638716362775.9982597470174543148220891454 940 -> 677621063891416076248230276783145121158916.0018892548309602322004898534 986 -> 6954830200814801770418837940281460320666108.994649611250605331131122063 1005 -> 17910081680940580833529050259595126076784743.00652422098176402344384390 1169 -> 44555719382988281777368496770130045948309444044.99996080286386846150243 1194 -> 139661526073504116557581973059759277212070858620.0003900603188035532686 1213 -> 330144200785402970319166028643329915082011865217.0064534054200532543561 N::meprec: Internal precision limit $MaxExtraPrecision = 50. reached while evaluating -( 1938766283555706196415301648109962894754207498417 Sqrt[1237] Pi -------------------------------------------------) + E . 2 1245 -> 1384892132296689864688150528414254481739817624464.999423621295089731039 N::meprec: Internal precision limit $MaxExtraPrecision = 50. reached while evaluating -( 3309173472789647250136240543502288628041647543181 Sqrt[1249] Pi -------------------------------------------------) + E . 2 N::meprec: Internal precision limit $MaxExtraPrecision = 50. reached while evaluating -( 4514931544489018513609201179433753739448459339035 2 Sqrt[314] Pi -------------------------------------------------) + E . 2 General::stop: Further output of N::meprec will be suppressed during this calculation. 1257 -> 2359752187588332572926453870820027357203549890449.993034752664193580926 1293 -> 11499177736948672237714068560631910541735301233989.99496136788442126388 1326 -> 48171098188871186483096169726268818132470483648300.99134484794080091307 1332 -> 62382700950473563258623210672143849649476315193453.00092102414610595950 1467 -> 18095625621654510801615355531263454706630064771074975.99999999012369367 1556 -> 659805499174190199819286657618770540166630302112791359.9959424231045979 1850 -> 48310987197300327887464627364483701432184761367510399635913.99985950299 1872 -> 107633344087088750110483164611005972787304802294303445731718.9992468149 1960 -> 2532305471868198233465298022928017175581855191972722719356926.993687927
On Tue, Apr 1, 2014 at 2:27 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Besides the mysterious number theory explanations for why some are so very close, it's also puzzling why so many more of these are just above an integer than just below one.
653 = 163*4, so it's no surprise that it's so close; we also expect 2/100 to be within .01 by chance. How many of these are due to Heegner numbers? -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
See http://oeis.org/A019296. And why did you miss 6? On Tue, Apr 1, 2014 at 4:27 PM, Dan Asimov <dasimov@earthlink.net> wrote:
OK, I decided to acquiesce to Mathematica's ridiculous demands. (Why should you have to apply AccountingForm[] just to get a number in standard decimal format?)
But gripes aside, appended are the numbers N (other than 1237, 1249, 1256, which it seemed to choke on), 1 <= N <= 2000, for which exp(pi*sqrt(N)) is within .01 of an integer. Besides the mysterious number theory explanations for why some are so very close, it's also puzzling why so many more of these are just above an integer than just below one.
--Dan
------------------------------------------------------------------------------
In[52]:= g[n_] := Exp[Pi*Sqrt[n]]
In[53]:= K[max_] := For[n=1,n<=max,n=n+1,If[N[Abs[FractionalPart[g[n]]-1/2],3] > .49, Print[n," -> ", AccountingForm[N[g[n],70]]], Null]]
In[54]:= K[2000] 17 -> 422150.9976756804516223118279935465573938998932276160355506282041005362 18 -> 614551.9928856196354139298276299092637721589143090195364477936836190191 22 -> 2508951.998257424467165529194121687162476410734868206435729660830423741 25 -> 6635623.999341134233266264067099104921836106934150987203247166936354241 37 -> 199148647.9999780465518567665009238753359004336658664318323947056203771 43 -> 884736743.9997774660349066619374620785853768473991271391609175146278345 58 -> 24591257751.99999982221324146957619235526581222761017107146978074727952 59 -> 30197683486.99318226092820317456691819659501730074805447587158906382489 67 -> 147197952743.9999986624542245068292613125786285081833125038167126333713 74 -> 545518122089.9991746788535498566430173362368690907009069646240495704728 103 -> 70292286279654.00194128887588078323607339804118079323350802547781482432 148 -> 39660184000219160.00096667435857524642577260262167893454080881851324518 149 -> 45116546012289599.99183028700036243820106838306889700225231435049418180 163 -> 262537412640768743.9999999999992500725971981856888793538563373369908627 164 -> 296853791705948489.0026726248354647230571999609920977505604998845455156 177 -> 1418556986635586485.996179355249780456304054322609687324822525165865396 205 -> 34268610654606782799.00302588709819877957417711509991955739178349255586 223 -> 236855705574162154847.0034451037730456731334687474109472878887472801644 226 -> 324394960614997599147.0065272185438674490961889863263111309144075035267 232 -> 604729957825300084759.9999921715268564302785946808125512858845316413892 267 -> 19683091854079461001445.99273704076983901658449709887562598444136513736 268 -> 21667237292024856735768.00029203884241295945428349129791564877323635540 326 -> 4309793301730386363005719.996011651626851524869273743200857493473875733 386 -> 639355180631208421212174016.9976698325078231117287843106768301634122745 522 -> 14871070263238043663567627879007.99984872648279481477388379523706422285 566 -> 288099755064053264917867975825573.9938983115610667783462631133127007347 638 -> 28994858898043231996779771804797161.99237293954516048470864023572454327 652 -> 68925893036109279891085639286943768.00000000016373864420923460757232906 719 -> 3842614373539548891490294277805829192.999987249566012187563270183657068 790 -> 223070667213077889794379623183838336437.9920551177281967668330417762103 792 -> 249433117287892229255125388685911710805.9960973230079997367491007072130 928 -> 365698321891389219219142531076638716362775.9982597470174543148220891454 940 -> 677621063891416076248230276783145121158916.0018892548309602322004898534 986 -> 6954830200814801770418837940281460320666108.994649611250605331131122063 1005 -> 17910081680940580833529050259595126076784743.00652422098176402344384390 1169 -> 44555719382988281777368496770130045948309444044.99996080286386846150243 1194 -> 139661526073504116557581973059759277212070858620.0003900603188035532686 1213 -> 330144200785402970319166028643329915082011865217.0064534054200532543561
N::meprec: Internal precision limit $MaxExtraPrecision = 50. reached while evaluating -( 1938766283555706196415301648109962894754207498417 Sqrt[1237] Pi -------------------------------------------------) + E . 2 1245 -> 1384892132296689864688150528414254481739817624464.999423621295089731039
N::meprec: Internal precision limit $MaxExtraPrecision = 50. reached while evaluating -( 3309173472789647250136240543502288628041647543181 Sqrt[1249] Pi -------------------------------------------------) + E . 2
N::meprec: Internal precision limit $MaxExtraPrecision = 50. reached while evaluating -( 4514931544489018513609201179433753739448459339035 2 Sqrt[314] Pi -------------------------------------------------) + E . 2
General::stop: Further output of N::meprec will be suppressed during this calculation. 1257 -> 2359752187588332572926453870820027357203549890449.993034752664193580926 1293 -> 11499177736948672237714068560631910541735301233989.99496136788442126388 1326 -> 48171098188871186483096169726268818132470483648300.99134484794080091307 1332 -> 62382700950473563258623210672143849649476315193453.00092102414610595950 1467 -> 18095625621654510801615355531263454706630064771074975.99999999012369367 1556 -> 659805499174190199819286657618770540166630302112791359.9959424231045979 1850 -> 48310987197300327887464627364483701432184761367510399635913.99985950299 1872 -> 107633344087088750110483164611005972787304802294303445731718.9992468149 1960 -> 2532305471868198233465298022928017175581855191972722719356926.993687927
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
This is almost exactly http://oeis.org/A019296, although that one starts with -1, 0, 6, 17, etc. None of the three numbers on which Mathematic chokes are on the list. The last four terms are not on the OEIS. Cheers, Seb On 1 April 2014 22:27, Dan Asimov <dasimov@earthlink.net> wrote:
OK, I decided to acquiesce to Mathematica's ridiculous demands. (Why should you have to apply AccountingForm[] just to get a number in standard decimal format?)
But gripes aside, appended are the numbers N (other than 1237, 1249, 1256, which it seemed to choke on), 1 <= N <= 2000, for which exp(pi*sqrt(N)) is within .01 of an integer. Besides the mysterious number theory explanations for why some are so very close, it's also puzzling why so many more of these are just above an integer than just below one.
--Dan
------------------------------------------------------------------------------
In[52]:= g[n_] := Exp[Pi*Sqrt[n]]
In[53]:= K[max_] := For[n=1,n<=max,n=n+1,If[N[Abs[FractionalPart[g[n]]-1/2],3] > .49, Print[n," -> ", AccountingForm[N[g[n],70]]], Null]]
In[54]:= K[2000] 17 -> 422150.9976756804516223118279935465573938998932276160355506282041005362 18 -> 614551.9928856196354139298276299092637721589143090195364477936836190191 22 -> 2508951.998257424467165529194121687162476410734868206435729660830423741 25 -> 6635623.999341134233266264067099104921836106934150987203247166936354241 37 -> 199148647.9999780465518567665009238753359004336658664318323947056203771 43 -> 884736743.9997774660349066619374620785853768473991271391609175146278345 58 -> 24591257751.99999982221324146957619235526581222761017107146978074727952 59 -> 30197683486.99318226092820317456691819659501730074805447587158906382489 67 -> 147197952743.9999986624542245068292613125786285081833125038167126333713 74 -> 545518122089.9991746788535498566430173362368690907009069646240495704728 103 -> 70292286279654.00194128887588078323607339804118079323350802547781482432 148 -> 39660184000219160.00096667435857524642577260262167893454080881851324518 149 -> 45116546012289599.99183028700036243820106838306889700225231435049418180 163 -> 262537412640768743.9999999999992500725971981856888793538563373369908627 164 -> 296853791705948489.0026726248354647230571999609920977505604998845455156 177 -> 1418556986635586485.996179355249780456304054322609687324822525165865396 205 -> 34268610654606782799.00302588709819877957417711509991955739178349255586 223 -> 236855705574162154847.0034451037730456731334687474109472878887472801644 226 -> 324394960614997599147.0065272185438674490961889863263111309144075035267 232 -> 604729957825300084759.9999921715268564302785946808125512858845316413892 267 -> 19683091854079461001445.99273704076983901658449709887562598444136513736 268 -> 21667237292024856735768.00029203884241295945428349129791564877323635540 326 -> 4309793301730386363005719.996011651626851524869273743200857493473875733 386 -> 639355180631208421212174016.9976698325078231117287843106768301634122745 522 -> 14871070263238043663567627879007.99984872648279481477388379523706422285 566 -> 288099755064053264917867975825573.9938983115610667783462631133127007347 638 -> 28994858898043231996779771804797161.99237293954516048470864023572454327 652 -> 68925893036109279891085639286943768.00000000016373864420923460757232906 719 -> 3842614373539548891490294277805829192.999987249566012187563270183657068 790 -> 223070667213077889794379623183838336437.9920551177281967668330417762103 792 -> 249433117287892229255125388685911710805.9960973230079997367491007072130 928 -> 365698321891389219219142531076638716362775.9982597470174543148220891454 940 -> 677621063891416076248230276783145121158916.0018892548309602322004898534 986 -> 6954830200814801770418837940281460320666108.994649611250605331131122063 1005 -> 17910081680940580833529050259595126076784743.00652422098176402344384390 1169 -> 44555719382988281777368496770130045948309444044.99996080286386846150243 1194 -> 139661526073504116557581973059759277212070858620.0003900603188035532686 1213 -> 330144200785402970319166028643329915082011865217.0064534054200532543561
N::meprec: Internal precision limit $MaxExtraPrecision = 50. reached while evaluating -( 1938766283555706196415301648109962894754207498417 Sqrt[1237] Pi -------------------------------------------------) + E . 2 1245 -> 1384892132296689864688150528414254481739817624464.999423621295089731039
N::meprec: Internal precision limit $MaxExtraPrecision = 50. reached while evaluating -( 3309173472789647250136240543502288628041647543181 Sqrt[1249] Pi -------------------------------------------------) + E . 2
N::meprec: Internal precision limit $MaxExtraPrecision = 50. reached while evaluating -( 4514931544489018513609201179433753739448459339035 2 Sqrt[314] Pi -------------------------------------------------) + E . 2
General::stop: Further output of N::meprec will be suppressed during this calculation. 1257 -> 2359752187588332572926453870820027357203549890449.993034752664193580926 1293 -> 11499177736948672237714068560631910541735301233989.99496136788442126388 1326 -> 48171098188871186483096169726268818132470483648300.99134484794080091307 1332 -> 62382700950473563258623210672143849649476315193453.00092102414610595950 1467 -> 18095625621654510801615355531263454706630064771074975.99999999012369367 1556 -> 659805499174190199819286657618770540166630302112791359.9959424231045979 1850 -> 48310987197300327887464627364483701432184761367510399635913.99985950299 1872 -> 107633344087088750110483164611005972787304802294303445731718.9992468149 1960 -> 2532305471868198233465298022928017175581855191972722719356926.993687927
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Where of course "above" means "below" and "below" means "above". --Dan On Apr 1, 2014, at 1:49 PM, Seb Perez-D <sbprzd+mathfun@gmail.com> wrote:
OK, I decided to acquiesce to Mathematica's ridiculous demands. (Why should you have to apply AccountingForm[] just to get a number in standard decimal format?)
But gripes aside, appended are the numbers N (other than 1237, 1249, 1256, which it seemed to choke on), 1 <= N <= 2000, for which exp(pi*sqrt(N)) is within .01 of an integer. Besides the mysterious number theory explanations for why some are so very close, it's also puzzling why so many more of these are just above an integer than just below one.
More experiments: I tried using g[n_] := Exp[Sqrt[n]] with the same form of K: K[max_] := For[n=1,n<=max,n=n+1,If[N[Abs[FractionalPart[g[n]]-1/2],3] > .49, Print[n," -> ",AccountingForm[N[g[n],70]]],Null]] ... and even plugging in 1 million got no output at all. Even though random numbers should be hits 2% of the time! Then, tried instead this definition: g[n_] := Exp[EulerGamma*Sqrt[n]] with the same K: K[max_] := For[n=1,n<=max,n=n+1,If[N[Abs[FractionalPart[g[n]]-1/2],3] > .49, Print[n," -> ",AccountingForm[N[g[n],70]]],Null]], and this was the output up to 1000: In[89]:= K[1000] 44 -> 46.00801254989580374866821393281718990610808755385916137088675721910220 72 -> 133.9996690682195024916379108364436984642366431675814385787629532249629 106 -> 380.9998560899922652985048364133353260948427549094148511587819994344508 142 -> 970.9922482270692677823683566362486703758343384197035855953939483686496 152 -> 1231.998165320086794113206659448727243056884763108326053348929991822208 191 -> 2913.991881693797749913437687584167601069437667150760604838637626844605 318 -> 29532.00302716531235593173259733035039994363373691206154022508694551477 320 -> 30502.00551977682189313224051223001203289587620722158978081666039302332 345 -> 45311.00106373947342773854350867556874544213023995930362766218155941872 454 -> 219452.9945686432069421577154825428216777397159357514383664094397968059 466 -> 257911.9921461867934643982746851372951258497151014207816190016716897832 503 -> 418987.9922146247967498624482658586339260085392808280647138753327451585 525 -> 554416.9963737390879335581569231667971310399032797345458721163129398121 674 -> 3221604.998395203239131677759219596409276001991060563008032795557771631 688 -> 3761111.003683565245331237337931653954132556761830043597215507655483516 741 -> 6666259.991745126708920504918284533297983410319524424920971083230722710 757 -> 7891525.001284764658545293638044726097008102685225884136766957587145273 765 -> 8580446.004732329867080747545028212880152161498187621710548761089218119 793 -> 11461918.99161594923239240165170113390157236484193567263737374380053738 803 -> 12694854.00796358714126243803067300233356698650720543389962885867148105 870 -> 24776745.99653706667749829322322634885572464342147049948027495645265893 927 -> 42896361.99301774554623061821047007944328721040711227839052158844485217 ------------------------------------------------------------------------------ Which is 22 hits, pretty close to 2% of 1000 -- though there are still more just-belows (14) than just-aboves (8). (Going through 3000 instead of 1000, there are a total of 24 just-aboves and 38 just-belows, so this may beg for an explanation. There are 25 total hits 1001-2000, and 15 total hits 2001-3000.) Okay, so why does exp(sqrt(n)) have so few almost-integers -- a total of 0 up through 1 million if you define them to be within .01 of an integer, whereas 2% of 1 million is 20000 ????? (Assuming my Mma didn't have a bug.) --Dan
Warren's observation that my lemma proof failed to deal with both boundary edges of the first octant region is well spotted, though straightforward (if tedious) to repair. The second problem he raises was obscured by my failure to state the inductive hypothesis explicitly. But the actual gremlin is unjustified assumption of the `obvious' d(x-2, y-1) < d(x, y) for [x, y] sufficiently far into first octant: so I ought not to rely on d(x-2, y-1) < f . It begins to look as though the geometric material at the end of that screed may constitute a topological component essential to a successful proof. Back to the drawing board! WFL
It is a pleasure to report the defeat of the horrid spectre of topology, by dint of abandoning attempts to reason about attaching an extra step at the far end [x-2, y-1] in favour of considering (shorter) paths from neighbours [2, 1] etc. of the origin instead. Then straightforwardly the distance function d(x, y) satisfies the same recursion as the explicit expression f(x, y) , whence they are equal. A corrected and slightly expanded screed is posted at https://www.dropbox.com/s/nzmzjswtctju23f/knights_path.txt Reports of attempts to blow further holes in it would be welcome, even if unsuccessful. Particularly if unsuccessful! Fred Lunnon On 4/3/14, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Warren's observation that my lemma proof failed to deal with both boundary edges of the first octant region is well spotted, though straightforward (if tedious) to repair.
The second problem he raises was obscured by my failure to state the inductive hypothesis explicitly. But the actual gremlin is unjustified assumption of the `obvious' d(x-2, y-1) < d(x, y) for [x, y] sufficiently far into first octant: so I ought not to rely on d(x-2, y-1) < f .
It begins to look as though the geometric material at the end of that screed may constitute a topological component essential to a successful proof.
Back to the drawing board! WFL
On 4/4/14, Warren D Smith <warren.wds@gmail.com> wrote:
WDS: I don't agree that your lemma 2 is proven. (Same objection I gave before, I don't see that it was impacted in the slightest.) MInd you, I believe this general approach should work, just a lot more cases will be needed.
WDS's latest postings discussed f(x, y) , the formula function. Lemma 2 is concerned exclusively with d(x, y) , the distance function. Regardless, if the proof of either lemma is incorrect or incomplete, it would be helpful to know at what precise point my logical sequence breaks down or lapses into obscurity. If there is a gap, what case is still missing? As with programmming, it is all too easy when constructing a proof to assume obvious some step which is either nontrivial, or may even be faulty. --------------------- Which reminds me that when the holes in my previous version surfaced, I became aware that I had subconsciously been unhappy about it from the start --- it somehow seemed too easy to be true. I have often had a similar experience previously, yet rarely succeed in articulating it sufficiently to incorporate it into the activity. There should be a word for this situation --- wishful thinking at work, perhaps. But it is intriguing to reflect that the big parallel processor in the background may well have a better grasp of formal logical processes than the feeble I/O unit which is all we can directly access. It was said of the pre-war world chess champion Alexander Alekhine that he seemed incapable of explaining why his own best moves were sound. So maybe this sort of experience is common in many fields. WFL On 4/3/14, Fred Lunnon <fred.lunnon@gmail.com> wrote:
It is a pleasure to report the defeat of the horrid spectre of topology, by dint of abandoning attempts to reason about attaching an extra step at the far end [x-2, y-1] in favour of considering (shorter) paths from neighbours [2, 1] etc. of the origin instead.
Then straightforwardly the distance function d(x, y) satisfies the same recursion as the explicit expression f(x, y) , whence they are equal.
A corrected and slightly expanded screed is posted at https://www.dropbox.com/s/nzmzjswtctju23f/knights_path.txt Reports of attempts to blow further holes in it would be welcome, even if unsuccessful. Particularly if unsuccessful!
Fred Lunnon
On 4/4/14, Warren D Smith <warren.wds@gmail.com> wrote:
Here is a sketch of how to prove the knight distance formula using MAPLE9. I am not going to prove it, I am merely going to explain how somebody better than I with symbolic manip programs, could prove it. ...
This looked an interesting idea, and I tinkered with it for a while to see if it could be persuaded to work under Maple 17. My version 1 is essentially identical to WDS' first attempt, except for assuming integers and attaching special case x = y = 0 to his function g . The impressively messy result looks nothing like WDS' expression starting g(x,y) = max(| x |, | y |) - min(| x |, | y |) - 2 floor(1/4 max(| x |, | y |) - ... --- however both deliver incorrect test results for some arguments! Version 2 restricts the region to x > y > 1 . The result is considerably shorter, and tests correct for all arguments --- both in the region and outside! Version 3 omits all special cases from both f and g definitions. The result (unsurprisingly) still tests incorrect --- but (remarkably) is now identical to WDS' original above! Version 4 again restricts the region to x > y > 1 . The result is much shorter again than any previous --- and despite the incorrect definitions, tests correct for all arguments! I get g(x, y) = 1 for |x|,|y| <= 10 , where g(x, y) := x-y-2*floor((1/4)*x-(1/2)*y) - min( max(x-2, y+1)-min(x-2, y+1)-2*floor((1/4)*max(x-2, y+1)-(1/2)*min(x-2, y+1)), max(x-1, y+2)-min(x-1, y+2)-2*floor((1/4)*max(x-1, y+2)-(1/2)*min(x-1, y+2)), x-y-2*floor((1/4)*x-(1/2)*y)-1, x+1-y-2*floor((1/4)*x+1/4-(1/2)*y), x+1-y-2*floor((1/4)*x+3/4-(1/2)*y) ); This sadly predictable muddle confirms my suspicion that the project is ahead of the technology available to implement it, which will come as no surprise to anyone who recalls my posts on failing to prove automatically theorems about binomial coefficients. It might perhaps be worth another attempt under Mathematica or Macsyma --- but I'm not holding my breath!
OK? So I hope I've made it clear (a) exactly how to prove this now (b) Lunnon should see what is inadequate about his "proof", (c) what is inadequate about MAPLE9 simplifier ... this whole proof would have been a triviality if it had a good simplifier.
As I have observed on a previous occasion: if my proof is claimed incorrect, I would be much obliged to be informed where the error is believed to occur. Fred Lunnon
And with a sense of appalling inevitability, I am obliged to confess that Warren's intuition is once again proved prescient: my optimistically floated proof of Lemma 2 is indeed unfit for purpose, for much the same reason as previously: an implicit inductive assumption that d(x-2, y-1) < d(x, y) . It now seems inevitable that any proof of d = f is going to involve some mildly gruesome grappling with details, overlapping to a large extent existing published attacks on counting the number of cells at distance d . Miller & Farnsworth "Counting the Number of Squares Reachable in k Knight's Moves" http://dx.doi.org/10.4236/ojdm.2013.33027 give a reasonable informal account of the geometrical approach, although I have reservations about how far it qualifies as a copper-fastened proof. Katzman "Counting monomials" http://www.katzman.staff.shef.ac.uk/Articles/CountingMonomials.pdf employs an algebraic approach via Hilbert functions. Er, I might get back later about this ... Warren envisages a CAS-based computation establishing functional equivalence. This ain't on the cards any time soon --- not at least using Maple, as the script attached below illustrates --- two allegedly equal symbolic expressions h, h0 evaluating to incompatible numerical results. Fred Lunnon _______________________________ # Attempted automated proof, after Warren Smith f := proc (x, y) # conjectured counting function local X,Y,p,q,r; X := max(abs(x), abs(y)); Y := min(abs(x), abs(y)); if [X, Y] = [1, 0] then 3 elif [X, Y] = [2, 2] then 4 else p := X-Y; q := p-Y; r := (7 + signum(2*q+1))/2; p - 2*floor(q/r) fi end; h := proc (x, y) # test recursive distance property if [x, y] = [0, 0] then 0 else f(x, y) - 1 - min( f(x-2, y-1), f(x-2, y+1), f(x-1, y-2), f(x-1, y+2), f(x+2, y-1), f(x+2, y+1), f(x+1, y-2), f(x+1, y+2) ) fi end; n := 10; m := 1; # range of numerical verification { seq(seq(h(i, j), j = -n..+n), i = -n..+n) }; # { 0 } ; at all points on n x n board --- OK !! [ seq([ seq(h(i, j), j = -m..+m) ], i = -m..+m) ]; # [ [ 0, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 0 ] ] assume(x::integer, y::integer); h0 := h(x, y); # output one page long { seq(seq(eval(subs({x = j, y = i}, h0)), j = -n..+n), i = -n..+n) }; # { -2, 0 } ; special value 3 in f() ignored --- BUG ?? [ seq([ seq(eval(subs({x = j, y = i}, h0)), j = -1..+1) ], i = -1..+1) ]; # [ [ 0, -2, 0 ], [ -2, -2, -2 ], [ 0, -2, 0 ] ] _______________________________
The nettle has finally been grasped --- as intuition has been prompting from the start, if only I would listen --- and the resulting geometrical proof of the formula for knight's-move distance posted at https://www.dropbox.com/s/nzmzjswtctju23f/knights_path.txt Maybe not as short as initially hoped, but neither as long and tedious as recently feared. Third time lucky? And since it was easy to do --- not to mention more fun than writing up that dratted proof --- version 3 also tabulates the number of shortest paths from [0, 0] to [x, y] . Which in turn raises the question of finding the maximum number possible of shortest paths to a given [x, y] at given distance d . Unsurprisingly, the relevant points appear to hug the axis, along path [x, y] = [2d-3, d+1 mod 2] for d > 4 , these being at smallest Euclidean distance from the origin. The number of paths appears to approach 2^d d^2 for large d ; the counts for 0 <= d <= 48 are tabulated below, pending addition to OEIS. Fred Lunnon [ 1, 1, 2, 12, 54, 100, 330, 1050, 3024, 8736, 23220, 62700, 158004, 406692, 986986, 2452450, 5788640, 14002560, 32357052, 76640148, 174174520, 405623400, 909582212, 2089064516, 4633556448, 10519464000, 23120533800, 51977741400, 113365499940, 252725219460, 547593359850, 1211884139250, 2610998927040, 5741708459520, 12309472580460, 26917328938500, 57457069777800, 125016198060600, 265832233972140, 575824335603660, 1220234181784800, 2632570331352000, 5561593101431640, 11955215864166120, 25186887938801160, 53963277227145000, 113403569798134980, 242237549346710580, 507901544029952064 ];
participants (10)
-
Andy Latto -
Dan Asimov -
Fred Lunnon -
Marc LeBrun -
Michael Kleber -
Mike Stay -
Seb Perez-D -
Tom Rokicki -
W. Edwin Clark -
Warren D Smith