I just wonder, but this problem had been posted earlier, without any mention of ISL 2013, but soon was deleted. That time I wondered why it was deleted, as I had posted my solution there, but now I know why it might have been deleted! [mod: indeed!]

Define $f(n) = n^2+n+1$. Then \[ n^4 + n^2 + 1 = (n^2+n+1)(n^2-n+1) = f(n)f(n-1). \] So it suffices to show that $\textstyle\max_p f(n)$ is at least the larger of $\textstyle\max_p f(n-1)$ and $\textstyle\max_p f(n+1)$ infinitely often, where $\textstyle\max_p(n)$ is the largest prime dividing $n$. If not, either $\textstyle\max_p f(1), \textstyle\max_p f(2), \dots$ is eventually strictly increasing or strictly decreasing. Since the latter is impossible for integer sequences, we only need to show this sequence cannot decrease monotonically. But $f(n^2) = f(n)f(n-1)$, so $\textstyle\max_p f(n)^2$ is at most $\textstyle\max \left( \textstyle\max_p f(n), \textstyle\max_p f(n-1) \right)$, so the sequence cannot be strictly increasing at any time. This is similar to a Russian 2010 problem, which asked to show infinitely many distinct $a$, $b$, $c$ satisfied $\textstyle\max_p (a^2+1) = \textstyle\max_p (b^2+1) = \textstyle\max_p (c^2+1)$.

I think it's very nice problem, but some easier. You can use by: \[ n^4+n^2+1=(n^2+n+1)((n-1)^2+(n-1)+1) \] let $a_n=n^2+n+1$ and $a_{n^2}=a_{n}a_{n-1}$. It means \[ max_p(a_{n^2})\le max(max_p(a_n),max_p(a_{n-1})) . \]

Quite a nice problem. Let $f(n)=n^2+n+1$, and $g(n)$ be the greatest prime dividing $f(n)$. The key observation is that $f(n^2)=n^4+n^2+1=f(n)f(n-1)$. So we are done if we can show that there are infinitely many positive integers $n$ such that $g(n) < g(n+1) > g(n+2)$. Assume this is not the case. Then after some stage the sequence $g(1), g(2), ...$ must be strictly increasing or decreasing (note consecutive $g(i)$ can never be equal as $(i^2+i+1, (i+1)^2+(i+1)+1)=1$ for positive integers $i$). If eventually it is strictly decreasing, we have a contradiction as primes are discrete with a lower bound. But it cannot eventually be always strictly increasing since $f(n^2)=f(n)f(n-1) \implies g(n^2)=g(n)$ or $g(n-1)$ for all n.

After finding the factorization this problem is relatively easy, one must simply consider the function $g$ that takes the greatest prime divisor of $n^2+n+1$. However, finding the factorization is not so easy! :/ Took me some time...

Let $f(n)$ be the greatest prime factor of $n^2+n+1$. Then note $f(n)\neq f(n+1)$ as they are relatively prime. Moreover, we want to show that $f(n)>f(n-1), f(n+1)$ for infinitely many $n$. But this is equivalent to showing that $f$ is not monotone strictly increasing or decreasing, which is easy to show since $\text{max}(f(n-1), f(n))=f(n^2)$, so we cannot be infinitely increasing.

Beautiful problem!

This problem badly overlaps with ARO 2011 11-7: https://artofproblemsolving.com/community/c6h404321_aro_2011_117 (Note in particular the solution by "yugrey" in post #10.)

Let $f(n)$ be the greatest prime factor of $n$. Since \begin{align*} n^4+n^2+1 &=(n^2+n+1)(n^2-n+1)\\ (n+1)^4+(n+1)^2+1 &= (n^2+n+1)(n^2+3n+3) \end{align*}we want to show that there are infinitely many $n$ such that $f(n^2+n+1) > f(n^2-n+1)$ and $f(n^2+n+1)>f(n^2+3n+3)$. Let $g(n)=n^2+n+1$. We want to show there are infinitely many $n$ such that $f(g(n)) > f(g(n-1)), f(g(n+1))$. This is only impossible if the sequence $\{ f(g(n)) \}$ becomes monotonic starting at some point. Note that we cannot have $f(g(n)) = f(g(n+1))$ since $\text{gcd}(g(n),g(n+1))=1$ by Euclidean Algorithm. It cannot be monotonically decreasing, so it must be increasing. Now, note that $g(n)g(n-1)=g(n^2)$. This means $f(g(n)g(n-1)) = f(g(n^2))$. But \[ f(g(n)g(n-1)) = \max(f(g(n)), f(g(n-1))),\]which is a contradiction.

Well, I guess it was just too simply easy

Really nice problem, the analytic-like technique kinda reminded me of 2015 N4, and in general a good fit for a N3. It was fun solving this one... Firstly, it becomes quite clear that $n^4+n^2+1=(n^2+n+1)(n^2-n+1)=(n^2+n+1)((n-1)^2+(n-1)+1)$ is going to play a part here, and as $(n+1)^4+(n+1)^2+1=(n^2+n+1)((n+1)^2+(n+1)+1)$, we immediately see that we need to prove that the largest prime factor of $(n^2+n+1)$ is $\geq$ the largest prime factors of $(n-1)^2+(n-1)+1$ and $(n+1)^2+(n+1)+1$ infinitely many times. Also note that $\text{gcd}(n^2+n+1,n^2-n+1)=(2n,n^2+n+1)=(n,n^2+n+1)=(n,1)=1$, as $n^2+n+1 \not \equiv 0 \pmod{2}$. But what does it mean for the prime divisor of $n^2+n+1$ to be larger than the prime divisor of both $(n-1)^2+(n-1)+1$ and of $(n+1)^2+(n+1)+1$? Well, if you were plotting the function of largest prime divisor of $n^2+n+1$ versus $n$, all $n$ satisfying this condition would be represented by a little "mountain peak" in the locality of $n$. Thus, if we assume to the contrary, it would imply that, after some $M$, the function $f(n)=$ largest prime factor of $n$ must become either strictly increasing or decreasing (as gcd of 2 consecutive $f(n)$ is 1). Of course it can't be strictly decreasing as it's restricted to naturals, we conclude that the function must eventually be strictly increasing. Well, how do we attack this problem now? Well, it'd be pretty nice if we could prove that, for arbitrarily large $n$, $f(n)=f(m)$ for $m>n>M$ (the value after which function becomes strictly increasing), as this must imply the existence of a peak somewhere on our graph between the 2 intervals. Now here's the part of the problem that ties it all together, ending the problem with the factorization we started with- $n^4+n^2+1=(n^2+n+1)(n^2-n+1)$, and as by assumption largest prime factor of $n^2+n+1=f(n)>f(n-1)$, hence largest prime factor of $n^4+n^2+1=f(n^2)=f(n)$. Thus clearly $f(n)$ can't be monotonic between $n$ and $n^2$, thus we're done.

Let $f(n)=n^2+n+1$, and let $p(n)$ denote the largest prime divisor of $f(n)$. The key observation is that \[n^4+n^2+1=\left(n^2+n+1\right)\left(n^2-n+1\right)=f(n)f(n-1),\]so we want to show $p(n)p(n-1)=p(n)p(n+1)$ for infinitely many $n$; it suffices, therefore, to prove $p(n)\ge\max(p(n-1),p(n+1))$ for infinitely many $n$. Assume for contradiction otherwise. Then $p(n)$ is eventually strictly increasing (since integer sequences cannot be eventually strictly decreasing). This is absurd, since for each $n$ we have $f(n^2)=f(n)f(n-1)$ and thus $p(n^2)=\max(p(n),p(n-1))$.

First of all, observe that $n^4+n^2+1=(n^2+n+1)(n^2-n+1)$ and $gcd(n^2+n+1,n^2-n+1)=1$ for all $n$. Furthermore, if $q$ is an odd prime such that $q|n^2-n+1$, so $q$ does not divide $(n+1)^2-(n+1)+1=n^2+n+1$ and $(n+1)^2+(n+1)+1=n^2+3n+3$. The first divisbility is from the $gcd$ condition and the second one would implie that $q|2n+2 \implies q|n+1,(n+1)^2+(n+1)+1,$ so $q|1$, contradiction. Now, let $p_n$ be the largest prime factor of $n^4+n^2+1$ and assume that there exists an $N$ such that for all $n \geq N$, we have $p_n \neq p_{n+1}$. Observe that if $p_k|k^2+k+1=(k+1)^2-(k+1)+1$ for some $k \geq N$, then $p_k|(k+1)^4+(k+1)+1$, so since $p_k$ is the largest prime factor of $k^2+k+1$ and $p_{k+1} \neq p_k$, we must have $p_{k+1}|(k+1)^2+(k+1)+1$ and $p_{k+1} > p_k \implies$ by induction, $p_{K+1} > p_K$ for all $K \geq k$, but this cannot happen infinitely, since $p_{k^2}=p_k$ ($p_k$ is also the largest prime factor of $k^2+k+1$), so we would have $p_k= p_{k^2} > p_{k^2-1}>...>p_k$, a contradiction. Hence, such $k$ doesn't exist. Therefore, for all $n \geq N$, $p_n|n^2-n+1$ and $p_n$ is the largest prime factor of $n^2-n+1$. However, since $p_{n+1}|(n+1)^2-(n+1)+1= n^2+n+1$, $p_{n+1}|n^4+n^2+1$, so $p_{n+1} < p_n$ for all $n \geq N$. Since the sequence $\{p_n\}_{n=N}^{\infty}$ is bounded below by $0$, that cannot happen infinitely, otherwise we would have negative $p_n$, contradiction. As a result, our assumption is false, so such $N$ does not exist. Thus, there are infinitely $n$ such that $p_{n+1}=p_n$, so we are done. $\blacksquare$

lyukhson wrote: Prove that there exist infinitely many positive integers $n$ such that the largest prime divisor of $n^4 + n^2 + 1$ is equal to the largest prime divisor of $(n+1)^4 + (n+1)^2 +1$. Loved it! Just observe $n^4+n^2+1=(n^2+n+1)(n^2-n+1),(n+1)^4+(n+1)^2+1=(n^2+n+1)(n^2+3n+3)$ Claim-: There are infinetly many $n$ such that largest prime divisor of $n^4+n^2+1, (n+1)^4+(n+1)^2+1$ is same. Prove-: FTSOC Assume there are only Finite set of natural number $n$ Satisfying the claimed statement. For a while call that Finite Set as "Set A" Then Let $N$ be The largest element of Set $A$ then for all $n>N$ we must have $P_{n+1}>P_n>P_{n-1}$ or $P_{n+1}<P_n<P_{n-1}$ Here $P_n$ is the Largest Prime divisor of $n^2+n+1$ Now we will investigate the $2$ possible cases. Case 1-: If $P_{n+1}<P_n<P_{n-1}$ for all $n>N$ then $P_{N}$ will be the greatest prime among all other $P_n$ for any $n>N$ Let $P_{N}=K^\text{th}$ Prime number then Then clearly at most after $n>N+k$ we will not be left with any primes to Define this decreasing sequence. Hence Contradiction this case is not possible. Case 2-: if $P_{n+1}>P_n>P_{n+1}$ for all $n>N$ Now as we have defined $P_n$ as the largest prime divisor of $n^2+n+1$. So if we choose $n>N$ such that $n=x^2-1$ for $x\in N$ Then $P_{n+1}$ we will get $(n+1)^2+(n+1)+1=(x^2-1+1)^2+(x^2-1+1)+1=x^4+x^2+1=(x^2+x+1)(x^2-x+1)$ $\implies P_{n+1}=\text{max}(P_x, P_{x-1})$ which is clear Contradiction. Hence this Case is also not possible. Hence our claime is Proved. $\blacksquare$

Let $f(x)=x^2+x+1$ and $P(x)$ be the largest prime number that divides $x$. It is well known that $f(n^2)=f(n-1)f(n)$. Thus, it follows that $f((n+1)^2)=f(n)f(n+1)$. So, it is sufficient to prove there exists infinitely many positive integers $n$ where $P(f(n-1)) \leq P(f(n)) \geq P(f(n+1))$. Or in other words, prove that $P(f(i))$ never becomes an increasing or decreasing sequence forever. Case 1: $P(f(i))$ is strictly decreasing. Clearly, $P(f(n))$ is always a positive integer. Thus, the sequence cannot decrease forever. Case 2: $P(f(i))$ is strictly increasing. Recall $P(f(n^2)) = P(f(n)f(n-1)) = \max(P(f(n)),P(f(n-1)))$ which contradicts increasing.

Define the function $f(n)$ to be the largest prime divisor of $n^2+n+1.$ Note that this implies $f(n^2) = \max(f(n), f(n-1))$ and $f((n+1)^2) = \max(f(n), f(n+1)).$ Claim: There are infinitely many $n$ such that $f(n) \ge f(n-1), f(n+1)$ (which proves the problem). Proof. Suppose not. Then for some large $N,$ $f(N), f(N+1),\dots$ is either strictly increasing or strictly decreasing. Obviously it cannot be strictly decreasing. Moreover, since $f(n^2) = \max(f(n), f(n-1))$ for all $n,$ it cannot be that the sequence is strictly increasing. $\blacksquare$

The key idea is $q(n+f(n))=max(q(n),q(n+1))$ if $F(x)F(x+1)=F(x+F(x))$ Denote $F(x)=x^2-x+1$,clearly $F(x+1)=x^2+x+1$,hence the previous becomes $F(n^2+1)=n^4+n^2+1=F(n)F(n+1)$ Let $P(n)$ denote the largest prime factor of $f(n)$,the problem requires $q(n^2+1)=q((n+1)^2+1$ for infinitely many $n$,or equivalently, $\max(q(n),q(n+1))=\max(q(n+1),q(n+2))$ for infinite many $n$ Clearly this is good if $q(n+1) \ge \max(q(n),q(n+2))$,and we will prove that this inequality holds over infinitely many $n$. For the sake of contradiction,assume not hence $q(n+1) < \max(q(n),q(n+2))$ for some $n \ge N$ where $N$ is any positive integer. By infinite descent,no sequence with an infinitely large length exists such that $\min(n)=n_0>N$ with $q(n_0+1)<q(n_0+2)$. Note that this is also implies $q(n)<q(n+1)$ for $n>n_0$,but this contradicts since the equality $q(n^2+1)=max(q(n),q(n+1))$ cannot hold for $n>n_0$.(since $n^2>n+1$)

Solved it with trigocalc Define $f(x)$ as largest prime factor of x, $A(x)=x^2+x+1$ and $g(x)=f(A(x))$ $A(x^2)=A(x)A(x-1), A((x+1)^2)=A(x)A(x+1)$ [trivial factorization] $g(x^2)=max(g(x),g(x-1)) , g((x+1)^2)=max(g(x),g(x+1))$ Claim: $g(m)\neq g(m+1)$ Consider $gcd(A(m),A(m+1))=gcd(m^2+m+1,m^2+3m+1)=1$ $\Rightarrow$ $A(m)$ and $A(m+1)$ have no common prime divisors.$\Rightarrow g(m) \neq g(m+1) $ Lets assume the contrary, Let there be only finite number of 'n' such that $g(n^2)=g((n+1)^2)$ Let 'x' be the largest value of 'n' such that $g(n^2)=g((n+1)^2)$ is true. Lets consider $g(k)$ and $g(k+1)$ for some $k>x$ Case 1: $g(k)<g(k+1)$ subcase 1: $g(k+1)>g(k+2)$ $g((k+1)^2)=g(k+1) , g((k+2)^2)=g(k+1). \Rightarrow$ contradiciton subcase 2: $g(k+1)<g(k+2)$ In previous subcase we showed that if $g(m)<g(m+1)$ for $m>x+1$, then $g(m+1)>g(m+2)$ is not possible. So, $g(k+2)<g(k+3)<g(k+4)... $ $\Rightarrow$ if $2<x+1<a<b$, then $g(a)<g(b)$ $\Rightarrow$ $g(m)<g(m+1)<g(m+2)....<g((m+1)^2)$ Now, $g((m+1)^2)=max(g(m),g(m+1))=g(m+1)$. But, $g(m+1)<g((m+1)^2)$ $\Rightarrow$ contradiction Case 2: $g(k)>g(k+1). $ Since we proved in our previous case that $g(m)<g(m+1)$ for $m>k$ is not possible. $\Rightarrow g(k)>g(k+1)>g(k+2).....>g((k+1)^2)$ $g((k+1)^2)=max(g(k),g(k+1))=g(k), but g(k)>g((k+1)^2)$ $\Rightarrow$ contradiction Our assumption was wrong, hence proved.

I am not proud of this solution, after getting the idea to look at $p(P(n^2))$ for the final part, I ended up using the Prime Number Theorem. Nevertheless, it is simply the same solution except we use the Prime Number Theorem rather than the deep fact that $n^2 > n$.

cmsgr8er wrote: Define the function $f(n)$ to be the largest prime divisor of $n^2+n+1.$ Note that this implies $f(n^2) = \max(f(n), f(n-1))$ and $f((n+1)^2) = \max(f(n), f(n+1)).$ Claim: There are infinitely many $n$ such that $f(n) \ge f(n-1), f(n+1)$ (which proves the problem). Proof. Suppose not. Then for some large $N,$ $f(N), f(N+1),\dots$ is either strictly increasing or strictly decreasing. Obviously it cannot be strictly decreasing. Moreover, since $f(n^2) = \max(f(n), f(n-1))$ for all $n,$ it cannot be that the sequence is strictly increasing. $\blacksquare$ very nice solution.

can someone explain for me why k is nonless than m

Let $f(n)=n^2+n+1$, and $P(n)$ denote the largest prime divisor of $n$. Then we have $n^4+n^2+1=f(n)f(n-1)$, so it suffices to show that there are infinitely many $n$ with $$P(f(n))>P(f(n-1)), P(f(n+1)).$$One can easily check that $\gcd(f(n),f(n+1))=1$ for all $n$, so we never have $P(f(n))=P(f(n+1))$. Suppose otherwise. Then, for all sufficiently large $n$, we either have $P(f(n))>P(f(n-1))$ or $P(f(n))<P(f(n+1))$, which implies that $P(f(n))$ is eventually (strictly) increasing, since $P(f(n))>P(f(n-1)) \implies P(f(n+1))>P(f(n))$ for large enough $n$. But we also have $P(f(n^2))=\max\{P(f(n)),P(f(n-1))\}$, but if $P(f(n))$ is increasing we must have $P(f(n^2))>P(f(n)),P(f(n-1))$: contradiction. $\blacksquare$

Let $f(n)=n^2+n+1$ and let $p(n)$ be the largest prime divisor of $n$ and let $g(n)=p(f(n))$. Notice that $n^4+n^2+1=f(n)f(n-1)$, so $g(n^2)=\max\{g(n),g(n-1)\}$ and $g((n+1)^2)=\max\{g(n),g(n+1)\}$. Thus it suffices to show that there are infinitely many $n$ such that $g(n)=\max\{g(n-1),g(n),g(n+1)\}$. Suppose otherwise, then there are finitely many such $n$. Say that the largest such $n$ is $m-1000$. Then, let $n\gg m$. Since: $$\gcd(f(n),f(n+1))=\gcd(n^2+n+1,n^2+3n+3)=\gcd(n^2+n+1,2n+2)=\gcd(n^2+n+1,n+1)=\gcd(1,n+1)=1$$we have that $g(n)\ne g(n+1)$. So either $g$ is strictly increasing or strictly decreasing, but this cannot be the case as $g((n+1)^2)=\max\{g(n),g(n+1)\}$. Boom.

Let $f(n)=n^2+n+1$ then $f(n^2)=f(n)f(n-1).$ Let $g(n)$ be the largest prime divisor of $f(n)$ then $g(n^2)$ equals the bigger of $g(n)$ and $g(n-1)$, and the largest prime divisor of $g((n+1)^2)$ equals the bigger of $g(n+1)$ and $g(n).$ If we find a number $n$ such that $g(n-1),g(n+1)<g(n)$, then $g(n^2)=g((n+1)^2)=g(n).$ It remains to show there are infinitely many such local maxima. If this is false, $g(n)$ is eventually monotonous. It cannot be so because $g(n^2)=g(n)$ or $g(n-1)$.

Just factor. $P(n) = n^2 + n + 1$, then $n^4 + n^2 + 1 = P(n-1)P(n), (n+1)^4+(n+1)^2+1 = P(n)P(n+1)$, so it suffices to show if $f(n)$ is the largest prime factor of $P(n)$ that $f(n)$ has unboundedly many cases where $f(n - 1) \leq f(n) \geq f(n+1)$. This is trivial since assuming otherwise, then after some $N$ we must have that $f(n)$ is strictly increasing but this is impossible since for all large $n$ we would always have a prime factor at least $n - c$ but then $P(n^2)$ has no large prime divisors, giving contradiction.

Let $f(x)$ be the largest prime divisor of $x^2+x+1$. Since \[n^4+n^2+1=((n-1)^2+(n-1)+1)(n^2+n+1)\]\[(n+1)^4+(n+1)^2+1=(n^2+n+1)((n+1)^2+(n+1)+1)\]we just want to find values of $n$ such that \[f(n)\ge f(n-1),f(n+1).\]Therefore, it is enough to show that $f$ cannot eventually only increase. Since $f(n^2)=\text{max}(f(n-1),f(n))$ this is true, and we are done. $\blacksquare$

Let $f(x)=x^2+x+1$ and $g(x)$ be the largest prime divisor of $x$. Note that $f(x-1)f(x)=f(x^2)$ and $g(xy)=\text{max}(g(x),g(y))$. Then we want to prove that there exist infinitely many positive integers $n$ such that $g(f(n^2))=g(f((n+1))^2)$ Claim. For any positive integer $N$, there exists a positive integer $n>N$ such that $g(f(n))=g(f(n^2))$. Proof. We will prove that there exists an increasing sequence of such $n$. Firstly, manually check that \[g(f(36))=\text{max}(g(f(5)),g(f(6)))=g(f(6)).\]Now note that there must be some positive integer $6\le k < 36$ such that $g(f(k))\le g(f(k+1))$. Then \[g(f((k+1)^2))=\text{max}(g(f(k)),g(f(k+1)))=g(f(k+1)).\;\blacksquare\] Claim. There exists infinitely many positive integers $n\ge 2$ such that $g(f(n))\ge g(f(n+1))$ and $g(f(n))\ge g(f(n-1))$. Proof. Suppose not. Then $g(f(x))$ is strictly increasing or strictly decreasing past one point, which is impossible due to the previous claim. Now simply note that such $n$ satisfy the given constraint. QED.

nice

Let $f(x) = x^2 + x + 1$ and $P(x)$ be the largest prime divisor of $x$. Then we wish to show that \[P(f(n^2)) = P(f((n+1)^2).\]However, $f(x^2) = f(x)f(x-1)$, so this is equivalent to \[\max(P(f(n), P(f(n-1)) = \max(P(f(n), P(f(n+1)).\]We will show that there exist infinitely many $n$ so that $P(f(n)) \ge \max(P(f(n-1)), P(f(n+1))$; this clearly finishes. Note that this is equivalent to showing that the sequence $a_n = P(f(n))$ cannot be strictly increasing; however, since $a_{n^2} = \max(a_n, a_{n-1})$ this is impossible and we are done. $\square$

Let $a_n$ denote the largest prime factor of $n^2+n+1$. The largest prime factor of $n^4+n^2+1$ is just $\max(a_n,a_{n-1})$ because $n^4+n^2+1=(n^2+n+1)(n^2-n+1).$ Claim 1: There are infinitely many $n$ such that $a_{n+1}\geq a_n$. Note that given any prime $p$, there is a value of $n\pmod p$ such that $n^2+n+1$ is not divisible by $p$. Thus, given any finite list of primes, by Chinese Remainder Theorem we can pick $n$ to avoid all of them. Thus, the sequence $a_i$ is unbounded, which clearly shows the claim. Claim 2: There are infinitely many $n$ such that $a_{n+1}\leq a_n$. Suppose for the sake of contradiction that after some point, the sequence is strictly increasing. Then, after a certain point, the largest prime divisor keeps increasing. The slowest that the "largest prime divisor" sequence is allowed to increase is by going to the next prime, and counting primes grows at a faster than linear rate by PNT, so for sufficiently large $n$, all $n^2+n+1$ has a prime factor greater than say $1434n$. However, when $n$ is a perfect square, we have that $$n^2+n+1=(n+\sqrt{n}+1)(n-\sqrt{n}+1).$$Both of these factors are less than $1434n$, hence contradiction as we know that there is a prime factor at least $1434n$ for all sufficiently large $n$. Thus, there are infinitely many nonincreasing steps, and infinitely many nondecreasing steps. Thus, there must be infinitely many transitions between the two, and thus infinitely many turns where a nondecreasing step is followed by a nonincreasing step. Thus, there are infinitely many runs of 3 numbers such that the middle number is equal to the max of the 3 numbers, hence done as if $a_n\geq a_{n-1}$ and $a_n\geq a_{n+1}$, then $\max(a_{n-1},a_n)=\max(a_n,a_{n+1}).$

Talk about being nonstandard! Let $f(n) = n^2+n+1$. Notice that if we can find infinitely many $n$ such that $f(n-1), f(n+1) \leq f(n)$, then all these $n$ will satisfy the problem statement. It just suffices to show that there cannot exist an $N$ such that $f(n)$ is strictly increasing for all $n \geq N$. To see this, construct a sequence $\{p_i\}$ where $p_0 = f(N)$ and $p_i > p_{i-1} = f\left(N +\prod_{j=1}^{i-1} p_i\right)$. It follows that for every $m$, $$p_0p_1 \cdots p_m \mid f(N + p_0p_1 \cdots p_{m-1}) = (p_0p_1 \cdots p_{m-1})^2 + (2N+1)(p_0p_1 \cdots p_{m-1}) + N^2+N+1.$$By picking $m$ large enough we have $p_0p_1 \cdots p_{m-1} > N^2+N+1$, hence contradiction. It follows that $f(n)$ switches from increasing to decreasing and vice versa infinitely many times. Picking these maximum critical points $n$ yields the desired solutions.

Very intuitive NT! Let $f(n)=n^2+n+1$ and let $F(x)$ denote the largest prime factor of $x$. Note that $F(f(n))$ is clearly unbounded. Also it cannot be increasing or decreasing due to obvious reasons. Therefore it must have infinitely many "peaks". Hence we're done.

Notice that $n^4+n^2+1 = (n^2+n+1)(n^2-n+1)$ and $(n+1)^4+(n+1)^2+1 = (n^2+2n+3)(n^2+n+1)$. Define $f(x)$ as the largest prime divisor of $x^2+x+1$. Then, we have that $f(x^2) = f(x)f(x-1)$. We would like to show there exist infinitely many $n$ such that $f(n^2) = f((n+1)^2)$. Since $f(n^2) = \max(f(n), f(n-1))$, this is equivalent to showing that $f(x)$ has infinitely many ``local maxima.'' FTSoC assume that $f(x)$ has finitely many ``local maxima.'' Then, this implies that for big enough $N$, $f(x)$ is either strictly increasing or strictly decreasing for $x > N$. Since $f(x)$ always outputs a positive number, it is impossible for it to be always strictly decreasing, so we would like to show that $f$ cannot be strictly increasing forever. This is easy to show since $f(n^2) = \max(f(n), f(n-1))$ and $n^2 > n$, so clearly it cannot be strictly increasing, done.

Define the function $f(x)=x^2+x+1$, and notice that our desired expressions factor as $f(n-1) \cdot f(n)$ and $f(n) \cdot f(n-1)$. It remains to show that there exists infinitely many $n$ for which the largest prime factor of $f(n)$ is greater than or equal to the largest prime factor of $f(n-1)$ or $f(n)$. In other words, the largest prime factor of $f(n)$ is neither always increasing or decreasing for large $n$. The decreasing claim is trivial. For the increasing portion, assume FTSOC there exists some $m$ for which the largest prime factors of each term in $f(m), f(m+1), f(m+2), \ldots$ is always strictly increasing. However, we simply note that \[f((m+1)^2) = f(m) \cdot f(m+1),\] so the greatest prime factor of $f((m+1)^2)$ is the greatest prime factor of $f(m+1)$, contradiction. $\blacksquare$

Time For Another Unnecessary Long And Motivated Solution Posting after a long while..... Let $W(n)$ denote the largest prime factor of some $n$ and $f(n)=n^2+n+1$. We basically want that \[W(n^4+n^2+1)=W((n+1)^4+(n+1)^2+1)\]however notice the factorizations, \[n^4+n^2+1=f(n)f(n-1) \ \land \ (n+1)^4+(n+1)^2+1=f(n)f(n+1)\]which gets us to $max\{W(f(n)),W(f(n-1))\}=max\{W(f(n)),W(f(n+1))\}$ although, there are a few cases to deal with. We check a few $W(f(n))$ points by hand and want that $max$ on both points are $W(f(n))$ as then we are automatically done. We just want, \[W(f(n)) \ge max\{W(f(n+1)),W(f(n-1))\}\]to hold and call all such pairs as "good tuples". Now, first assume that there are only finitely many points such that $W(f(n)) \ge W(f(n-1))$ then, obviously $\exists \ C$ such that $\forall x \ge C$ we have, $W(f(x)) \le W(f(x-1))$ as in this function becomes decreasing after a finite point. However this means that the primes dividing $n^2+n+1$ are bounded above. We shall prove the opposite. Basically $\exists$ arbitrarily large $n$ divisble by arbitrarily large primes $p$. Consider a large prime of the form $1 \ (mod \ 3)$ by dirichlet's theorem now by a bit of trivial quadratic residue check, one realizes that $(-3)$ is a quadratic residue and for any such $p$ we have some $\sqrt{-3} \equiv d \ (mod \ p)$. Now we have that, \[n^2+n+1 \equiv 0 \ (mod \ p) \iff (2n+1)^2 \equiv (-3) \ (mod \ p) \iff (2n+1) \equiv d \ (mod \ p) \iff n \equiv \frac{d-1}{2} \ (mod \ p)\]so arbitrarily large $n$ exist. Also modular inverse of $2$ exists due to $(2,p)=1$. Thus we have infinitely many points where this sign flip occurs (or perhaps not a flip but this thing entirely as a chain), in any case if infinitely many such points also had $W(f(n)) \ge W(f(n+1))$ then we would be done. Hence assuming the opposite we have only finite such points where our original condition holds. So there is some finite constant $G'$ above which whenever there is a \[W(f(n)) \ge W(f(n-1)) \implies W(f(n))<W(f(n+1))\]and hence pick the first such point and on the next point if $W(f(n+2)) \le W(f(n+1))$ then this pair is a "good tuple" but we have already assumed that we have exceeded the finite set (Euclid's Infinitude Style Argument) and thus we must have a strict increasing $W$ after that point. We shall prove this is not the case as arbitrary points have, what we called "sign-flips" earlier. Herein the idea comes after a while of playing around with say $n^2+n+1=p^a, k^2, k^{2a}$ and so on. All these forms have some conclusion which is not something we like. Generalizing to a general power seems too wanky to work with, but testing $n=1,2,\dots,10$ turns out we can wish for $a^2+a+1 \mid b^2+b+1$ and thus, \[a^2+a+1 \mid b^2+b-a^2-a \iff a^2+a+1 \mid (b-a)(b+a+1)\]again by a bit of Evan's "Blackjack Analogy" we have that, $a^2+a+1=b-a \implies b=(a+1)^2$ when we suddenly realize $f((n+1)^2)=f(n)f(n+1)$ and thus, \[W(f(n+1)^2))=max\{W(f(n)),W(f(n+1))\}\]when we let $n>G'$ arbitrary so that $f(n)<f(n+1)$ and hence $W(f(n+1)^2)=W(f(n+1))$ however, $(n+1)^2>(n+1)$ and thus $W(f((n+1)^2))>W(f(n+1))$ due to condition which creates an obvious contradiction! Therefore we are done! Q.E.D Remark : I might have missed out on an equality somewhere, but I'm pretty sure it can be easily corrected if so. Also, kindly spot out major errors (if any). Secondly I know there are a lot of optimizations say for example, the problem statement itself points out $f((n+1)^2)$ observation but whatever.

Factorizing $n^4+n^2+1$ and $(n+1)^4+(n+1)^2+1$ gives $(n^2+n+1)(n^2-n+1)$ and $(n^2+n+1)(n^2+3n+3)$ respectively. Now, if we show that the largest prime diving both the equation comes from $(n^2+n+1)$ infinitely many times, we are done. Claim: Above statement Proof: Assume this happens finitely, then we will get a chain of increasing numbers having their largest prime coming from $(n^2+3n+3)$ and the other factor. Take the successive number, we see they share a factor Eg; take $n+2$, we see that it factorizes to $(n^2+3n+3)(n^2+5n+7)$, the larger polynomial becomes the smaller one. So, if after some $n$, the largest prime always comes from the larger polynomial, this means that the largest prime will always increase in $n^2+n+1$ form (in $n^2+3n+3$ is just $n=n+1$). This is obviously false as the largest prime of $n=n^2$ (n^4+n^2+1) equals that of $n^2+n+1$, so all the numbers in between $n$ and $n^2$ will either have equal or smaller largest prime than $n^2+n+1$, this solves our problem by contradiction. As there should be some $n$ for which the largest prime belongs to the smaller polynomial, in a chain of numbers where it belongs to the larger one. So, we can find two consecutive numbers. For the largest prime coming from the smaller polynomial always, we can show that this means the largest prime decreases with $n$ but this can not happen due to the same above argument.