Anti-Fibonacci Sequences and Rings of Saturn
Assume a process which repeatedly marks all of positive integers which belong to a Fibonacci sequence which start with the lowest unmarked x and x+c. For example, if c is one, the first Fibonacci sequence marks 1, 2, 3, 5, 8, 13, 21, etc. The process would start the second Fibonacci sequence at 6 and 7, marking thereafter 13, 20, 33, ..., the third one would mark 9, 10, 19, 29, etc. The unmarked numbers 4, 18, 22, 28, 32, 47, 54, 72, etc. are then what I call the anti-Fibonacci numbers for the given c = 1. For c = 2 the anti-Fibonacci numbers would be 5, 8, 9, 24, 34, 38, 45, 50, etc.
One might assume that anti-Fibonacci number generation is a sufficiently complicated process to be essentially pseudo-random. My back-of-the-envelope calculation went as follows: Let p(i) be the probability that i is anti-Fibonacci. A single existing Fibonacci sequence grows sparser with a rate of phi/i where phi is the base of the golden ratio (sqrt(5) + 1) / 2 with which the Fibonacci values grow, but with a probability of p(i)^2 the i and i+c starts a new Fibonacci sequence and p(i) gets a nudge of 2/i upwards. Putting these in equilibrium and solving for p gives sqrt(sqrt(5) + 1) / 2, or roughly 0.899. I knew I had made some lofty approximations in the derivation above, especially in assuming that the density of multiple Fibonacci sequences would decrease as rapidly as that of one sequence, so I wrote a little program that computes some 100 million first anti-Fibonacci numbers. I was somewhat surprized to see that p is only approximately 0.856 for c = 1. For c = 2 the program gave 0.872, which as again surprizing because I didn't expect c to affect p. But when my computer spat out what looks like interference patterns my jaw really dropped.
Having seen the non-randomness of the average of p over all i and observed how it depends on c, a change in coordinates lead me to wonder if conversely the average of p over c's depends on i. The answer is yes. Below I have a sample of p(i) estimated by c up to ten thousand.
The moral of the story? Whenever playing with number theory, staple your jaw so it won't keep falling off constantly.
One might assume that anti-Fibonacci number generation is a sufficiently complicated process to be essentially pseudo-random. My back-of-the-envelope calculation went as follows: Let p(i) be the probability that i is anti-Fibonacci. A single existing Fibonacci sequence grows sparser with a rate of phi/i where phi is the base of the golden ratio (sqrt(5) + 1) / 2 with which the Fibonacci values grow, but with a probability of p(i)^2 the i and i+c starts a new Fibonacci sequence and p(i) gets a nudge of 2/i upwards. Putting these in equilibrium and solving for p gives sqrt(sqrt(5) + 1) / 2, or roughly 0.899. I knew I had made some lofty approximations in the derivation above, especially in assuming that the density of multiple Fibonacci sequences would decrease as rapidly as that of one sequence, so I wrote a little program that computes some 100 million first anti-Fibonacci numbers. I was somewhat surprized to see that p is only approximately 0.856 for c = 1. For c = 2 the program gave 0.872, which as again surprizing because I didn't expect c to affect p. But when my computer spat out what looks like interference patterns my jaw really dropped.
Having seen the non-randomness of the average of p over all i and observed how it depends on c, a change in coordinates lead me to wonder if conversely the average of p over c's depends on i. The answer is yes. Below I have a sample of p(i) estimated by c up to ten thousand.
The moral of the story? Whenever playing with number theory, staple your jaw so it won't keep falling off constantly.
posted by cessu at 12:26 PM
2 Comments:
I noticed this post has been discussed elsewhere, and in good internet fashion those discussions haven't gone "upstream".
I started the Fibonacci sequences (for any c) from zero, not from two ones as usually. This seems to have little effect on the images, but for c>1 the actual anti-Fibonacci numbers are a little different. For example for c=2 the anti-Fibonacci sequence starting from one would be 2, 5, 9, 16, 20, 42, 45, 53, 54, 60, etc.
Another note is that I wasn't aware that the term anti-Fibonacci sequence is already used for the extension of the conventional Fibonacci sequence to negative numbers ..., -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, ...
Have you read Richard Merrick's work on Interference theory?
www.interferencetheory.com
You will find it quite interesting.
Post a Comment
<< Home