# A problem in number of prime factors

Let $n,k\in\mathbb{N}$ $$^kn = n^{n^{n^{.^{.^{.^{.^{n}}}}}}}(k\space\text{times})$$

with $^0n = 1$.

Let $$S_n= {}^nn + {}^{\left\lfloor\sqrt{n}\right\rfloor}n + {}^{\left\lfloor\sqrt{\left\lfloor\sqrt{n}\right\rfloor}\right\rfloor}n + \dots + 1$$

Here in $S_n$, $n$ appears only once. So, for example $S_3=3^{3^3}+3+1$, $S_4=4^{4^{4^4}}+4^4+4+1$, $S_5=5^{5^{5^{5^5}}}+5^5+5+1$, etc.

Show that for infinitely many values of $n$, number of prime factors of $S_n$ is less than $n$.

I checked $n=2$ and $n=3$: $S_2=7$ and $S_3=7625597484991=223\times 34195504417$.

I don't know how to start actually. My teacher(who gave me this problem) did not give any hint. Can anyone help me here?

Also see here

• $n \uparrow \uparrow k$? – Kenny Lau Aug 17 '17 at 8:15
• @KennyLau I know the notation something like suffix k then n, is this also notation for that? – D1AmZUa sumU Aug 17 '17 at 8:18
• @D1AmZUasumU Yes $^kn$ is also a notation for this operation. – cirpis Aug 17 '17 at 8:20
• Note that the examples (presumably provided by your teacher) conveniently stopped at $n=3$. $S_4$ is well defined, but you'll never find it -- it's way too big to compute. – quasi Aug 17 '17 at 8:37
• @D1AmZUa sumU: I would forget the problem. In my view, it's intractable. But if your teacher supplies a proof, please post it here. – quasi Aug 17 '17 at 8:44