home | index | units | counting | geometry | algebra | trigonometry | calculus | functions
analysis | sets & logic | number theory | recreational | misc | nomenclature & history | physics
 border
 border

Final Answers
© 2000-2023   Gérard P. Michon, Ph.D.

Number Theory

God created the integers, all else is the work of man.
Leopold Kronecker (1823-1891)

Articles previously on this page:

 border
 border
 Michon

See also:

Related Links (Outside this Site)

Mathematics Enrichment  |  NRICH Prime Site  |  Plus Magazine  |  Math Mojo
What's Special About This Number?  by Erich Friedman of Stetson University.
Conjectures  at The Prime Puzzles & Problems Connection, by Carlos Rivera.
The Half-Totient Tree by Kevin Brown (1995-02-03)
Bézout's Identity for Gaussian Integers  by  Larry Freeman.
Arithmetic Progressions of Three Squares  by  Keith Conrad.
 
border
border

Arithmetic  and  Number  Theory


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

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

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

Time is defined so that motion looks simple.

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

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

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

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

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

What you'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.

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


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

No it's not, although it comes close.  Even in the realm of positive integers the number 1 is neither composite nor prime (see previous article).  The 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.   Adam Ries 
 (1492-1559) 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?

 Carl Friedrich Gauss 
(1777-1855) 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.

Smallest (Positive) Gaussian Primes
1+i, 2+i, 2-i, 3, 3+2i, 3-2i, 4+i, 4-i, 5+2i, 5-2i, 6+i, 6-i, 5+4i, 5-4i, 7, 7+2i ...

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:

LCM ( 3, 7, 24, 86, 125, 214 )   =   23 ´ 3 ´ 53 ´ 7 ´ 43 ´ 107   =   96621000

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:

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

vorobya (Alexey Vorobyov. 2002-10-18)   Aurifeuillian 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 :

4 a4  +  b4   =   ( 2 a2 - 2ab + b2 )  ( 2 a2 + 2ab + b2 )

A similar identity shows that   n6 + 27   is neither prime nor semiprime:

27 a6  +  b6   =   ( 3 a2 - 3ab + b2 )  ( 3 a2 + b2 )  ( 3 a2 + 3ab + b2 )

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 printLes 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).
 
 Antoine Aurifeuille
 (aka Alfred de Caston) 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.

How was F6 factored?   by  Hugh C. Williams  (1993)
 
Cunningham Numbers by Tim Morrow   |   Aurifeuillian Factorizations (MersenneForum)
 
Video :  (a+b)2 - (a+b)2  =  4 ab   Area of a Triangle  by  Presh Talwalkar  (MindYourDecisions, 2013-12-22).


 Gerard Michon (2020-05-28)   High-order  Aurifeuillian  Factorizations
Here are some algebraic factorizations, among many others.

a2 - b2     =     ( a - b )  ( a + b )
a3 - b3     =     ( a - b )  ( a2 + ab + b2 )
a3 + b3     =     ( a + b )  ( a2 - ab + b2 )
( 2 a2 ) 2  +  b4 = ( 2 a2 - 2ab + b2 )  ( 2 a2 + 2ab + b2 )
( 3 a2 ) 3  +  b6 = ( 3 a2 - 3ab + b2 )  ( 3 a2 + b2 )  ( 3 a2 + 3ab + b2 )
( 5 a2 ) 5  -  b10 = ( 5 a2 - b2 )  ( 25 a4 - 25 a3 b + 15 a2 b2 - 5 a b3 + b4 )
( 25 a4 + 25 a3 b + 15 a2 b2 + 5 a b3 + b4 )
( 7 a2 ) 7  +  b14 = ( 7 a2 + b2 ) ×
( 73 a6 - 73 a5b + 3×72 a4b2 - 72 a3 b3 + 3×7 a2 b4 - 7 a b5 + b6 )
( 73 a8 + 73 a7b + 3×72 a4b2 + 72 a3 b3 + 3×7 a2 b4 + 7 a b5 + b6 )
a18  -  b18 = ( a - b )  ( a + b ) ×
( a2 - a b + b2 )  ( a6 + a3 b3 + b6 )
( a2 + a b + b2 )  ( a6 - a3 b3 + b6 )
( 11 a2 )11  +  b22 = ( 11 a2 + b2 ) ×
(115a10-115a9b+5×114a8b2-114a7b3-113a6b4+113a5b5-112a4b6-112a3b7+5×11a2b8-11ab9+b10)
(115a10+115a9b+5×114a8b2+114a7b3-113a6b4-113a5b5-112a4b6+112a3b7+5×11a2b8+11ab9+b10)
( 13 x2 )13  -  1 = ( 13 x2 - 1 ) ×
(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).

( 1133 + 2322 ) / ( 113 + 232 )   =   526636296123323 × 23711108297379757

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:

(1717 2434 - 1)  /  (17×242 - 1)   =   81077141422755792907751304373417
× 88122823335010249161498758966233

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))))))

Likewise,   (19x2 )19 + 1   =   (19x2 + 1)  P19 (-x)  P19 (x)   where:
P19 (x)   =   A19 ( 19 x2 )  +  (19 x) B19 ( 19 x2 )   with
A19 (y)   =   1+y (9+y (17+y (27+y (31+y (31+y (27+y (17+y (9+y))))))))
B19 (y)   =   1+y (3+y (5+y (7+y (7+y (7+y (5+y (3+y)))))))

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.

Numericana :   Lucas coefficients
 
The Search for Aurifeuillian-like Factorizations  by  Samuel S. Wagstaff, Jr. (1945-)
 
On primitive prime factors of an-bn   by   Andrzej Schinzel (1937-)
Proc. Cambridge Philos. Soc., 58, 4,  pp 555-562 (October 1962).


(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):

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

Note that  u  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
bezout(x,y)
 

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

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

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

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.

Bézout's Lemma in the Language of  Rings and Ideals :

m Z  +  n Z     =     GCD(m,n) Z

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 sumsMinkowski products  or  Minkowski operations.

Thus,  n Z  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 commensurable iff 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

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 Î Z :

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   Done!

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  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    QED

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).

 x   1  3 5157 2135945113363 551377
y 0412824 20124028605616 488436
z 15131725 29374153616565 738585

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

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

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

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

1105 is the hypothenuse of 13 distinct nontrivial Pythagorean triplets:

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

Smallest hypothenuse of at least  N  distinct Pythagorean triples
N 123,45,6,78,9 ... 13 14,15 ... 2223, 24 ... 3132, 33 ... 40
A088959 525653251105 55252762532045

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

All possible Pythagorean triples, visualized (15:55)  by  Grant Sanderson (3Blue1Brown, 2017-05-26).
 
Fibonacci & Pythagorean triples: A beautiful connection (42:34)  by  Burkard Polster (Mathologer, 2022-12-03).


(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.

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

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

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

  1. N is the product of 3 distinct primes.
  2. N is the product of a prime by the cube of another prime.
  3. N is the seventh power of a prime.
There are a lot more solutions this time:
  1. The first class of solutions starts with 2´3´5 = 30, 2´3´7= 42, 2´3´11=66, 2´5´7=70, 2´3´13=78, 2´3´17=102, 3´5´7=105, 2´5´11=110, 2´3´19=114, 2´3´23=138, etc.
  2. The second class starts with 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.
  3. The third class is the sequence of seventh powers of primes: 128, 2187, 78125, 823543, etc.
The combined list is therefore: 24, 30, 40, 42, 54, 56, 66, 70, 78, 88, 102, 104, 105, 110, 114, 128, 130, 135, 136, 138, 152, 154, 165, 170 ... A030626.

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


(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.

Video :   Maths Puzzle: Back to Black  by  James Grime  (2012-01-08).


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 = pQ  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.

1, 6, 8, 10, 14, 15, 16, 21, 22, 24, 26, 27, 30, 33, 34, 35, 38, 39, 40, 42, 46,  51, 54, 55, 56, 57, 58, 60, 62, 65, 66, 69, 70, 72, 74, 77, 78, 81, 82, 84, 85, 86, 87, 88, 90, 91, 93, 94, 95, 96, 102, 104, 105, 106, 108, 110, 111, 114, 115, 118, 119, 120, 122, 123, 125, 126, 128, 129, 130 ...   (A048943)

Divisor Product  by  Eric W. Weisstein,  in MathWorld


(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:

  • No fewer than 300 decimal digits.  [BCR 1991]
  • A prime factorization with only one odd exponent.
  • At least three prime factors greater than 100.   [Iannucci 2000]
  • At least two prime factors greater than 10000.   [Iannucci 1999]
  • At least one prime factor greater than 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)


 Marin Mersenne (2000-10-25)  Mersenne Numbers  &  Mersenne Primes
The ongoing search for prime numbers of the form  2- 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.)

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

The list is widely believed to be  infinite,  but this has yet to be proved.

In recent years  (since 1989)  the largest known prime has always been a Mersenne prime  (contrary to popular belief,  this wasn't always so).

The  17  largest  known  Mersenne primes were found by  GIMPS :
RankPrime NumberDigitsDiscovered byDate
51 ?2 82589933-1   24862048 Patrick Laroche 2018-12-21
50 ?2 77232917-1   23249425 Jonathan Pace 2018-01-03
49 ?2 74207281-1   22338618 Curtis Cooper 2016-01-07
482 57885161-1   17425170 Curtis Cooper 2013-01-25
472 43112609-1   12978189 Edson Smith, UCLA2008-08-23
462 42643801-1   12837064 Odd Magnar Strindmo2009-04-12
452 37156667-1   11185272 Hans-Michael Elvenich2008-09-06
442 32582657-1   9808358 Curtis Cooper, Steven Boone2006-09-04
432 30402457-1   9152051 Curtis Cooper, Steven Boone2005-12-05
422 25964951-1   7816230 Dr. Martin R. Nowak2005-02-18
412 24036583-1   7235733 Josh Findley2004-05-15
402 20996011-1   6320430 Michael Shafer2003-11-17
392 13466917-1   4053946 Michael Cameron2001-11-14
382 6972593-1   2098960 Nayan Hajratwala1999-06-01
372 3021377-1   909525 Roland Clarkson1998-01-27
362 2976221-1   895932 Gordon Spence1997-08-24
352 1398269-1   420921 Joël Armengaud1996-11-13

See www.mersenne.org  for the latest update on the search for Mersenne primes.

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

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

 Leonhard Euler 
 (1707-1783) 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,  Dr. John Selfridge, c. 1997  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 Prime Factors of Mersenne Numbers


(2009-04-27)   Multiperfect Numbers  &  Hemiperfect Numbers

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).
s(n)/n   Multiperfect Numbers  (MPN)   A007691  Count 
1 11
2 6, 28, 496, 8128, 33550336, 8589869056, 137438691328 ... ¥ ?
3 120, 672, 523776, 459818240, 1476304896, 510011801606
4 30240, 32760, 2178540, 23569920, 45532800, 142990848, 1379454720, 43861478400, 66433720320, 153003540480, 403031236608, 704575228896, 181742883469056, ... 36
5 14182439040, 31998395520, 518666803200, 13661860101120, 30823866178560, 740344994887680, 796928461056000, 212517062615531520, 69357059049509038080, 87934476737668055040, 170206605192656148480, 1161492388333469337600, 1245087725796543283200, ...65
6 154345556085770649600, 9186050031556349952000, 680489641226538823680000, 6205958672455589512937472000, 13297004660164711617331200000, 15229814702070563916152832000, 34111227434420791224041472000, 36669339708545656151565926400, 41254809330254618094796800000, 52693888533626064627302400000, 59023729003862626557345792000 ...245
7 141310897947438348259849402738485523264343544818565120000 ...516 ?

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:

2468 . 3140 . 566 . 749 . 1140 . 1331 . 1711 . 1912 . 239 . 297 . 3111 . 378 . 415 . 433 . 473 . 534 . 593 . 612 . 674 . 714 . 733 . 79 . 832 . 89 . 974 . 1014 . 1033 . 1093 . 1132 . 1273 . 1313 . 1372 . 1392 . 1492 . 151 . 1572 . 163 . 167 . 173 . 181 . 191 . 1932 . 197 . 199 . 2113 . 223 . 227 . 2292 . 239 . 251 . 257 . 263 . 2693 . 271 . 2812 . 293 . 3073 . 313 . 317 . 331 . 347 . 349 . 367 . 373 . 397 . 401 . 419 . 421 . 431 . 4432 . 449 . 457 . 461 . 467 . 491 . 4992 . 541 . 547 . 569 . 571 . 599 . 607 . 613 . 647 . 691 . 701 . 719 . 727 . 761 . 827 . 853 . 937 . 967 . 991 . 997 . 1013 . 1061 . 1087 . 1171 . 1213 . 1223 . 1231 . 1279 . 1381 . 1399 . 1433 . 1609 . 1613 . 1619 . 1723 . 1741 . 1783 . 1873 . 1933 . 1979 . 2081 . 2089 . 2221 . 2357 . 2551 . 2657 . 2671 . 2749 . 2791 . 2801 . 2803 . 3331 . 3433 . 4051 . 4177 . 4231 . 5581 . 5653 . 5839 . 6661 . 7237 . 7699 . 8081 . 8101 . 8269 . 8581 . 8941 . 10501 . 11833 . 12583 . 12941 . 13441 . 14281 . 15053 . 17929 . 19181 . 20809 . 21997 . 23063 . 23971 . 26399 . 26881 . 27061 . 28099 . 29251 . 32051 . 32059 . 32323 . 33347 . 33637 . 36373 . 38197 . 41617 . 51853 . 62011 . 67927 . 73547 . 77081 . 83233 . 92251 . 93253 . 124021 . 133387 . 141311 . 175433 . 248041 . 256471 . 262321 . 292561 . 338753 . 353641 . 441281 . 449653 . 509221 . 511801 . 540079 . 639083 . 696607 . 746023 . 922561 . 1095551 . 1401943 . 1412753 . 1428127 . 1984327 . 2556331 . 5112661 . 5714803 . 7450297 . 8334721 . 10715147 . 14091139 . 14092193 . 18739907 . 19270249 . 29866451 . 96656723 . 133338869 . 193707721 . 283763713 . 407865361 . 700116563 . 795217607 . 3035864933 . 3336809191 . 35061928679 . 143881112839 . 161969595577 . 287762225677 . 761838257287 . 840139875599 . 2031161085853 . 2454335007529 . 2765759031089 . 31280679788951 . 75364676329903 . 901563572369231 . 2169378653672701 . 4764764439424783 . 70321958644800017 . 79787519018560501 . 702022478271339803 . 1839633098314450447 . 165301473942399079669 . 604088623657497125653141 . 160014034995323841360748039 . 25922273669242462300441182317 . 15428152323948966909689390436420781 . 420391294797275951862132367930818883361 . 23735410086474640244277823338130677687887 . 628683935022908831926019116410056880219316806841500141982334538232031397827230330241

Here are other numbers which divide  twice  the sum of their divisors:

s(n)/n   Hemiperfect Numbers  (HPN)   A159907  Count 
3/221
5/2 24, 91963648, 102002360323
7/2 4320, 4680, 26208, 20427264, 197064960, 21857648640, 57575890944, 88898072401645056, 301183421949935616, 9083288595228991885541376, 22290964134962716779872256, 230361837156847526055247872, 3551746147589248994873004392448, 8716209461184471402733217906688, 90076051101488582786918337478656, 275517471462331149989751161880576, 8319263987369391948455878608398843904, 20415999472827819113761327282781159424, 3081634264657305632386843579602306072576, 93050102500349677040144591462063024482811904, 228350830852095014942603539620449439316967424. 21
9/2 8910720, 17428320, 8583644160, 57629644800, 206166804480, 1416963251404800, 15338300494970880, 6275163455171297280, 200286975596707184640, 215594611071909888000, 5997579964837140234240, 39887491844324122951680, 189478877946949032837120, 464993138593758319902720, 4577250484712348791603200, 314220801442981320248524800, 14048146725436554258960875520, 20270811496597107858493931520, 81703797123392614369698250752, 612078178502919543930287114158080, 939834592031480161274941547741184, 1502078523847443989273473166868480, 2306413471743588373372911017263104, 157127060125322787706213898932715520, 954799029953763034837845432097308672, 2343137147924117580221226004651180032, 11528505172715763556107234109992568639979520000. 27
11/2 17116004505600, 75462255348480000, 6219051710415667200, 14031414189615513600, 352444116692828160000, 835095457414213632000, 59485231752222033838080, 64031599488357236736000, 564178061132326319357952000, 1208818605469519237939200000, 1384528609279142174195712000, 3101020675856435565821952000, 3333576337140514195596902400   ...117
or
more
13/2 170974031122008628879954060917200710847692800, 1893010442758976546037991125738431754692198400, 54361481238923605327597493185154939181072384000, 251754911117461891901909334695193204308626636800, 1896011572527867940620729403187025422081379532800, 1949479690331253229796013159150974699442693734400   ...303
or
more

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:

s-1 (n)   =   s-1 (7 n) / s-1 (7)   =   7 / (8/7)   =   72 / 8
Therefore,   s-1 (72 19 n)   =   s-1 (72 19)  72 / 8   =   15/2

One satisfactory cofactor is:    n   =   2121. 324. 57. 116. 135. 173. 23 . 292. 312. 43 . 47 . 61 . 67 . 79 . 83 . 103 . 109 . 1572. 233 . 281 . 313 . 331 . 373 . 827 . 1549 . 2833 . 8269 . 8387 . 8951 . 9293 . 37171 . 45319 . 391151 . 1824726041 . 768614336404564651 . 2305843009213693951

The above replacement of the partial factorization   7190   by   7191   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:

s-1 ( 115. 17 . 372. 43 . 67 . 79 / s-1 ( 114. 37 . 432. 792. 179 . 631 . 3221 )   =   16 / 15

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:

268 . 325 . 57 . 712 . 135 . 194 . 232 . 29 . 47 . 612 . 71 . 97 . 103 . 131 . 137 . 1512 . 1572 . 197 . 2112 . 313 . 421 . 439 . 547 . 709 . 769 . 811 . 827 . 853 . 877 . 911 . 1093 . 1621 . 8269 . 19993 . 36833 . 110563 . 178481 . 3985812 . 797161 . 32668561 . 16148168401 . 10052678938039

Abundancies  15/2,  17/2,  19/2  and beyond...

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 :

12749472205565550032020636281352368036406720997031277595140988449695952806020854579200000
=   235. 320. 55. 76. 112. 132. 17 . 192. 23 . 29 . 312. 372. 41 . 61 . 67 . 73 . 83 . 109 . 127 . 137 . 263 . 331 . 409 . 547 . 1093 . 4733 . 36809 . 368089

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).

n   =   3.30181224610218582352934080494271949153807... 10 285
     =   2104. 343. 59. 712. 116. 134. 194. 232. 29 . 314. 373. 412. 432. 472. 53 . 59 . 61 . 67 . 713. 73 . 792. 83 . 89 . 97 . 1032. 107 . 127 . 1312. 1372. 1512. 191 . 211 . 241 . 331 . 337 . 431 . 521 . 547 . 631 . 661 . 683 . 709 . 911 . 1093 . 1301 . 1723 . 2521 . 3067 . 3571 . 3851 . 5501 . 6829 . 6911 . 8647 . 17293 . 17351 . 29191 . 30941 . 45319 . 106681 . 110563 . 122921 . 152041 . 570461 . 16148168401

By contrast,  19  never  appears with multiplicity one  in any known 10-perfect number.  We don't know any number of abundancy 19/2 (yet).

Multiply Perfect Numbers by  Achim Flammenkamp  (Universität Bielefeld)
Multiperfect Numbers  by  Eric W. Weisstein   |   Abundancy Resources  by  Walter Nissen
Nombres tétraparfaits  by  Édouard Lucas (1842-1891), quoted (in French)  by  Charles-É. Jean.
 
The Six Triperfect Numbers (7:36)  by  James Grime  (Numberphile, 2018-06-29).


(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?)

 The quantity z a^n 
 remains the same at 
 both points A & B

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  an modulo 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.

"On the partition function p(n)"  by  Hans Rademacher (1892-1969)
Proceedings of the London Mathematical Society, 43, pp. 241-254  (1938).

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

(1+x+x2+x3+...) (1+x2+x4+x6+...) (1+x3+x6+...) (1+x4+x8+...) (...) ...

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.

Values of the Partition Function   [ more... ]
n 01234567 891011121314 1516171819
 p(n)  1123571115 2230425677101135 176231297385490

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   Leonhard Euler 
 (1707-1783) 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
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).

L-adic Properties of the Partition Function (pdf)
by  Amanda Folsom, Zachary A. Kent, and Ken Ono   (21 January 2011)
That result was immediately given a shorter proof  by  Frank Calegari  (bef. 2011-01-27).
 
An Algebraic Formula for the Partition Function (pdf)
by  Jan Hendrik Brunier and Ken Ono   (21 January 2011)
 
A suprise dimension to adding and counting (video)
Lecture delivered on 2011-01-21 by  Ken Ono  (2011-01-27)
 
New math theories reveal the nature of numbers  PR by  Beverly Clark, Emory University  (2011-01-20)
New math theories reveal the nature of numbers  First reactions at Physorg.com forum  (2011-01-20)
Finite formula found for partition numbers   by  S.C. Kavassalis   (2011-01-20)
Sequence of partition numbers found to be fractal   by  Ktwop   (2011-01-21)
Euler's Partition Function Theory Finished   by  Soulskill   (2011-01-21)
Ken Ono cracks partition number mystery   by  Yuiop  on PhysicsForum   (2011-01-21)
Una nueva teoría matemática revela la naturaleza de los números  ABC/Ciencia, Madrid  (2011-01-21).
Algebraic Formula for Partition Numbers (News) & Archives...   by  Robin Whitty   (2011-01-22)
Ken Ono Leads Team in Recent Mathematical Discovery  by  Elizabeth Bruml  for  emorywheel.com   (2011-01-24)
Una nueva teoría matemática revela la naturaleza de los números  by  En Línea Directa  (2011-01-26)
Deep meaning in Ramanujan's Simple Pattern.    by  Jacon Aaron  (2011-01-27)
Euler's Legacy:  Mathematiker feiern Entdeckung in der Zahlentheorie.   (2011-01-27)
 
Videos :   New Theories Reveal the Nature of Numbers  by  Ken Ono   (2011-01-27)
 
Partition numbers & Euler's pentagonal formula (53:33)  by  Burkard Polster  (Mathologer, 2020-10-17).


 Gerard Michon 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 Ù Uq = ( Up-q Uq+1 + B Up-q-1 Uq ) Ù Uq   =   ( Up-q Uq+1 ) Ù Uq
= 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.  Halmos

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.  Halmos

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

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

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

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

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

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

Computer-assisted proofs


(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).

 Come back later, we're
 still working on this one...

(2008-05-06)   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):

n3Perfect SquaresCount
001
11, 42
89, 16, 253
2736, 492
6464, 81, 100, 1214
125144, 169, 1963
216225, 256, 289. 3244
343361, 400, 441, 4844
512529, 576, 625, 6764
729729, 784, 841, 900, 9615
 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:

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

closed formula  for this  bit sequence  is easy to obtain:

bn   =    floor
floor
( n3 + 3n2 + 3n ) 1/2 floor
floor
  -   ceiling
ceiling
n 3/2 ceiling
ceiling
  +   1   -   floor
floor
3   n 1/2 floor
floor
vinculum
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 )  
0p(j)1-p(j)
11-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"  (V, V).

For example, the (first part of) the above lemma can be construed as expressing any such sequence  V  as a linear combination of the two linearly independent sequences of coordinates  (0,1)  and  (1,A).  If the first of those is dubbed  U,  the second 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
vinculum
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
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 Golden Ratio  by  Ben Sparks (Numberphile, 2018-05-08).
 
The Silver Ratio and other metallic ratios,  by  Tony Padilla (Numberphile, 2018-05-11).
 
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 ) ]


 Jean-Dominique 
 Cassini (1625-1712) (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        QED


 Maurice d'Ocagne 
 (1862-1938) X1880 (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) 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 = WUi  where the value  W1 = (-B)m  is obtained immediately from Cassini's Identity.    QED

Curry's Paradox  by  Alexander Bogomolny
 
Philibert  Maurice d'Ocagne  du Plessis (1862-1938; X1880)   a.k.a. Pierre Delix, playwright.


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

Un2  -  Un+m Un-m     =     (-B)n-m  Um2       [ where  n ≥ m ]

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

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

Vn   =   an - (-B/a)n

Well, let's just evaluate   Vn2  -  Vn+m Vn-m     :

a2n  -  2 (-B)n  +  (-B/a)2n  -  { an+m - (-B/a)n+m }  { an-m - (-B/a)n-m }
=     -  2 (-B)n  +  (-B)n-m a2m  +  (-B)n+m / a2m
=     (-B)n-m  [ a2m  -  2 (-B)m  +  (-B/a)2m ]
=     (-B)n-m  Vm2    QED


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

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

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

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

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).

Faulhaber's formula   |   Johann Faulhaber (1580-1635)
 
Faulhaber formula and Euler-Maclaurin formula (50:00)  by  Burkard Polster  (Mathologer, 2019-10-26).
 
Faulhaber's formula  by  Robin Whitty  (Theorem of the Day #222).


(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 (af (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 ( p).  Here are some examples  (the first eight are easy to compute  without  factoring 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]
  • Principal character modulo m:   c(pn ) = 0  if p divides m;  1 otherwise.
  • 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
     
  • Möbius function:   m(p) = -1   and   m(pn ) = 0  for  n>1.
  • Euler's totient function:   f(pn )  =  pn-1 (p-1)
    f(n)  is the number of integers coprime to n, between 1 and n.
  • Pillai's GCD-sum function:  g(pn )  =  (n+1) pn - n pn-1  [K.A. Broughan]
    g(n) is the sum of the GCD's with n of the first n integers.  [ g = f*N ]
  • Inverse of the above :   g [-1] (pn ) = (p-1)2 or 1-2p if n=1. (A101035)
  • Dedekind's psi function:   y(pn )  =  pn-1 (p+1)   (A001615)
     
  • Liouville's function:   l(pn )  =  (-1)n   (A008836) 
  • Squarefree part:   sf (p2n )  =  1   and   sf (p2n+1 )  =  p   (A007913)
    The smallest multiplier which makes a number a perfect square. 
  • Cubefree part:   cf (pn )  =  p(n mod 3)   (A050985) 
  • Squarefree kernel  (or "radical") :   rad(pn )  =  p   (A007947)
    The  radical  of an integer is the product of its distinct prime factors. 
  • Multiplicative parity :   g(pn )  =  m(rad(pn ))  =  -1   (A076479). 
  • Enumeration of Abelian groups :   Abel (pn )  =  p(n)   (A000688)
    In this,  p(n)  is simply the number of partitions of n. 
  • Inverse of the above :   f (pn ) = 0  or (-1) 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)  if p is 1, 2 or 3 modulo 4.
    Totally multiplicative and period 4:  1, 0, -1, 0, ...  (A056594 or A101455) 
  • Ramanujan's  Tau function :   t(n)   (A000594) 

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 )

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 :

k.M + M/2 + M/3 + M/5 + M/7 + M/11 + M/13 + ... + M/p

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...

On the number of squarefree integers not exceeding  N


(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.

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

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|n f (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 QED

Generalization:  The Dirichlet Convolution

 Johann Peter Gustav Lejeune Dirichlet  
 1805-1859
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:

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  1973Eric Langford briefly investigated how convolution could be defined to allow the above to hold  only  for totally-multiplicative factors...

Math 105 notes, week #3  by  Carl Pomerance  (Dartmouth College).


(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 [ ½ ] (p)  =  (-1)n C(½,n)
m = 123456789 101112
m[½] (m)  1 -1/2-1/2-1/8-1/21/4 -1/2-1/16-1/81/4-1/21/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:

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

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:

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


(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)

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.


(2002-11-16)   Dirichlet Characters
An important example of  totally multiplicative functions.

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 10
c1 (n) 10
 
k = 5     f(k) = 4
n 12340
c1 (n) 11110
c2 (n) 1i-i-10
c3 (n) 1-ii-10
c4 (n) 1-1-110
k = 10 1379*
 
k = 3
n 120
c1 (n) 110
c2 (n) 1-10
 
k = 4     f(k) = 2
n 1230
c1 (n) 1010
c3 (n) 10-10
 
k = 6     f(k) = 2
n 123450
c1 (n) 100010
c5 (n) 1000-10
 
k = 7     f(k) = 6
n 12345 60
c1 (n) 11111 10
c2 (n) 1w2 -w -w w2 10
c3 (n) 1-w -w2 w2 w-10
c4 (n) 1-w w2 w2 -w10
c5 (n) 1w2 w -w -w2 -10
c6 (n) 11-11-1 -10
k=9 142758*
k=14 19311513*
k=18 113117517*
 

k = 8     f(k) = 4
n 12345670
c1 (n) 10101010
c3 (n) 10-1010-10
c5 (n) 1010-10-10
c7 (n) 10-10-1010
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 2345 678910 0 
c1 (n) 11111 111110
c2 (n) 1x-x3x2x4 -x4-x2x3-x-10
c3 (n) 1-x3x4-xx2 x2-xx4-x310
c4 (n) 1x2-xx4-x3 -x3x4-xx210
c5 (n) 1x4x2-x3-x -x-x3x2x410
c6 (n) 1-x4x2-x3-x xx3-x2x4-10
c7 (n) 1-x2-xx4-x3 x3-x4xx2-10
c8 (n) 1x3x4-xx2 -x2x-x4-x3-10
c9 (n) 1-x-x3x2x4 x4x2-x3-x10
c10 (n) 1-1111 -1-1-11-10
k=22 17953 1917131521*
 
k = 13     f(k) = 12       y  =  exp ( ip/6 )
n  1 2345 6789101112 0 
c1 (n) 11111 11111110
c2 (n) 1yy4y2 -y3y5-y5y3 -y2-y4-y -10
c3 (n) 1y4y4-y2 1-y2-y21 -y2y4y4 10
c4 (n) 1y2-y2y4 -1-y4y4-1 y4-y2y2 10
c5 (n) 1-y31-1 -y3-y3y3y3 1-1y3 -10
c6 (n) 1y5-y2-y4 -y3y-yy3 y4y2-y5 -10
c7 (n) 1-y5-y2-y4 y3-yy-y3 y4y2y5 -10
c8 (n) 1y31-1 y3y3-y3-y3 1-1-y3 -10
c9 (n) 1-y2-y2y4 1y4y41 y4-y2-y2 10
c10 (n) 1-y4y4-y2 -1y2y2-1 -y2y4-y4 10
c11 (n) 1-yy4y2 y3-y5y5-y3 -y2-y4y -10
c12 (n) 1-111-1 -1-1-111-110
k=26 1792321 111553171925*
We didn't simplify y and y to w and i  (to allow y to be any primitive 12-th root of unity).
 
k = 15     f(k) = 8
n 12478111314
c1 (n) 11111111
c2 (n) 1i-1-i-i-1i1
c4 (n) 1-11-1-11-11
c7 (n) 1-i-1-ii1i-1
c8 (n) 1-i-1ii-1-i1
c11 (n) 1-111-1-11-1
c13 (n) 1i-1i-i1-i-1
c14 (n) 111-11-1-1-1
k=16 13951171315
k=20 179173111319
k=30 1171973111329
 

k = 24     f(k) = 8
1571113171923
 1 1111111
 1 111-1-1-1-1
 1 1-1-1-1-111
 1 1-1-111-1-1
 1 -1-11-111-1
 1 -1-111-1-11
 1 -11-11-11-1
 1 -11-1-11-11
01234567
  Multiplicative residues modulo 24 are like additive 3-bit vectors.

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  01234567
( a | 2 ) 010-10-101

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 (Z/kZ)*,  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 ) 1zz2z3z4 z5z6z7z8 z9z10z11z12 z13z14z150
k=17 139101351511 161487412260
k=34 139271351511 333125721291923*
 
f(k) = 18       z18  =  1
c ( n ) 1zz2z3z4 z5z6z7z8 z9z10z11z12 z13z14z15 z16z17
k=19 139851572 61816101114412 1713
k=27 1525174201914 1626222102378 1311
k=38 13927515721 2537352911332331 1713
k=54 15251731471941 435349293723735 1311

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 ) 1yy2 y3y4y5 xxyxy2 xy3xy4xy5 0
k=21 154201617 1321081911*
k=42 1525413717 132331291911*

The  Dirichlet characters modulo k  are just the homomorphisms from the multiplicative group  (Z/kZ)*  into the group of the  f(k)-th  roots of unity.


 Leonhard Euler 
 (1707-1783) (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.)

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)   =   Sn  f (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   1230
c1 (n) 1010
c3 (n) 10-10

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:

b(s)   =   L(c3,s)
=   1 - 3-s + 5-s - 7-s + 9-s - 11-s + 13-s - 15-s + 17-s - 19-s + ...
=   1
Vinculum
(1+3-s) (1-5-s) (1+7-s) (1+11-s) (1-13-s) (1-17-s) (1+19-s) ...

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) = ½).

The key to the Riemann hypothesis (12:37)  Jon Keating (Numberphile, 2016-05-10).
The Zeros of the Dirichlet Beta Function [...]   by  Tony Lander  (2018-04-24).
The L-functions and modular forms database  (LMFDB).


(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:

2-s + 3-s + 4-s/2 + 5-s + 7-s + 8-s/3 + 9-s/2 + 11-s + 13-s + 16-s/4 + 17-s + 19-s + 23-s ...   =   Log z(s)
3-s + 5-s + 7-s + 9-s/2 + 11-s + 13-s + 17-s + 19-s + 23-s + 25-s/2 ...   =   Log z(s) + Log (1-2-s )
1 - 3-s + 5-s - 7-s + 9-s/2 - 11-s + 13-s + 17-s - 19-s - 23-s ...   =   Log b(s)

 Come back later, we're
 still working on this one...

Logarithm of Dirichlet L-Functions  (ProofWiki)
Grant Sanderson's  Unexpected logarithms  (Big Internet Math-Off #5, 2019-07-05).
Natural Log (1:14:53)  by  Grant Sanderson's  (3Blue1Brown, 2020-05-08).
The Prime Race (20:28)  by  Grant Sanderson's  (Numberphile, 2023-02-23).


(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:

z(s,n/k)   =   Sc  c(n) L(s,c)

Dirichlet's theorem           Wikipedia :     Euler product   |   L-functions   |   Hurwitz zeta function


(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 additivetotally 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 Î N ,   " p Î N ,   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.

Some totally additive arithmetic functions:

  • Zero function:   f (pn )  =  0   (A000004).
  • Number of prime factors repeated:   W (pn )  =  n   (A001222).
  • Sum of prime factors repeated:   sopfr (pn )  =  n p   (PotencyA001414).
  • Euler's sub-gradus:  g0 (pn ) = n (p-1)   (A275314 - 1).
  • Logarithm of a positive totally multiplicative function.
  • Generic totally additive function:  g (pn ) = n g (p)    (arbitrary for primes).

Wikipedia :     Additive functions

border
border
visits since Dec. 6, 2000
 (c) Copyright 2000-2023, Gerard P. Michon, Ph.D.