Here you will find a few things that I have thought of over the years. I make not claims to originality, but I have not seen these things elsewhere.
The standard simple algorithm for finding primes is called the sieve of Eratosthenes. This algorithm has the advantage of being very simple. But as one must make a pass through the counting numbers for each prime found crossing out, for example, every11th number to remove all the numbers that contain 11 as a factor. In the described algorithm only one pass through the counting numbers is required and only two operations are required, increment by one and compare zero. This makes the algorithm especially easy to implement in hardware if extreme speed is desired.The memory required for this implementation grows logarithmacally. Here is the algorithm.
In school, if you take enough math courses, you will learn that squares and donuts are very different kinds of things. The important thing, you will learn, is that donuts have holes and squares do not. In this analysis we take a different point of view. We suggest that squares do, in fact, have holes, but these holes have a diameter of zero.
This problem was originally encountered by the author when he was working on a so called intelligent memory at IBM in the 1990's. The memory elements of this device could be thought of as nodes in a network of memory locations. The network topology was an important design consideration and tuned out to be a 4 dimensional torus with each dimension having a diameter of 8. Many problems have a communications topology inherent to the problem and so mapping these topologies into a torus was important. In addition the hypercube was well studied and so mapping the torus into the cube was important.
A cube or a torus can be viewed as a network of nodes connected in a particular way and the way they are connected is given by a rule. In the case of the torus each node is associated wtih an ordered pair (for 2 dimensions). This network can be defined by specifying, given some node (a,b) in a nxm mesh, what other nodes are directly connected to that node. In this case for each node, (a,b), it is directly connected to (a-1modn,b) (a+1modn,b) (a,b-1modm) (a,b+1modm). In the case of the cube we assign a unique binary number to each node. In this case two nodes are connected if each nodes corresponding binary number differs in exactly one bit position.
These two connection schemes seem really quite different and yet as we will see this difference is somewhat superficial. If we have a torus with the connection scheme described above and a cube with its connection scheme, is there a way to map the nodes of the torus into the cube in such a way that the nearest neighbor property of the torus is preserved in the cube? The short answer is yes. But if it is, then what is it?
We can restate this problem more formally.What is the mapping, M from the torus to the cube such that if (a,b) is directly connected to (c,d) then M(a,b) is directlly connected to M(c,d))?
We must first provide a definition of what constitutes a Gray Code. Gray Codes are used by engineers in the design of digital circuits, but we will use them for another purpose. A Gray Code, G, is a bijective mapping of the counting numbers into the set of all possible n bit binary strings such that G(i) differs from G(i+1) in exactly one bit position. Given a set, B,of all possible n bit binary strings, it is not clear that the function G is always possible. This can be proved by the use of so called reflected Gray Codes. Reflected Grey codes have the interesting property that they are always circular, that is the last binary string always differs from the first in exactly one bit position.
Let M be a mapping from a set of ordered pairs into a set of binary strings. Let G be a reflected grey code.
Then M(a,b) = G(a)|G(b) where | is the concatenation operator.
(a,b) is connected to (a+1modn, b) and G(a+1modn) differs in exactly one bit position from G(a), If the G is a reflected Grey Code.