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.

Weekend Cat Blogging and Photo Hunt: Heart

Our combined Weekend Cat Blogging and Saturday Photo Hunt features the theme Heart. We have a few images that blend the theme with our interests in music, mathematics and of course, cats.

Here Luna poses with a heart-shaped kalimba (thumb piano).

Luna peers at the iPad, which displays a plot of a cardioid. We used a mathematical function that produces the heart-shaped figure when plotted with polar coordinates. The formula for the cardioid is: r = 1 – sin(θ), where r is the radius from the center of the plot and θ is the angle sweeping around the center. The best way to visualize polar coordinates is using one of those old circular radar screens where the plotter sweeps in a circular motion.

The photo also features one of Luna’s favorite toys, a heart-shaped plush toy with the word “kitty” inscribed on it. We have had it for years now (indeed, it was featured in a WCB/Photo Hunt back in 2008).


Weekend Cat Blogging #349 (Valentines Day edition) is hosted by Meowza.

The Saturday Photohunt theme is Heart.

The Carnival of the Cats will be up this Sunday at Meowzings of an Opinionated Pussycat.

And the Friday Ark is at the modulator.

11:11 on 11/11/11

At 11:11 on this day 11/11/11, I snapped screenshots of both the iPad and iPhone featuring Luna.

Of course, the symmetry and homogeneity of the date and time is quite attractive, and unique (at least within a given century). The number 111111 is also interesting when you decompose it into primes:

111111 = 11 * 13 * 3 * 37 * 7

I find the prime factorization quite poetic.

We can also factor the date and time together (11:11:11 on 11/11/11):

111111111111 = 11 * 13 * 3 * 37 * 7 * 101 * 9901

Note quite as poetic as the previous example, but still interesting. In particular, 9901 is interesting as the greatest prime factor for any repeating series of 12 numbers. Other related properties can be seen at the site Prime Curios.

Weekend Cat Blogging and Photo Hunt: Digital

The theme of this week’s Photo Hunt is digital. Rather than simply use a digital photo – which could be any photo ever taken of Luna – I chose a couple of images that demonstrate the unique opportunities of the medium. A digital photo is really just a stream of numbers, not unlike digital audio, and can be processed in countless ways using digital signal processing or applying other mathematical functions.

For a piece I originally did in 2007, I took one of Luna’s adoption photos from Santa Cruz County Animal Services and applied an algorithm that overlaid these colored bands, as shown above.  The color bands were generated using a set of hastily chosen trigonometric and hyperbolic functions applied to the timeline of the animation sequence.  These photos are stills from the full animation.

I did these using image and video extensions to Open Sound World – one nice feature of that work was that I could use the same functions for both audio and video, and “see” what a particular audio-processing algorithm looked like when applied to an image.   And I would probably use the Processing environment for future visual work, perhaps in conjunction with OSW.


Weekend Cat Blogging #309 and Carnival of the Cats are both being hosted by Billy SweetFeets this weekend. Perhaps Luna’s animation could be part of one of the dance videos they often feature.

Photo Hunt #264 is hosted by tnchick. This week’s theme is digital.

And the Friday Ark is at the modulator.

A special note this week. Our friend Judi at Judi’s Mind over Matter (home of Jules and Vincent) has information on how to help animals affected the storms and tornadoes in the southeast US. They live in Alabama, not far from the place that was hit hardest by the tornadoes. We’re glad they’re safe, and able to provide this information for those who would like to help.

108

Sometimes when things get a bit overwhelming it’s good to turn to numbers and highways. As mentioned in earlier posts, I maintain a rather cursory yoga routine for both health/exercise and grounding. The number 108 comes up fairly often in cycles of repetition and I have been curious about its significance. Long before it was featured on Lost, 108 prominently figured in Hinduism as the number of beads on a mala and in other contexts, and through Hinduism finds its way into Buddhism. 108 has several interesting purely mathematical properties. My favorite is its being the hyperfactorial of 3. The hyperfactorial is the product of consecutive integers, each raised to itself as an exponent:

11 x 22 x 33 = 108

Among the more random properties is being the sum of 9 consecutive integers:

8 + 9 + 10 + 11 + 12 + 13 + 14 + 15 + 16 = 108

9 is of course a divisor of 108, as in 9 x 12 = 108. And both 9 and 12 appear in the above series.

More significantly, 108 degrees is the angle of a vertex a regular pentagon, and 108 degrees can also be used to derive the golden ratio.

The relationship to the golden ratio would seem to be an interesting one, until one remembers that the representation of angles as degrees is itself arbitrarily based on the number 360. The 3π/5 radian representation is more significant in this regard.

And what about fun with highways numbered 108? Here in California, state highway 108 runs from the Central Valley town of Modesto northward and eastward across the Sierra via the Sonora Pass (north of Yosemite) to meet US 395 on the eastern side of the Sierra.

[Photo by jodastephen on flickr.  (License CC BY-ND 2.0)]

While I have not driven CA 108, I am sure I have crossed its path on CA 120 on the way to Yosemite. From the picture above, it looks like it would be a nice drive, particularly in the summer. The eastern side of the Sierra has that stark, desolate quality, in comparison to the heavily wooded slopes on the western side. They are both quite beautiful, but the eastern side tends to speak to me more.

In New York, Route 108 is a short highway on Long Island. In fact, it is very short, a little under two miles total.  It’s southern terminus is the picture below.

[Photo by dougtone on flickr.  (License CC BY-SA 2.0)]

Route 108 southbound crosses into Nassau County, but soon curves away back into Suffolk. Soon after, the two-lane road continues into Trail View State Park, where the route becomes desolate, passing two local ponds.

It is interesting how the word “desolate” can come up for both highways, with very different connotations.

Pi Day, 2011 (with Music)

Every year, we at CatSynth join numerous other mathematics enthusiasts, geeks and otherwise eccentric characters in celebrating Pi Day on March 14.

March 14 is notated in the U.S. and some other countries as “3-14”, which evokes the opening digits of π (pi). Although the date representation is a very arbitrary connection to the number, we also recognize that the representation of π in decimal digits is arbitrary, an accident of human beings having ten fingers. So this year we are exploring the representations in binary and other related bases.

To represent an integer in binary, one of course presents it as a sum of powers of two, e.g., 11 = 8 + 2 + 1 or 1011 in binary. But one can also represent fractional numbers in binary. Digits to the right of the decimal point represents powers of one-half. So the binary number 0.11 is 1/2 + 1/4, or 3/4. Fractions like 1/3 can be represented with repeating digits as 0.010101…, much like in base ten. And this concept can be extended to irrational numbers like π.

The author of this website has calculated 32768 digits of pi in binary. We reprint the first 258 below:

11.
00100100 00111111 01101010 10001000 10000101 10100011 00001000 11010011 
00010011 00011001 10001010 00101110 00000011 01110000 01110011 01000100 
10100100 00001001 00111000 00100010 00101001 10011111 00110001 11010000  
00001000 00101110 11111010 10011000 11101100 01001110 01101100 10001001 

The initial “11” represents the 3 in π, and the remaining digits begin the non-integral portion. Like in the decimal representation, the binary representation continues forever with no particular pattern. While not as iconic or memorable as the decimal representation 3.14159…, there is something about the binary representation that makes it seem more universal, i.e., based on fundamental mathematical truths rather than a quirk of human anatomy. For me, the binary representation also lends itself to musical ideas. And for the occasion, I have created a couple of short synthesized pieces representing the 32768 binary digits of pi. In the first example, each binary digit represents a sample. The “1” represents full amplitude and the zero represents no amplitude (silence). The result, which at 44.1kHz sample rate is less than one second long, can be heard below.

The random configuration of digits sounds like noise, and more specifically like white noise, suggesting something approaching uniform randomness at least to human hearing. I also made an example slowed down to a level whether the individual samples became musical events. I find this one quite interesting.

With some additional refinement (and may some more digits to extend the length), it could certainly stand alone as a composition.

One interesting counterpoint to the notion that digits of pi form white noise is a conjecture related to its representation in hexadecimal (base 16), which as a power of two is “closer” to binary and seemingly less arbitrary than decimal. From Wolfram MathWorld, we find the following “remarkable recursive formula conjectured to give the nth hexadecimal digit of π – 3 is given by where is the floor function:

The formula is attributed to (Borwein and Bailey 2003, Ch. 4; Bailey et al. 2007, pp. 22-23). If true, it would add some sense of order to the digits, and thus additional musical possibilities.

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.

Happy 102nd Birthday to Elliott Carter

This evening we at CatSynth wish a slightly-belated 102nd birthday to Elliott Carter. His birthday was this past Saturday, December 11. An inspiring figure, not only has he lived to an impressive age, but continues to be a prolific composer. Indeed, as reported on Sequenza21, he attended a concert in Toronto entirely of works he has composed since turning 100. They also mention that earlier last week he attended a concert in honor of that young upstart Pierre Boulez, who turned 85 this year.

It was also interesting to see him placed in the context of the last century, from a personal connection with Charles Ives, one of the first “truly modern” American composers stretching to the current era. His work, like Ives and those that followed in that tradition, is very often very complex and often very precise in detail (and challenging to perform). Of interest to those like me who are also into mathematics alongside music, many of his formal methods with pitches and harmonies used more complex combinatorial structures than earlier serial composers, including collections of all possible pitches of a particular length – an approach that would later be categories as “musical set theory.” Many of these ideas have been collected in the Harmony Book which was published in 2002 (when Carter would have been 93).

Autonomous Individuals Network, 23 SECONDS ov TIME,

I am happy to announce the release of 23 SECONDS OV TIME, a project of the Autonomous Individuals Network in which I am participating.

The collection contains 97 individual tracks, each exactly 23 seconds in length, with the total assemblage running for 37 minutes and 14 seconds. You can find my 23-second contribution, entitled “Four ideas in 23 seconds”, at track 80!

Volume One will be released in a limited edition of 123 hand numbered CD Copies.
This CD is planned for release on November 23,2010. Until November 23, you can download or stream the entire collection for free as a single MP3. In either format, I encourage everyone to check it out!

It is interesting to hear the pieces as a single unit, with such short durations they become phrases in a larger whole piece, sometimes with very sharp transitions.

You can also find out more about the Autonomous Individuals Network (and the significance of 23) at the official website.