34
$\begingroup$

A high-school student named Erna Fekete made a conjecture to me via email three years ago, which I could not answer. I've since lost touch with her. I repeat her interesting conjecture here, in case anyone can provide updated information on it.

Here is how she phrased it. Let $b(0) = 1$ and $b(n)= \tan( b(n-1) )$. In other words, $b(n)$ is the repeated application of $\tan(\;)$ to 1: $$\tan(1) = 1.56, \; \tan(\tan(1)) = 74.7, \; \tan^3(1) = -0.9, \; \ldots $$

Let $a(n) = \lfloor b(n) \rfloor$. Her conjecture is:

Every integer eventually appears in the $a(n)$ sequence.

This sequence is not unknown; it is A000319 in Sloane's integer sequences. Essentially hers is a question about the orbit of 1 under repeated $\tan(\;)$-applications. Her and my investigations at the time led us to believe it was an open problem.

  • 11
    How about a more daring conjecture, that the b(n) themselves are dense in R? At least it does away with the nasty floor function. Is it obviously false?2010-10-14
  • 0
    @Alon: Good point! Not only is it not obviously false---I think the orbit _is_ dense!2010-10-14
  • 1
    Is it obvious that the sequence is everywhere defined? (I think it must be true but I don't see how to prove it.)2010-10-14
  • 0
    @Qiaochu: Not obvious to me either!2010-10-15
  • 2
    @Qiaochu, @Joseph O'Rourke: Suppose we consider the set $X$ of all $x \in \mathbb{R}$ such that some $\tan^{n}(x)$ is not defined. Because $X$ is the union of repeated (set-valued) applications of $\tan^{-1}$ on $\{(2k+1)\pi/2\}$, it seems to me that $X$ is countable but dense in $\mathbb{R}$. Is it plausible to conjecture that $X$ contains no rational number?2010-10-20
  • 1
    Generalizing to an arbitrary starting point x, rather than just starting at 1, the (possibly terminating) sequence [a(0),a(1),a(2),...] looks a lot like a kind of continued fraction representation. In fact, it gives a one-to-one map between real x and possibly terminating sequences of integers. So there are uncountably many starting points where every integer appears, and uncountably many where only a finite set of integers occur. There's uncountably many x for which only 0 and 1 appear. However, I think, for almost every x, the sequence a(n) will tend to some fixed distribution.2010-10-21
  • 1
    So, this question sounds like a much more difficult version of problems involving regular continued fractions. It is not even known if the continued fraction of $\pi$ contains every positive integer (according to Sloane: http://akpublic.research.att.com/~njas/sequences/A032523). It seems likely that this question is much harder than that.2010-10-21

2 Answers 2

16

I had made the same conjecture as Fekete, apparently around the same time -- mid-2007. In 2008 I verified that the first twenty million terms do not include 319. (I actually pushed the verification further, but I can't find the more recent records at the moment.)

Because $\tan(x) - x = x^3/3 + O(x^5)$, the function spends a lot of its time in a small neighborhood around $0$. It escapes when it nears $\pi/2$ and quickly returns for many iterations.

A mostly-unexplained phenomenon presumably related to the above: there are long spans of small numbers followed by short, 'productive' spans with large numbers. $\tan^k(1)$ is "below 20 or so" (according to a 2008 email I sent) for $360110\le k\le1392490$ but in the next 2000 numbers there are five which are above 20.

More theory is needed!

  • 1
    @Charles: Indeed, more theory is needed! Very interesting that you have explored this so substantively... Thanks for sharing (as the kids say)!2010-10-21
  • 0
    @Charles: That's very interesting. But I have to ask-- how can you assure accuracy of your values under so many iterations? As you note, iterations of values close to pi/2 are arbitrarily sensitive to small changes in the initial value.2010-10-21
  • 1
    I repeated the calculations to about 10 million (sorry, don't have the exact numbers here; hopefully I saved them somewhere) on a different computer using a different computer program and they matched. On the larger calculation I used interval arithmetic which gave further confidence.2010-10-21
  • 0
    @Charles: Interval arithmetic handles round-off error of course, but I have a hard time seeing how it would work for so many iterations. (When I did iterations of the logistic map, round-offs caused problems very quickly.) Perhaps you or someone else can give details to resolve this for me, but here's my doubt: tan(x) everywhere has slope (tan(x)^2+1), which stretches your interval with each iteration. Just by hitting every positive integer up to 318, you've increased your interval by at least a factor of (318!)^2 ~= 10^1318. (The actual factor will be much greater.)2010-10-21
  • 0
    @Charles: And at no point can your interval of uncertainty contain pi/2+n*pi, or the answer would be undefined. So you would have to be using many thousands of decimal digits at each step. This doesn't seem possible to me. My apologies if I've misunderstood.2010-10-21
  • 2
    I should have looked at the OEIS link above. It mentions that 3000-digit precision was used. I would have guessed that millions of iterations at that level were unfeasible. Wow!2010-10-21
  • 3
    @Jonas: Far more than 3000 digits are needed to get to ~25 million where I had targeted. Of course using that much precision, one must use quasilinear tangent algorithms rather than quadratic. I used a quadratic algorithm to 10 million as a double-check and it took the better part of a year.2010-10-21
  • 0
    @Charles: Are you the one cited in the OEIS entry on this sequence?2010-10-21
  • 0
    @Joseph: No. I was in the process of my 25 million digit effort when Tony Noe added his comment and I never bothered to send an update.2010-10-22
4

This isn't a proof, but's too long for a comment, and may just be a restatement of the problem.

For contradiction, let $k$ be any integer such that $b(n) = k$ never holds. This means $k \leq a(n) < k+1$ never holds.

Since $a(n)$ can't be between $k$ and $k+1$, $\arctan a(n)$ can't be either.

Thus, there's an interval between $-\pi/2$ and $\pi/2$ that a(n) may not touch. Let's call it $[c,d)$.

Since tan is periodic, $a(n)$ must also avoid $m\pi+[c,d)$.

Since $\pi$ is irrational, $m\pi+[c,d)$ must contain an infinite number of integers (pretty sure this is true, but I could be wrong).

Therefore, there are an infinite number of intervals (approaching $\pi/2$) that $a(n)$ must avoid. Further, $a(n)$ must avoid the arctans of these intervals, and the arctans of those intervals, etc. The repeated arctan intervals approach 0.

Of course, $a(n)$ also has to avoid those intervals plus any multiple of $\pi$.

This non-proof actually applies to any interval $a(n)$ misses, so, if true, shows that $a(n)$ is dense in $\mathbb{R}$. Hope that helps.