MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If $A(m,n)$ is Ackermann's function, and $c$ is a fixed integer, are there any heuristics/conjectures/obvious things that can be said about primes of the form $A(m,n)+c$, $m \geq 4$,at all?

EDIT: I guess I should add that heuristically, for sufficiently large $m$, the set is so sparse that the expected number of primes of the form $A(m,n)+c$, for fixed $m$ and $c$, should be finite! So maybe I should ask if there is any reason why the number of primes of the form $A(m,n)+c$, for fixed $m$ and $c$, despite $m$ being large, might actually not be finite.


share|cite|improve this question
I can't imagine anything is known, as (1) the number-theoretic structure of Ackermann's function is not clear (2) the question does not seem amenable to experimentation (3) simpler questions are wide open (e.g. are there infinitely many primes of the form $x^2+1$). – B R Nov 8 '11 at 18:29
What definition of Ackermann's function are you using? There are several different versions, equivalent in terms of rates of growth, but they would differ for problems like the ones you are asking. – Andrés E. Caicedo Nov 9 '11 at 3:34
I'm using the one which is called the Ackermann-P\'{e}ter function on Wikipedia ( Thanks. – Timothy Foo Nov 10 '11 at 1:06
Anyway, thank you very much, BR and Andres, for helpful comments; I'm wondering what more can be asked or said about $\lim_{k \rightarrow \infty}2\uparrow\uparrow k \bmod N$ , since this limit seems to exist. It's a residue in $(\mathbb{Z}/N\mathbb{Z})^{*}$, and I'm now wondering about the fractions $\frac{\lim_{k \rightarrow \infty}2\uparrow\uparrow k \bmod N}{N}$. – Timothy Foo Nov 10 '11 at 4:24
Timothy, I think you'd enjoy looking at the paper Iterated exponents in number theory, by D.B. Shapiro and S.D. Shapiro: – so-called friend Don Dec 10 '11 at 5:31

Hartley ( gives that 13 and 71 divide $A(m,n)$ for sufficiently large $m$.

Since $\{A(m+1,n): n \geq N\} \subset \{A(m,n): n\geq A(m+1,N-1)\}$, we need only consider smaller $m$.

The case $m=4$ definitely involves $2\uparrow\uparrow k \bmod p$. If, for all primes $p$, $2 \uparrow\uparrow a \equiv 2 \uparrow\uparrow b \bmod p$, for sufficiently large $a,b$, then the $A(m,n)+c$, for fixed $c$, will be composite for sufficiently large $m$, since some prime $p$ will divide $A(4,n)+c$ for some large $n$ and then it will also divide $A(4,r)+c$ for $r \geq n$ if $n$ is sufficiently large, if the condition is true.

But $2 \uparrow\uparrow a \equiv 2 \uparrow\uparrow b \bmod p$ if $2 \uparrow\uparrow (a-1) \equiv 2 \uparrow\uparrow (b-1) \bmod (p-1)$ which is true if $2 \uparrow\uparrow (a-1) \equiv 2 \uparrow\uparrow (b-1)$ mod each prime power, say $q$, dividing $p-1$. But then this reduces to considering $2 \uparrow\uparrow (a-2) \equiv 2 \uparrow\uparrow (b-2) \bmod \varphi(q)$. The point is that the modulus keeps shrinking and eventually we can check $2\uparrow\uparrow k$ modulo small primes.

For example, $2\uparrow\uparrow k \equiv 1 \bmod 3$ and $2\uparrow\uparrow k \equiv 1 \bmod 5$ for sufficiently large $k$.

It seems then that for sufficiently large $m$, and fixed $c$, $A(m,n)+c$ cannot be prime. Does this work?

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.