[math-fun] negafibonacci numbers and the hyperbolic plane
Did anyone go to Knuth's talk at MathFest this past weekend? It sounded interesting, but I wasn't able to go and couldn't find a write-up on the web; I'm hoping one of you can summarize. Here's what's on the web: PI MU EPSILON J. SUTHERLAND FRAME LECTURE NEGAFIBONACCI NUMBERS AND THE HYPERBOLIC PLANE Donald E. Knuth, Stanford University, Professor Emeritus of the Art of Computer Programming Saturday, August 4, 8:00 pm - 8:50 pm All integers can be represented uniquely as a sum of zero or more "negative" Fibonacci numbers F-1 = 1, F-2 = -1, F-3 = 2, F-4 = -3, provided that no two consecutive elements of this infinite sequence are used. The NegaFibonacci representation leads to an interesting coordinate system for a classic infinite tiling of the hyperbolic plane by triangles, where each triangle has one 90 degree angle, one 45 degree angle, and one 36 degree angle. Jim Propp
I haven't looked at this one, tho' I can probably reconstruct it if you can't find a more authoritative version elsewhere. It sounds very like a Fibonacci-based "co-ordinate" system I developed for naming tiles within a Penrose tiling. You can do this kind of thing with any tiling generated by an "inflation" [actually a 2-D production rule] which replaces each tile by a set of smaller tiles. Fred Lunnon On 8/7/07, James Propp <jpropp@cs.uml.edu> wrote:
Did anyone go to Knuth's talk at MathFest this past weekend?
It sounded interesting, but I wasn't able to go and couldn't find a write-up on the web; I'm hoping one of you can summarize.
Here's what's on the web:
PI MU EPSILON J. SUTHERLAND FRAME LECTURE
NEGAFIBONACCI NUMBERS AND THE HYPERBOLIC PLANE
Donald E. Knuth, Stanford University, Professor Emeritus of the Art of Computer Programming
Saturday, August 4, 8:00 pm - 8:50 pm
All integers can be represented uniquely as a sum of zero or more "negative" Fibonacci numbers F-1 = 1, F-2 = -1, F-3 = 2, F-4 = -3, provided that no two consecutive elements of this infinite sequence are used. The NegaFibonacci representation leads to an interesting coordinate system for a classic infinite tiling of the hyperbolic plane by triangles, where each triangle has one 90 degree angle, one 45 degree angle, and one 36 degree angle.
Jim Propp
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Sorry, in the last message, I missed out one of the ones: 1 -1 2 -3 5 -8 13 ... R. On Tue, 7 Aug 2007, James Propp wrote:
Did anyone go to Knuth's talk at MathFest this past weekend?
It sounded interesting, but I wasn't able to go and couldn't find a write-up on the web; I'm hoping one of you can summarize.
Here's what's on the web:
PI MU EPSILON J. SUTHERLAND FRAME LECTURE
NEGAFIBONACCI NUMBERS AND THE HYPERBOLIC PLANE
Donald E. Knuth, Stanford University, Professor Emeritus of the Art of Computer Programming
Saturday, August 4, 8:00 pm - 8:50 pm
All integers can be represented uniquely as a sum of zero or more "negative" Fibonacci numbers F-1 = 1, F-2 = -1, F-3 = 2, F-4 = -3, provided that no two consecutive elements of this infinite sequence are used. The NegaFibonacci representation leads to an interesting coordinate system for a classic infinite tiling of the hyperbolic plane by triangles, where each triangle has one 90 degree angle, one 45 degree angle, and one 36 degree angle.
Jim Propp
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Someone came up to me the other day and said, ``I'm Don Knuth'', to which I answered, ``I see you are.'' He first showed how all integers, including the negative ones, could be uniquely represented using base -2 and also, under the Zeckendorf condition of no two adjacent one-bits, using the negative Fibs, F_-n, i.e., 1, -2, 3, -5, 8, -13, ... . I can't, off the top of my head, give the correspondence twixt triads of digits and the below-mentioned tiling of the hyperbolic plane with pi/2, pi/4, pi/5 triangles. R. On Tue, 7 Aug 2007, James Propp wrote:
Did anyone go to Knuth's talk at MathFest this past weekend?
It sounded interesting, but I wasn't able to go and couldn't find a write-up on the web; I'm hoping one of you can summarize.
Here's what's on the web:
PI MU EPSILON J. SUTHERLAND FRAME LECTURE
NEGAFIBONACCI NUMBERS AND THE HYPERBOLIC PLANE
Donald E. Knuth, Stanford University, Professor Emeritus of the Art of Computer Programming
Saturday, August 4, 8:00 pm - 8:50 pm
All integers can be represented uniquely as a sum of zero or more "negative" Fibonacci numbers F-1 = 1, F-2 = -1, F-3 = 2, F-4 = -3, provided that no two consecutive elements of this infinite sequence are used. The NegaFibonacci representation leads to an interesting coordinate system for a classic infinite tiling of the hyperbolic plane by triangles, where each triangle has one 90 degree angle, one 45 degree angle, and one 36 degree angle.
Jim Propp
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Getting a tiling inflation to work in the hyperbolic plane turns out to be harder than it looked at first sight --- because, of course, there is no such thing as similarity --- so the Penrose tiling analogy is probably a red herring. Maybe there's a nice canonical form for the associated hyperbolic (symmetry) group? On 8/8/07, Richard Guy <rkg@cpsc.ucalgary.ca> wrote:
Someone came up to me the other day and said, ``I'm Don Knuth'', to which I answered, ``I see you are.'' He first showed how all integers, including the negative ones, could be uniquely represented using base -2 and also, under the Zeckendorf condition of no two adjacent one-bits, using the negative Fibs, F_-n, i.e., 1, -2, 3, -5, 8, -13, ... . I can't, off the top of my head, give the correspondence twixt triads of digits and the below-mentioned tiling of the hyperbolic plane with pi/2, pi/4, pi/5 triangles. R.
What "triads of digits" are these --- could you give an example? WFL On 8/7/07, James Propp <jpropp@cs.uml.edu> wrote:
Did anyone go to Knuth's talk at MathFest this past weekend?
It sounded interesting, but I wasn't able to go and couldn't find a write-up on the web; I'm hoping one of you can summarize.
Here's what's on the web:
PI MU EPSILON J. SUTHERLAND FRAME LECTURE
NEGAFIBONACCI NUMBERS AND THE HYPERBOLIC PLANE
Donald E. Knuth, Stanford University, Professor Emeritus of the Art of Computer Programming
Saturday, August 4, 8:00 pm - 8:50 pm
All integers can be represented uniquely as a sum of zero or more "negative" Fibonacci numbers F-1 = 1, F-2 = -1, F-3 = 2, F-4 = -3, provided that no two consecutive elements of this infinite sequence are used. The NegaFibonacci representation leads to an interesting coordinate system for a classic infinite tiling of the hyperbolic plane by triangles, where each triangle has one 90 degree angle, one 45 degree angle, and one 36 degree angle.
Jim Propp
At Knuth's site he has posted previews of forthcoming A of CP chapters --- that entitled "fasc1a" contains a discussion of exactly this subject on pp 36-39, which cites F. Herrman & M. Margenstern, Theoretical Comp. Sci. vol 296 pp. 345--351 (2003). The tiling is originally by regular pentagons meeting in fours at their vertices. The naming system in the book assigns to each cell a unique pair of integers, one of which when encoded in signed Fibonacci base permits easy computation of the names of neighbouring cells. I suspect that the other integer can be dispensed with, by naming fundamental triangles rather than entire pentagons: maybe this improvement was described in his lecture? Fred Lunnon On 8/7/07, James Propp <jpropp@cs.uml.edu> wrote:
Did anyone go to Knuth's talk at MathFest this past weekend?
It sounded interesting, but I wasn't able to go and couldn't find a write-up on the web; I'm hoping one of you can summarize.
Here's what's on the web:
PI MU EPSILON J. SUTHERLAND FRAME LECTURE
NEGAFIBONACCI NUMBERS AND THE HYPERBOLIC PLANE
Donald E. Knuth, Stanford University, Professor Emeritus of the Art of Computer Programming
Saturday, August 4, 8:00 pm - 8:50 pm
All integers can be represented uniquely as a sum of zero or more "negative" Fibonacci numbers F-1 = 1, F-2 = -1, F-3 = 2, F-4 = -3, provided that no two consecutive elements of this infinite sequence are used. The NegaFibonacci representation leads to an interesting coordinate system for a classic infinite tiling of the hyperbolic plane by triangles, where each triangle has one 90 degree angle, one 45 degree angle, and one 36 degree angle.
Jim Propp
participants (3)
-
Fred lunnon -
James Propp -
Richard Guy