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).
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 :
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 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:
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))))))
(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 coprimeintegers
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:
x = 3121 + 15625 n
y = 204 + 1024 n
Indeed: 1024 ( 3121 + 15625 n ) -
15625 ( 204 + 1024 n ) = 8404
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 allcoprime 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:
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 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 thats(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 oldestunsolved 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 nthMersenne 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.
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.
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 :
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 sequenceA000225.
Similarly, Fibonacci primes occur only at prime indices within the
Fibonacci sequenceA000045,
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
-
n3/2
+ 1 -
3
n1/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) :
Fn =
[ fn
-
(-f)-n ] /
Ö5
where
f = (1+Ö5) / 2
= 1.61803...
Jacques Binet
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).
The Fibonacci (or golden) sequence (A=1,B=1) is the first
metallic sequence (A=1).
Next is Silver (B=2),
Bronze (B=3),
Copper (B=4),
Nickel (B=5), etc.
The zeroth metallic ratio is platinum (B=0), with f0 =1.
f B =
½ [ B + Ö(1+B2 ) ]
(2007-11-29)
Cassini's Identity (1680)
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 withoutfactoring the argument):
Dirichlet unit:
e(pn ) = 0 [e(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]
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
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
aboveDirichlet 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 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 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) =
å nf (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 =
å nf[k] (pn ) zn
A similar relation defines the Dirichlet product of two
multiplicative functions:
(
å nf (pn ) zn
) (
å ng (pn ) zn
)
=
å nf
*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.
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).
k = 1
n
0
u(n)
1
k = 2
n
1
0
c1 (n)
1
0
k = 5 f(k) = 4
n
1
2
3
4
0
c1 (n)
1
1
1
1
0
c2 (n)
1
i
-i
-1
0
c3 (n)
1
-i
i
-1
0
c4 (n)
1
-1
-1
1
0
k = 10
1
3
7
9
*
k = 3
n
1
2
0
c1 (n)
1
1
0
c2 (n)
1
-1
0
k = 4 f(k) = 2
n
1
2
3
0
c1 (n)
1
0
1
0
c3 (n)
1
0
-1
0
k = 6 f(k) = 2
n
1
2
3
4
5
0
c1 (n)
1
0
0
0
1
0
c5 (n)
1
0
0
0
-1
0
k = 7 f(k) = 6
n
1
2
3
4
5
6
0
c1 (n)
1
1
1
1
1
1
0
c2 (n)
1
w2
-w
-w
w2
1
0
c3 (n)
1
-w
-w2
w2
w
-1
0
c4 (n)
1
-w
w2
w2
-w
1
0
c5 (n)
1
w2
w
-w
-w2
-1
0
c6 (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 f(k) = 4
n
1
2
3
4
5
6
7
0
c1 (n)
1
0
1
0
1
0
1
0
c3 (n)
1
0
-1
0
1
0
-1
0
c5 (n)
1
0
1
0
-1
0
-1
0
c7 (n)
1
0
-1
0
-1
0
1
0
k=12
1
*
5
*
7
*
11
*
w =
exp ( ip/3 )
=
(1+iÖ3) / 2
[ w3 = -1 ]
k = 11 f(k) = 10
x =
exp ( ip/5 )
n
1
2
3
4
5
6
7
8
9
10
0
c1 (n)
1
1
1
1
1
1
1
1
1
1
0
c2 (n)
1
x
-x3
x2
x4
-x4
-x2
x3
-x
-1
0
c3 (n)
1
-x3
x4
-x
x2
x2
-x
x4
-x3
1
0
c4 (n)
1
x2
-x
x4
-x3
-x3
x4
-x
x2
1
0
c5 (n)
1
x4
x2
-x3
-x
-x
-x3
x2
x4
1
0
c6 (n)
1
-x4
x2
-x3
-x
x
x3
-x2
x4
-1
0
c7 (n)
1
-x2
-x
x4
-x3
x3
-x4
x
x2
-1
0
c8 (n)
1
x3
x4
-x
x2
-x2
x
-x4
-x3
-1
0
c9 (n)
1
-x
-x3
x2
x4
x4
x2
-x3
-x
1
0
c10 (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 f(k) = 12
y =
exp ( ip/6 )
n
1
2
3
4
5
6
7
8
9
10
11
12
0
c1 (n)
1
1
1
1
1
1
1
1
1
1
1
1
0
c2 (n)
1
y
y4
y2
-y3
y5
-y5
y3
-y2
-y4
-y
-1
0
c3 (n)
1
y4
y4
-y2
1
-y2
-y2
1
-y2
y4
y4
1
0
c4 (n)
1
y2
-y2
y4
-1
-y4
y4
-1
y4
-y2
y2
1
0
c5 (n)
1
-y3
1
-1
-y3
-y3
y3
y3
1
-1
y3
-1
0
c6 (n)
1
y5
-y2
-y4
-y3
y
-y
y3
y4
y2
-y5
-1
0
c7 (n)
1
-y5
-y2
-y4
y3
-y
y
-y3
y4
y2
y5
-1
0
c8 (n)
1
y3
1
-1
y3
y3
-y3
-y3
1
-1
-y3
-1
0
c9 (n)
1
-y2
-y2
y4
1
y4
y4
1
y4
-y2
-y2
1
0
c10 (n)
1
-y4
y4
-y2
-1
y2
y2
-1
-y2
y4
-y4
1
0
c11 (n)
1
-y
y4
y2
y3
-y5
y5
-y3
-y2
-y4
y
-1
0
c12 (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
*
We didn't simplify y2 and
y3 to w and i
(to allow y to be any 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
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) =
Snf (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.)
Pp
( 1 + f (p) p-s
+ f (p2 ) p-2s
+ f (p3 ) p-3s
+ f (p4 ) p-4s
+ ... )
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:
F(s) =
Snf (n) n-s
=
Pp
( 1 - f (p) p-s
) -1
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 :
L(c,s) =
Sn
c (n) n-s
=
Pp
( 1 -
c (p) p-s
) -1
n mod 4
1
2
3
0
c1 (n)
1
0
1
0
c3 (n)
1
0
-1
0
Here's what's obtained in the case of the two
Dirichlet characters modulo 4, given at right.
The first one reduces to the zeta function:
L(c1,s) =
(1-2-s ) z(s)
The other one (the alternating character of period 4)
defines Dirichlet's
Beta function, which is also known as
Catalan's Beta 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) = ½).
(2021-07-03) Logarithm of Dirichlet L-Functions
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
c(p) p-s never exceeds 1:
Log L(c,s)
=
- åp
Log ( 1 -
c (p) p-s )
=
åp
åk
c (pk) (pk )-s / k
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.