No, 1 is not prime. This fact turns out to bemore than a mere "technicality":
The moderndefinition 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 conciseEnglish translation byJohn A. Wheeler, namely:
Time is defined so that motion looks simple.
Good mathematical definitions are designed to make theorems simpler to stateand easier to use. We exclude "1" from the realm of prime numbersmerely 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 anempty product equal to one? Why is anempty sum equal to zero?Well, the same principle applies: Any other definition would crippleMathematical 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 befar more awkward to use,and that's why we got rid of them: 1 is not prime. Period.
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 invertiblepolynomials[with real coefficients] are thenonzero constants (the polynomials of degree zero) which I'd like to call"prime", along with the polynomials of degree 1and those polynomials of degree 2 which have no real roots.
What you're describing are, in fact, the irreducible elements of aring;those which cannot be expressed as a non-trivial product(a product of two factors being considered trivial if at least one of themis a unit of the ring).
The concept ofirreducibility is more generally applicable than the conceptof primality, which is restricted to those rings where factorizationsinto irreducible elements are essentially unique (which is to say that,in two such factorizations, every factor of one equals some factor of the othermultiplied by an invertible element of the ring). One example where factorizations arenot unique is the set ofcomplex numbersof the form a + ib5,wherea andb are integers. In this, the number 6 has two unrelated factorizations into irreducible factors:
6 = 2 3 = (1 +i5)(1i5)
There are onlynine discrete "grids" of complex numbers where factorizationsare unique (related to the nineHeegnernumbers: 1, 2, 3, 7, 11, 19, 43, 67 and 163) most notablytheGaussian integers and theEisenstein 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 whichare not invertible and have somead hoc additional featurewhich ensures factorization unicity. (We keep as primes onlypositive numbersin the case of integers, or polynomialswith leading coefficientsequal 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.
(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 compositenor prime (seeprevious article). The onlynatural integerswhich are neither prime nor composite are 0 and 1.
The term "irreducible" is favored todenote something that'snot composite, but it's prudent to state exactlywhat 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 needprior explanations...
"Rectangular Number" is a deprectaed term :
In Number Theory, the deprecated term rectangular was sometimes used as synonymous for composite in the above sense.
However, Rectangular numbers were also sometimes understood to denote products of two consecutive integers, which were of special interest to the ancient, along with their halves called triangular numbers, a term we still usefor integers of the form n(n-1)/2.
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) How does the concept of primality generalize beyond ordinary integers?
The so-calledGaussian integers arecomplex numbers of the form a+ib, wherea andb are integers.
Gauss showed that every Gaussian integer uniquely decomposes into a unit (one of the four invertibleelements +1, -1, +i, -i ) and a product of irreducible elements fromthe positive quarter of the complex plane, calling a Gaussian integer x+iy positive when -x < y < x+1 .
This is entirely analoguous to the FundamentalTheorem of Arithmetic whereby every ordinary integer is a productof an invertible unit (namely, its sign; +1 or -1) and a unique decomposition of positive primes.
Note that 1+i is the onlypositive Gaussian prime whose conjugateis not apositive Gaussian prime as well (since 1-i = (-i)(1+i) isn'tpositive).
Ordinary prime integers are not necessarilyprime among Gaussian integers. Actually, a prime integer is a Gaussian prime if and only if it's congruentto 3modulo 4. In particular,2 and 5 are not Gaussian primes:
2 = -i (1+i)2 5 = (2+i) (2-i)
Note that the above factorization of 2 (involving the "unit" -i) is indeed the proper "unique" one, since themore obvious factorization (1+i)(1-i) uses a Gaussian integer which is notpositive 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 233. 86 is 243. 125 is 53. 214 is 2107.
The factorization of their least common multiple (LCM) is obtained by using for each primethe highest exponent that appears in each of the above factorizations. The result is, therefore:
Factoring large numbers is often very difficult,so it's not a realistic option. (In fact some modern schemes inpublic key cryptography do rely on the factthat it's difficult to retrieve two large prime numbers from their product.)
To find the least common multiple (LCM) of two large numbers, compute their greatest common divisor (GCD)usingEuclid'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:
This type of factorization is often called Aurifeuillian (sometimes also spelledAurifeuillean) in honor of the French mathematician [Léon François] Antoine Aurifeuille (1822-1882;X1841) whose factorization methods were applied by Henri Le Lasseur de Ranzay (an enthusiastic amateur who ownedthe Château du Bois-Hue in Saint-Joseph du Portricq,near Nantes). Le Lasseur routinely shared his factorizations withEdouard Lucas (1842-1891) and Eugène Catalan (1814-1894; X1833). Another amateur of that era was Charles Henry Gauss (1845-1913) grandson of the great Carl Gauss (1777-1855).
Aurifeuille once earned a living teaching high-school mathematicsinToulouse. and authored three mathematical textbooks as L. Aurifeuille :
Cours de géométrie élémentaire, with C. Richaud (1847).
Traité d'arithmétique, with C. Dumont (1859).
Traité de géométrie élémentaire, with C. Dumont (1860).
With b = 1, the above identities can be used to break up 22(2n+1) +1 and 33(2n+1) +1 into two or three nearly equal factors :
22(2n+1) + 1 =
(22n+1 2n+1 + 1) (22n+1 + 2n+1 + 1)
33(2n+1) + 1 =
(32n+1 3n+1 + 1) (32n+1 + 1) (32n+1 + 3n+1 + 1)
In 1871, Aurifeuille himself used the first of those (with n = 14) to obtain immediately the following celebrated factorization:
258 + 1 = 536838145 . 536903681
The second number is prime. The first one factors as 5 . 107367629
That very factorization had been painstakingly obtainedby the retired Parisian mathematician Fortuné Landry(1798-1895) after casting out the factor 5. Summarizing his factorizations in 1869, Landry wrote:
1gave as much trouble and labor as that of 258 + 1
This number is divisible by 5; if we remove this factor,we obtain a number of 17 digits whose factors have 9 digits each. If we lose this result, we shall lack the patience and courage to repeat all calculationsthat we have made and it is possible that many years will pass before someone elsewill discover the factorization of 258 + 1
On July 12, 1880, the 82-year old Landry earned a permanent spotin the history of numbers by presenting his factorizationof the sixth Fermat number, without saying how he did it (there's no Aurifeuillian shortcut):
F6 = 2 64 + 1 = 274177 . 67280421310721
The primality of the second factor was subsequently proved by Edouard Lucas (1842-1891). Besides Mersenne primes, that 14-digit number is the largest prime ever discovered without the help of a computer.
(2020-05-28) Factorizations Here are some algebraic factorizations, amongmany others.
( x + 1 ) × (x2 x + 1) ×(x4 x3+ x2 x + 1) × (x8+ x7x5 x4 x3+ x + 1 )
With a = 11, one of the above says that (1133 + b22) / (113+b2) splits into two large factors (bothprime when b = 23). It's divisible by 23 when n isn't (courtesy of Fermat'slittle theorem, since 1133 equals -1 modulo 23) unless b is 7 or 16 modulo 23 (as the denominator is then a multiple of 23).
It's typographically simpler to express such identities in terms of the ratio x = a/b. Large values of x (in particularwith b = 1) yield very even splitsinto two factors which are occasionally prime. For example:
Those two factors are respectively P17(-24) and P17(24) where: P17(x) = A17( 17 x2) + (17 x) B17( 17 x2) with A17(y) = 1 + y (9 + y (11 + y (-5 + y (-15 + y (-5 + y (11 + y (9 + y))))))) B17(y) = 1 + y (3 + y (1 + y (-3 + y (-3 + y (1 + y (3 + y))))))
Tiny values of x (in particularwith a = 1) also yield even splits, but certain intermediate values of the ratio a/b can give very lopsided results.
(2006-02-05) Euclid's Algorithm gives the greatest common divisor dof two integers p and q, and also yields two integersu and v such that up + vq = d.
In the so-calledEuclidean division of two positive integers (thedividend n and the divisor p) thequotient q is the largest integer which goes p timesinto n. This leaves a nonnegativeremainder r less than p. In other words:
n = p q + r ( 0 r < p )
Euclid's Algorithm is an iterative procedure based on the remarkthat 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 thegreatest common divisor (GCD)of the original two numbers. Here's how Euclid's algorithm yields 3 as the GCDof 5556 and 1233:
5556 =
1233 . 4 +
624
1233 =
624 . 1 +
609
624 =
609 . 1 +
15
609 =
15 . 40 +
9
15 =
9 . 1 +
6
9 =
6 . 1 +
3
6 =
3
. 2 + 0
An important remark (expandedbelow) is thatwe may express the resultinggreatest common divisoras a linear combination of the original two numbersby tracing back the steps in Euclid's algorithm (proving Bézout's lemma).
Subtractive Version of Euclid's Algorithm (anthyphairesis) :
The GCD of two integers may also be worked out by repeatedly replacingthe 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 divisionrather than mere subtraction) but it can be convenientin proofs and other theoretical arguments (seebelow).
(2006-02-05) Thegreatest common divisor (d) of two integers (p and q) isa linear combination of them: d = up + vq (where u and v are integers).
The canonical solution is obtained by tracing back the steps ofEuclid's algorithm which compute theGCD of p and q. With the above example (p=5556, q=1233):
Note that u and v are not uniquely defined by Bézout's identity, since:
u p + v q = (u+kq) p + (v-kp) q
However, the pair obtained from the above procedure is well-defined:
Bézout Coefficients and Bézout Function :
A careful backtrack of Euclid's algorithm yieldsthe definition of a unique function of two variableswhich gives the so-called Bézout coefficients (u and v) without the aforementioned ambiguity as the simplest possible solution. Formally, sucha 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). (For the sake of expediency, we've retained bezout (x, x) = 0 instead.)
Forsaking thatad hoc exception, here's how to define bezout on a TI-92, TI-89 orVoyage 200.
The above algorithm remains valid when the arguments of bezout are not integers (because the same is true ofthe mod function which it uses). Luckily, this is consistent with the generalizedGCD function presented in thenext article.
OnHewlett-Packard calculators (HP-49g+, HP-50g) the above bezout function for integerscan simply be given the following definition:
« IEGCD ROT DROP2 »
The acronym IEGCD (probably) stands for Integer Euclid Greatest Common Divisor [Algorithm ] which gives a clue that the result is indeed precisely what the abovedescribes However, the terse wording of HP's technical documentation would, by itself,merely tell that the above three-instruction program yields what we need modulo y.
The above expression may serve as a good introduction to the universally accepted conventionintroduced by Hermann Minkowski (1864-1909) whereby an operator defined for two elements is also defined when either formal operandis a set of such elements (or when both are). The result is then the set of all possible operations between an element from the firstformal operand and an element from the second one. Those things are called Minkowski sums, Minkowski products or Minkowski operations.
Thus, n is the set of all multiples of the integer n. Likewise, he sum on the left-hand-side is the set of all sums where one addend is a multiple of m and the otheris a multiple of n. Bézout's lemma states that those sums are precisely the multiples ofthe greatest common divisor of m and n.
(2007-05-07) Extending the definition of a GCD beyond the realm of integers.
The greatest common divisor (GCD) normally definedamong integers (as computed byEuclid's algorithm)has two fundamental properties:
gcd ( xp , xq ) = x gcd(p,q)
x / gcd(x,y) and y / gcd(x,y) aretwocoprimeintegers
Both properties are retained by defining the GCD of two fractions as the GCD of theirnumerators divided by theLCM of their denominators. Software packages which support exact rational arithmetic (in advancedhandheld calculatorsand elsewhere) normally use this definition toextend the range of their GCD function beyond integers. Rightly so...
gcd (2/3 ,1/2 ) = 1/6
This allows the GCD of twocommensurablenumbers to be defined as well: Two real numbers arecommensurableiff they are proportional to two integers; Their GCD is simply the GCD of those integers multiplied by the common scaling factor.
gcd (2/3 ,/2 ) = /6
The GCD of two numbers that are not commensurable isbest defined to be zero. This makes the second fundamental property listed above fail gracefully (as it would entail forbidden divisionsby zero). With this convention, the celebrated irrationalityof 2 can be stated compactly. So can theepitaph of Roger Apéry (the irrationality ofApéry's constant).
gcd ( 1 , 2 ) = 0 gcd ( 1 , (3) ) = 0
A clue of theincommensurability of two numbers x and y may take the form of a small upper bound on their GCD. Something like:
gcd ( x , y ) < = 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 :
xn = 1 + 2 n yn = 4 3 n
Any such equation whose unknown variables are required to be integers is calleda Diophantine equation (as they were much studied by Diophantus of Alexandria, who died at the age of 84 around AD 284). Here's how to solve for x and y any linear Diophantine equation, like:
ax + by = c
First, compute the Greatest Common Divisor (GCD) d of a and b, usingEuclid's Algorithm. In the process, you will obtain two integers u and vsuch that au +bv =d(as explainedabove, the existence of such a pair of integers is a result commonly known asBezout's lemma).
Since the LHS of the equation is divisible byd, the RHS must be also. Therefore,d must dividec, or else the equation has no integer solutions. Let's assume, then, that c is equal to dc'. Using the above expression ford, 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 producta' (x-uc').Sinceb' anda' arecoprime,b' must divide(x-uc'). In other words, there exists an integer k such that x is given by the first equationof the following pair. The second equation, giving y, is obtained bysubstituting that value of x in the original equation:
x = uc' + kb' y = vc' - ka'
All solutions are thus explicitly given in terms of an arbitrary integer k
In the proposed example, a = 1024, b = -15625, c = 8404. So, we have:
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 givesall the integer solutions of 1024 x - 15625 y = 8404 in terms of a single integer parameter k :
x = uc' + kb' = -40137504 - 15625 k y = vc' - ka' = -2630452 - 1024 k
To make the constants as small as possible, we introduce n = -2569 - k. This way, we obtain canonical formulas where nonnegative solutionsfor x and y correspond to nonnegative values of the parameter n:
x = 3121 + 15625 n y = 204 + 1024 n
Indeed: 1024 ( 3121 + 15625 n ) 15625 ( 204 + 1024 n ) = 8404
Before negative numbers became commonplace (in theRenaissance) most ancient mathematicians were ultimately interested only in nonnegative solutions to this type of puzzles. To us nowadays, this can be disposed of quickly at the end, in the form of an afterthought (as we did above). To them, it would have been a burden to devise a sequenceof steps where a greater number was never subtracted from a smaller one.
When devising recreational puzzles, it can be amusing to engineer linear Diophantineequations which have only one positive solution. To do so, start with canonical solution formulas which clearly give negativesolutions for any nonzero value of the parameter n andwork your way backward to eliminate n and obtain a linearequation which encodes a unique pair of nonnegative integers.
(2006-02-03) (Pythagorean Triplets) Solutions, incoprime positive integers, to the equation x2 + y2 = z2
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 allcoprime solutions are ofthe following form (the special case v=1 was given byArchimedes).
( u2-v2) 2 + (2uv) 2 = ( u2+v2) 2
x and y can't both be odd (otherwise, the sum of their squares would be 2 modulo 4, which can't be a square). So, one of them must be even. WLG, we may thus assume that y is even. Let y = 2a :
4a 2 = (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).As their product is a square (a2) both of them are. So, there are two integers u and v such that:
z+x = 2u2 and z-x = 2v2, which implies y2 = (2uv)2
Conversely, the above yieldscoprime solutions whenever u and v are coprime,without being both odd... Below are the smallest such coprime solutions (arguably, the trivial solution y = 0, does belong here).
The numbers that are expressible in many ways as sums of two squares (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 ? [Aproper divisor is a positive integer less than the dividend which divides evenly into it.]
Consider the factorization into primes of the numberN = AaBbCc...
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.
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 questionmust 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:
N is the product of 3 distinct primes.
N is the product of a prime by the cube of another prime.
N is the seventh power of a prime.
There are a lot more solutions this time:
The first class of solutions starts with etc.
The second class starts with etc.
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 orderthe products of 3 distinct elements from a given list of increasing integers.)
(2010-01-25) The only positive integers witn an odd number of positive divisors.
With the notations introduced in theprevious section, the totalnumber of the positive divisors of N = AaBbCc... is: (1+a) (1+b) (1+c) ...
This product is odd only when all its factors are, which is to say that all multiplicities (a, b, c...) are even. This happensiff N is a perfect square.
Anonymous query, via Google (2010-10-09) For what numbers is the product of all divisors a perfect square?
If p is a prime factor of N, then N = pk Q where Q iscoprime with p (k is the multiplicity of p in N). Let m be the number of divisors of Q.
The number of divisors of N is d = (1+k) m. Exactly m of those are divisible by p with any prescribedmultiplicity between 0 and k. Therefore,the multiplicity of p in theproduct of all the divisors of N is:
m.0 + m.1 + m.2 + ... + m.k = m k (k+1) / 2 = kd / 2
The product of all the divisors of N is thus a perfect squareif and only if all such quantities are even, which is to say that kd is a multiple of 4 for the multiplicity k of every prime factor of N.
If d is odd (whichmeans that N is a perfect square) then the above is only satisfied when every multiplicity k isa multiple of 4, which is to say that N itself is a fourth power.
If d is singly even (which happens when one prime factor has a multiplicity congruentto 1 modulo 4 while all the others have even multiplicities) then the above condition fails for the factor with odd multiplicity.
When d is a multiple of 4, the above condition clearly holds. This happens when N has at least two prime factors with odd multiplicitiesor one factor with multiplicity congruentto 3modulo 4 (as k+1 is divisible by 4, so is d).
All told, the product of all the divisors of N is a perfect square if and only if one of the following three conditions holds:
N is a fourth power.
N has at least two prime factors with odd multiplicities.
N has a prime factor with a multiplicity congruentto 3modulo 4.
(J.E. of Lubbock, TX.2000-10-25) Aperfectnumber 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?
(n)ofall the divisors of nhas the desirable property of beingmultiplicative(which is to say that(pq) = (p)(q), whenever p and q arecoprime). A perfect number may thus (also) be defined as an integer n such that(n) = 2n. The factorization into primes of any number n consists ofrelatively prime factors of thetype pm (p is prime and m is itsmultiplicityin the factorization);(n)/n is the product of thefactors(pm+1-1)/(pm+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 toNicomachus of Gerasa (c.AD 60-120 ;Gerasa is nowJerash, Jordan). Nicomachus discusses the topic in his Arithmetike Eisagoge ("Introduction to Arithmetic", c. 100) an influential work which includes multiplication tablesand the earliest known use of Arabic numerals (Indiandecimal 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. Some of his "results" are just guesses. Wrong guesses tainted the study ofperfect numbersfor centuries!
Euler proved that allevenperfect numbers are of the form given by Euclid, namely: 2p-1(2p-1), provided(2p-1) is prime. Such a prime number (i.e., one unit less than a power of 2) is known as a Mersenne prime.
Are there any odd perfect numbers?
Nobody knows... Finding an odd perfect number, or showing that none exist,is one of theoldestunsolved mathematical problems.
I think an odd perfect number can be found. RenéDescartes (1638)
The existence of an odd perfect number would be little short of a miracle. James Joseph Sylvester (1888)
Anodd perfectnumber wouldnecessarily be congruent to 1, 9, 13 or 25 modulo 36 (Touchard, 1953) and would have the following properties:
At leastthree prime factors greater than 100. [Iannucci 2000]
At leasttwo prime factors greater than 10000. [Iannucci 1999]
At leastone prime factor greater than 108. Jenkins had established a lower bounded of 107 in2003. The same method was used by Goto and Ohno in 2006 to improve the lower bound to108.
At least one prime-power greater than 1020. [Cohen 1987]
At least 9different prime factors. The number of different prime factors was first proved to be at least 4 byBenjamin Peirce in 1832 (The Mathematical Diary,2, XIII, pp. 267-277) and, independently,by V.A. Lebesgue (1844). It was shown to be at least 8 by Chein (1979) and/or Hagis (1980). Nielsen improved this to 9 in 2006.
Multiplicities whose sum has beenshown to be at least 29 by Sayers (1986), at least 37 byIannucciand Sorli (2003) and at least 47 byKevinG. Hare (2004). Hare improved successively his own record to 69, 71, 73 and 75 in2005 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 exceed24k[Nielsen 2003].
(2000-10-25) The ongoing search for prime numbers of the form 2p 1
In his honor, the number 2n-1 is called the nthMersenne number (thezeroth Mersenne number is thus zero). When a Mersenne number is prime, it's called a Mersenne prime. Mersenne primes are tied to perfect numbers.
Fr. Mersenne's first two mistakes were to omit exponent 61 from his mysterious listand to include exponent 67, which was shown to yield a composite Mersenne number byEdouardLucas, around 1875 (well beforeFrank Nelson Cole (1861-1926)heroicallyfactorized it, in 1903).
As of October 2022, only 51 Mersenne primes are known, corresponding to the following values of theexponent p. (These are necessarily prime, because if d divides p then 2d-1 divides 2p-1.)
Of these, the last two (n = 31 and 61 in the above formula)were respectively discovered by Leonhard Euler (1772) andIvan Mikheevich 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 shownto 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 (theLucas-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.
(2009-04-27)
Theabundancy (n) = -1(n) = (n) / n of a perfect number is 2. More generally, a number whose abundancy is an integer is variously called a multiperfect number (MPN) or a pluperfect number. The competing locution "multiply perfect" (used as early as 1907 by R.D. Carmichael) is not recommended ("multiply" would rhyme with "triply", not "apply"). Multiperfect numbers whose abundancy is greater than 2 are called proper multiperfect numbers.
In spite of mounting computational evidence that some of the lists tabulated beloware complete,Walter Nissenpoints out that this need not be so, even for our tiny listof six 3-perfect numbers. Indeed,if was a [ huge ] odd perfect number, then the abundancy of 2 would be (2) () = 3.
In 1925, Paul Poulet (1887-1946) reported the first two 8-perfect numbers; they're both multiples of 262 with42 and 43 distinct prime factors, respectively.
As of 2010, the only known number n = 2.5185... 101906 for which (n)/n = 11 is amonster of 246 prime factors, found byGeorge F. Woltmanon 2001-03-13:
Here are other numbers which divide twice the sum of their divisors:
Thanks to Michel Marcus for contributing to the extensions of the above tables [ 11/2 |13/2 ]. Note that, if the prime 2q-1 isn't a factor of n, then:
(2q-1) -1( n (2q-1) ) = 2q-1(n)
Thus, if the abundancy of n (2q-1) happens to be q, then the abundancy of n is equal to q-1/2. This way, a few hemiperfect numbers are obtained from some multiperfect numbers. For example, with 2q-1 = 5 the above applies to the three 3-perfect numbers which are multiples of 5 (since none of them is a multiple of 25) namely120, 459818240 and 51001180160 and yields the three known numbers of abundancy 5/2, namely: 24, 91963648 and 10200236032.
Hemiperfect numbers of abundancy 5/2, 7/2, 11/2, 13/2, 17/2...are likewise obtained from some multiperfect numbers of abundancy 3, 4, 6, 7, 9...
This doesn't work for 15/2 because 15 is not prime, but Michel Marcus has observed (2009-09-15) that a different transformation can be used to obtain numbers of abundancy 15/2 fromany known number 7n of abundancy 7 when n iscoprime with 7 and 19. Indeed, for such acofactor n, we have:
The above replacement of the partial factorization 71 190 by 72 191 is one exampleof what's known, in this context, as a substitution. Michel Marcus has used such substitutions extensively tounearth large numbers with simple abundancies... Conversely, some nontrivial substitutions were discovered as a byproduct of that search. The following example (which transforms a number of abundancy 8 into a number of abundancy 15/2 ) was obtained byMarcus on 2009-09-28:
-1() /-1() = 16/ 15
A cofactor of that substitution (coprime with 11, 17, 37, 43, 67, 79, 179, 631 and 3221) whichyields numbers of abundancies 8 and 15/2 (225 digits) is:
Michel Marcus first found (the hard way) a 97-digit integer of abundancy 15/2 on July 4, 2009. He then found many more, including the following 89-digit number of abundancy 15/2, discovered on August 15, 2009 :
As of 2010,the smallest known 9-perfect number is a 287-digit number x which is divisibleby 17 only once (it was discovered by Fred W. Helenius in 1995). So, the number n = x/17 (which has 286 digits) is an example of a number ofabundancy 17/2 (the smallest known one has 191 digits).
By contrast, 19 never appears withmultiplicity one in any known 10-perfect number. We don't know any number of abundancy 19/2 (yet).
(G. S. of Farley, IA.2000-11-15) How can a power , like 1217, be calculatedwithout actually multiplying the whole thing out? [ as in ... ]
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 librarysince 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 table backwards to find that 0.3460804 is the log of 2.2186,so that your result is about2.2186.
Second way: Use repeated squaring.
To obtain an exact result without going through 16 multiplications,you may notice that an even exponent meanssquaring the result for an exponent that's only half as big (so that you "pay" the cost of just one multiplication to halve the exponentinstead 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 ofjust one extra multiplication. (Can't you?)
With exponent 17, squaring four times with just one"extra" multiplication will do the trick :
12 17 = (((12 2)2)2)2 12
In other words:
12 2 = 144,
144 2 = 20736,
20736 2 = 429981696,
4299811696 2 = 184884258895036416
Multiply this by 12 to obtain the answer:12 17 = 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 often use the above approach to compute anmodulo n, for very large values of the exponent n. Withmodular arithmetic, we don't have to deal with larger and larger resultsbecause, at each iteration,we only consider the remainder of the division by m, which remains less than m.
(Steve of Somerville, MA.2000-11-16)(A000041) Howmany 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're asking is the "number ofpartitions of 15",which is often called p(15). Apartition of n is a collection of positiveintegers (not necessarily distinct) whose sum equals n.
This has been studied at length by the best mathematical minds of all times, including theIndian geniusS. Ramanujan (1887-1920) whocollaborated withJ.H. Hardy (1877-1947) to come up witha fantastic exact formula for thepartitionfunction 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 1936, Rademacher gave a formula for p(n) as a convergent series.
The number of partitions p(n) is the coefficient of xn in the expansion of
This coefficient is indeed obtained by counting the number of ways there isto choose an exponent multiple of 1 from thefirst 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 ofall factors (1-xn) where n ranges over the positive integers. (SeeEncyclopediaBritannica.)
Among many other similar essays, we recommend a recentlecture 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 program that will compute the number p(n) of partitions of nas 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 mcoefficients in the product of all the series(1+xu+x2u+x3u+ ...).(arrays "a" and "p" hold the coefficients of the resulting polynomials):
INPUT mDIM a(m),p(m)FOR i = 0 TO m: p(i) = 1: NEXT iFOR 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 jNEXT uREM At this point, p(n) is the number of partitions of nREM (for any n between 0 and m).
The following program achieves the same result much faster !
input mdim p(m)p(0) = 1for 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) = snext i
The above relies on the connection of partitions to both typesof pentagonal numbers (A000326andA005449) which also translates into a simple way to compute theDirichlet inverse(A129667)of thepartition-based multiplicative sequence which enumerates distinct Abelian groups (A000688). All of this ultimately rests on the following (nice) statement proven by Euler...
Euler'sPentagonal Number Theorem :
n = 1
( 1 x n) =
k =
(-1)k x (3k2+k) / 2
(2011-01-21) Ken Ono's great on the partition function.
10 years after I enthusiastically recommended a lecture of his in theabove introduction,Ken Ono made headlines on this topic by giving a formula for the partition function!
Ono appears modestly as the last author of two papers just publishedby the American Institute of Mathematics. The references below give links to the whole papers,a video by Ono and links to the press releases and blogsthat are helping break the news (in chronological order).
by Amanda Folsom, Zachary A. Kent, and Ken Ono (21 January 2011) That result was immediately given ashorter proof by Frank Calegari (bef. 2011-01-27).
by Jan Hendrik Brunier and Ken Ono (21 January 2011)
Lecture delivered on 2011-01-21 by Ken Ono (2011-01-27)
DrGerard (Gérard Michon from Los Angeles, CA.2000-11-18) Let M be the sequence M0= 0, M1= 1, and Mn+2 = Mn+1 2 Mn 0, 1, 1, , -3, ,5, 7, -3, -17, -11, 23, 45, , -91, -89, 93, 271, ... TheBinet formulaforMn is : Mn = (2/7) 2n/2sin (n atan 7 ) Considering this sequence modulo 8, it's clear thatMn cannot be equal to 1 if n > 2. Prove thatMn can't be equalto if n > 13.
As advertised, looking at the sequence modulo 8 (0, 1, 1,, 5, , 5, , ...)we see it can't go back to +1. To prove that M never returns to -1 either for n13 is more difficult. We need a few preliminary results about sequences obeying a second-orderlinear recurrence relation:
Lemma(s) :
If U0 = 0, U1 = 1, and Un+2 = A Un+1 + B Un then, forany sequence V such that Vn+2 = A Vn+1 + B Vn we have:
Vn = V0 Un+1 +(V1 A V0) Un
(This is easily established by induction on n.) In the special case where Vn = Un+k+1 we obtain :
Un+k+1 = Un+1 Uk+1+ B Un Uk
Theorem :
With the notations introduced above, the following relation holds whenever A B = 1(that is to say, when the integers A and B arecoprime):
Up Uq = | Upq |
The expression x y denotes thegreatest common divisor (GCD) of x and y (also known as theirhighest common factor, HCF).
Proof (outline): The case p = q is trivial. We assume,WLG, that pq and we leave it to the reader to prove, by induction on q, that Uq+1 Uq = 1. We use the above lemma with n+k+1 = p and k = q :
This theorem shows that a term in the M sequence can only be a primeor 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 indicesdo not correspond to a value of -1 for M. From this, we deduce that thelowest index n above 13 corresponding to a value of -1 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, theonly terms in the first period that are congruent to -1 correspond tothe indices 3, 5 and 13. This means that any index n for which M is equal to -1 must be of one of the followingthree 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 termsof 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 ofand 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,onJuly 8, 2002,was provided by the interest the problem generated among the first math topics(2002-06-08)of the newAnswerPool.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 onmsnAnswerPoint]
I fear that the methods required are over my head.[FlyingHellfish].
I've given it some thought, but I'm stuck. [Maiku]
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 recurrencewithcoprime coefficients, a prime number can only occur at an indexwhich is either prime or only divisible by another index where the sequence is1. For example,Mersenne primesmay only occur at prime locations [sic] in the Mersenne sequenceA000225.
Similarly,Fibonacci primes occur only at prime indices within the Fibonacci sequenceA000045,with justone exception (the number 3 occurs at index 4).
The sequence M itself happens to have thelowest [exponential] growth among suchsequences (we're ruling out 6 trivial cases with subexponential growth). Heuristically, M is thus expected to be more densely populated with primesthan 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 nfor which Mn is prime, namely:
(2009-06-29) A standard sequence has only finitely many primes of composite index.
Let's generalize theabove result to any Lucas sequence of the first kind withcoprime coefficients (which we may call a standard Lucas sequence, for short). By definition, such a sequence starts with 0,1and obeys the following recurrence relationfor two coprime integers A and B :
U0 = 0, U1 = 1, Un+2 = A Un+1 + B Un
This makes the abovelemma andtheorem hold. We shall use the same approach as in theprevious articleto prove that the values -1 amd +1 appear only finitely manytimes (the advertised result follows from that fact, as previously explained).
(2008-05-06) On the number of perfect squares between two consecutive cubes.
Let's count the squaresbetween n3 (included) and (n+1)3 (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 aremany more, of course. Let's see how many: Within k consecutive numbers located aroundsome large integer m, we would expect to find about k / 2m perfect squares. There are k = 3n+3n+1 numbers between m = n and the next cube, so we may expect to find roughly1.5 n perfect squares amongthese. This is, in fact, an excellent estimate sincethe actual count is always one of the two integerswhich bracket that quantity...
So, by subtractingthe 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:
A closed formula for this bit sequence is easy to obtain:
bn =
(n3 + 3n2 + 3n) 1/2
n3/2
+ 1
n1/2
This sequence of pseudo-random bits has particularlyintriguing statistics. The properties listed below have been conjecturedby observing one million terms. In particular, for a given integer j, we may study the value of bn+j knowing the value of bn+j and conjecture that they match with a definite probability p(j) as n tends to infinity.
Conjectured correlations for a given spead j
bn
Prob ( bn+j = 0 )
Prob ( bn+j = 1 )
0
p(j)
1-p(j)
1
1-p(j)
p(j)
Conjectures about the values of p(j) :
p(0) = 1/2 (values 0 and 1 are equally likely).
p(1) = 1/2 (two adjacent bits are equally likely to match or not).
p(2) = 2/3 (bits one place apart match twice more often than not).
p(j) varies slowly with j in what appears to be a long-period damped oscillation with a limit of 1/2 (the first minimum having a value of about 0.45 around j = 400).
Other short-range correlations exist which are not accounted for by the above. For example, the patterns 0011 and 1100 are very rare.
In spite of the many open questions thus raised,this sequence serves as an example of a "natural" pseudo-random sequencewhich unexpectedly fails to obey long-range randomness for mysterious reasons.
Let's draw a bold analogy with a fundamental open question: TheRiemann Hypothesis (RH) can be construed asa belief that the sequence ofprime numberslacks a certain type of long-range order. I offer the above example as a stern warning that the opposingbelief is tenable, in spite of currentheuristic "evidence". The fashionable temptation to assume that RH is trueought to be resisted...
(2007-12-02) 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
Vn+2 = A Vn+1 + B Vn
Those form a two-dimensionalvector space, whereeach element is entirely determined by its "coordinates" (V0 , V1 ).
For example, the (first part of) the abovelemma can be construedas expressing any such sequence V as a linear combinationof the two linearly independent sequences of coordinates (0,1) and (1,A). If the first of those is dubbed U, the second one is simply the sequence whose n-th term is Un+1
Now, consider the following sequence W :
Wn = z n where z 2 = 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 tothat equation, yielding two linearly independent sequences of the aboveform, which can serve as a vector basis. So, the n-th term of any sequence V is of the form:
Vn = xn + yn where (z)(z) = z 2 A z B
In particular, for the sequence U (which starts with U0 = 0 and U1 = 1) :
Un =
nn
In the special case when the above breaks down. Instead, we have:
Un = n n-1
Such explicit expressions are called Binet formulas, in honor of the influential French mathematician Jacques Binet(1786-1856;X1804) who succeededPoissonas Professor of mechanics at Polytechnique in 1815. (Binet had been a classmate ofFresnel and thecoach ofBabinet.) The term applies especially to the case of Fibonacci numbers (A = B= 1) :
The general formulas predate Binet by more than a century. They were known to Abraham de Moivre (1667-1754) and Leonhard Euler ((1707-1783). D'Alembert (1717-1783) had even presented the degenerate case ( = ) as a limit of the nondegenerate one (in a nonrigorous way, by modern standards).
Recall that any sequence V obeying a second-order linear recurrence ["degenerate" or not] canbe expressed in terms of the above standard sequence U (obeying the same recurrence and starting with 0 and 1) :
Vn = Un2 Un+1 Un-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 byRobertSimson (1687-1768;pedal line) in 1753.
: Using V1 = 1, the general case is establishedby induction on n :
Vn+1 = (A Un + B Un-1) Un+1 (A Un+1 + B Un) Un = (-B) Vn
(2007-11-29) A generalization ofCassini's Identitydue to Maurice d'Ocagne.
Un Um+1 Un+1 Um = (-B)m Un-m [ where n ≥ m ]
: For a given value of m, let's consider the following function of i :
Wi = Um+i Um+1 Um+i+1 Um
As W0 = 0, theabove lemma shows that Wi = W1 Ui where the value W1 = (-B)m is obtainedimmediately fromCassini's Identity.
: We'll applyBinet's formula to etablish the result when thetwo roots and = (-B/) of the characteristic equation are distinct (by continuity, this will alsoestablish the result for the special case when they are equal). To streamline notations, we prefer to deal with the sequence Vn = () Un
Kirk Guidry (2002-03-30; e-mail) [...]For a given p, how do you derive a formula for the sum of the p-th powersof 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 calledFaulhaber's Formula and I'llgive it to you below... However, your question is not really about formulas butrather about the methods which may be used to obtain them.I'll give youtwo such methods.The first one is elementary and can easily be used to solve your original concernabout the formula for the sum of fifth powers.The second method is not so elementary(it involves the concept ofgenerating functions)but is much more powerful and can be used to establish the generalformula, which involves Bernoulli Numbers.
[...] I recall reading a derivation of this formula in my calculus book(as the trepidation induced by my first encounter with the Bernoulli sequenceserves to vivify). I remember the dissatisfaction that ensued,and theprompt 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 aLagrange interpolating polynomial. For example:
In the above expression, the chosen range for kand j (namely {1, 2, ... p+2})is anarbitrary 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.
Johann Faulhaber worked out the above table up to p = 17 and observed that the result was a polynomial function of x = n(n+1)/2 for odd values of p (a fact that would only be proved rigorously by Carl Jacobi in 1834).
(2002-11-16) An important class ofarithmetic functions
Anarithmetic function or arithmetical function (in German:zahlentheoretische Funktion) is a numeric function (with real orcomplex values) of the positive integers. In the context ofnumber theory,an arithmetic function f is said to bemultiplicative if
f (ab) = f (a) f (b) whenever the integersa andb arecoprime.
If we rule out the function that's identically zero [as is always done in this context] this implies that f(1) = 1 for any multiplicative function f.
) defined below.
Also, the value of a multiplicative function at zero is always 0, whenever it's convenient to define that [1,2,3,4 ]. However, that convention is only mandatory in the case of totally multiplicative functions, for whichmultiplicativity must holds even if the factors are not coprime (recall that zeroisn't coprime to any integer).
To define a multiplicative function,it is sufficient to specify its value when the argument is a positive power of a prime( pn ). Here are some examples(the first eight are easy to compute withoutfactoring the argument):
Dirichlet unit: (pn) = 0 [(k) =1/k= 0k-1 is zero unless k=1]
Identity function:N(pn) = pn [N(k) = k, for any k]
Trivial character: u(pn) = 1 [u(k) = 1, for any positive integer k]
Character modulo 2: v(2n) = 0, v(pn) = 1 if p>2[v(k) = k mod 2]
Abundancy: -1(n) = (n) / n[Aperfect number has abundancy 2.]
Otherdivisor functions: k(pn) = (pkn+k1) /(pk1) k(n) is the sum of the k-th powers of thedivisors of n. k can be negative (orcomplex). Note that: -k(n) = k(n) / nk
The ordinary product of two multiplicative functionsis 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 amultiplicative function(so is the nonintegral power of a multiplicative function withpositive real values). Another very interesting type of multiplication, describedbelow,also yields a multiplicative result from two multiplicative operands...
A multiplicative function whose value at the nth power ofany primeis a function of n only is said to depend only on the prime signature of its argument. Some examples are: theDirichlet unit (),thetrivial character (u),thedivisor count (d),theMöbius function (),Liouville's function () andthemultiplicative parity (). Another example is the aforementioned function Abel, which gives the number of distinct (i.e., non-isomorphic) Abelian groups of a givenorder.
Multiplicative function f summed over all divisors of n :
The sum of the values of a multiplicative function f for all divisor of an integer n factorizes into as many factors as n has distinct prime divisors. The factor corresponding to a prime divisor p of multiplicity k is:
1 + f ( p ) + f ( p2) + ... + f ( pk)
A very important special case is thatof the Möbius function, for which all such factors vanish! Thus, the values of the Möbius function at alldivisors of any positive integer always add up to zero, unless that integer is just 1 (which has no prime divisors). That wonderful property is what makes the Möbius inversion formula work. More about thatsoon...
For any integer n > 1
0 =
(d)
(2009-05-03) ) A table of its values can be computed very fast by sieving.
The Moebius function is definedabove, as a multiplicative function,in terms of the factorization of its argument n. It is equal to zero if n is divisible by the square ofa prime. Otherwise, (n) is equal to either -1 (if n has an odd numberof prime factors) or +1 (when n has an even number of prime factors).
A slight modification of the Sieveof Eratosthenes can builda table of two-bit entries (four possible values) from which (n) can be obtained immediately. This can be done without performing a single multiplicationor division. The idea is expressed by the following pieceof code, which uses syntax but is really intendedto serve as a model for an assemblylanguage implementation:
10 ' This puts into M%(n) a two-bit code describing n: 20 ' 30 ' 0 = Prime number 40 ' 1 = Product of an odd number of distinct primes. 50 ' 2 = Product of an even number of distinct primes. 60 ' 3 = Multiple of the square of a prime. 70 ' 80 Top=3000 ' Running time is O( Top * Log(Log(Top)) ) 90 '100 dim M%(Top) ' Array is initialized with zeroes110 M%(1)=2 ' 1 is the product of 0 primes (0 is even)120 '130 P=2:I=P+P140 '150 while I<=Top ' Outer loop160 '170 J=2 ' I remains equal to J*P modulo P^2180 '190 while I<=Top ' Inner loop200 if J=P then J=0:M%(I)=3:goto 230210 X=M%(I):if X=3 then 230220 if X=1 then M%(I)=2 else M%(I)=1230 I=I+P:J=J+1240 wend ' End inner loop250 '260 inc P:while M%(P):P=P+1:wend ' Fetch next prime270 I=P+P280 wend ' End outer loop290 '300 for N=1 to Top ' Check against built-in function310 if fnMu(N)<>moeb(N) then stop320 if M%(N)=0 then print N,' DEMO: Show list of primes330 next N340 end350 '360 fnMu(X)370 X=M%(X)380 if X=3 then return(0)390 if X=2 then return(1)400 return(-1)
For the sake of simplicity, this didactic example does not attemptto produce a very compact array. Ideally, one bit of data per integer will suffice,since it's enough to store 2 bits for each odd integer. Indeed, no even integer (besides 2) is prime and (2n) is either trivially zero (if n is even) or is found directly from the tablefor odd numbers, as equal to -(n).
The number of additions performed to make a table of size M with the above procedure is proportional tothe following expression, wherek is a constant and p is the largest prime less than or equal to M/2 :
This is O(M Log Log M) because the sum of the reciprocal of all primes less than x isroughlythe integral of 1/(x Log x) which is Log Log x. (Incidentally, this argument can be considered the backbone of a proof thata large number N has an average of about Log Log N distinct prime factors.)
Although it does grow without bounds, the quantityLog Log x is equal to 3 for all practical purposes! (It's exactly that when x is around one billionand it changes only by 10% or so when x varies by a factor of one thousand.) The result of the above procedure is thus not worth storing on a computer disk;it can be recomputed faster than it could be loaded back into core memory...
(2002-11-16) The weirdmultiplication in the "Dirichletring"of arithmetic functions. Multiplicative functions form a group under Dirichlet convolution.
Prototypical Example: The Sum-Function
If f is an arithmetic function, a function F, called thesum-function off, is defined by letting F(n) be the sum of the termsf(d) for all divisors d of n.
The function f may be retrieved from F by using the so-calledMöbius inversion formula, which states that f (n) is the sum of all terms F(d) (n/d) for all divisors d of n,where is theMoebius function.
: d|n F(d) (n/d) = i.j|nf (i) (j) In this, the factor of f (i) is the sum of all (j)when j is a divisor of n/i. That's clearly equal to 1 when i=n. For all other values of i,the sum over j vanishes, because of apreviously made remark.
Generalization: The Dirichlet Convolution
Generally, the Dirichlet product (or convolution) F = fg of two arithmetic functions is defined by letting F(n) be the sum of theterms f (d)g(n/d) for all divisors d of n :
F(n) = fg (n) =
f (d) g(n/d)
F is multiplicative wheneverf andg are, because any divisor of n =ab (wherea andb arecoprime) is the productd = uv of two coprime factors u and v, respectively dividinga andb. 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)
Among arithmetic functions, the Dirichlet product (also calledDirichlet convolution) is a commutativeand associative operation (the value at point n of fgh 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 withthe structure of aring, called the Dirichlet ring.
Dirichlet Inverse :
For Dirichlet multiplication, the neutral element is theaboveDirichlet unit (). Any arithmetic function f for which f (1) is nonzerohas a Dirichlet inverse if we're considering arithmetic functions whosevalues are in afield.
If f (1) = 1 (which holds for all multiplicative functions) an arithmetic function f whose values are in a unital 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 agroup.
The Dirichlet inverse of the trivial character u [u(n) = 1] is the Möbius function . This is equivalent to the above Möbius inversion formula :
If F = uf then f = F
Convolutive group over a unital ring of coefficients :
Over any unital ring, an arithmetic functions f has a Dirichlet inverseiff its leading coefficient f (1) is invertible. With respect to the Dirichlet product, the set of all such arithmetic functions form a group which I'll callthe convolutive group. Two of its subgroups are of particular interest:
Special group of arithmetic functions whose leading term is 1.
Unlike some of their subgroups, those convolutive groups are also stable under pointwise multiplication, for which the following distributive equationshold if the function h happens to be totally multiplicative andits values commute with the values of f and g.
(f *g )h = f h * g h h (f *g ) = h f * h g
In 1973, Eric Langfordbriefly investigated how convolution could be defined to allow the above to hold only for totally-multiplicative factors...
(2004-11-27) Well-defined for any function whose leading term is real and positive.
It's easy to show that, for any positive integer q and any arithmeticfunction f with real positive leading term f (1) there's a unique root (with a positive leading term) of which the function 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 again a multiplicative function.
(2004-11-27) Negative powers are positive powers of its inverse u = 1,1,1,1,1,1...
The Dirichlet power [k] of the Möbius function happens to have avery nice explicit definition (in terms of its values at the powers of any prime p):
[k](pn) = (-1)n C(k,n)
This formula holds even if k is negative (powers of u =[-1] ,including d = uu ). More surprisingly, it's also true for fractional values of k:
Dirichlet square root of the Möbius function : [ ½ ](pn ) = (-1)nC(½,n)
m =
1
2
3
4
5
6
7
8
9
10
11
12
[½] (m)
1
-1/2
-1/2
-1/8
-1/2
1/4
-1/2
-1/16
-1/8
1/4
-1/2
1/16
(2002-11-16) by u (or ) and N : Where u = 1,1,1,1,1,1,1... and N = 1,2,3,4,5,6,7...
Whole powers of the Möbius function and/or its inverse u follow the pattern generalized in the previous section, namely:
The simplest multiplicative function excluded from thisis the identity function N = 1,2,3,4,5... Convolving its own Dirichlet powers with the above, we obtain many noteworthy multiplicative functions, including:
(2009-11-14) Their values on { pn | n = 1,2,3... } depend only on valuesof f there.
A multiplicative function f can be specified by giving,for every prime p, the generating function of the values of f at the powers of p.
Conversely, any family of formal generating functions (i.e., formal power series, convergent or not) indexed by the primes and such that p(0) = 1 uniquely determines a multiplicative function, provided only that
p(z) = nf (pn) zn
The following beautiful formula determines theDirichlet power of f for any exponent k (the Dirichlet inverse of f is obtained for k = -1 ).
p(z) k = nf[k](pn) zn
A similar relation defines the Dirichlet product of twomultiplicative functions:
nf (pn) zn ng (pn) zn = nfg (pn) zn
Essentially, a multiplicative function is thus usefullydescribed as an object with infinitely many components (one for each prime p) each consisting of a sequence starting with 1 (one). The Dirichlet convolution (or Dirichlet product) of two such things is the object whose componentsare ordinary Cauchy products of the corresponding pairs of component sequences. That's all there is to it.
A function f is calledcompletely multiplicative(ortotally multiplicative) when f(ab) =f(a)f(b) always holds, whethera andb arecoprime or not. In that case, the Dirichlet inverse g verifies g(n) = (n)f(n), since:
gf (n) =
(d)f(d)f(n/d) = f(n)
(d) = f(n) (n) = (n)
The last equality holds for n=1 because f(1)=1,and for n>1 because (n)=0.
Dirichlet-Inverse g of a totally-multiplicative function f
g (n) = (n) f (n)
A completely multiplicative arithmetic function f and itsDirichlet-inverse g are fully determined by the values f (p) chosen for f at prime indices p :
f (pn) = f (p) n whereas g(p) = -f (p) & g(pn) = 0, if n>1
That's just a special case ofthe above formula, with p(z) 1 = 1- f (p) z
A multiplicative function which is zero for squares of primes, and higher powersof prime numbers, is thus the Dirichlet inverse of atotallymultiplicative function.
This applies, in particular, to the Dirichlet characters (presentednext) as those are indeed totally multiplicative.
Unless it's 1 everwhere, a totally multiplicative must vanish at zero.
The convention f (0) = 0 is mandatory for any totally multiplicative functions, with the possible exception of the function which is everywhere equal to 1. By convention, neither that function nor the zero function (which vanishes everywhere) are considered totally multiplicative, so that all such functions can be statedto verify f (n) = n when n is 0 or 1.
A Dirichlet character modulo k (also called character to the modulus k ) is acomplex-valued completely multiplicative function of period k,which vanishes whenever its argument isn'tcoprime with k.
The conductor of a given Dirichlet characteris its smallest period. The characters to the modulus k with conductors equal to k are called primitive (those whose conductors areproper divisorsof k are called imprimitive ).
There are exactly (k) possible Dirichlet characters to the modulus k (where is Euler'stotient function). They are tabulated below for some small values of k.
Except for k=3, k=4 and k=6 (which could have been tabulatedtogether) we've spared the expense of separate tables for isomorphic structures. Instead, we indicate at the bottom of the relevant tables how to relabel thecolumns for additional values of k (a wildcard label '*' is to be used for unlisted valuesof n, which correspond to zero columns because they're notcoprime with k).
For example, such an isomorphism exists among all the values of k (7, 9, 14 and 18)for which (k)=6,as there's only oneAbelian group of order 6. On the other hand, the two distinct 4-line structurescorrespond to the two distinct Abelian groups of order 4, namely, the cyclic group (k=5, k=10) and theKlein group (k=8, k=12).
k = 1
n
0
u(n)
1
k = 2
n
1
0
1(n)
1
0
k = 5 (k) = 4
n
1
2
3
4
0
1(n)
1
1
1
1
0
2(n)
1
i
-i
-1
0
3(n)
1
-i
i
-1
0
4(n)
1
-1
-1
1
0
k = 10
1
3
7
9
*
k = 3
n
1
2
0
1(n)
1
1
0
2(n)
1
-1
0
k = 4 (k) = 2
n
1
2
3
0
1(n)
1
0
1
0
3(n)
1
0
-1
0
k = 6 (k) = 2
n
1
2
3
4
5
0
1(n)
1
0
0
0
1
0
5(n)
1
0
0
0
-1
0
k = 7 (k) = 6
n
1
2
3
4
5
6
0
1(n)
1
1
1
1
1
1
0
2(n)
1
2
-
-
2
1
0
3(n)
1
-
-2
2
-1
0
4(n)
1
-
2
2
-
1
0
5(n)
1
2
-
-2
-1
0
6(n)
1
1
-1
1
-1
-1
0
k=9
1
4
2
7
5
8
*
k=14
1
9
3
11
5
13
*
k=18
1
13
11
7
5
17
*
k = 8 (k) = 4
n
1
2
3
4
5
6
7
0
1(n)
1
0
1
0
1
0
1
0
3(n)
1
0
-1
0
1
0
-1
0
5(n)
1
0
1
0
-1
0
-1
0
7(n)
1
0
-1
0
-1
0
1
0
k=12
1
*
5
*
7
*
11
*
= exp ( i/3) = (1+i3) / 2 [3 = -1 ]
k = 11 (k) = 10 x = exp ( i/5)
n
1
2
3
4
5
6
7
8
9
10
0
1(n)
1
1
1
1
1
1
1
1
1
1
0
2(n)
1
x
-x3
x2
x4
-x4
-x2
x3
-x
-1
0
3(n)
1
-x3
x4
-x
x2
x2
-x
x4
-x3
1
0
4(n)
1
x2
-x
x4
-x3
-x3
x4
-x
x2
1
0
5(n)
1
x4
x2
-x3
-x
-x
-x3
x2
x4
1
0
6(n)
1
-x4
x2
-x3
-x
x
x3
-x2
x4
-1
0
7(n)
1
-x2
-x
x4
-x3
x3
-x4
x
x2
-1
0
8(n)
1
x3
x4
-x
x2
-x2
x
-x4
-x3
-1
0
9(n)
1
-x
-x3
x2
x4
x4
x2
-x3
-x
1
0
10(n)
1
-1
1
1
1
-1
-1
-1
1
-1
0
k=22
1
7
9
5
3
19
17
13
15
21
*
k = 13 (k) = 12 y = exp ( i/6)
n
1
2
3
4
5
6
7
8
9
10
11
12
0
1(n)
1
1
1
1
1
1
1
1
1
1
1
1
0
2(n)
1
y
y4
y2
-y3
y5
-y5
y3
-y2
-y4
-y
-1
0
3(n)
1
y4
y4
-y2
1
-y2
-y2
1
-y2
y4
y4
1
0
4(n)
1
y2
-y2
y4
-1
-y4
y4
-1
y4
-y2
y2
1
0
5(n)
1
-y3
1
-1
-y3
-y3
y3
y3
1
-1
y3
-1
0
6(n)
1
y5
-y2
-y4
-y3
y
-y
y3
y4
y2
-y5
-1
0
7(n)
1
-y5
-y2
-y4
y3
-y
y
-y3
y4
y2
y5
-1
0
8(n)
1
y3
1
-1
y3
y3
-y3
-y3
1
-1
-y3
-1
0
9(n)
1
-y2
-y2
y4
1
y4
y4
1
y4
-y2
-y2
1
0
10(n)
1
-y4
y4
-y2
-1
y2
y2
-1
-y2
y4
-y4
1
0
11(n)
1
-y
y4
y2
y3
-y5
y5
-y3
-y2
-y4
y
-1
0
12(n)
1
-1
1
1
-1
-1
-1
-1
1
1
-1
1
0
k=26
1
7
9
23
21
11
15
5
3
17
19
25
*
and i (to allow y to beany primitive 12-th root of unity).
Incidentally, the entries in any row, beyond the first one, add up to zero. That's to say that any nontrivial character of period k satisfies a linear recurrence relation of order k-1. Namely:
(n+k-1) = (n+k-2) ...(n+1)(n)
Collectively, the (k) characters modulo k form a group with respect to pointwise multiplication (isomorphic to themultiplicative groupof the residues coprime to k) whose neutral element isthe so-called principal Dirichlet character modulo k(whose value is 1 for an argument coprime to k and 0 otherwise). It is denoted by the symbol 1 in the above tables.
We have indexed the characters in those tables with the multiplicativeresidues modulo k themselves, in accordance with the aforementioned isomorphism(for the smallest relevant k). This convention makes the above tables symmetrical:
m(n) = n(m)
Except in the trivial cases (i.e., k = 1, 2, 3, 4 or 6) there are several indexing scheme with this property (because several automorphisms exist). Thus, the above does not assign unambiguous names to the various Dirichlet characters.
Some (real) Dirichlet characters are obtained by generalizingtheLegendre symbol (ofquadratic reciprocity fame). Generalized versionsof the Legendre symbol often go by other names (Jacobi symbol orKronecker symbol) which we don't advocate, because suchnomenclature is not technically needed...
(n) = ( n | k )
That's sometimes called the alternating character of period k (especially when k = 4). The above tables always show this particular characterin the last row ( green shading ). Recall that the Kroneker generalization ofthe Legendre symbol obeys the followingad hoc conditions:
(a | -1 ) = sign(a)
a mod 8
0
1
2
3
4
5
6
7
(a | 2 )
0
1
0
-1
0
-1
0
1
If k is 1, 2, 4,the power of an odd prime, or twice the power ofan odd prime (A033948) then the corresponding group iscyclic (i.e., it has aprimitive root). In that case, we may consider a given primitive root r of themultiplicative group formed by theinvertible elements modulo k, often denoted(/k)*, and state that every character modulo k is obtained by the following definingrelation for some (k)-th root of unity z (not necessarily a primitive one).
n (rn) = z n
Some of the above tables were so obtained; sorting columns in ascendingorder of the arguments (r n ). Here's another way to present things:
(k) = 16 z16 = 1
()
1
z
z2
z3
z4
z5
z6
z7
z8
z9
z10
z11
z12
z13
z14
z15
0
k=17
1
3
9
10
13
5
15
11
16
14
8
7
4
12
2
6
0
k=34
1
3
9
27
13
5
15
11
33
31
25
7
21
29
19
23
*
(k) = 18 z18 = 1
()
1
z
z2
z3
z4
z5
z6
z7
z8
z9
z10
z11
z12
z13
z14
z15
z16
z17
k=19
1
3
9
8
5
15
7
2
6
18
16
10
11
14
4
12
17
13
k=27
1
5
25
17
4
20
19
14
16
26
22
2
10
23
7
8
13
11
k=38
1
3
9
27
5
15
7
21
25
37
35
29
11
33
23
31
17
13
k=54
1
5
25
17
31
47
19
41
43
53
49
29
37
23
7
35
13
11
The same compact tabulation may be used for non-cyclic groups (A033949). We may illustrate that with the smallest modulus not yet encountered (k=21):
(k) = 12 x2 = 1 y6 = 1
()
1
y
y2
y3
y4
y5
x
xy
xy2
xy3
xy4
xy5
0
k=21
1
5
4
20
16
17
13
2
10
8
19
11
*
k=42
1
5
25
41
37
17
13
23
31
29
19
11
*
The Dirichlet characters modulo k are just the homomorphisms from the multiplicative group (/k)* intothe group of the (k)-th roots of unity.
(2007-04-17) Consider the series F(s) = nf (n) n-s for some value of s.
If f is amultiplicative function,this can be expressed as an Euler product , namely an infinite product whose factors are functions of all the consecutiveprimes: p = 2, 3, 5, 7, 11, ... (: Every coefficient f (n) appears in the expansion of this product, tied to theunique factorization of n into primes.)
p ( 1 + f (p) p-s + f (p2) p-2s + f (p3) p-3s + f (p4) p-4s + ... )
This formal equality (discarding issues of numericalconvergence) holds if and only if the function f is multiplicative, in the sensespecified above.
When f istotally multiplicative,eachEuler factor becomes a geometric series, which we may sum upto obtain the simple relation:
F(s) = nf (n) n-s = p ( 1 f (p) p-s) -1
When f (n) = 1 for any n (with theabove notations,f isthetrivial character u ) that relation expresses Riemann's zeta function F(s) = (s).
The above series converges only for Re(s) > 0 but it hasan analytic continuation to the entire complex plane (without singularities) brought about by the following reflection formula, using theGamma function:
(1-s) = (/2)-s sin(s/2) (s) (s)
It's conjectured that the analytic continuation of any series in n-s with totally multiplicative coefficients which satisfiessuch a reflection formula always verifies a counterpart of Riemann's hypothesis, namely: All zeros in the critical strip (0 < Re(s) < 1) lay on the criticalline (Re(s) = ½).
(2021-07-03) Nice sums of some series over prime powers, where pk has weight 1/k.
There's something magical about some series indexed by the powers of the primes when kth powers have their weight reduced by a factor k.
Indeed, consider the Euler factorization of Dirichlet L-functions when the magnitude of (p) p-s never exceeds 1:
Log L(,s) = p Log ( 1 (p) p-s) = pk (pk) (pk)-s / k
That can be described as the original series without the composite indices, exceptprime powers, for which the terms are divided by the exponent. This presentation looks "magical" and is a favorite of Grant Sanderson (who rarely bothersif ever to give the above proof, which works for any absolutely convergent series (sothe termscan be commuted freelywithout changing the sum) with totally multiplicative ceoefficients(Dirichlet characters are an example). Examples:
(s) 3-s+ 5-s+ 7-s+ 9-s/2+ 11-s+ 13-s+ 17-s+ 19-s+ 23-s+ 25-s/2... = Log (s) + Log (1-2-s) 1 3-s+ 5-s 7-s+ 9-s/2 11-s+ 13-s+ 17-s 19-s 23-s... = Log (s)
(2007-04-17) L-functions can be expressed in terms of these generalizations of Riemann's zeta function (and vice-versa).
The Hurwitz zeta function is defined as follows:
(s,q) = n (n+q)-s
The parameter q is usually assumed to be a real between 0 and 1,although the function is well-defined for other values of q.
The L-function for any Dirichlet character to the modulus k is just a linear combination of Hurwitz zeta functions(for rational values of q):
L(s,) = k-s
k
n=1
(n) (s,n/k)
Conversely, the Hurwitz zeta function for a proper fraction q = n/k (expressed in lowest terms)can be expressed as a finite sum over all theDirichlet characters to the modulus k,namely:
Anarithmetic function with numerical values is said to beaddittive if
f (ab) = f (a) + f (b) whenever the integersa andb arecoprime.
This implies that f (1) = 0. [f (0) can't be assigned any finite value. ]
If the above holds even when a and b are not coprime, then f is said to be fully additive, totally additive or completely additive.
An additive function is fully defined by the values it takes at the powers of primes. Conversely, arbitrary values at those points uniquely define an additive function. An additive function f is totally additive if and only if:
n , p , f (pn) = nf (p)
Prescribed values for primes uniquely define a totally additive function.
The sum of two (totally) additive functions is (totally) additive. Likewise, a (totally) additive function is obtained by multiplying into ascalar a (totally) additive funstion. The additive functions form a vector space of which totally additive functions are a subspace.
The zero function (vanishing everywhere) is additive (but not multiplicative). It's the zero vector in the linear space of additive functions.
Some additive arithmetic functions:
Number of distinct prime factors: (pn) = 1 (A001221).
Sum of distinct prime factors: sopf (pn) = p (A008472).
Logarithm of a positive multiplicative function.
Generic additive function: g (pn) is arbitrary for powers of primes.
