A Tantonalizing Problem

In times like these one craves distraction, or maybe anaesthesia. On the whole, mathematics is better for you than ethanol, and you can even do it while driving. So in spare moments I’ve been noodling away at the following problem, tweeted a week ago by James Tanton:

Tanton tweet

The answer to Tanton’s question is surely No: The series will never again land on an integer. I leaped to that conclusion immediately after reading the definition of the series and glancing at the first few terms. But what makes me so sure? Can I prove it?

I wrote a quick program to generate more terms:

1
2
5/2
17/6
37/12
197/60
69/20
503/140
1041/280
9649/2520
9901/2520
111431/27720
113741/27720
1506353/360360
1532093/360360
1556117/360360
3157279/720720
54394463/12252240
18358381/4084080
352893319/77597520

Overall, the trend visible in these results seemed to confirm my initial intuition. When the fractions are expressed in lowest terms, the denominator generally grows larger with each successive term. Looking at the terms more closely, it turns out that the denominators tend to be products of many small primes, whereas the numerators are either primes or products of a few comparatively large primes. For example:

\[\frac{9649}{2520} = \frac{9649}{2^3 \cdot 3^2 \cdot 5 \cdot 7} \qquad \textrm{and} \qquad \frac{18358381}{4084080} = \frac{59 \cdot 379 \cdot 821}{2^4 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17}.\]

To produce an integer, we need to cancel all the primes in the factorization of the denominator by matching primes in the numerator; given the pattern of these numbers, that looks like an unlikely coincidence.

But there is reason for caution. Note the seventh term in the sequence, where the denominator has decreased from \(60\) to \(20\). To understand how that happens, we can run through the calculation of the term, which starts by summing the six previous terms.

\[\frac{60}{60} + \frac{120}{60} + \frac{150}{60} + \frac{170}{60} + \frac{185}{60} + \frac{197}{60} = \frac{882}{60}.\]

Then we calculate the mean, and add 1 to get the seventh term:

\[\require{cancel}\frac{882}{60} \cdot \frac{1}{6} = \frac{882}{360} = \frac{\cancel{2} \cdot \cancel{3} \cdot \cancel{3} \cdot 7 \cdot 7}{\cancel{2} \cdot 2 \cdot 2 \cdot \cancel{3} \cdot \cancel{3} \cdot 5} = \frac{49}{20} + 1 = \frac{69}{20}\]

Cancelations reduce the numerator and denominator of the mean by a factor of 18. It seems possible that somewhere farther out in the sequence there might be a term where all the factors in the denominator cancel, leaving an integer.

Another point to keep in mind: For large \(n\), the value of the Tanton function grows very slowly. Thus if integer values are not absent but merely rare, we might have to compute a huge number of terms to get to the next one. Reaching the neighborhood of 100 would take more than \(10^{40}\) terms.

value of tanton(n) for n from 1 to 300

So what do you think? Can we prove that no further integers appear in Tanton’s sequence? Or, on the contrary, might my instant conviction that no such integers exist turn out to be an alternative fact?


I’ve had my fun with this problem. I know the answer now, but I’m not going to reveal it yet. Others also deserve a chance to be distracted, or anaesthetized. I’ll be back in a few days to follow up—unless commenters explain what’s going on so thoroughly there’s nothing left for me to say.


Update 2017-01-30: Okay, pencils down. Not that anyone needs more time. As usual, my readers are way ahead of me. (See comments below, if you haven’t read them already.)

My own slow and roundabout voyage of discovery went like this. I had written a little piece of code for printing out n terms of the series, directly implementing the definition given in James Tanton’s tweet:

from fractions import Fraction as F
from statistics import mean

def tanton (n):
    seq = [F(1)]
    for i in range(n):
        print(seq[i])
        seq.append(mean(seq) + 1)

But this is criminally inefficient. On every pass through the loop we calculate the mean of the entire sequence, then throw that work away and do it all again the next time. Once you have the mean of \(n-1\) terms, isn’t there some way of updating it to incorporate the nth term? Well, yes, of course there is. You just have to appropriately weight the new term, dividing by n, before adding it to the mean. Here’s the improved code:

from fractions import Fraction as F

def faster_tanton (n):
    m = F(1)
    for i in range(1, n):
        print(m)
        m += F(1, i)

Tracing the execution of this function, we start out with 1, then add 1, then add 1/2, then 1/3, then 1/4, and so on. This is 1 plus the harmonic series. That series is defined as:

\[H_{n} = \sum_{i=1}^{n} \frac{1}{i} = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}\]

The first 10 partial sums are:

1
3/2
11/6
25/12
137/60
49/20
363/140
761/280
7129/2520
7381/2520

One fact about the harmonic series is very widely known: It diverges. Although \(H_{n}\) grows very slowly, that growth continues without bound as \(n\) goes to infinity. Another fact, not quite as well known but of prime importance here, is that no term of the series after the first is an integer. The simplest proof shows that when you factor the numerator and the denominator, the denominator always has more \(2\)s than the numerator; thus when the fraction is expressed in lowest terms, the numerator is odd and the denominator even. This proof can be found in various places on the internet, such as StackExchange. There’s also a good explanation in Julian Havil’s book Gamma: Exploring Euler’s Constant.

Neither of those sources mentions anything about the origin or author of the proof. When I scouted around for more information, I found more than a dozen sources that attribute the proof to “Taeisinger 1915,” but with no reference to an original publication. For example, a recent paper by Carlo Sanna (Journal of Number Theory, Vol. 166, September 2016, pp. 41–46) mentions Taeisinger and cites Eric Weisstein’s Concise Encyclopedia of Mathematics; consulting the online version of that work, Taeisinger is indeed credited with the theorem, but the only reference is to another secondary source, Paul Hoffman’s biography of Erdős, The Man Who Loved Only Numbers; there, on page 157, Hoffman writes, “In 1915, a man named Taeisinger proved. . .” and gives no reference or further identification. So who was this mysterious and oddly named Taeisinger? I have never heard of him, and neither has MathSciNet or the Zentralblatt or the MacTutor math biography pages. In Number Theory: A Historical Approach John J. Watkins gives a slender further clue: The first initial “L.”

After some further rummaging through bookshelves and online material, I finally stumbled on a reference to a 1915 publication I could actually track down. In the Comptes Rendus Mathematique (Vol. 349, February 2011, pp. 115–117) Rachid Aït Amranea and Hacène Belbachir include this item in their list of references:

L. Taeisinger, Bemerkung über die harmonische Reihe, Monatsch. Math. Phys. 26 (1915) 132–134.

When I got ahold of that paper, here’s what I found:

Opening lines of the Theisinger 1915 paper

Not Taeisinger but Theisinger!

I still don’t know much of anything about Theisinger. His first name was Leopold; he came from Stockerau, a small town in Austria that doesn’t seem to have a university; he wrote on geometry as well as number theory.

What I do know is that a lot of authors have been copying each other’s references, going back more than 20 years, without ever bothering to look at the original publication.

This entry was posted in mathematics, problems and puzzles.

8 Responses to A Tantonalizing Problem

  1. unekdoud says:

    It might be a little too early to post spoilers, but that graph and those denominators are really screaming something at me, something that seems easy enough to verify. But what’s the best way to prove it? And how does it help?

  2. Thales says:

    x[n] = PolyGamma[0,n] + EulerGamma + 1

  3. rms says:

    we need to cancel all the primes in the factorization of the denominator

    if one could just cancel those damned twos to begin with..
    but they keep appearing

  4. Gerry Myerson says:

    Use induction to show the n-th term is one plus the (n-1)-st harmonic number; then it’s a standard exercise to show that the harmonic numbers (after the first) are not integers.

  5. rms says:

    What I do know is that a lot of authors have been copying each other’s references, going back more than 20 years, without ever bothering to look at the original publication.

    ..and that’s again another interesting observation that can also be found in some more or less obscure literature.

  6. Gerry Myerson says:

    Theisinger must be in vogue. Silberger and Silberger, Sums of finitely many distinct reciprocals, just showed up on Arxiv, citing his paper (with the correct spelling of his name).

  7. This kind of sequence is easier to calculate efficiently in Haskell, where the laziness and mathematical notation really shine, both to the eye and with respect to efficiency.
    tanton :: [Rational]
    tanton = [1] ++ map (1+) (zipWith (/) (scanl1 (+) tanton) [1..])

Leave a Reply

Your email address will not be published. Required fields are marked *

*

In addition to the basic HTML formatting options offered by the buttons above, you can also enter LaTeX math commands. Enclose LaTeX content in \( ... \) for inline mode or \[ ... \] for display mode.