Things of Interest

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.

How to find prime numbers

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.

  1. Set N to 2
  2. Create ModN counter and set to 0
  3. N is prime
  4. Increment N
  5. Increment all ModN counters
  6. If any ModN = 0  goto 4  Else goto 2
As can be seen the machine defined by the algorithm continues to grow as  more new primes are found, but the growth is only logaritihmic. It is interesting to consider what happens if at a certain point no new counters are created. If the last counter created were K then the machine would continue to correctly identify primes up to K2 . After that certain composite numbers will be identified as prime, but we would know that all the factors of these numbers would be at least as large as K and they would all be larger than K2. These numbers might be of interest to people concerned with creating public cryptographic keys.
Additionally if one dumps the modn counter states to a data base for each N, then one would have all the remainders for N when divided by all the primes less than N.

How to map a torus into a hypercube

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.

The problem and a little history

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))?

The solution

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.

    The Mapping

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.