Prime Vector Notation

Background and Motivation

Different ways of representing numbers are useful for different purposes. The tally method, for example, is simple to understand and is useful for comparisons and operations like adding and subtracting. It's awkward for use with large numbers.

The Roman numeral system is a compact form of the tally method, and extends to somewhat large numbers, but it's fairly difficult to multiply and divide using Roman numerals. For that reason, Arabic numeral notation supplanted Roman numerals late in the Middle Ages.

Arabic notation is really a base 10 polynomial system. For example, the number six thousand, seven hundred, and eighty-three (6783) is six times the base (10) cubed, plus seven times the base squared, plus eight times the base, plus three times the base to the zeroeth power. By extending the polynomial system to negative exponents (using a decimal point), we can represent any rational number. Adding, subtracting, multiplying, and dividing are all straightforward using Arabic decimal notation. There are some tasks, however, for which this polynomial system is not well suited. Those tasks include factoring numbers and determining whether a number is prime.

Representing Numbers as Products of Primes

Theorem

Every positive whole number can be represented as a product of prime numbers.

Proof

Every whole number is either prime or composite. If it's prime, the product is trivial. If it's composite, the factors can themselves be represented as products of primes.

The first ten prime numbers are listed below:

The number 6783 can be represented as a product of the primes 3, 7, 17, and 19 (6783 = 3 x 7 x 17 x 19).

Vectors

A vector is a "tuple," a sequence of numbers. In mathematics, vectors are usually written as a list of numbers in parentheses separated by comas. Vectors are used to represent positions in multi-dimensional space, for example.

A Vector of Primes

If we regard each prime as a dimension, then the number 6783 has zero displacement in 2, unit displacement in 3, zero displacement in 5, unit displacement in 7, and so on so that we can represent 6783 as a vector like this:

(0, 1, 0, 1, 0, 0, 1, 1)

The number 40, as a further example, would be represented like this:

(3, 0, 1)

because 40 is two cubed times five.

Operations

Primality Test

Using prime vector notation, a primality test is trivial. Is the dimensionality of the number unity? Then it's prime, otherwise not.

Factoring

Factoring a number in prime vector notation is merely a matter of inspection!

Multiplication and Division

To multiply two numbers in prime vector notation, simply add their vector components. For example, to multiply 273 or (0, 1, 0, 1, 0, 1) by 234 or (1, 2, 0, 0, 0, 1) we have (1, 3, 0, 1, 0, 2) or 63,882.

   (0, 1, 0, 1, 0, 1)
 x (1, 2, 0, 0, 0, 1)
   ------------------
   (1, 3, 0, 1, 0, 2)

Division is the reverse, simply subtract the vector components. If any of the components of the divisor are larger than a corresponding component of the dividend, then the dividend cannot be divided evenly by the divisor and there will be a remainder.

Addition and Subtraction

Unlike the operations above which are much easier with prime vector notation than with polynomial notation, addition and subtraction in prime vector notation are hard. The numbers must be converted to polynomial notation, added or subtracted, and the sum or difference must then be converted back to prime vector notation.

Implementation

In theory, prime vector notation makes the factoring of numbers trivial, but in practice, a very large database of prime numbers is required, so prime vector notation has not found widespread adoption. I devised prime vector notation in the 1990s when I was interested in fast factoring algorithms. However, to be useful on significant numbers (40 decimal digits or more), the database required would consume even the largest computer hard drives.

For example, this text file of the first million primes is about 20 megabytes. The format of the file is two columns, separated by commas. The first column is the series number of (n^th) the prime, and the second column is the prime itself. For example, the hundredth prime is 541. The numbers in both columns are in quotation marks because they were saved as text strings from the generating program (Big Number Cruncher, a Windows 3.0 application). The file does not quite go up to a million entries.

Here are the first (nearly) million primes in HTML.

Email Richard dot J dot Wagner at gmail dot com