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.

$\endgroup$
7
  • 11
    $\begingroup$ 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? $\endgroup$
    – Alon Amit
    Oct 14, 2010 at 18:09
  • 1
    $\begingroup$ Is it obvious that the sequence is everywhere defined? (I think it must be true but I don't see how to prove it.) $\endgroup$
    – Qiaochu Yuan
    Oct 14, 2010 at 21:02
  • 2
    $\begingroup$ @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? $\endgroup$
    – user856
    Oct 20, 2010 at 18:40
  • 1
    $\begingroup$ 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. $\endgroup$
    – George Lowther
    Oct 21, 2010 at 23:18
  • 1
    $\begingroup$ 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: akpublic.research.att.com/~njas/sequences/A032523). It seems likely that this question is much harder than that. $\endgroup$
    – George Lowther
    Oct 21, 2010 at 23:23

2 Answers 2

Reset to default
17
+125
$\begingroup$

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!

$\endgroup$
9
  • 1
    $\begingroup$ @Charles: Indeed, more theory is needed! Very interesting that you have explored this so substantively... Thanks for sharing (as the kids say)! $\endgroup$
    – Joseph O'Rourke
    Oct 21, 2010 at 2:02
  • $\begingroup$ @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. $\endgroup$
    – Jonas Kibelbek
    Oct 21, 2010 at 2:15
  • 1
    $\begingroup$ 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. $\endgroup$
    – Charles
    Oct 21, 2010 at 3:16
  • 2
    $\begingroup$ 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! $\endgroup$
    – Jonas Kibelbek
    Oct 21, 2010 at 7:58
  • 3
    $\begingroup$ @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. $\endgroup$
    – Charles
    Oct 21, 2010 at 13:23
4
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .