2
$\begingroup$

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$ ?

$\endgroup$
1
  • $\begingroup$ Something about this title really catches me. I like it. $\endgroup$
    – davidlowryduda
    Jan 23, 2014 at 19:44

1 Answer 1

3
$\begingroup$

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):

First addend:

  • $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}$

Second addend:

  • $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.

$\endgroup$
4
  • $\begingroup$ 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). $\endgroup$
    – Peter
    Jan 22, 2014 at 10:18
  • $\begingroup$ 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$. $\endgroup$
    – Peter
    Jan 22, 2014 at 11:11
  • $\begingroup$ I extended the search for z(15) up to $3*10^7$. $\endgroup$
    – Peter
    Jan 22, 2014 at 11:19
  • $\begingroup$ I reached $5*10^7$, but as said, I might have missed some factors because my program handles some cases wrong. $\endgroup$
    – Peter
    Jan 22, 2014 at 11:33

You must log in to answer this question.

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