def fib_does_generate(n): found = {} last, curr = 1, 1 while not (last == 0 and curr == 1): found[curr] = True last, curr = curr, (last + curr) % n return len(found.keys()) == n print [x for x in xrange(2, 10000) if fib_does_generate(x)]

The result:

`[2, 3, 4, 5, 6, 7, 9, 10, 14, 15, 20, 25, 27, 30, 35, 45, 50, 70, 75, 81, 100, 125, 135, 150, 175, 225, 243, 250, 350, 375, 405, 500, 625, 675, 729, 750, 875, 1125, 1215, 1250, 1750, 1875, 2025, 2187, 2500, 3125, 3375, 3645, 3750, 4375, 5625, 6075, 6250, 6561, 8750, 9375]`

It looks like the only prime factors that seem to be allowed are 2, 3, 5, and 7, but not in all combinations. My next instinct in this sort of situation is to look the sequence up in the Online Encyclopedia of Integer Sequences. And indeed, it's sequnce A079002, which tells us that the sequence "consists of the integers of the form: 5^k, 2*5^k, 4*5^k, 3^j*5^k, 6*5^k, 7*5^k and 14*5^k."

This is quite intriguing, and until I get a chance to look at the reference noted there, I won't know why this should be the case, but meanwhile I thought it would be interesting to create a visualization of the cyclic Fibonacci numbers. The horizontal axis in the picture below corresponds to the modulus n, and the vertical axis corresponds to magnitude of the Fibonacci numbers mod n, which are displayed as white pixels.

The horizontal white lines come at Fibonacci numbers. And the diagonals with negative slope are the "ghosts" of Fibonacci numbers larger than n. But there's a lot more interesting structure in there.1, 11, 21, 1211, 111221, 312211...

Those are the first few numbers in the look-and-say sequence, so called because it is formed by looking at the previous number in the sequence and describing it by the lengths of runs of digits. For example, you would look at "1" and describe it as "one one," and "11" would become "two ones," then "21" becomes "one two, one one," and so on.

John Conway did some interesting work on this sequence, characterizing 92 "elements" or substrings that appear in look-and-say numbers, which have descendant strings that never interact with the descendant strings of neighboring elements.

As you might imagine, the numbers in the sequence exhibit fractal-like characteristics, since multiple instances of the same element appearing early in the sequence will result in longer repeated sequences in later look-and-say numbers.

Unfortunately, this sort of structure in a 1-d string is not particularly visually satisfying — but what if we could translate look-and-say numbers into two dimensions? It occurred to me that we could use the fact that only the digits 1, 2, and 3 appear in look-and-say numbers to generate walks in a square grid from them. We would pick one of these digits to map to "go forward one step" and the others to map to "turn left, then step forward" and "turn right, then step forward."

For the image below, I chose 3 as the "go straight" digit. I got something of a tangled mess using 1, and 2 gave me big blobs where the path wandered around in the same area for a long time. This is the 37th look-and-say number, as translated into a square grid walk:

The path looks somewhat random at first, but a second look reveals repeated patterns all over it.

If you have questions, comments, solutions to unsolved problems, or ideas for new, related problems, please email me.

Home→Recreational Mathematics