Out of all of mathematics, there will always be a few theorems that go beyond all common sense. One of these is the fact that there are different sizes of infinity. Another interesting fact is the idea that many infinities which seem to be of different size are actually of the same size. There are just as many even numbers as integers, as there are rational numbers.
The general concept of this question is to confront the bizarre reality of infinity. In this challenge, your program will output a list which will:
- At any specific moment of time, always have a whole number of entries
- Eventually contain (if left to run long enough) any specific (non-zero) rational number precisely once on the entire list
- Contain an unbounded number of empty slots (entries on the list that are needlessly set to 0)
- Have a proportion of empty slots that approaches a limit of 100%
- For every positive integer N, have an infinite number of places with N consecutive empty slots
Your challenge is to write that shortest possible program that will output a special list with the following rules:
- All entries with an index that is not a square number should be set to zero. So, the first entry will be nonzero, the second and third will be zero, the fourth will nonzero, etc.
- All rational numbers will be in the form of an improper fraction (such as 4/5 or 144/13) that has been simplified. The exception is zeroes, which will be simply
- All (positive and negative) rational numbers should eventually appear on the list if your program runs for long enough and with enough memory. For any particular rational number, the time required may be an arbitrarily large, but always finite, amount of time.
- If run for an infinite amount of time, no non-zero rational number should ever appear twice.
Rule 3 does allow for some variation, as in there is an infinite number of different possible legal outputs.
Output will be a stream of lines. Each line will be of the general form of
5: 2/3 where the first number is the entry number, then followed by the rational number. Note that
1: 0 will always be the first line of output.
Example snippet of output:
Rules, Regulations, and Notes
This is code golf. Standard code golf rules apply. Also, due to the variation allowed in the output, you need to at least show why you believe that your list will contain all possible rational numbers exactly once, and that your solution is correct.
EDIT: Since the primes numbers did distract from the challenge, I am changing it to square numbers. This accomplishes the same purpose, and also shortens the solutions.