Date: Tue, 1995-05-23 16:30:33 From: Walter NissenNewsgroups: 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