## Primes and Ackermann’s function

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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.

Thanks!

-

6
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$). – BR Nov 8 2011 at 18:29

1
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. – Andres Caicedo Nov 9 2011 at 3:34
I'm using the one which is called the Ackermann-P\'{e}ter function on Wikipedia (en.wikipedia.org/wiki/Ackermann_function). Thanks. – Timothy Foo Nov 10 2011 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 2011 at 4:24

1
Timothy, I think you'd enjoy looking at the paper Iterated exponents in number theory, by D.B. Shapiro and S.D. Shapiro: math.osu.edu/~shapiro/IE.pdf – Anonymous Dec 10 2011 at 5:31

## 1 Answer

Hartley (http://primes.utm.edu/curios/page.php/71.html) 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?

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 47, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9300144910812378, "perplexity_flag": "head"}