Exponential Prime Power Representation
Date: Tue, 1995-05-23 16:30:33
From: Walter Nissen
Newsgroups: sci.math
Subject: Exponential Prime Power Representation
Exponential Prime Power Representation
What is this sequence?
1, 10, 2, 100, 11, 1000, 3, 20, 101, 10000, 12, 100000, 1001, 110, 4, ...
I posed this sequence as a challenge under the subject heading "integer
sequence" for the purpose of announcing the usefulness of exponential
prime power representation. This representation can be directly used to
represent any rational number, giving a new perspective on the
relationships between the rationals and a new facility of arithmetic
calculation.
Exponential prime power representation directly manifests the fundamental
theorem of arithmetic and makes its power directly available for rapid
manipulation of arithemtic quantities and number theoretic functions,
particularly in multiplicative number theory.
A Fundamental Concept
A prime number is evenly divisible only by 1 and itself. The fundamental
theorem of arithmetic, or prime factorization theorem, holds that every
positive integer can be factored into a set of a prime factors which is
unique.
Therefore, every positive integer can be represented by, and in a
fundamental sense is, a product of prime powers.
a2 a3 a5 ar 0 0
n = 2 * 3 * 5 * ... * r * r' * r'' * ...
where some or all of the ai may be 0 and all subsequent exponents are 0.
Since the successive primes are, in principle, known, they can be
dispensed with, i.e., made implicit, and the number n represented as a
vector of exponents (a2, a3, a5, a7, ...). For example, 12 is the vector
(2, 1, 0, 0, ...) = 2^2 * 3^1 * 5^0 * 7^0 * ... = 4 * 3 * 1 * 1 * ...,
where all subsequent elements and exponents are 0 and all subsequent
factors are 1.
A Fundamental Representation
This vector of exponents can be represented as a string of digits, e.g.,
12 = 2100000000000 ... . As in radix notation, the infinite string of
0's can be dispensed with, leaving 21 as the exponential prime power
representation for 12. It is sometimes valuable to reverse the
presentation of the digits (and the exponents and the primes), making the
notation appear more similar to radix notation. This is the form used in
the challenge sequence. In this form, we have the happy coincidence
12 = 12 in both decimal radix and exponential prime power representation.
It is curious to note that this coincidence was noted in an article posted
in the newsgroup rec.puzzles under the subject heading "More Number
Puzzlers" by Scott Purdy, spurdy@pomona.edu, only two days after the
posting of the initial message containing the initial challenge sequence.
And the sequence is seen to be the positive integers starting with 2
(decimal), or 2, 3, 4, 5, 6, 7, 8, 9, 10, ... .
Negative numbers can be represented in exponential prime power
representation by prepending (or appending) a negative sign, and rationals
can be represented by prepending a negative sign to *each* digit. So in
reversed form, as in the sequence, the fraction -2/3 is represented as
- -11 = (-)-11 = -11- = - 3^(-1) * 2^1 and 5/18 = 1-2-1 (the reader can
use this hint to convert Pascal's triangle of binomial coefficients into a
numeric vector).
Powerful in Calculation, Because It Is So Trivial
The motivation for exponential prime power (epp) representation may be
conceptual, but the value of it is powerfully realized in a wide range of
calculations in multiplicative number theory.
The most dramatic case may be the gcd and Euclid's algorism (algorithm).
In contrast to the extensive literature devoted and effort expended to
efficiently calculate the gcd; in epp representation, the gcd is obvious
and direct, requiring merely the calculation of the minima of the
corresponding digits of the two (or more) numbers. E.g., gcd (152, 326) =
122. (For those of you still trying to think in decimal in odd and
nostalgic moments, this is equivalent to gcd (4860, 72000) = 180).
It is equally easy with relatively prime integers. In decimal, it may be
obscure whether 2618 and 2332719675 are relatively prime. In epp, it is
immediately obvious that 1011001 and 420230 are not relatively prime
^ ^
because, by examining the corresponding digits in each number we quickly
perceive that they share non-zero digits (exponents) for the fifth digit
(in decimal again, p[5] is 11), and at the same time we see that the gcd
is 10000, or in decimal, 11.
An Architecture for Machine Implementation
Using existing (and now obsolete) compilers and mathematical systems,
exponential prime power representation can be (relatively) efficiently
implemented in a variety of ways, all of which are straight-forward. If
the size of the largest prime needed to represent a number can be fixed,
and that prime is p[r], then a vector n of size r+2 will suffice. n[0] is
the zero bit (0 itself is already taken as the representation for decimal
1), n[1] is the sign bit, n[2] is the exponent for 2, n[3] is the exponent
for 3, n[4] is the exponent for 5, etc., for r digits. It may be that in
many practical implemenations of multiplicative number theory that neither
the zero nor the sign bit is required, but omitting them is not
recommended for code which will leave its author's hands.
If a wider range of values is desired (one more like radix notation), then
a more complicated form can be used, with n[0] and n[1] as above, n[2]
taken for a pointer m, n[3] for a count f of the number of basic factors,
n[4] for the exponent for 2, etc., as above. But past p[m], the values in
the vector are not exponents as in the simple form, but are actual factors
in radix notation, either integer or floating point, as desired (floating
point is recommended for the same reasons it is the ultimate Cadillac
representation in IEEE arithmetic). For example, the vector (omitting the
zero and sign bits) (7, 1, 0, 2, 1, 1, 0, 1, 1, 241) represents
10000000000000000000000000000000000000000000001101120 = 2^24 - 1 =
16777215 (decimal) = 2^0 * 3^2 * 5^1 * 7^1 * 11^0 * 13^1 * 17^1 * 241 =
3^2 * 5 * 7 * 13 * 17 * 241; the initial 7, 1, i.e., m, f, being the count
of the exponents provided for p[1] thru p[7], namely 7, and the count of
the basic factors, there being only one of these, namely, 241. (For
certain problems, BCD representation may be a practical and efficient way
to realize this structure).
Display of epp is simple. It may be either direct or reversed. I prefer
direct, but have used reversed in this article for consistency with the
challenge sequence. The only details are the representation of zero and
the representation of the basic factors. For zero, I prefer Z or ZZ. 0,
again, is already taken for the representation of decimal 1. The basic
factors can follow a symbol, I prefer **, or can even be truncated if the
investigation under way is focused on the small factors and has no use for
the larger ones. The truncation can leave behind a symbol to denote it, I
prefer *. Another truncation that may occur is for very large exponents.
To reduce this problem, the decimal digits may be extended as in
hexadecimal notation. I prefer to use all the digits and all the letters,
allowing exponents to reach 35 (10 + 26 - 1) before truncation, though
upper and lower case may be easily distinguished allowing an exponent of
61. These two forms are denoted [0-9A-Z] and [0-9A-Za-z]. Under this
scheme, a K (i.e, 1024 decimal, as in KB) is A (as in 2^10, and where A is
the digit following 9), an M (as in MB) is K (as in 2^20) and a G (as in
GB) is U (= 2^30).
Some Obvious Applications
Let's take a look at some perfect numbers (those whose proper divisors sum
to themselves). The first 3 are, now in direct notation, 11 (God created
the Earth in 11 days), 2001 (the Moon revolves about the Earth in 2001
days, and 40000000001 (the Earth revolves about the Sun in 40000000001
days; oh, not?; oh, well, no wonder physics and numerology are too hard
for mere mortals). The structure of these perfect numbers, discovered by
Euclid, and revealed in such stark contrast in epp representation here, is
exactly that proven by Euler to characterize every even perfect number.
It may not be too much to hope that a future mathematician using the
powerful tool of epp representation will find an odd perfect number, or
prove none exist. This last value can be displayed more concisely as
4 ** 31, meaning in decimal, 2^4 * 31 = 2^(5-1) * (2^5 - 1) = 496.
Some other concepts facilitated and illuminated by epp are lcm, the
sigma-nil function (sum of the proper divisors), abundancy, and multiply
perfect numbers. Just to give an example of these last, consider decimal
120 = epp 311 and sigma-nil (311) = 411.
Exponential prime power representation directly manifests the fundamental
theorem of arithmetic and makes its power directly available for rapid
manipulation of arithemtic quantities and number theoretic functions,
particularly in multiplicative number theory.
Reference
Reference: Oystein Ore, Number Theory and Its History, McGraw-Hill, 1948;
(oops, I mean, 2 ** 487).
This article is being posted simultaneously under the subject heading
"integer sequence" in rec.puzzles and under the subject heading
"Exponential Prime Power Representation" in sci.math. There is some
related material under "integer sequence" in sci.math.
Cheers.
Walter I. Nissen, Jr., CDP
Supplementary material added 2008-09-10 :
2000 Mathematics Subject Classification : Primary 11A67 ; Secondary
11A05 , 11A41 , 11A51 , 11A63