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.
What you're describing are, in fact, the� 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
is a� unit� of 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�
(related to the nine Heegner
numbers:� 1, 2, 3, 7, 11, 19, 43, 67 and�163)� most notably
the Gaussian integers and the
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.
(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 only natural integers
which are neither prime nor composite are� 0� and� 1.
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...
"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 use
for 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) �
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 every Gaussian integer�
uniquely� decomposes into a� unit� (one of the four invertible
elements +1, -1, +i, -i�) and a product of irreducible elements from
the� positive� quarter of the complex plane,�
calling a�Gaussian integer� x+iy�
positive� when� -x�<�y�<�x+1�.
This is entirely analoguous to the� Fundamental
Theorem of Arithmetic� whereby every ordinary integer is a product
of an invertible unit� (namely,� its� sign;� +1 or -1)�
and a unique decomposition of� positive� primes.
Note that� 1+i� is the only positive Gaussian prime whose conjugate
is not a positive Gaussian prime as well�
(since� 1-i = (-i)(1+i)� isn't positive).
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)2
� � � � �
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 23�3.�
86 is 2�43.� 125 is 53.�
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:
Factoring large numbers 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,�
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:
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 Factorizations
Prove that � n4 + 4 � is composite (i.e., not prime) for all� n
> 1
Well, �
n4 + 4 � = � (n2 - 2n + 2) (n2 + 2n + 2) �
is a proper factorization,�
since�the�smaller of the two factors is greater than� 1� when�
n�>�1.
That's a special case of the so-called� Sophie Germain identity�:
This type of factorization is often called� Aurifeuillian� (sometimes also spelled
Aurifeuillean)�
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 owned
the� Ch�teau du Bois-Hue� in Saint-Joseph du Portricq,
near Nantes).� Le Lasseur routinely shared his factorizations with
Edouard�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 mathematics
in Toulouse. 
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).
Curiously,� Aurifeuille became quite famous as�an illusionist under the stage name of� [Vicomte]�
Alfred de Caston.�
The�great magician
Robert-Houdin (1805-1871)
was impressed by the way Aurifeuille used his wits in an act of mentalism.�
Signing "de Caston",
Aurifeuille authored several other books, related to "magic" or not, including:�
Tartuffe Spirite (1866),
Les�vendeurs de Bonne Aventure (1866),
La�Turquie en�1873 (1874).�
His masterpiece is still
in
print:� Les�marchands de miracles:
Histoire de la superstition humaine (1864).
�
The self-styled "vicomte" Alfred de Caston claimed to be a native of America.�
He once lived in Turkey
where he became editor-in-chief of the� Revue de Constantinople� in 1875-1876.�
According to the records at
Polytechnique� (which he entered in 1841)�
Antoine Aurifeuille was born in Toulouse (France) on March 9, 1822� to�an
unwed mother of unspecified means of support, Jeanne Andr�e Aurifeuille,
living 26 place Mage� (a nice part of Toulouse)...�
He joined a French writers guild:�
La soci�t� des gens de lettres�
(founded in 1838).
�
The attached caricature of Antoine Aurifeuille / Alfred de Caston�
(provided by Ian Keable on 2012-02-12)�
appeared in the French magazine� L'Escamoteur�
(45,�march-april 1954)� next to the photograph that inspired it.�
The military description of Aurifeuille (1841) was:�
Cheveux�bruns.�
Front d�couvert.�
Nez��pat�.�
Yeux�bruns.�
Bouche moyenne.�
Menton�rond.�
Visage�ovale.�
Taille:�171�cm.
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�:
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� obtained
by the retired Parisian mathematician�
Fortun� Landry
(1798-1895)� after casting out the�factor� 5.�
Summarizing his factorizations in 1869, Landry wrote:
None of the numerous factorizations of the numbers�
2n � 1
gave 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 calculations
that we have made and it is possible that many years will pass before someone else
will discover the factorization of�
258�+�1
On July 12, 1880, the 82-year old Landry earned a permanent spot
in the history of numbers by presenting his factorization
of 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.
(1+ 13x
(1+ x
(7+ 13x
(3+ x
(15+ 13x
(5+ x
(19+ 13x
(5+ x
(15+ 13x
(3+ x
(7+ 13x
(1 + x))))))))))))
(1- 13x
(1- x
(7- 13x
(3- x
(15- 13x
(5- x
(19- 13x
(5- x
(15- 13x
(3- x
(7- 13x
(1 - x))))))))))))
x 15 �+� 1
=
( x + 1 ) � (x2 - x + 1) �
(x4 - x3 + x2 - x + 1) �
(x8 + x7 -
x5 - x4 - x3 + x + 1 )
With� a = 11,� one of the above says that�
(1133�+�b22)�/�(113+b2)�
splits into two� large� factors�
(both prime when b�=�23).�
It's divisible by� 23� when� n� isn't�
(courtesy of� Fermat's
little 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 particular
with� b�=�1)� yield very even splits
into two factors which are� occasionally� prime.� For example:
Tiny values of� x� (in particular
with� 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 establishes B�zout's Lemma
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:
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 (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�
(proving� B�zout's lemma).
Subtractive Version of Euclid's Algorithm�
(anthyphairesis) :
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 lemma� (or identity) �=�
Bachet-B�zout theorem
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 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 appears in the work of
Claude
Gaspar Bachet de M�ziriac (1581-1638)� of�
Bachet squares� fame (1624).
The canonical 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):
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 :
� 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).�
(For the sake of expediency,� we've retained�
bezout (x, �x) = 0 � instead.)
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:
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.
On Hewlett-Packard calculators� (HP-49g+, HP-50g)�
the above� bezout� function for integers
can 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 above
describes�
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.
BUG REPORT: � At least for versions 2.15 and below (2009) of the HP�firmware,
the� IEGCD� function requires the calculator to be set to� radian mode,�
although angle measurements are utterly irrelevant.
The above expression may serve as a good introduction to the universally accepted convention
introduced by� Hermann Minkowski (1864-1909)�
whereby an operator defined for two elements is also defined when either formal operand
is a� set� of such elements� (or when both are).�
The result is�then the set of all possible operations between an element from the first
formal 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 other
is a multiple of��n.�
B�zout's lemma� states that those sums are precisely the multiples of
the� greatest common divisor� of� m� and� n.
(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 ( 2/3 , 1/2 )
� = � 1/6
This allows the GCD of two commensurable
numbers to be defined as well:� Two real numbers are commensurableiff they are proportional to two integers;�
Their GCD is simply the GCD of those integers multiplied by the common scaling factor.
gcd ( 2p/3 ,
p/2 )
� = � p/6
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 would entail� forbidden� divisions
by zero).�
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 their GCD.� Something like:
gcd ( x , y ) � < � e
= 10-100
Otisbink
(2002-04-02)
� Linear Diophantine Equations
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 called
a��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,�
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 such a pair of integers is a result commonly known as
Bezout's lemma).
We have � a = da' � and
� b = db' , where a' and b'
are relatively prime.
Since the LHS of the equation is divisible by d, the RHS must be also.�
Therefore, d must divide c, or else the equation has no integer solutions.�
Let's�assume, then, that� 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 is given by the first equation
of the following pair.� The second equation,� giving y,� is obtained by
substituting that value of x in the original equation:
x � = � u c' + k b'
y � = � v c' - k a'
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 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 make the constants as small as possible, we introduce� n = -2569 - k.�
This way, we obtain� canonical� formulas where nonnegative solutions
for� x� and� y� correspond to nonnegative values of the parameter� n:
Before negative numbers became commonplace�
(in the Renaissance)�
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 sequence
of steps where a greater number was never subtracted from a smaller one.
When devising� recreational�
puzzles,� it can be amusing to engineer linear Diophantine
equations which have only one positive solution.�
To do so,� start with canonical solution formulas which clearly give negative
solutions for any nonzero value of the parameter� n� and
work your way backward to eliminate� n� and obtain a linear
equation which encodes a unique pair of nonnegative integers.
(2006-02-03) �
Pythagorean Triples � (Pythagorean Triplets)
Solutions, in coprime 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� all� coprime solutions are�of
the following form� (the special case v=1 was given by
Archimedes).
( u2-v2 ) 2 �+�
(2uv) 2 � = �
( u2+v2 ) 2
Proof : �
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�:
4 a 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 yields coprime 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).
(Joe of Ann Arbor, MI.
2000-10-24)
What numbers have exactly� 6� proper divisors�? �
[A proper divisor is a�positive integer�
less than� the dividend which divides evenly into it.]
Consider the factorization into primes of the number
N = 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 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:
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
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.
The second class starts with 23�3=24,
23�5=40, 2�33=54, 23�7=56,
23�11=88, 23�13=104, 33�5=135,
23�17=136, etc.
The third class is the sequence of seventh powers of primes:
128, 2187, 78125, 823543, etc.
(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.)
(2010-01-25)�
Perfect Squares
The only positive integers witn an� odd� number of positive divisors.
With the notations introduced in the previous section, the total
number 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 happens
iff� N� is a perfect square.
Anonymous query, via Google�
(2010-10-09)�
Product of all divisors
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� is coprime 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 prescribed
multiplicity between 0 and k.� Therefore,
the multiplicity of� p� in the
product of all the divisors of� N� is:
The product of all the divisors of� N� is thus a perfect square
if 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� (which means that N is a perfect square)�
then the above is only satisfied when every multiplicity� k� is
a 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 congruent
to 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 multiplicities
or one factor with multiplicity congruent
to 3 modulo 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 congruent
to 3 modulo 4.
(J.E. of Lubbock, TX.
2000-10-25) �
Perfect Numbers
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 pm (p is prime and m is its multiplicity
in the factorization);
s(n)/n is the product of the
factors (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 to Nicomachus of Gerasa�
(c.AD�60-120�; Gerasa is now
Jerash, Jordan).�
Nicomachus discusses the topic in his�
Arithmetike Eisagoge� ("Introduction to Arithmetic",� c.�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.�
Some of his "results" are just guesses.�
Wrong guesses tainted the study of
perfect numbers
for centuries!
Euler� proved that all even
perfect 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 the oldest�
unsolved� 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)
An odd perfect
number would necessarily be congruent to 1, 9, 13 or 25 modulo 36�
(Touchard, 1953)� and would have the following properties:
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 108. �
Jenkins had established a lower bounded of 107 in
2003.�
The same method was used by Goto and Ohno in 2006 to improve the lower bound to
108.
At least one� prime-power� greater than 1020. �
[Cohen 1987]
At least 9 different prime factors.�
The number of different prime factors was first proved to be at least� 4� by
Benjamin 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 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
24k
[Nielsen 2003].
MathWorld
� | �
OddPerfect.org by William Lipp
(still under construction as of 2007-12-01)
Seminar
by Oliver Knill (Dec. 2007)
(2000-10-25)� Mersenne Numbers� &� Mersenne Primes
The ongoing search for prime numbers of the form� 2p�-�1
Marin Mersenne (1588-1648)
was a Parisian friar who built around him an influential scientific circle,
well before the official creation of the French Academy of Sciences (1666).�
In�1644, Mersenne proposed a tentative list of the powers of 2 whose predecessors are prime...
In his honor,� the number� 2n-1� is called the� nth�
Mersenne number� (the zeroth 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 list
and to include exponent� 67,�
which was shown to yield a composite Mersenne number by Edouard
Lucas, around 1875� (well before
Frank Nelson Cole (1861-1926)
heroically factorized it, in 1903).
As of� October 2022,�
only 51 Mersenne primes are known, corresponding to�the following values of the
exponent� 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) and
Ivan 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 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.
�
The above incident has set a standard which was recently put to the test:�
The computation that proved� M74207281�
to be prime was acually completed on September 17, 2015.�
However, the original e-mail report was either lost or ignored and
nobody noticed for almost four months.� The official discovery
date is thus January 7, 2016.�
This may well be the weakest part of the GIMPS project,
since Curtis Cooper is on record as stating that e-mail notifications
failed for all four of the record-breaking primes he was involved with!
The abundancy �
a(n) �=�
s-1 (n) �=�
s(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.
The effort to chart them has been spearheaded by�
Achim Flammenkamp.
In�spite�of mounting computational evidence that some of the lists tabulated below
are complete, Walter Nissen
points out that this need not be so, even for our tiny list
of six� 3-perfect numbers.� Indeed,
if� W� was a� [�huge�]�
odd perfect number,�
then the abundancy of� 2W� would be�
a(2)���a(W)�=�3.
Arguably, the existence of an�
odd perfect number� is a top contender for the title of�
"oldest unsolved mathematical problem"...
�
We conjecture that there are only finitely many integers of abundancy� x,�
except when� x�=�2� (but a huge surprise is not ruled out here).
In 1925,� Paul Poulet (1887-1946)�
reported the first two 8-perfect numbers; they're�both multiples of� 262� with
42 and 43 distinct prime factors, respectively.
As of 2010, the only known number� n = 2.5185... 101906� for which�
s(n)/n�=�11� is a
monster of� 246� prime factors, found by
George F. Woltman
on 2001-03-13:
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)�
s-1 ( n (2q-1) ) � = �
2q s-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)� namely
120, 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� from
any known number� 7n� of abundancy� 7� when� n�
is coprime with� 7� and� 19.� Indeed, for such a
cofactor� n,� we have:
The above replacement of the partial factorization �
71�190 � by �
72�191 � is one example
of what's known, in this context, as a� substitution.�
Michel Marcus has used such substitutions extensively to
unearth 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 by
Marcus on 2009-09-28:
A cofactor of that substitution�
(coprime with 11, 17, 37, 43, 67, 79, 179, 631 and 3221)� which
yields 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 divisible
by 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 of
abundancy�17/2�
(the smallest known one has 191 digits).
(G. S. of Farley, IA.
2000-11-15)
How can a� power�,�
like 1217,� 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 table backwards to find that 0.3460804 is the log of 2.2186,
so that your result is about
2.2186�1018.
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 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.�
With modular arithmetic, we don't have to deal with larger and larger results
because, 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) �
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're 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)� who
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 1936,� Rademacher� gave a formula for p(n) as a convergent series.
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-xn) where n ranges over the positive integers.�
(See Encyclopedia
Britannica.)
Among many other similar essays, we recommend a recent
lecture by Ken Ono.
�
[�10 years after we made that recommendation here, Ken Ono made
big news on this very topic�!�]
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+xu+x2u+x3u+�...).
(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
(2011-01-21)� Ken Ono's great�
epilog� on the partition function.
��
Ken
Ono, 2011 Emory University Photo by Carol Clark �
10 years after I enthusiastically recommended a lecture of his in the
above 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 published
by 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 blogs
that are helping break the news� (in chronological order).
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, -1, -3, -1,
5, 7, -3, -17, -11, 23, 45, -1, -91, -89, 93, 271, ...
The Binet formula
for Mn is�: �
Mn = (2/�7) 2n/2
sin�(n atan��7�) Considering this sequence modulo 8, it's clear that
Mn cannot be equal to�1 if n�>�2.�
Prove that Mn 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� U0 = 0, � U1 = 1, � and �
Un+2 = A Un+1 + B Un � then, for
any 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 are coprime):
Up � Uq � = �
| Up�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, WLG, that� p>q�
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�:
Up-q � Uq
� � �
(since� we know that �
Uq+1 � Uq �=� 1)
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� U0�=�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 value of -1 for M.�
From this, we deduce that the lowest 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, 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 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 Mn is prime, namely:
(2009-06-29) �
Primes in� standard Lucas sequences A standard sequence has only finitely many primes of composite index.
Let's generalize the above result to any�
Lucas sequence of the first kind with coprime coefficients�
(which we may call a� standard Lucas sequence, for short).�
By definition, such a sequence starts with 0,1
and obeys the following recurrence relation
for two� coprime� integers  A� and� B�:
U0 = 0, � � U1 = 1,
Un+2 � = � A Un+1 + B Un
This makes the above lemma and
theorem hold.�
We shall use the same approach as in the previous article
to prove that the values -1 amd +1 appear only finitely many
times� (the advertised result follows from that fact, as previously explained).
(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� 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 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�=�3n2+3n+1�
numbers between� m�=�n3�
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:
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.� The properties listed below have been conjectured
by 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 sequence
which unexpectedly fails to obey�long-range randomness for�
mysterious� reasons.
Let's draw a bold analogy with a fundamental open question:� The
Riemann Hypothesis (RH) can be construed as
a belief that the sequence of prime numbers
lacks a certain type of long-range order.�
I offer the above example as a stern warning that the opposing
belief is tenable, in spite of current
heuristic "evidence".�
The fashionable temptation to� assume� that RH is true
ought to be resisted...
(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
Vn+2 � = � A Vn+1 + B Vn
Those form a two-dimensional vector space, where
each element is entirely determined by its "coordinates"�
(V0�,�V1�).
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 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 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:
Vn � = �
x an
�+�
y bn
� � � where �
(z-a)(z-b)
�=�
z 2 - A z - B
In particular, for the sequence� U�
(which starts with� U0 = 0� and� U1 = 1)�:
Un � = �� �
an�- bn
a - b
In the special case when� a = b �
the above breaks down.� Instead, we have:
Un � = �
n a n-1
Such explicit expressions are called� Binet formulas,�
in honor of the influential French mathematician�
Jacques Binet
(1786-1856; X1804)�
who succeeded Poisson
as Professor of mechanics at� Polytechnique� in 1815.�
(Binet had been a classmate of Fresnel and the
coach of Babinet.)�
The term applies especially to the case of�
Fibonacci numbers� (A�=�B=�1)�:
That special case is certainly the most popular use
of� Binet's formulas, but�
all��such formulas are named after�
Jacques Binet,�
whether they pertain to the Fibonacci sequence or not.�
Binet was apparently the first to explain the general formula
in the way outlined above,� using what we would now call�
abstract vectors�
(this was a novel idea in 1843,� the very year when
Hamilton
invented quaternions,�
since even� geometric� vectors weren't commonplace).�
Famous for his algebraic generalizations,�
Binet had been the first to describe the general rule
for matrix multiplication, in 1812.
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�
(a�=�b)�
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]� can
be expressed in terms of the above� standard� sequence�
U� (obeying the same recurrence and starting with 0 and�1)�:
Vn � = � V0 Un+1 +
(V1 - A V0 ) Un
Usage Note : �
Any explicit formula for the n-th term of a sequence
obeying a linear recurrence relation can be called a "Binet formula".�
When the complex roots
of the characteristic equation are not real, their powers
can be expressed with
trigonometric functions� (the sequence has then
an oscillatory aspect examplified elsewhere).�
Arguably, that usage extends beyond the second order,
regardless of the scarcity of examples�
(see A141385
for an example of a third-order Binet formula).
If� U0 = 0, � U1 = 1, � and �
Un+2 = A Un+1 + B Un � then:
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 by
Robert
Simson (1687-1768; pedal line)� in 1753.
Proof : �
Using� V1 = 1,� the general case is established
by induction on� n :
Vn+1 � = �
(A Un + B Un-1 ) Un+1
�-�
(A Un+1 + B Un ) Un
� = � (-B) Vn
� � �
(2007-11-29)
� d'Ocagne's Identity
A generalization of Cassini's Identity
due to� Maurice d'Ocagne.
Un Um+1 �-�
Un+1 Um � � = � �
(-B)m� Un-m
� � � [ where� n ≥ m ]
Proof : �
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,� the
above lemma shows that�
Wi = W1�Ui� where the value�
W1�=�(-B)m� is�obtained
immediately from Cassini's Identity. �
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�
Vn�=�(a-b)�Un
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.
[...]�
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:
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.
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) � Multiplicative Functions
An important class of arithmetic functions�
An arithmetic function� or� arithmetical function�
(in German: zahlentheoretische Funktion)�
is a numeric function� (with real or complex values)�
of the� positive� integers.�
In the context of number theory,
an�arithmetic 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 always done in this context]�
this implies that� f(1) = 1�
for any multiplicative function��f.
Excluding, by convention, the zero function from the realm of 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.
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 which
multiplicativity must holds even if the factors are not coprime� (recall that zero
isn'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� without�
factoring the argument):
Grandi series: �
G(2n ) = -1,�
G(pn ) = 1� if p>2 � [G(k) = (-1)k+1 = 2v(k)-1]
Greatest common divisor: �f�(pn )� =� gcd(a,pn ) �
for a given number� a.
Indicator of the perfect squares: �f (p2n ) = 1 � and � f (p2n+1 ) = 0 Note that,� for any positive integer k,� we have: �
f (k) �=� so (k) mod 2.
�
Number of divisors (so� or� d)
: � d(pn ) = n+1.�
["t" � isn't recommended]
Sum of divisors (s1� or�
s) : �
s(pn ) �=�
(pn+1 -1) / (p-1)
Abundancy: �
s-1 (n) �=�
s(n) / n �
[A perfect number has abundancy 2.]
Other divisor functions: �
sk (pn ) �=�
(pkn+k -1) /
(pk -1)
sk (n)� is the sum of the k-th powers of the
divisors of n.
k� can be� negative� (or
complex).� Note that:�
s-k (n) �=�
sk(n) / nk
�
Inverse of the above : �f�(pn ) = 0� or (-1)k�
if� n = (3k2 ��k)/2 �
(A129667)
Number of squarefree divisors : �f�(pn ) = 2 �
(A034444)�
Number of cubefree divisors : �f�(p) = 2 �
f�(pn ) = 3 �
(A073184)�
Hardy's�
Chi function : �
c(pn ) = 1, 0 or (-1)n��
if p is 1, 2 or 3 modulo 4. Totally multiplicative and period 4:� 1, 0, -1, 0, ...�
(A056594 or
A101455)�
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 below,
also yields a multiplicative result from two multiplicative operands...
A multiplicative function whose value at the nth power of any prime
is a function of� n� only�
is said to depend only on the� prime signature� of its argument.�
Some examples are:�
the Dirichlet unit (e),
the trivial character (u),
the divisor count (d),
the M�bius function (m),
Liouville's function (l) and
the multiplicative parity (g).�
Another example is the aforementioned function�
Abel,� which gives the number of�
distinct� (i.e., non-isomorphic)� Abelian groups of a given
order.
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 that
of the M�bius function, for which all such factors vanish!�
Thus, the values of the M�bius function at all
divisors 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 that soon...
For any integer� n� > 1
0 � = ��
�
�� m(d)
�
d | n
�
(2009-05-03) � The M�bius Function�
(m)
A table of its values can be computed very fast by� sieving.
The� Moebius function� m�
is defined above, 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 of
a prime.� Otherwise,� m(n)�
is equal to either� -1�
(if��n� has an odd number
of prime factors)� or� +1�
(when� n� has an even number of prime factors).
A slight modification of the�
Sieve
of Eratosthenes� can build
a table of two-bit entries� (four possible values)�
from which� m(n)�
can be obtained immediately.�
This can be done without performing a single multiplication
or division.� The idea is expressed by the following piece
of code, which uses�
UBASIC� syntax but is really intended
to serve as a model for an�
assembly
language� 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 zeroes
110 M%(1)=2 ' 1 is the product of 0 primes (0 is even)
120 '
130 P=2:I=P+P
140 '
150 while I<=Top ' Outer loop
160 '
170 J=2 ' I remains equal to J*P modulo P^2
180 '
190 while I<=Top ' Inner loop
200 if J=P then J=0:M%(I)=3:goto 230
210 X=M%(I):if X=3 then 230
220 if X=1 then M%(I)=2 else M%(I)=1
230 I=I+P:J=J+1
240 wend ' End inner loop
250 '
260 inc P:while M%(P):P=P+1:wend ' Fetch next prime
270 I=P+P
280 wend ' End outer loop
290 '
300 for N=1 to Top ' Check against built-in function
310 if fnMu(N)<>moeb(N) then stop
320 if M%(N)=0 then print N,' DEMO: Show list of primes
330 next N
340 end
350 '
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 attempt
to 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� m(2n)�
is� either� trivially zero�
(if n is even)� or� is found directly from the table
for odd numbers, as equal to�
-m(n).
The number of additions performed to make a table of size� M�
with the above procedure is proportional to
the following expression, where
k� 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�
is roughly
the� integral�
of� 1/(x�Log�x)� which is� Log�Log�x.�
(Incidentally, this argument can be considered the backbone of a proof that
a large number N has an average of about� Log�Log�N�
distinct prime factors.)
Note that we cannot abort the procedure at the square root of� M�
(as is allowed with the straight Sieve of Eratosthenes)�
because we are essentially counting the numbers of prime factors of all indices, not
merely determining whether or not there are any such factors.
Although it does grow without bounds, the quantity
Log�Log�x� is equal to� 3� for all practical purposes!�
(It's exactly that when� x� is around one billion
and 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) � M�bius Inversion Formula�
&� Dirichlet Convolution
The weird multiplication in the "Dirichlet ring"
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 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.
The function � f� may be retrieved from F by 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 Moebius function.
Proof : �
� d|n F(d) m(n/d)
� = �
� � i.j|nf (i) m(j)
In this, the factor of� f�(i)� is the sum of all m(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 a previously made remark.�
Generalization:� The Dirichlet Convolution
Lejeune Dirichlet
(1805-1859)
Generally, the� Dirichlet product� (or� convolution)�
F�=�f�*�g�
of two arithmetic functions is� defined� by letting� F(n)� be the sum of the
terms� f�(d) g(n/d)� for all divisors d of�n�:
� � F(n) � = �
f * g�(n) � = � �
�
d | n
� f (d)� g(n/d) � �
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.
Dirichlet Inverse :
For Dirichlet multiplication,� the neutral element is the
above� Dirichlet unit�
(e).�
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 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 a group.
The Dirichlet inverse of the� trivial character� u� [u(n) = 1]�
is the M�bius function m.�
This�is equivalent to the above�
M�bius inversion formula�:
If � � F �=� u * f � �
then � � f �=� m * F
Convolutive group over a unital ring of coefficients :
Over any� unital ring,�
an arithmetic functions� f� has a� Dirichlet inverse�
iff� 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 call
the� 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 equations
hold if the function� h� happens to be�
totally multiplicative� and
its�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 Langford
briefly investigated how convolution could be defined to allow the above to hold�
only� for totally-multiplicative factors...
(2004-11-27) � Fractional Dirichlet-Power of an Arithmetic Function:
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 arithmetic
function� 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) � Dirichlet-Powers of the M�bius Function�
m
Negative powers are positive powers of its inverse� u = 1,1,1,1,1,1...
The Dirichlet power� m[k]�
of the M�bius function happens to have a
very nice� explicit definition�
(in terms of its values at the powers of any prime p):
m[k] (pn )
� = � (-1)n C(k,n)
This formula holds even if� k� is� negative�
(powers of� u = m[-1]�,
including� d�=�u*u�).�
More surprisingly, it's also true for�
fractional� values of�k:
Dirichlet square root of the M�bius function�: �
m [ ½ ] (pn�) �=�
(-1)n 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
(2002-11-16) � Convolutive subgroup�
generated�
by� u� (or� m)� 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�
m� and/or its inverse� u� follow the pattern�
generalized� in the previous section,� namely:
The simplest multiplicative function excluded from this
is 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) �
Dirichlet Powers of a Multiplicative Function� f
Their values on� { pn | n = 1,2,3... }� depend only on values
of� 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�
yp(0)�=�1�
uniquely determines a multiplicative function, provided only that�
yp (z) � = �
� n�
f (pn )� zn
The following beautiful formula determines the
Dirichlet power of� f� for any exponent��k�
(the� Dirichlet inverse� of� f�
is obtained for� k�=�-1�).
yp (z) k � = �
� n�
f[k] (pn )� zn
A similar relation� defines� the Dirichlet product of two
multiplicative functions:
(
� n�
f (pn )� zn
) (
� n�
g (pn )� zn
)
� � = � �
� n �
f
*g (pn )� zn
Essentially, a� multiplicative function� is thus usefully
described 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 components
are ordinary� Cauchy products�
of the corresponding pairs of component sequences.�
That's all there is to it.
(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�that case,� the Dirichlet inverse� g�
verifies � 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.
Dirichlet-Inverse� g� of a totally-multiplicative function� f
g (n) � = � m (n)� f (n)
A� completely multiplicative� arithmetic function� f� and its
Dirichlet-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 of the above formula, with �
yp (z)�-1
�=�
1-�f�(p)�z
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.
This applies, in particular, to the� Dirichlet characters�
(presented next)� as�those are indeed�
totally multiplicative.
Unless it's 1 everwhere,� a� totally multiplicative� must vanish at zero.
This need not be so for partially multiplicative functions, as their conditional
multiplicativity holds vacuously when one factor is zero�
(0�isn't coprime to any integer).
People rarely bother defining the value of a multiplicative
function at zero because it's almost always irrelevant.
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 stated
to verify� f�(n)�=�n� when� n� is� 0� or��1.
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.
The� conductor� of a given Dirichlet character
is its� smallest� period.�
The characters to the modulus k with conductors equal to k are called�
primitive�
(those whose conductors are proper divisors
of� k� are called� imprimitive�).
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 distinct Abelian groups of order�4,�
namely,� the cyclic group (k=5, k=10) and the
Klein group (k=8, k=12).
Incidentally,� the entries in any row, beyond the first one, add up to zero.�
That's�to�say that any� nontrivial� character�
c� of period� k�
satisfies a� linear�recurrence relation of order� k-1.� Namely:
c(n+k-1) � = �
- c(n+k-2)
- ...
- c(n+1)
- c(n)
Collectively, the �f(k)�
characters modulo k form a�group�
with respect to pointwise multiplication�
(isomorphic� to the multiplicative group
of the residues coprime to k)� whose neutral element is
the 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� c1�
in the above tables.
This should not be confused with the� trivial character�
(denoted above by the symbol��u�)�
which is the unique character to the modulus�1� and whose value is
simply 1 for all positive integers� [and 0 at point 0].
We have indexed the characters in those tables with the multiplicative
residues modulo k� themselves, in accordance with the aforementioned isomorphism
(for the smallest relevant k).�
This convention makes the above tables symmetrical:
cm (n)
� = �
cn (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 generalizing
the Legendre symbol�
(of quadratic reciprocity fame).� Generalized versions
of the Legendre symbol often go by other names� (Jacobi symbol or
Kronecker symbol)� which we don't advocate, because such
nomenclature is not technically needed...
c(n) � = � ( n | k )
That's sometimes called� the alternating character� of period� k�
(especially when� k�=�4).� The above tables always show this particular character
in�the last row� (�green shading�).�
Recall that the Kroneker generalization of
the Legendre symbol obeys the following ad 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 of
an odd prime�
(A033948)�
then the corresponding group is cyclic�
(i.e., it has a primitive root).�
In that case, we may consider a given primitive root� r� of the
multiplicative group formed by the
invertible elements modulo�k,�
often denoted
(/k)*,�
and state that every character�
c� modulo k is obtained by the following defining
relation for� some�
f(k)-th� root of unity� z�
(not necessarily a primitive one).
" n � �
c(rn )
� = � z n
Some of the above tables were so obtained;� sorting columns in ascending
order of the arguments� (r�n�).�
Here's another way to present things:
f(k) = 16
� � � z16 �=� 1
c�( n )
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
*
�
f(k) = 18
� � � z18 �=� 1
c�( n )
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):
f(k) = 12
� � � x2 �=� 1
� � � y6 �=� 1
c�( n )
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)*� into
the group of the� f(k)-th� roots of unity.
(2007-04-17) � Euler Products and Dirichlet L-Functions
Consider the series � F(s) �=�
Sn� f�(n) n-s
� for some value of s.
If� f� is a multiplicative function,
this can be expressed as an� Euler product�,�
namely an�infinite product whose factors are functions of all the consecutive
primes: p�=�2, 3, 5, 7, 11, ... �
(HINT:�
Every coefficient�
f�(n)� appears in the expansion of this product, tied to the
unique factorization of�
n� into primes.)
This� formal� equality� (discarding issues of numerical
convergence)� holds� if�and only if� the function�
f� is� multiplicative, in the sense
specified above.
When� f� is totally multiplicative,
each Euler factor becomes a geometric series, which we may sum up
to obtain the simple relation:
When� f (n) = 1� for any n�
(with the above notations, f� is
the trivial character� u�)�
that relation expresses Riemann's�
zeta function�
F(s)�=�z(s).
z(s) � = �
Sn� n-s
� = �
Pp�
( 1 �-� p-s
) -1
If� f�
is a Dirichlet character c,
the above is called a� Dirichlet L-function�:
The above series converges only for� Re(s)�>�0� but it has
an� analytic continuation�
to the entire complex plane� (without singularities)�
brought about by the following� reflection formula,�
using the Gamma function:
b(1-s) � = �
(p/2)-s� sin(ps/2)�
G(s)�
b(s)
It's� conjectured� that the analytic continuation of any series in� n-s�
with� totally multiplicative� coefficients which satisfies
such 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 critical
line� (Re(s)�=��).
That can be described as the original series without the composite indices,� except
prime powers,� for which the terms are divided by the exponent.�
This presentation looks "magical" and is a favorite of Grant Sanderson (who rarely bothers
if ever to give the above proof, which works for any absolutely convergent series (so
the terms can be commuted freely
without changing the sum) with totally multiplicative ceoefficients
(Dirichlet characters are an example).� Examples:
(2007-04-17) � Introducing the Hurwitz Zeta Function
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:
z(s,q) � = �
Sn�
(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 c
to the modulus�k� is just a�linear combination of Hurwitz zeta functions
(for rational values of q):
L(s,c) � = � k-s �
k
�
n=1
� c(n) z(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 the
Dirichlet characters� c� to the modulus�k,
namely:
(2020-08-24) � The Vector-Space of Additive Functions
A class of� arithmetic functions� similar to� multiplicative functions.
An arithmetic function� with numerical values is said to be addittive if
f (ab) �=� f (a) �+� f (b) � �
whenever the integers a and b are coprime.
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 ) � = � n f (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 a
scalar 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: �
w (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.
