number theory

The Fundamental Theorem of Arithmetic

It is not uncommon to hear operations on numbers, even the computations carried out in modern computers, as “mere arithmetic.” But arithmetic is hardly simple or obvious when one gets down to the fundamentals and realizes the structure that must be present in our number system in order for it to work they way we intuitively think it should work. Thus, today we consider the Fundamental Theorem of Arithmetic.

Every positive integer (except the number 1) can be represented in exactly one way apart from rearrangement as a product of one or more primes.

Thus every integer has a canonical representation as a product of powers of primes:

where p1 < p2 < … < pk are primes and the αi are positive integers; 1 is represented by the empty product. As example 12 = 22 × 3, and 666 = 2 × 32 × 37. Fairly familiar stuff for anyone who paid attention during grade school and secondary school math classes. But the theorem itself is not self-evident, it is something that had to be proven true in order for our everyday arithmetic to hold. A good article on why the theorem is not obvious can be found here. It also has implications beyond the natural numbers. If we extend the canonical representation to allow both positive and negative values for ai, we get the set of positive rational numbers (fractions), for which the theorem still holds. It can also be generalized to more exotic constructions, such as Gaussian Integers. Gaussian integers, often denoted ℤ[i] are complex numbers a + bi where i is the square root of -1, and a and b are integers. It can be shown that the fundamental theorem of arithmetic holds for Gaussian integers, and that there is a definite set of “Gaussian primes” just as there are prime numbers. But while plotting the prime numbers and looking for visual patterns is an exercise in frustration, the rotational nature of complex numbers (which we have discussed in a previous article) causes the Gaussian primes to fall into a visually interesting radial pattern:

With all the important and sometimes confounding properties of primes, having ways to visualize them is always intriguing.

Any mathematical construct (specifically, a “domain”) that obeys the fundamental theorem of arithmetic is known as a Euclidean Domain. (Note that this has very little to do with Euclidean spaces or the other uses of the term in geometry.) We can observe many more Euclidean domains, such as generalizing Guassian integers to other roots of 1. If we use the cube roots of 1, for example (yes, 1 has three cube roots), we get the set of Eisenstein Integers: numbers of the form a + bω, where a and b are integers and:

Like Gaussian primes, Eisenstein primes have a distinctive radial pattern when viewed on the complex plane. Whereas Guassian primes divide into quadrants, Eisenstein primes form a hexagonal pattern.

Note that while the generalization works for square roots of -1, cube roots of 1, etc., it doesn’t necessarily work for all roots of 1. Some of those sets will not form Euclidean domains.

We can also look beyond numbers to other mathematical entities that form Euclidean domains. One such example can be found in knot theory, which we discussed in an article a few years ago. Knots can be expressed as unique combinations of prime knots:

From here we can consider the implications for music of the Euclidean domains, the accompanying Euclidean algorithm for computing greatest common divisors in any of these domains. But that will be left as an exercise for another day.

Fun with the Arithmetic Derivative and Twin Primes

Anyone who has stayed in math classes long enough to reach calculus quickly comes to believe that calculus is more advanced and complex than arithmetic. And while that may be true for the most intuitive aspects of arithmetic that we learn in grade school, the seemingly innocent discipline quickly becomes more mysterious as one advances into it.

Consider the most basic operation in calculus, the derivative. The derivative of the a function is said to describe the instantaneous rate of change of function (how fast it is going up or down in any given direction), or alternatively the slope of a function at any given point. However, there is a related operation on integers is called the arithmetic derivative, defined as follows:

  1. p’ = 1 for any prime number p
  2. (ab)’ = a’b + ab’ for any a,b ∈ &#8469
  3. 1′ = 0
  4. 0′ = 0

While there is an intuitive and even “visual” nature to the calculus derivative, the arithmetic derivative seems more abstract and opaque. Additionally, the former is about continuous functions, while the latter is about discrete entities such as integers or rational numbers. The main thing the two concepts have in common is that they obey the Liebniz Rule governing the products of derivatives, as described on line 2 above.

So can the arithmetic derivative tell us anything useful about integers? It is intimately tied to prime numbers and prime factorization, so it is in that sense an additional tool for examining fundamental properties of numbers as they relate to primes and patterns of primes. The article Deriving the Structure of Numbers quotes Linda Westrick, who has studied the arithmetic derivative and says that it “provides a different context from which to view many topics of number theory, especially those concerning prime numbers. The complex patterns which arise from its simple definition make it interesting and worthy of study.” To see such patterns, one can apply the derivative repeatedly, n’, (n’)’, etc., just as one would in calculus, to chart the variations even among the first few natural numbers.

n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n‘
0
1
1
4
1
5
1
12
6
7
1
16
1
9
8
32
1
21
n"
0
0
0
4
0
1
0
16
5
1
0
32
0
6
12
80
0
10
n"’
0
0
0
4
0
0
0
32
1
0
0
80
0
5
16
176
0
7

Indeed the interesting patterns include the fact that some numbers quickly go to zero as one repeatedly applies the arithmetic derivative, as on the case of 6′ = 5, 6” = 1, 6”’ = 0. Other numbers, seem to increase without bound. In the above chart, for example, powers of 2 appear to grow quite quickly. Yet others bounce around unpredictably somewhere in between. In many ways, this reminds me a bit of the Collatz Conjecture which have discussed on CatSynth in the past.

Perhaps the most intriguing property of the arithmetic derivative is its relation to twin primes, pairs of prime numbers whose difference is 2, like 11 and 13 or 29 and 31. It is conjectured that there are infinitely many such pairs of twin primes, but no one has ever proven this. However, it turns out that twin primes are related to the second derivative of a number n”. So if there are infinitely many numbers n for which n” = 1, then there are infinitely many twin primes. As described in this paper by Victor Ufnarovsk, one can derive this from the following theorem:

Let p be a prime and a = p+2. Then 2p is a solution for the equation n’ = a

The proof is relatively straightforward:
(2p)’ = 2’p + 2p’ = p + 2

So if 2p’ = p + 2 and p + 2 is also prime, as would be the case for twin primes, then 2p” = (p + 2)’ = 1.

Unfortunately, this does not answer the question of whether there are infinitely many such pairs. So the famous problem remains open.

Ackermann’s Function and “Really Big Numbers”

Today we return to to the topic of mathematics with a look at Ackermann’s Function. Anyone who has studied computer science has probably encountered this function (though I’m sure many have gone on to forget it). It is most commonly defined as follows:

This is actually a variant of Wilhelm Ackermann’s original function, often called the Ackermann–Péter function. It is quite a simple function to define and to trace, and it is very easy to implement in just about any programming language, including Python:

def ackermann(m, n):
  if m == 0:
    return n + 1
  elif n == 0:
    return ackermann(m - 1, 1)
  else:
    return ackermann(m - 1, ackermann(m, n - 1))

However, its complexity (in terms of run-time and memory) grows quite quickly. As such, it is often used as an exercise in teaching students more complex forms of recursion, and also as a test case in compiler development for optimizing recursion. It also has some interesting mathematical properties for particular values of m:

The numbers in the case of A(4,n) are quite large. Indeed, one could describe Ackermann’s function as “computing really really large numbers really really slowly.” Although the numbers grow quickly, the function is really just doing subtraction and recursion. We can take advantage of the properties described above, however, to make some shortcuts that yield a much more efficient function.

def ackermann(m, n):
  while m >= 4:
    if n == 0:
      n = 1
    else:
      n = ackermann(m, n - 1)
    m -= 1
  if m == 3:
    return 2 ** ( n + 3) - 3
  elif m == 2:
    return 2 * n + 3
  elif m == 1:
    return n + 2
  else: # m == 0
    return n + 1

With this version computing A(m,n) for m≤3 becomes trivial. And this makes computations for m≥4 possible. Or at least A(4,2), which we can actually run in python to reveal the 19,000 digit answer.

You can see the full value on this page. Computing A(4,3) is infeasible. Even with the optimizations, most computers will run out of memory trying to compute this value. But one can still reason about these rather large numbers. Let us move from the more common function we have been using to Ackermann’s original version:

This version has three arguments instead of two, and on the surface it may seem a bit more complicated. However, different values of the third argument p yield very familiar operations.


Again, this function is a rather inefficient way to compute addition, multiplication and exponentiation, but it is an interesting way to reason about them and extrapolate to other more exotic operations. For example, if we take p to be 3, we get the following operation.

Just as m x n is adding m to itself n times, and exponentiation mn is multiplying m by itself n times, this new operation (sometimes called tetration) is the next level: exponentiating m by itself n times.

Such an operation grows so fast as to be uncomparable to exponential growth. It grows even too fast to compare to the gamma function which have explored on CatSynth in the past. This series of ever higher-order operations is often noted with an arrow, called Knuth’s up-arrow notation after legendary computer scientist Donald Knuth.

Using this notation, we can define as sequence of numbers, called Akermann Numbers, where each is an ever higher-order operation of the element applied to itself.

  • 1↑1 = 11 = 1,
  • 2↑↑2 = 2↑2 = 22 = 4,
  • 3↑↑↑3 = 3↑↑3↑↑3 = 3↑↑(3↑3↑3) = 

Even just the 4th number is this sequence is so large that we can’t even easily notate it with exponents. So forget about the 5th number in sequence. But a question that interests me is what about interpolating with real numbers. What is the 1 1/2th Ackermann number? That question, if it even has an answer, will have to wait for another time.

Properties of 2011

The number “2011” abounds with fun numerical and “visual-numerical” properties. Early into the new year, we experienced the time “1:11:11 on 1/1/11”. And this week, we had the even more auspicious “1:11:11 on 1/11/11”, at least with the date-writing convention we use in the United States. This week all the dates have been palindromes using the two-digit year convention, e.g., today is “1 14 11”, and if one uses the full four-digit year, this past Monday was “1 10 2011”, also a palindrome.

While text-based properties are fun, they are somewhat arbitrary and less interesting than mathematical properties of numbers. First, 2011 is a prime number, the first prime year since 2003. And from @mathematicsprof on twitter, we have this interesting coincidence:

“2011 is also the sum of 11 CONSECUTIVE prime numbers:
2011=157+163+167+173+179+181+191+193+197+199+211”.

In other words, this is not just a series of prime numbers, but all the prime numbers between 157 and 211. I like that the last prime in the series happens to be 211!

The Republic of Math blog follows the consecutive-prime inquiry further, with the observation that 2011 can also be written as the sum of three consecutive primes “661 673 and 677”.

From The Power of Proofs, we have the property that 2011 is the sum of three squares:

2011 = 392 + 172 + 72

However, any number not congruent to 7 modulo 8 will have such a property. I.e., if you divide 2011 by 8, you have 3 left over. So really 7 out of 8 integers can be expressed this way. Finding the series of squares can take some time, though.

Please feel free to share any other mathematical or fun coincidental properties in the comments below.

Calculus for Cats and Prime Number Theorem

<I was looking for a quick way to combine cats and mathematics this morning, and came across the book Calculus for Cats.

This is a book for people about to take calculus, and for survivors of calculus who still wonder what it was all about. It gently explains the basic concepts and vocabulary without making the reader ever do a single problem.

Basically, the book draws (quite literally) an analogy between the fluid motion of cats at play (or in pursuit of “prey”) and the concepts and techniques of calculus, which focuses on continuous functions.

We at CatSynth remember calculus fondly as a mathematical pursuit. But number theory is more my thing. Calculus primary concerns itself with continuous functions of real and complex numbers, while number theory deals with discrete entities, like integers. But in mathematics, all things are interconnected. For example, we demonstrated the connection between the gamma function, pi and factorials, combining continuous and discrete concepts.

Consider the function π(x), the prime-counting function. It's a bit unfortunate they chose the symbol π, but it is what it is. Basically, this function counts the number of primes less than or equal to a particular number. For example π(20) would be all the prime numbers less than 20: 2, 3, 5, 7, 11, 13, 17 and 19. So π(20) = 8.

So to calculate π(1000) would one have to literally count all the prime numbers less than 1000, including figuring out which numbers are prime? And what about π(1000000)? Unfortunately, the answer is yes. But there are good ways to approximate the number of primes, using the results of the Prime Number Theorem. Those interested in the formal theorem are encouraged to follow the link, but we will skip ahead to one of the interesting results. One of basic functions to come out of calculus is the natural logarithm ln(x), whose base is the famous constant e. If you don't know about it, go look it up. Otherwise, the rest of this article will not make much sense. One can use ln(x) to build more complicated functions in calculus, one of which is the offset logarithmic integral, or Li(x):

This is one of those functions, like the gamma function, that cannot be expressed without the use of calculus. Turns out, however, that it is a good approximately for π(x), which is very much a discrete concept and quite distant from the continuous motions involved in calculus. The prime number theorem provides the connection.

This article is included in Carnival of Mathematics #31 at recursivity.