A343990 Number of grid-filling curves of order n (on the square grid) with turns by +-90 degrees generated by folding morphisms that are self-avoiding but not plane-filling.
0, 0, 1, 1, 2, 7, 10, 15, 33, 45, 93, 186, 300, 530, 825, 1561, 2722, 4685, 7419, 13563
Offset: 1
Examples
Examples for n = 5 are given in Knuth's 2010 update. There are pictures which show (or suggest) that the 5-folds coded by DDUU, DUDD, DDUD are perfect, DUUD and DUDU yield a self-avoiding curve which is not plane-filling, and the other 3 give self-intersecting curves. So A343992(5) = 3 and a(5) = 2.
References
- Chandler Davis and Donald E. Knuth, Number Representations and Dragon Curves -- I and II, Journal of Recreational Mathematics, volume 3, number 2, April 1970, pages 66-81, and number 3, July 1970, pages 133-149. Reprinted and updated in Donald E. Knuth, Selected Papers on Fun and Games, CSLI Publications, 2010, pages 571-614. See page 611, table A_s = a(s).
Links
- Michel Dekking, Table of n, a(n) for n = 1..20
- Chandler Davis and Donald E. Knuth, Number Representations and Dragon Curves, Journal of Recreational Mathematics, volume 3, number 2, April 1970, pages 66-81, and number 3, July 1970, pages 133-149. [Cached copy, with permission]
- F. M. Dekking, Paperfolding Morphisms, Planefilling Curves, and Fractal Tiles, Theoretical Computer Science, volume 414, issue 1, January 2012, pages 20-37. Also arXiv:1011.5788 [math.CO], 2010-2011.
Extensions
Rewritten and renamed by Michel Dekking, Jun 06 2021
Comments