Related Links (Outside this Site)

---

dottcomguy00 (2001-03-21)
Is 1 a prime number?     (Modern A000040  vs. obsolete A008578.)

No, 1 is not prime.  This fact turns out to be more than a mere "technicality":

The modern definition of primality is that "a prime number is a positive integer with exactly two positive divisors". However, this may seem unconvincing (and/or arbitrary) by itself, until you stop to consider why we define things the way we do in mathematics, physics or other sciences. A relevant quote from Henri Poincaré has been given a superb concise English translation by John A. Wheeler, namely:

Time is defined so that motion looks simple.

Good mathematical definitions are designed to make theorems simpler to state and easier to use.  We exclude "1" from the realm of prime numbers merely because almost all properties involving prime numbers, divisibility and factorizations would be more awkward to state if we didn't.

Consider just one essential example:  "Every positive number has a unique factorization into primes".  This would not be true if "1" was considered prime since you could add any number of "1" factors to (other) primes and obtain a product with the same value.

Even "1" has a unique factorization into primes, namely the "empty product" which contains no factors  and is therefore equal to the neutral element for multiplication.  (Why is an empty product equal to one?  Why is an empty sum equal to zero? Well, the same principle applies:  Any other definition would cripple Mathematical discourse with dubious "special cases".)

Historically, some number theorists did list "1" as a prime (e.g., D.N. Lehmer, the father of D.H. Lehmer, in 1914).  Some older textbooks also took this deprecated view.  This goes to show that it's not totally impossible to adopt other conventions...  However, such alternate definitions have proven to be far more awkward to use, and that's why we got rid of them:  1 is not prime.  Period.

On 2004-06-14, Edgar Bonet wrote:       [edited summary] Regardless of what's currently accepted for positive integers, wouldn't it be more natural to call "prime" anything that does not have a non-trivial factor within a given set?   For example, the invertible polynomials [with real coefficients] are the nonzero constants (the polynomials of degree zero) which I'd like to call "prime", along with the polynomials of degree 1 and those polynomials of degree 2 which have no real roots. Edgar Bonet, Physicist

What you are describing are, in fact, the so-called irreducible elements of a ring; those which cannot be expressed as a non-trivial product (a product of two factors being considered trivial if at least one of them has a reciprocal in the ring).

The concept of irreducibility is more generally applicable than the concept of primality, which is restricted to those rings where factorizations into irreducible elements are essentially unique (which is to say that, in two such factorizations, every factor of one equals some factor of the other multiplied by an invertible element of the ring).  One example where factorizations are not unique is the set of complex numbers of the form  a + ibÖ5, where a and b are integers.  In this, the number 6 has two unrelated factorizations into irreducible factors:

6   =   2 ´ 3   =   (1 + iÖ5) (1 - iÖ5)

There are only nine discrete "grids" of complex numbers where factorizations are unique, most notably Gaussian integers and Eisenstein integers.

In those cases where factorizations can be shown to be unique in the above sense, the term "prime" is often restricted to those irreducible elements which are not invertible and have some ad hoc additional feature which ensures factorization unicity.  (We keep as primes only positive numbers in the case of integers, or polynomials with leading coefficients equal to 1 in the case of polynomials.)  In this context, invertible elements are commonly called "units".  "Units" and "primes" play totally different roles in this general scheme.

+1 and -1 are units, they are not primes.

---

(2002-06-16)
Is "composite" the opposite of "prime" ?

No it's not, although it comes close.  Even in the realm of positive integers the number 1 is neither composite nor prime (see previous article).

The term "irreducible" is favored to denote something that's not composite, but it's prudent to state exactly what you have in mind just before you use it for the first time in a speech or a text.  The ugly adjective "noncomposite" could be another option, which does not need prior explanations...

---

Anonymous query, via Google   (2004-11-05)
What two prime numbers add up to their product?

As each prime divides the sum of both, it must divide the other.  This is only possible if the two primes are equal to some number p.  The sum and the product being both equal to 2p, we must have   p = 2.

2 + 2   =   2 ´ 2

---

(2002-06-14)   Gaussian Integers, Gaussian Primes, etc.
How does the concept of primality generalize beyond ordinary integers?

The so-called Gaussian integers  are complex numbers of the form  a+ib,  where a and b are integers.

Gauss showed that each Gaussian integer has a unique factorization as a product of a so-called "unit" (one of the 4 invertible elements +1, -1, +i, -i ) and irreducible elements in an abitrarily chosen "quarter" of the complex plane, equivalent to positive primes among ordinary integers  (in this context, a Gaussian integer  x+iy  is said to be "positive" when  -x < y < x+1 ).

Note that  1+i  is the only "positive" Gaussian prime whose conjugate is not a "positive" Gaussian prime as well.  (HINT:  How can  x+xi  be irreducible?)

Ordinary prime integers are not necessarily prime among Gaussian integers.  Actually, a prime integer is a Gaussian prime if and only if it's congruent to 3 modulo 4.  In particular, 2 and 5 are not Gaussian primes:

2   =   -i (1+i)²           5   =   (2+i) (2-i)

Note that the above factorization of 2  (involving the "unit" -i)  is indeed the proper "unique" one, since the more obvious factorization  (1+i)(1-i)  uses a Gaussian integer which is not "positive" in the above sense...

---

AlisonWonder (2002-06-23)
How do you find the lowest common multiple (LCM)
of 3, 7, 24, 86, 125 and 214 ?

Small numbers like these are easily factored into primes:

3 and 7 are prime.  24 is 2³´3.  86 is 2´43.  125 is 5³.  214 is 2´107.

The factorization of their least common multiple (LCM) is obtained by using for each prime the highest exponent that appears in each of the above factorizations.  The result is, therefore:

LCM(3,7,24,86,125,214)   =   2³ ´ 3 ´ 5³ ´ 7 ´ 43 ´ 107   =   96621000

Factoring larger numbers into primes is often very difficult, so it's not a realistic option.  (In fact some modern schemes in public key cryptography do rely on the fact that it's difficult to retrieve two large prime numbers from their product.)

To find the least common multiple (LCM) of two large numbers, it's much better to first compute their greatest common divisor (GCD) using Euclid's algorithm (or related algorithms that are similarly efficient).  You may then use the relation:

LCM(a,b)   =   ( a ´ b ) / GCD(a,b)

Given huge numbers like:

       a = 2562047788015215500854906332309589561
       b = 6795454494268282920431565661684282819

The above formula allows you to "easily" compute the LCM of a and b:

15669251240038298262232125175172002594731206081193527869

Note:   The above numbers (a and b) are not random ones.
They are both products of two very special 19-digit prime numbers...
HINT: Their GCD is 1111111111111111111 and the other factors are of a similar nature (in nondecimal bases of numeration).

---

vorobya (Alexey Vorobyov. 2002-10-18)   Aurifeuillian Factorization
Prove that   n⁴ + 4   is composite (i.e., not prime) for all  n > 1

Well,   n⁴ + 4   =   (n² - 2n + 2) (n² + 2n + 2)   is a proper factorization, since the first factor is the smaller one and is greater than 1 when n > 1.

This type of factorization is sometimes called Aurifeuillian (less commonly spelled Aurifeuillean) after the Frenchman [Léon François] Antoine Aurifeuille, who published a special case in 1873.  Here are some algebraic factorizations:

a2 - b2	=	( a - b )  ( a + b )
a3 - b3	=	( a - b )  ( a2 + ab + b2 )
a3 + b3	=	( a + b )  ( a2 - ab + b2 )
4 a4  +  b4	=	( 2 a2 - 2ab + b2 )  ( 2 a2 + 2ab + b2 )

---

(2006-02-05)   Euclid's Algorithm establishes Bézout's Theorem
Euclid's Algorithm gives the  greatest common divisor  d of two integers  p and q, and also yields two integers u and v such that  up + vq = d.

In the so-called Euclidean division of two positive integers  (the dividend  n  and  the  divisor  p)  the quotient  q  is the largest integer which goes p times into n.  This leaves a nonnegative remainder  r  less than p.  In other words:

n   =   p q  +  r       ( 0 £ r < p )

Euclid's Algorithm is an iterative procedure based on the remark that any common factor of n and p is also a common factor of p and r.  Until r vanishes, we may perform simpler and simpler divisions  where the divisor and remainder of one become the dividend and divisor of the next...  The last divisor (or last nonzero remainder) is then the greatest common divisor (GCD) of the original two numbers.  Here's how Euclid's algorithm yields 3 as the GCD of 5556 and 1233:

An important remark (expanded below) is that we may express the resulting greatest common divisor as a linear combination of the original two numbers by tracing back the steps in Euclid's algorithm  (this proves  Bézout's Theorem ).

Subtractive Version of Euclid Algorithm :

The GCD of two integers may also be worked out by repeatedly replacing the larger of them by the  difference  of the two.  This simpler version of Euclid's algorithm is  less efficient  than the usual one described above  (using Euclidean division rather than mere subtraction)  but it can be convenient in proofs and other theoretical arguments (see below).

---

(2006-02-05)   Bézout's Theorem  (Bézout's Identity):
The greatest common divisor (d) of two integers (p and q) is a linear combination of them:   d = up + vq  (where u and v are integers).

This fundamental (very useful) result is named after the French mathematician Etienne Bézout (1730-1783) although it was already well-known before his time.  In particular, it's featured in the work of Claude Gaspar Bachet de Méziriac (1581-1638) who is best remembered by for his own Bachet squares (1624).

One solution is obtained by tracing back the steps of Euclid's algorithm which compute the GCD of p and q.  With the above example  (p=5556,q=1233):

3 =    (1)    9 +   (-1)    6 =   (1)    9 -     (  15 -      9)
  =   (-1)   15 +    (2)    9 =  (-1)   15 +   2 ( 609 - 40. 15)
  =    (2)  609 +  (-81)   15 =   (2)  609 -  81 ( 624 -    609)
  =  (-81)  624 +   (83)  609 = (-81)  624 +  83 (1233 -    624)
  =   (83) 1233 + (-164)  624 =  (83) 1233 - 164 (5556 - 4.1233)
  = (-164) 5556 +  (739) 1233

Note that u is defined modulo q and v is defined modulo p, because:

u p  +  v q   =   (u+kq) p  +  (v-kp) q

Bézout Coefficients and Bézout Function :   bezout(x,y)

A careful backtrack of Euclid's algorithm yields the definition of a  unique  function of two variables which gives the so-called  Bézout coefficients  (u and v)  without  the aforementioned ambiguity as the  simplest  possible solution.  Formally, such a function satisfies the following  nice  identity, unless |x|=|y|.

x bezout(x,y)  +  y bezout(y,x)   =   gcd(x,y)   ≥ 0

To make this hold in all cases, we'd have to put:   bezout (x, ±x) = ½ sign(x).  That's an unpalatable exception (a non-integer value) for just one trivial case.  (It's more natural to retain  bezout (x, ±x) = 0   rather than insist on the above.)

Forsaking that ad hoc exception, here's how to define  bezout  on a TI-92, TI-89 or Voyage 200.		bezout(x,y) Func If x<0 : Return -bezout(-x,y) Local u,v,q,t abs(y)®y : 1®u : 0®v While y¹0   mod(x,y)®t   (x-t)/y®q   y®x : t®y   u-q*v®t : v®u : t®v EndWhile u : EndFunc

Note that  bezout  is odd for one argument and even for the other:

bezout(-x,y)  =  - bezout(x,y)           bezout(x,-y)  =  bezout(x,y)

The above algorithm remains valid when the arguments of  bezout  are not integers  (because the same is true of the  mod  function which it uses).  Luckily, this is consistent with the generalized GCD function presented in the next article.

---

(2007-05-07)   GCD of two fractions... or two commensurable numbers
Extending the definition of a GCD beyond the realm of integers.

The  greatest common divisor  (GCD)  normally defined among integers (as computed by Euclid's algorithm) has two fundamental properties:

• gcd ( xp , xq )   =   x gcd(p,q)
  
• x / gcd(x,y)   and   y / gcd(x,y)   are two coprime  integers

Both properties are retained by defining the GCD of two fractions as the GCD of their numerators divided by the LCM of their denominators.  Software packages which support exact  rational arithmetic  (in advanced handheld calculators and elsewhere)  normally use this definition to extend the range of their GCD function beyond integers.  Rightly so...

gcd ( ²/₃ , ¹/₂ )   =   ¹/₆

This allows the GCD of two commensurable numbers to be defined as well:  Two real numbers are commensurable iff they are proportional to two integers;  Their GCD is simply the GCD of those integers times the common scaling factor.

gcd ( ^2p/₃ , ^p/₂ )   =   ^p/₆

The GCD of two numbers that are  not  commensurable is best defined to be  zero.  This makes the second fundamental property listed above  fail gracefully  (as it involves undefined ratios of vanishing denominators).  With this convention, the celebrated irrationality of  Ö2  can be stated compactly.  So can the epitaph of Roger Apéry  (the irrationality of Apéry's constant).

gcd ( 1 , Ö2 )   =   0
gcd ( 1 , z(3) )   =   0

A  clue  of the incommensurability of two numbers  x  and  y  may take the form of a small upper bound on theit GCD.  Something like:

gcd ( x , y )   <   e = 10^-100

---

Otisbink (2002-04-02)
How can I find integer solutions of a linear equation?
For example, (1,4) and (3,1) are integer solutions of   3x + 2y = 11.
How about a harder one like   1024 x - 15625 y  =  8404 ?

There are infinitely many integer solutions of   3x + 2y = 11  (two of them in  positive  integers).  They can be indexed by an integer  n Î  :

x_n   =   1  +  2 n
y_n   =   4  -  3 n

Any such equation whose unknown variables are required to be integers is called a  Diophantine equation.  Here's how to proceed to solve for x and y any linear Diophantine equation   ax + by = c:

First, compute the Greatest Common Divisor (GCD) d of a and b, using Euclid's Algorithm. In the process, you will obtain two integers u and v such that au + bv = d  (as explained above,  the existence of two such integers is a result commonly known as Bezout's theorem.)

We have   a = da'   and   b = db' , where a' and b' are relatively prime.

Since the RHS of the equation is divisible by d, the LHS must be also. Therefore, d must divide c, or else the equation has no integer solutions. Let's assume, then, than c is equal to dc'.  Using the above expression for d, the original equation [divided by d] may be rewritten as follows:

a' x + b' y   =   (a' u + b' v) c'       or       a' (x-uc') + b' (y-vc')   = 0

Therefore, b' divides the product a' (x-uc'). Since b' and a' are coprime, b' must divide (x-uc').  In other words, there exists an integer k such that x = u c' + k b' and we see that the equation is indeed satisfied if   y = v c' - k a'.  

For the numerical example  a = 1024,  b = -15625,  c = 8404,  we obtain:

d = gcd(a,b) = 1     therefore  a' = a ,   b' = b ,   c' = c
u = bezout (a,b) = -4776     and     v = bezout (b,a) = -313

The above gives all the integer solutions of   1024 x - 15625 y  =  8404   in terms of a single integer parameter  k :

x   =   u c' + k b'   =   -40137504 - 15625 k
y   =   v c' - k a'   =   -2630452 - 1024 k

To have smaller constants, we may want to introduce  n = -2569 - k

x   =   3121 + 15625 n
y   =   204 + 1024 n

Indeed:   1024 ( 3121 + 15625 n )  -  15625 ( 204 + 1024 n )   =   8404

---

(2006-02-03)   Pythagorean Triples   (Pythagorean Triplets)
Solutions, in coprime positive integers, of the equation   x² + y² = z² 

Such integers  x,y,z  are the sides of a right triangle.  The smallest solution is common knowledge:  x=3, y=4, z=5.  It turns out that  all  coprime solutions are of the following form  (given by Archimedes with v=1).

( u²-v² ) ²  +  (2uv) ²   =   ( u²+v² ) ²

Proof :   x and y can't be both odd (otherwise, the sum of their squares is 2 modulo 4, which can't be a square) so one of them must be even.  Without loss of generality, we may thus assume that y is even.  Let  y = 2a :

4 a ²   =   (z+x) (z-x)

The positive integers ½(z+x) and ½(z-x) are coprime  (or else the sum and the difference, z and x, wouldn't be coprime).   Their product can thus be a perfect square only if  both of them are, so  z+x = 2u²,   z-x = 2v²,   and   y = 2uv. 

Conversely, the above yields coprime solutions whenever u and v are coprime, without being  both  odd...  Below are the  smallest  such coprime solutions  (we've added the trivial solution  y = 0,  which arguably belongs here).

Babylonian clay tablets featuring lists of such  Pythagorean triples  (not necessarily coprime)  rank among the earliest mathematics on record.

• A009003  Hypothenuse numbers:   5, 10, 13, 15, 17, 20, 25, 26, 29, 30, 34, 35, 37, 39, 40, 41, 45, 50, 51, 52, 53, 55, 58, 60, 61, 65, 68, 70 ...
• A009177  Hypothenuses of more than one triplet:   25, 50, 65, 75, 85, 100, 125, 130, 145, 150, 169, 170, 175, 185, 195, 200, 205, 221 ...

4 nontrivial triangles have integer sides and hypothenuse 65  (resp. 85) :

65 ²   =   63 ²  +  16 ²   =   60 ²  +  25 ²   =   56 ²  +  33 ²   =   52 ²  +  39 ²
85 ²   =   84 ²  +  13 ²   =   77 ²  +  36 ²   =   75 ²  +  40 ²   =   68 ²  +  51 ²

1105 is the hypothenuse of 13 distinct nontrivial Pythagorean triplets:

1105 ²   =   1104 ²  +  47 ²   =   1100 ²  +  105 ²   =   1092 ²  +  169 ²
  =   1073 ²  +  264 ²   =   1071 ²  +  272 ²   =   1020 ²  +  425 ²
  =   1001 ²  +  468 ²   =   975 ²  +  520 ²   =   952 ²  +  561 ²
  =   943 ²  +  576 ²   =   884 ²  +  663 ²   =   855 ²  +  700 ²   =   817 ²  +  744 ²

The numbers which are expressible in many ways as sums of two squares  (cf. A016032)  enjoy an "unfair advantage" in the above record-breaking game.

---

(Joe of Ann Arbor, MI. 2000-10-24)
What numbers have exactly 6 "proper divisors" ?  [Calling "proper divisor" an integer less than the dividend which divides evenly into it.]

Consider the factorization into primes of the number N = A^aB^bC^c... When it comes to counting the number of divisors (for the time being let's count both 1 and N as divisors), only the sequence of exponents a,b,c,... matters (not the sequence of prime factors A,B,C,...). To get a divisor of N you should pick one exponent for the first prime among the (a+1) integers from 0 to a, one exponent for the second prime among the (b+1) integers between 0 and b, etc.

So, the total number of positive divisors of N is (a+1)(b+1)(c+1)...

If you want the number N to have exactly 6 proper divisors (counting 1 but excluding itself) the product (a+1)(b+1)... should be equal to 7. As 7 is prime this means the product in question only has one factor, so that you must have a=6 and nothing else. The number in question must be the sixth power of a prime. The first of these are 64, 729, 15625, 117649, 1771561, 4826809 ... A030516.

It is worth pointing out that the term "proper divisor" may exclude 1 as well as N. If you use this convention, the product (a+1)(b+1)... should be equal to 8. This corresponds to only 3 possible alternatives:

1. N is the product of 3 distinct primes.
2. N is the product of a prime by the cube of another prime.
3. N is the seventh power of a prime.

There are a lot more solutions this time:

1. The first class of solutions starts with 2´3´5 = 30, 2´3´7= 42, 2´3´11=66, 2´5´7=70, 2´3´13=78, 2´3´17=102, 3´5´7=105, 2´5´11=110, 2´3´19=114, 2´3´23=138, etc.
2. The second class starts with 2³´3=24, 2³´5=40, 2´3³=54, 2³´7=56, 2³´11=88, 2³´13=104, 3³´5=135, 2³´17=136, etc.
3. The third class is the sequence of seventh powers of primes: 128, 2187, 78125, 823543, etc.

The combined list is therefore: 24, 30, 40, 42, 54, 56, 66, 70, 78, 88, 102, 104, 105, 110, 114, 128, 130, 135, 136, 138, 152, 154, 165, 170 ... A030626.

(On a related topic, you may want to exercise your programming talents by  efficiently  generating in increasing order the products of 3 distinct elements from a given list of increasing integers.)

---

(J.E. of Lubbock, TX. 2000-10-25)  Perfect Numbers, Mersenne Primes
A perfect number is a number whose divisors add up to itself:  1+2+3=6 1+2+4+7+14=28.  After 6 and 28, what are the next perfect numbers?

The proper divisors of a positive integer used to be called aliquot parts or proper quotients.  These include unity and all other positive divisors of the integer, except itself.  It's often more convenient to consider all the positive divisors of a number.  The sum s(n) of all the divisors of n has the desirable property of being multiplicative (which is to say that s(pq) = s(p)s(q), whenever p and q are coprime).  A perfect number may thus (also) be defined as an integer n such that  s(n) = 2n.
      The factorization into primes of any number n consists of relatively prime factors of the type p^m (p is prime and m is its multiplicity in the factorization); s(n)/n is the product of the factors (p^m+1-1)/(p^m+1-p).  The integer n is a perfect number if and only if this product equals 2.

Only the first four perfect numbers (6, 28, 496 and 8128) were known to Nicomachus of Gerasa  (c.AD 60-120 ; Gerasa is now Jarash, Jordan).  Nicomachus discusses the topic in his celebrated Arithmetike Eisagoge ("Introduction to Arithmetic", c. AD 100), an influential work which includes multiplication tables and the earliest known use of Arabic numerals (Indian decimal numeration) outside of India.  Nichomachus was the first to deal with Arithmetic independently from geometry, but his work is far less rigorous than what Euclid had done 4 centuries earlier.  His "results" are often mere guesses.  Wrong guesses tainted the study of perfect numbers for centuries...

It's not difficult to show (Euclid did it first) that the even perfect numbers are the numbers of the form 2^n-1(2ⁿ-1), provided (2ⁿ-1) is prime.  A prime number of that shape (i.e., one unit less than a power of 2) is known as a Mersenne prime.

These are named after Marin Mersenne (1588-1648) the Parisian friar who built around him an influential scientific circle, well before the official creation, in 1666, of the French Academy of Sciences.  In 1644, Mersenne proposed a tentative list of the powers of 2 which follow a prime number.  His first mistake was to omit exponent 61 while wrongly including exponent 67.  Exponent 67 was shown to yield a composite Mersenne number (by Edouard Lucas, around 1875) well before Frank Nelson Cole (1861-1926) could heroically find its factors, in 1903.

As of  April 2007,  only 44 Mersenne primes are known, corresponding to the following values of the exponent (n):

2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657...

The list is thought to be infinite, but this has yet to be proved.  Double-checking has shown the above list to be complete up to its 39 ^th member (13466917).

enter>Martin R. Nowak

The ten largest known Mersenne primes were found by GIMPS :

Rank	Prime Number	Digits	Discovered by	Date
44?	2 32582657-1	9808358	Cooper & Boone	2006-09-04
43?	2 30402457-1	9152051	Cooper & Boone	2005-12-05
42?	2 25964951-1	2005-02-18
41?	2 24036583-1	7235733	Josh Findley	2004-05-15
40?	2 20996011-1	6320430	Michael Shafer	2003-11-17
39	2 13466917-1	4053946	Michael Cameron	2001-11-14
38	2 6972593-1	2098960	Nayan Hajratwala	1999-06-01
37	2 3021377-1	909525	Roland Clarkson	1998-01-27
36	2 2976221-1	895932	Gordon Spence	1997-08-24
35	2 1398269-1	420921	Joël Armengaud	1996-11-13

The search for the next Mersenne prime is very active and we encourage you to join it, by donating your computer's idle time.  This is fully automated and quite painless.  See www.mersenne.org for details  (and/or the latest update).

Therefore, only 44 perfect numbers are known at this [updated] writing, including huge ones.  Here is the beginning of the list:

6, 28, 496, 8128, 33550336, 8589869056, 137438691328,
2305843008139952128, 2658455991569831744654692615953842176

Of these, the last two (n = 31 and 61 in the above formula) were respectively discovered by Leonhard Euler (1772) and I.M. Pervushin (37 digits, in 1883).

The following ones, corresponding to n=89 and n=107, were discovered by R.E. Powers in 1911 and 1914.  They have respectively 54 and 65 digits.  Before that, the value n=127 had been shown to give a Mersenne prime of 39 digits (and a perfect number of 77 digits) by Edouard Lucas (1842-1891) in 1875.  Lucas could only achieve this by designing an efficient test, which would be the basis of all subsequent efforts, computerized or not (the "Lucas-Lehmer" test).  Lucas' heroic record would not be broken until the advent of the modern computer. The next two numbers in the list, the 13th and 14th Mersenne primes, are much larger (corresponding to n=521 and n=607) and were both discovered the same day (January 30, 1952, around 22:00 PST and shortly before midnight) by Raphael Mitchel Robinson (1911-1995), at the dawn of the computer age. 

There's an interesting tale about the later discovery of the 19th and 20th Mersenne primes (corresponding to exponents 4253 and 4423) by Hurwitz and Selfridge in 1961:  Because of the way the computer printout was stacked, Alexander Hurwitz read about the larger number a few seconds before the smaller one.  The fact that history has now recorded that the 19th Mersenne prime (n = 4253) never held the record as the largest known prime clearly indicates that what we mean by "known" [for now and in this context, at least] is "known to some human being".  Mathematical and other scientific facts may be gathered automatically, but they become actual knowledge only when someone is aware of them.  It's simply a question of what our current vocabulary means, and that meaning may evolve.  Students of philosophy may still have fun wondering if a falling tree makes a sound when nobody is around to hear it, but they are currently up against an anthropocentric majority opinion:  In the mid 20th century, we did not [yet?] acknowledge a record broken by a machine, if nobody was aware of it while it "held"...
      Henry Dobb (2002-05-26 e-mail) confirms the above story, which he heard from John Selfridge himself around 1990, when Selfridge was a visiting professor of mathematics at Florida Atlantic University.

Are there any  odd  perfect numbers?

Nobody knows for sure.  Almost everybody's guess is that there are none, but it's only a guess, and similar guesses have often been proved wrong in the past...
An odd perfect number would necessarily have the following properties:

• No fewer than 300 decimal digits.  [BCR 1991]
• A prime factorization with only one odd exponent.
• At least three prime factors greater than 100.   [Iannucci 2000]
• At least two prime factors greater than 10000.   [Iannucci 1999]
• At least one prime factor greater than 10⁸.   Jenkins had established a lower bounded of 10⁷ in 2003.  The same method was used by Goto and Ohno in 2006 to improve the lower bound to 10⁸.
• At least one prime power greater than 10²⁰.   [Cohen 1987]
• At least 9 different prime factors.  The number of different prime factors was first shown to be at least  8  by Chein (1979) and/or Hagis (1980).  This was improved to  9  by Nielsen in 2006.
• A sum of the exponents in the prime factorization which has been shown to be at least 29 by Sayers (1986), at least 37 by Iannucci and Sorli (2003) and at least 47 by Kevin G. Hare (2004).  Hare improved successively his own record to 69, 71, 73 and 75 in 2005  to introduce a new method but "not necessarily to extend this bound to the farthest extend possible".

An odd perfect number with k prime factors can't exceed 2^4k [Nielsen 2003].

The question of finding an odd perfect number, or showing that none exist, is often presented as the oldest unsolved mathematical problem...

MathWorld   |   OddPerfect.org by William Lipp (still under construction as of 2007-12-01)

---

(G. S. of Farley, IA. 2000-11-15)
How can a  power ,  like 12¹⁷,  be calculated without actually multiplying the whole thing out?   [ as in  12´12´12´12´12´12´ ... ]

There are at least  2  ways.  The second one applies beyond ordinary numbers.

First way: Use a table of logarithms.

You may use a table of logarithm.  Such tables have been available at your local library since the early 1600's.  Find the common logarithm of 12 (1.0791812) and multiply by 17.  This gives you 18.3460804.  You then use the log table to find that 0.3460804 is the log of 2.2186, so that your result is about 2.2186´10¹⁸.

Second way: Use repeated squaring.

To obtain an exact result without going through 16 multiplications, you may notice that an even exponent means squaring the result for an exponent that's only half as big  (so that you "pay" the cost of just one multiplication to halve the exponent instead of reducing it just by one as you do with the "naive" method).  What if the exponent is odd?  Well, you can reduce the problem to that of an even exponent at the cost of just one extra multiplication.  (Can't you?)

With exponent 17, squaring four times with just one "extra" multiplication will do the trick :

12 ¹⁷   =   (((12 ² )² )² )² ´ 12

In other words:

• 12 ² = 144,
• 144 ² = 20736,
• 20736 ² = 429981696,
• 4299811696 ² = 184884258895036416

Multiply this by 12 to obtain the answer:  12 ¹⁷ = 2218611106740436992

In this case, the number of multiplications has only been reduced from 16 to 5  (and they were more complicated to perform).  However, when the exponent is very large, the improved method becomes  much  better.  Indispensable, in fact.

Number theorists routinely use the above approach to compute  aⁿ modulo m  for  very  large values of the exponent  n.  With modular arithmetic, we don't have to deal with larger and larger results because, at each iteration, we consider only the remainder of the division by  m,  which remains less than  m.

---

(Steve of Somerville, MA. 2000-11-16)   Partition Function (A000041)
How many ways can the numbers 1 to 15 be added together to make 15? Is there a formula for that calculation?

The technical term for what you are asking is the "number of partitions of 15", which is often called p(15).  A partition of n is a collection of positive integers (not necessarily distinct) whose sum equals n.

This has been studied at length by the best mathematical minds of all times, including the Indian genius S. Ramanujan (1887-1920).  He collaborated with J.H. Hardy (1877-1947) to come up with a  fantastic  exact formula for the partition function  p(n), as a sum [rounded to the nearest integer] whose number of terms is on the order of Ön.  You may read about this on pages 97-99 of  Littlewood's Miscellany  by  John E. Littlewood (1885-1977).  In 1937, Hans Rademacher (1892-1969) gave a formula for p(n) as a convergent series ("On the partition function p(n)" Proc. London Math. Soc. 43 (1937) 241-254).

The number of partitions p(n) is the coefficient of xⁿ in the expansion of

(1+x+x²+x³+...) (1+x²+x⁴+x⁶+...) (1+x³+x⁶+...) (1+x⁴+x⁸+...) (...) ...

This coefficient is indeed obtained by counting the number of ways there is to choose an exponent multiple of 1 from the first factor, a multiple of 2 from the second factor, a multiple of 3 from the third, etc. so these exponents add up to n.  This leads to the formula for the "generating function" of p(n) which was first given by Euler (1707-1783) as the reciprocal of the products of all factors (1-xⁿ) where n ranges over the positive integers.  (See Encyclopedia Britannica.)

Among many other similar essays, we recommend a recent lecture by Ken Ono.

There are 176 partitions of 15, namely: 15, 14+1, 13+2, 13+1+1, 12+3, 12+2+1, 12+1+1+1, 11+4, 11+3+1, 11+2+2, 11+2+1+1, 11+1+1+1+1, 10+5, 10+4+1, ... ... 2+1+1+1+1+1+1+1+1+1+1+1+1+1+1, 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1.

Here's a simple BASIC program that will compute the number p(n) of partitions of n as an array of dimension m (m>2). The array "a" is just temporary storage. The program is based on Euler's basic remark and merely computes the first m coefficients in the product of all the series (1+x^u+x^2u+x^3u+ ...). (arrays "a" and "p" hold the coefficients of the resulting polynomials):

INPUT m
DIM a(m),p(m)
FOR i = 0 TO m: p(i) = 1: NEXT i

FOR u = 2 TO m
  FOR i = 0 TO m: a(i) = p(i): p(i) = 0: NEXT i
  FOR j = 0 TO m STEP u
    FOR k = j TO m
      p(k) = p(k) + a(k-j)
    NEXT k
  NEXT j
NEXT u

REM At this point, p(n) is the number of partitions of n
REM (for any n between 0 and m).

The following program achieves the same result  much  faster !

input m
dim p(m)
p(0) = 1

for i = 1 to m
  j=1 : k=1 : s=0
  while j>0
    j = i-(3*k*k+k)\2
    if j>=0 then s = s - (-1)^k*P(j)
    j = i-(3*k*k-k)\2
    if j>=0 then s = s - (-1)^k*P(j)
    k = k+1
  wend
  p(i) = s
next i

The above relies on the connection of partitions to both types of  pentagonal numbers  (A000326 and A005449)  which also translates into a simple way to compute the Dirichlet inverse (A129667) of the partition-based multiplicative sequence which  enumerates distinct Abelian groups  (A000688).  All of this ultimately rests on the following (nice) statement proven by Euler...

Euler's Pentagonal Number Theorem :

¥ Õ n = 1

( 1 - x n )     =

+ ¥ å k = -¥

(-1)k  x (3k2+k) / 2

---

DrGerard (Gérard Michon from Los Angeles, CA. 2000-11-18)
Let M be the sequence:   M₀= 0, M₁= 1, and  M_n+2 = M_n+1 - 2 M_n :
0, 1, 1, -1, -3, -1, 5, 7, -3, -17, -11, 23, 45, -1, -91, -89, 93, 271, ...
A closed expression for M_n is :   M_n = (2/Ö7) 2^n/2 sin (n atan Ö7 )
Considering this sequence modulo 8, it's clear that M_n cannot be equal to 1 if n > 2.  Prove that M_n can't be equal to -1 if n > 13.

As advertised, looking at the sequence modulo 8  (0, 1, 1, 7, 5, 7, 5, 7, ...) we see it can't go back to +1.  To prove that M never returns to -1 either for  n>13  is more difficult.  We need a few preliminary results about sequences obeying a second-order linear recurrence relation:

Lemma(s) :

If  U₀ = 0,   U₁ = 1,   and   U_n+2 = A U_n+1 + B U_n   then, for any sequence V such that V_n+2 = A V_n+1 + B V_n   we have:

V_n = V₀ U_n+1 + (V₁ - A V₀ ) U_n

(This is easily established by induction on n.)  In particular, with V_n = U_n+k+1 :

U_n+k+1   =   U_n+1 U_k+1 + B U_n U_k

Theorem :

With the notations introduced above, the following relation holds whenever  A Ù B = 1 (that is to say, when the integers A and B are coprime):

U_p Ù U_q   =   | U_pÙq |

The expression  x Ù y  denotes the greatest common divisor (GCD) of x and y  (also known as their highest common factor, HCF).

Proof (outline):   The case  p = q  is trivial.  We assume, without loss of generality, that  p>q  and we leave it to the reader to prove, by induction on q, that  U_q+1 Ù U_q  =  1.  We use the above lemma with  n+k+1 = p  and  k = q :

Up Ù Uq	=	( Up-q Uq+1 + B Up-q-1 Uq ) Ù Uq   =   ( Up-q Uq+1 ) Ù Uq
	=	Up-q Ù Uq

This parallels the founding relation   pÙq = (p-q)Ùq   of the subtractive version of Euclid's algorithm.  The conclusion is thus obtained by induction, from  U₀ = 0. 

This theorem shows that a term in the M sequence can only be a prime or a unit (±1) if its index is either prime or divisible only by indices corresponding to earlier units (±1) in the sequence.  Below 13 and besides  n = 1, the only such indices are 2, 3, 5, and 13.  We see by inspection that the pairwise products and the squares of these special indices do not correspond to a -1 value of M.  From this, we deduce that the lowest index n above 13 corresponding to a -1 value cannot be composite.  It must be prime.

Now, consider the sequence modulo 1171.  Its period is 1170, which is divisible by 3, 5 and 13.  The preperiod is of length zero (which is to say that the two residues 0 and 1 occur again consecutively, 1170 terms later).  Also, the only terms in the first period that are congruent to -1 correspond to the indices 3, 5 and 13.  This means that any index n for which M is equal to -1 must be of one of the following three forms (for some integer k):  1170 k + 3,  1170 k + 5,  or  1170 k + 13.  Each of these is divisible by 3, 5, or 13.  This implies that n cannot be prime, unless it's equal to 3, 5, or 13...  Therefore, the value -1 occurs only 3 times in the sequence M. 

This proof is only convincing if you actually check 1170+2 terms of the sequence modulo 1171.  There are many moduli like 1171  (including  1991, 3513, 5855, 5973, 6377, 8197, 8971 ...)  for which the period of M is a multiple of 3´5´13 and all the indices of terms congruent to -1 are divisible by 3, 5, or 13...

I first posted this problem on 2000-11-18 at the defunct "Answer Point" of ask.com, where it received no attention whatsoever.  The incentive which made me come up (finally!) with the above solution, on July 8, 2002, was provided by the interest the problem generated among the first math topics (2002-06-08) of the new AnswerPool.com board: Maiku, have you got the answer to DrGerard's "-1" question yet?  Working on it with a glass of Jack Daniels hasn't helped me one bit. [Coldfuse, 2002-06-10 on msn AnswerPoint]  I fear that the methods required are over my head.  [FlyingHellfish]. I've given it some thought, but I'm stuck.  [Maiku] I got lost really quickly.  [WiteoutKing] This one is a doozy!  [Coldfuse, 2002-07-02]  I have printed [this proof] for posterity [but] what's the significance of it all?   [Donaldekliros, 2002-07-13]

In any integer sequence which (like M) starts with 0 and 1 and obeys a second-order linear recurrence with coprime coefficients, a prime number can only occur at an index which is either prime or only divisible by another index where the sequence is ±1.  For example, Mersenne primes may only occur at  prime locations  [sic]  in the  Mersenne sequence  A000225.

Similarly, Fibonacci primes occur only at prime indices within the   Fibonacci sequence  A000045, with just one exception  (the number 3 occurs at index 4).

The sequence M itself happens to have the lowest [exponential] growth among such sequences  (we're ruling out 6 trivial cases with subexponential growth).  Heuristically, M is thus expected to be more densely populated with primes than any other sequence ot its kind.  The above result can be used to prove that there are only 9 composite indices  (4, 6, 8, 9, 10, 15, 25, 26, 65)  for which M is actually prime.  This makes it much easier to work out the sequence of all the indices n for which M_n is prime, namely:

4, 6, 7, 8, 9, 10, 11, 15, 17, 19, 23, 25, 26, 29, 31, 47, 53, 65, 67, 71, 73, 113, 127, 199, 257, 349, 421, 433, 449, 691, 761, 823, 991, 1237, 1277, 1399, 1531, 1571, 3461, 3697, 4933, 6199, 7351, 9551, 9719, 11681, 12037, 14629, 14951, 19079, 20327, 22549, 30517, 51511, 52813, 60923, 73943, 79687, 91249, 115321, 117017, 169493, 172411, 174413, 237053, 285631, 318751, 327433 ... (A101087)

---

(2008-05-06)   A  sequence of bits  with strange statistics
On the number of perfect squares between two consecutive cubes.

Let's count the squares between  n³  (included)  and  (n+1)³  (excluded):

n3	Perfect Squares	Count
0	0	1
1	1, 4	2
8	9, 16, 25	3
27	36, 49	2
64	64, 81, 100, 121	4
125	144, 169, 196	3
216	225, 256, 289. 324	4
343	361, 400, 441, 484	4
512	529, 576, 625, 676	4
729	729, 784, 841, 900, 961	5
1000	1024, 1089, 1156, 1225, 1296	5

Thus, there are at least two perfect squares between two (positive) consecutive cubes.  For large values of  n,  there are many more, of course.  Let's see how many:  Within  k  consecutive numbers located around some large integer  m,  we would expect to find about  k / 2Öm  perfect squares.  There are  k = 3n²+3n+1  numbers between  m = n³  and the next cube, so we may expect to find roughly 1.5 Ön  perfect squares among these.  This is, in fact, an excellent estimate since the actual count is always one of the two integers which bracket that quantity...

So, by subtracting the  floor  of  1.5 Ön,  from our counts of the perfect squares  (1, 2, 3, 2, 4, 3, 4...)  we obtain a particular sequence of zeroes and ones:

1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0...  (A140074)

A  closed formula  for this  bit sequence  is easy to obtain:

bn   =    ( n3 + 3n2 + 3n ) 1/2   -   n 3/2   +   1   -   3   n 1/2 2

This sequence of  pseudo-random  bits has particularly intriguing statistics.  Let's mention a few properties that have been observed by studying one million terms.  (Most of the following statements have yet to be formally proved.)

• 0 and 1 are equally likely. 
• Two adjacent bits are equally likely to match or mismatch. 
• If  j  is a nonzero number of positions between two bits,  then their values will match with probability  p(j).  The value of  p(1)  seems to be  2/3 and  p(j)  varies very slowly with  j  in what appears to be a long-period damped oscillation toward a limit which is (most probably) equal to 1/2.  The first minimum has a value of about  0.45  around  j = 400. 
• Other more complicated short-range correlations exist which are not fully accounted for by the above main effect.  For example, the patterns 0011 and 1100 are very rare.

---

(2007-12-02)   Binet's Formulas   (Euler c. 1730, Binet 1843)
The n-th term in a sequence obeying a second-order recurrence.

For two given constants  A  and  B,  consider the sequences  V  which obey

V_n+2 = A V_n+1 + B V_n

Those form a two-dimensional vector space, where each element is entirely determined by its "coordinates"  (V₀ , V₁ ).

For example, the (first part of) the above lemma can be construed as expressing any such sequence  V  as a linear combination of the two linearly independent sequences of coordinates  (0,1)  and  (1,A).  If the first of those is dubbed  U,  the second is simply the sequence whose  n-th  term is  U_n+1

Now, consider the following sequence  W :

W_n   =   z ⁿ       where   z ² = A z + B

The quadratic equation satisfied by  z  ensures that the sequence  W  belongs to the above vector space.  Usually, there are two distinct (complex) roots to that equation, yielding two linearly independent sequences of the above form, which can serve as a vector basis.  So, the n-th term of any sequence  V  is of the form:

V_n   =   x aⁿ  +  y bⁿ       where   (z-a)(z-b)  =  z ² - A z - B

In particular, for the sequence  U  (which starts with  U₀ = 0  and  U₁ = 1) :

Un   =	an - bn
	a - b

In the special case when  a = b   the above does break down, but we have:

U_n   =   n a ^n-1

Such explicit expressions are called  Binet formulas,  in honor of the French mathematician  Jacques Binet (1786-1856) X1804.  The term applies especially to the popular case of  Fibonacci numbers  (A=B=1) :

F_n   =   [ fⁿ - (-f)^-n ] / Ö5       where   f = (1+Ö5) / 2   =   1.61803...

---

(2007-11-29)   Cassini's Identity   (1680)

If  U₀ = 0,   U₁ = 1,   and   U_n+2 = A U_n+1 + B U_n   then:

V_n   =   U_n²  -  U_n+1 U_n-1   =   (-B)^n-1     for any positive integer  n

This relation is usually stated in the context of  Fibonacci numbers  (A=B=1) where it's known as  Cassini's identity.  It was discovered in 1680 by  Jean-Dominique Cassini (1625-1712)  and it has been rediscovered many times since, most notably by Robert Simson (1687-1768)  in 1753.

Proof :   Using  V₁ = 1,  the general case is established by induction on  n :

V_n+1   =   (A U_n + B U_n-1 ) U_n+1  -  (A U_n+1 + B U_n ) U_n   =   (-B) V_n      

---

(2007-11-29)   d'Ocagne's Identity
A generalization of Cassini's Identity due to  Maurice d'Ocagne.

U_n U_m+1  -  U_n+1 U_m     =     (-B)^m  U_n-m       [ where  n ≥ m ]

Proof :   For a given value of  m, let's consider the following function of  i :

W_i   =   U_m+i U_m+1  -  U_m+i+1 U_m

Since  W₀ = 0,  the above lemma shows that  W_i = W₁ U_i  where the value  W₁ = (-B)^m  is obtained immediately from Cassini's Identity.  

Curry's Paradox  by  Alexander Bogomolny

---

(2007-11-30)   Catalan's Identity   (1879)
Another generalization of Cassini's Identity.

U_n²  -  U_n+m U_n-m     =     (-B)^n-m  U_m²       [ where  n ≥ m ]

Like Cassini's Identity and d'Ocagne's identity, Catalan's Identity  is almost always stated  only  in the context of  Fibonacci numbers  (A=B=1).

Proof :   We'll apply Binet's formula to etablish the result when the two roots  a  and  b = (-B/a)  of the characteristic equation are distinct  (by continuity, this will also establish the result for the special case when they are equal).  To streamline notations, we prefer to deal with the sequence  V_n = (a-b) U_n

V_n   =   aⁿ - (-B/a)ⁿ

Well, let's just evaluate   V_n²  -  V_n+m V_n-m     :

a²ⁿ  -  2 (-B)ⁿ  +  (-B/a)²ⁿ  -  { a^n+m - (-B/a)^n+m }  { a^n-m - (-B/a)^n-m }
=     -  2 (-B)ⁿ  +  (-B)^n-m a^2m  +  (-B)^n+m / a^2m
=     (-B)^n-m  [ a^2m  -  2 (-B)^m  +  (-B/a)^2m ]
=     (-B)^n-m  V_m²  

---

Kirk Guidry (2002-03-30; e-mail) Faulhaber's Formula
[...] For a given p, how do you derive a formula for the sum of the p-th powers of the first n integers?  I have seen formulas for up to p = 10, but I still have difficulties deriving the formula for p = 5...

The general formula you are after is sometimes called Faulhaber's Formula and I'll give it to you below... However, your question is not really about formulas but rather about the methods which may be used to obtain them. I'll give you two such methods. The first one is elementary and can easily be used to solve your original concern about the formula for the sum of fifth powers. The second method is not so elementary (it involves the concept of generating functions) but is much more powerful and can be used to establish the general formula, which involves Bernoulli Numbers.

I still remember fondly the heroic elementary proof I devised for this very formula, at age 15 or 16, thus "discovering" this mysterious Bernoulli sequence, which I had never encountered before.

On 2002-12-24, Ben Orin wrote:     [edited text] [...]  I recall reading a derivation of this formula in my calculus book (as the trepidation induced by my first encounter with the Bernoulli sequence serves to vivify). I remember the dissatisfaction that ensued, and the prompt contrivance of the formula that would soon pacify me:   To sum the pth powers of the first n integers, note that this sum is a polynomial in n of degree p+1, which is thus fully specified by p+2 of its points.  Therefore, for each p, we may express the sum as a Lagrange interpolating polynomial.  For example: n p+2 { k }  å   m p   =     å å  m p Õ (n-j) / (k-j) m=1 k=1 m=1 j Î{1, 2 ... p+2}-{k}   Ben Orin Ventura College Dept. of Mathematics

In the above expression, the chosen range for k and j (namely {1, 2, ... p+2}) is an arbitrary example.  As Ben points out, any set of p+2 points would do.  This approach would establish the formula for p=5, say, by summing up 7 polynomials of degree 6 (each expressed as a product of 6 linear functions of n).  It fails to highlight the relation to the Bernoulli sequence.

Factored expressions for small values of the exponent p.

p	n å   m p   m=0
0	n+1
1	n (n+1) / 2
2	n (n+1) (2n+1) / 6
3	n2 (n+1)2 / 4
4	n (n+1) (2n+1) (3n2+3n-1) / 30
5	n2 (n+1)2 (2n2+2n-1) / 12
6	n (n+1) (2n+1) (3n4+6n3-3n+1) / 42
7	n2 (n+1)2 (3n4+6n3-n2-4n+2) / 24
8	n (n+1) (2n+1) (5n6+15n5+5n4-15n3-n2+9n-3) / 90
9	n2 (n+1)2 (2n6+6n5+n4-8n3+n2+6n-3) / 20
10	n (n+1) (2n+1) (3n8+12n7+8n6-18n5-10n4+24n3+2n2-15n+5) / 66
11	n2 (n+1)2 (2n8+8n7+4n6-16n5-5n4+26n3-3n2-20n+10) / 24
12	n (n+1) (2n+1) (105n10+525n9+525n8-1050n7-1190n6+2310n5                                     +1420n4-3285n3-287n2+2073n-691) / 2730
13	n2 (n+1)2 (30n10+150n9+125n8-400n7-326n6+1052n5                          +367n4-1786n3+202n2+1382n-691) / 420
14	n (n+1) (2n+1) (3n12+18n11+24n10-45n9-81n8+144n7+182n6-345n5                                 -217n4+498n3+44n2-315n+105) / 90
15	n2 (n+1)2 (3n12+18n11+21n10-60n9-83n8+226n7+203n6-632n5                         -226n4+1084n3-122n2-840n+420) / 48

Denominator sequence: 1,2,6,4,30,12,42,24,90,20,66,24,2730,420,90,48...

---

(2002-11-16)   Multiplicative Functions
An important class of arithmetic functions:

An arithmetic function (or arithmetical function) is a numeric function (with real or complex values) of the  positive  integers.  In the context of number theory, an arithmetical function  f  is said to be multiplicative if

f(ab) = f(a) f(b)     whenever the integers a and b are coprime.

If we rule out the function that's identically zero [as is usually done in this context] this implies that  f(1) = 1  for any multiplicative function  f.  Also, the value of a multiplicative function at zero (whenever it's convenient to define it) is always 0.

Ruling out the zero function from multiplicative functions ensures that a unique multiplicative function is specified by values attributed to the prime powers, as stated next.  Otherwise, there would be an ambiguity between the zero function and the Dirichlet unit (e) defined below.

To define a multiplicative function, it is sufficient to specify its value when the argument is the  positive  power of a prime ( pⁿ ).  Here are a few examples  (the first six are easy to compute  without  factoring the argument):

• Dirichlet unit:   e(pⁿ ) = 0   [e(k) = ë¹/_k û = 0^k-1  is zero  unless  k=1]
• Trivial character:   u(pⁿ ) = 1   [u(k) = 1,  for any positive integer k]
• Character modulo 2:   v(2ⁿ ) = 0,  v(pⁿ ) = 1  if p>2   [v(k) = k mod 2]
• Identity function:   N(pⁿ ) = pⁿ   [N(k) = k,  for any k]
• Indicator of the perfect squares:   f (p²ⁿ ) = 1   and   f (p²ⁿ⁺¹ ) = 0
• Greatest common divisor:   f (pⁿ )  =  gcd(a,pⁿ )   for a given number  a.
   
• Number of divisors (s_o   or  d) :   d(pⁿ ) = n+1.
• Sum of the divisors (s₁ ) :   s(pⁿ )  =  (pⁿ⁺¹ -1) / (p-1)
• Abundancy:   s_-1 (n)  =  s(n) / n   [A perfect number has abundancy 2.]
• Other divisor functions:   s_k (pⁿ )  =  (p^kn+1 -1) / (p^k -1)
  s_k (n)  is the sum of the k-th powers of the divisors of n.
   
• Möbius function:   m(p) = -1   and   m(pⁿ ) = 0  for  n>1.
• Euler's totient function:   f(pⁿ )  =  p^n-1 (p-1)
  f(n)  is the number of integers coprime to n, between 1 and n.
• GCD-sum function:   g(pⁿ )  =  (n+1) pⁿ - n p^n-1   [K.A. Broughan]
  g(n) is the sum of the GCD's with n of the first n integers.  [ g = f*N ]
• Dedekind's psi function:   y(pⁿ )  =  p^n-1 (p+1)   (A001615)
   
• Liouville's function:   l(pⁿ )  =  (-1)ⁿ   (A008836) 
• Squarefree part:   sf (p²ⁿ )  =  1   and   sf (p²ⁿ⁺¹ )  =  p   (A007913)
  The smallest multiplier which makes a number a perfect square. 
• Cubefree part:   cf (pⁿ )  =  p^{(n mod 3)}   (A050985) 
• Squarefree kernel  (or "radical") :   rad(pⁿ )  =  p   (A007947)
  The  radical  of an integer is the product of its distinct prime factors. 
• Enumeration of Abelian groups :   Abel (pⁿ )  =  p(n)   (A000688)
  In this,  p(n)  is simply the number of partitions of n. 
• Dirichlet inverse of the above :   f (pⁿ ) = 0  or (-1)^k  if  n = (3k² ± k)/2

The ordinary product of two multiplicative functions is itself a multiplicative function  (so is their quotient, assuming a divisor with only nonzero values).  A multiplicative function raised to the power of an integer is also a multiplicative function (so is the nonintegral power of a multiplicative function with positive real values).  Another very interesting type of multiplication, described next, also yields a multiplicative result from two multiplicative operands...

A multiplicative function whose value at the n^th power of any prime is a function of  n  only  is said to depend only on the  prime signature  of its argument.  Among the aforementioned functions, examples include the Dirichlet unit (e), the trivial character (u), the divisor count (d), the Möbius function (m), Liouville's function (l), and also the function which gives the number of distinct (i.e., non-isomorphic) Abelian groups of a given order.

---

(2002-11-16)   Möbius Inversion Formula  &  Dirichlet Convolution
The weird multiplication in the "Dirichlet ring" of arithmetic functions.  Multiplicative functions form a group under Dirichlet convolution.

If  f  is an arithmetic function, a function  F,  called the sum-function of f,  is defined by letting  F(n)  be the sum of the terms f(d) for all divisors d of n.

If  f  is multiplicative, so is its sum-function  F.

The function   f  may be retrieved from F using the so-called Möbius inversion formula, which states that f(n) is the sum of all terms F(d)m(n/d) for all divisors d of n, where m is the aforementioned Moebius function.

More generally, if f and g are two (multiplicative) functions, another (multiplicative) function F may be defined by letting F(n) be the sum of the terms f(d) g(n/d) for all divisors d of n.  The function F is the Dirichlet product  ( f*g )  of f and g :

F(n)   =   f*g (n)   =	å	f(d) g(n/d)
	d | n

F is multiplicative whenever f and g are, because any divisor of  n = ab (where a and b are coprime) is the product d = uv of two coprime factors u and v, respectively dividing a and b.  The same is true for  n/d = (a/u)(b/v).  Therefore:

F(ab)   =	å		å	f(u) g(a/u)  f(v) g(b/v)	=   F(a) F(b)
	u | a		v | b

Among  arithmetic functions,  the Dirichlet product (also called Dirichlet convolution) is a commutative and  associative  operation (the value at point  n  of  f*g*h  being the sum of all terms  f(u)g(v)h(w)  where u.v.w = n, for positive integers u,v,w).  Convolution is also distributive over ordinary [pointwise] addition.  Ordinary addition and Dirichlet multiplication thus endow  arithmetic functions  with the structure of a ring, called the  Dirichlet ring.

For Dirichlet multiplication, the neutral element is the  Dirichlet unit  (e)  defined above.  Any arithmetic function  f  for which  f(1)  is nonzero has a Dirichlet inverse  if we're considering arithmetic functions whose values are in a field.

If   f(1) = 1   (which is the case for all multiplicative functions)  an arithmetic function whose values are in a ring  (e.g., the ring of integers)  has a Dirichlet inverse with values in the same ring.  Thus, the Dirichlet product endows  multiplicative functions  with the structure of a group.

The Dirichlet inverse of the  trivial character  u  [u(n) = 1]  is the Möbius function m.  This is equivalent to the aforementioned  Möbius inversion formula :

If     F  =  u * f     then     f  =  m * F

Dirichlet Powers :

Dirichlet powers  m^[k]  of the Möbius function are easily defined (2004-11-27):

m^[k] (pⁿ )   =   (-1)ⁿ C(k,n)

This formula holds even if k is negative  [u = m^[-1]  or powers of u, like d = u*u].  More surprisingly, it's also true for fractional values of k...

It's not difficult to show that, for any positive integer q and any arithmetic function  f  with real positive  f(1)  there's a unique root (real positive at point 1) of which  f  is the Dirichlet q-th power.  This defines the Dirichlet 1/q power of  f  and the p/q power of  f  is the p-th power of that thing.  Any such Dirichlet power of a multiplicative function is itself a multiplicative function.

Dirichlet square root of the Möbius function :   m ^{[ ½ ]} (pⁿ)  =  (-1)ⁿ C(½,n)

m =	1	2	3	4	5	6	7	8	9	10	11	12
m[½] (m)	1	-1/2	-1/2	-1/8	-1/2	1/4	-1/2	-1/16	-1/8	1/4	-1/2	1/16

• A063524:   e   =   e*e   =   u*m   =   d*(m*m)   =   m^[0]
• A008683:   m(pⁿ )   =   resp. (-1, 0)   for   (n=1, n>1)
• A007427:   m*m(pⁿ )   =   resp. (-2, 1, 0)   for   (n=1, n=2, n>2)
• A007428:   m*m*m(pⁿ )   =   (-1)ⁿ C(3,n)
• A000012:   u   =   m*d   =   m^[-1]
• A000005:   d   =   u*u   =   m^[-2]
• A007425:   d*u   =   u*u*u   =   m^[-3]
• A007426:   d*d(pⁿ )   =   C(n+3,3)   =   (-1)ⁿ C(-4,n)   [A000292]

Other Special Examples :

Here are some relations involving the above standard multiplicative functions, featuring links to Sloane's  Encyclopedia of Integer Sequences :

• A000027:   N   =   u*f   =   m*s
• A000203:   s   =   u*N   =   d*f
• A000010:   f   =   m*N
• A018804:   g   =   f*N
   
• A055615:   N ^[-1] (k)   =   k m(k)
• A046692:   s ^[-1] (pⁿ )   =   (-p-1, p, 0)   for   (n=1, n=2, n>2)
• A023900:   f ^[-1] (pⁿ )   =   1-p     [Called reciprocity balance.]
• A101035:   g ^[-1] (p)   =   1-2p     and     g ^[-1] (pⁿ )   =   (p-1)² , if n>1.
   
• A038040:   N*N(k)   =   s*f(k)   =   k d(k)
• A034718:   N*N*N   =   s*g
• A007429:   u*s   =   d*N
• A007430:   d*s
• A007431:   m*f   =   m*m*N
• A007432:   m*m*f   =   m*m*m*N
• A029935:   f*f(pⁿ )   =   (n+1) pⁿ - 2n p^n-1 + (n-1) p^n-2

---

(2002-11-16)   Completely  Multiplicative Functions
The simplest type of multiplicative functions.

A function  f  is called completely multiplicative (or totally multiplicative) when  f(ab) = f(a) f(b)  always holds  (whether a and b are coprime or not)  in which case its Dirichlet inverse  g  is easily defined:   g(n) = m(n) f(n), since:

g*f (n)   =	å	m(d) f(d) f(n/d)   =   f(n)	å	m(d)   =   f(n) e(n)   =   e(n)
	d | n		d | n

The last equality holds for n=1 because  f(1)=1, and for n>1 because e(n)=0.

A completely multiplicative function  f  and its dirichlet inverse  g  are entirely determined by whatever values  f(p)  are chosen for prime numbers p, since:

f (pⁿ )  =  f (p) ⁿ     whereas     g(p) = - f (p)    &    g(pⁿ ) = 0,   if n>1

A multiplicative function which is zero for squares of primes, and higher powers of prime numbers, is thus the Dirichlet inverse of a totally multiplicative function.

Dirichlet Characters

A Dirichlet character modulo k  (also called  character to the modulus k )  is a complex-valued  completely multiplicative  function of period k, which vanishes whenever its argument isn't coprime with k.

There are exactly  f(k)  possible Dirichlet characters to the modulus k  (where f is Euler's totient function).  They are tabulated below for some small values of  k.

Except for k=3, k=4 and k=6 (which could have been tabulated together) we've spared the expense of separate tables for isomorphic structures.  Instead, we indicate at the bottom of the relevant tables how to relabel the columns for additional values of k  (a wildcard label '*' is to be used for unlisted values of n, which correspond to zero columns because they're not coprime with k).

For example, such an isomorphism exists among all the values of k (7, 9, 14 and 18) for which f(k)=6, as there's only one Abelian group of order 6.  On the other hand, the two distinct 4-line structures correspond to the two Abelian groups of order 4:  The cyclic group (k=5, k=10) and the Klein group (k=8, k=12).