# Prime factors of a sum of special power towers

Denote

$$x(n) = 2 \uparrow 3 \uparrow ... \uparrow n$$

and

$$y(n) = n \uparrow (n-1) \uparrow ... \uparrow 3 \uparrow 2$$

Finally denote

$$z(n) = x(n) + y(n)$$

So, the first few numbers z(n) are

$$z(2) = 2 + 2 = 4$$ $$z(3) = 2^3 + 3^2 = 17$$ $$z(4) = 2^{3^4}+4^{3^2} = 2^{81} + 4^9$$ $$z(5) = 2^{3^{4^5}} + 5^{4^{3^2}} = 2^{3^{1024}} + 5^{2^{18}}$$

For odd $n\ge3$, every prime factor p > 2 of z(n) has -2 as a quadratic residue because z(n) is of the form $x^2+2y^2$ with gcd(x,y)=1. For z(5), I checked the prime factors up to $10^7$ and only found 3,11,59 and 281.

The first number z(n) without very small prime factors is z(9).

Could anyone search for primefactors of z(9) upto, lets say, $10^7$ ?

My quick computer search suggests the smallest factor of $z(9)$ should be $523$. Confirmation (of it being a factor; not necessarily the smallest one):

• $2^{3\uparrow 4\uparrow 5\ldots\uparrow 9}\equiv 2^{(3\uparrow 4\uparrow 5\ldots\uparrow 9)\ \bmod\ 522}\pmod {523}$
• $522=2\times 3^2\times 29$
• $3^{4\uparrow 5\ldots\uparrow 9}\equiv 1\ \pmod 2$
• $3^{4\uparrow 5\ldots\uparrow 9}\equiv 0\ \pmod {3^2}$ since the exponent is certainly greater than $2$
• $3^{4\uparrow 5\ldots\uparrow 9}\equiv 3^{(4\uparrow 5\ldots\uparrow 9)\ \bmod\ 28} \pmod{29}$
• $28 = 2^2\times 7$
• $4^{5\uparrow\ldots\uparrow 9}\equiv 0\pmod 4$
• $4^{5\uparrow\ldots\uparrow 9}\equiv 4^{(5\uparrow\ldots\uparrow 9)\ \bmod\ 6}\pmod 7$
• $5^{6\uparrow \ldots \uparrow 9} \equiv 1\pmod 6$ since the exponent is even
• Thus, $4^{5\uparrow\ldots\uparrow 9}\equiv 4^1\equiv 4\pmod 7$
• Chinese Remainder Theorem then says $4^{5\uparrow\ldots\uparrow 9}\equiv 4\pmod{28}$
• Thus, $3^{4\uparrow 5\ldots\uparrow 9}\equiv 3^{4}\equiv 23\pmod {29}$
• CRT says $3^{4\uparrow 5\ldots\uparrow 9}\equiv 81\pmod {522}$
• Thus, $2^{3\uparrow 4\uparrow 5\ldots\uparrow 9}\equiv 2^{81}\equiv 424\pmod {523}$

• $9^{8\uparrow 7\uparrow 6\ldots\uparrow 2}\equiv 9^{(8\uparrow 7\uparrow 6\ldots\uparrow 2)\ \bmod\ 522}\pmod {523}$
• $522=2\times 3^2\times 29$
• $8^{7\uparrow 6\ldots\uparrow 2}\equiv 0\pmod 2$
• $8^{7\uparrow 6\ldots\uparrow 2}\equiv 2\pmod {3^2}$ since the exponent is even
• $8^{7\uparrow 6\ldots\uparrow 2}\equiv 8^{(7\uparrow 6\ldots\uparrow 2)\ \bmod\ 28}\pmod {29}$
• $28 = 2^2\times 7$
• $7^{6\uparrow\ldots\uparrow 2}\equiv 1\pmod {2^2}$ since the exponent is even
• $7^{6\uparrow\ldots\uparrow 2}\equiv 0\pmod 7$ (obvious)
• CRT says $7^{6\uparrow\ldots\uparrow 2}\equiv 21\pmod {28}$
• Thus, $8^{7\uparrow 6\ldots\uparrow 2}\equiv 8^{21}\equiv 12\pmod{29}$
• CRT says $8^{7\uparrow 6\ldots\uparrow 2}\equiv 128\pmod{522}$
• Thus, $9^{8\uparrow 7\uparrow 6\ldots\uparrow 2}\equiv 9^{128}\equiv 99\pmod{523}$

Since $424+99=523$, the sum of the terms is multiple of $523$, just as we wanted to prove.

• Very nice! I used Wolfram Alpha to check the primes with quadratic residue -2 up to 523. Indeed, 523 is the smallest prime factor of z(9) and $523^2$ does not divide z(9). z(15) has no prime factor up to 523. If you want, you can search for prime factors of z(15). Jan 22, 2014 at 10:18
• According to my calculation in PARI, z(9) has only the prime factor 523 up to $10^7$, but my program does not seem to manage all cases. Wolfram gives y(15)=16 mod 163, whereas my program gives y(15)=113 mod 163, so my calculation is not completely reliable. It is indeed very difficult to calculate the power towers modulo m. According to my program, z(15) has no prime factor below $10^7$. Jan 22, 2014 at 11:11
• I extended the search for z(15) up to $3*10^7$. Jan 22, 2014 at 11:19
• I reached $5*10^7$, but as said, I might have missed some factors because my program handles some cases wrong. Jan 22, 2014 at 11:33