Suppose $p$ is a prime divisor of $f(n)$ that does not divide $f(m)$ for $m\in\{1,\dots,n-1\}$. Then $p$ does not divide $f(n)-f(m)=3(n-m)(n+m)$, so $p\geq2n$. But there is at most one prime $p\geq2n$ that divides $f(n)=3n^2+1$, so we are done by induction. For some related problems, see 2008 IMO #3 and 2006 USAMO #3.

I think the following solution works: If $p$ is a prime divisor of $3n^2+1$ that does not divide any $3i^2+1$ for $i \le n-1$. Then, $ n \le \frac{p-1}{2} \implies 2n+1 \le p$ If $f(n)$ has two such prime divisors then, $f(n) \ge (2n+1)^2$ which is obviously not true. So,there can be only one prime divisor of $f(n)$ which does not divide any $f(i)$ for $i \le n-1$ from which the conclusion follows.

We prove the following stronger statement: Say $f(1)\cdot f(2)\cdot \cdots f(n-1)$ has $k$ prime divisors. Then $f(1)\cdot f(2)\cdot \cdots f(n)$ has at most $k+1$ prime divisors. Proof: Suppose $p\mid f(n)$ and $p\nmid f(i)$ for $0<i<n.$ Then we must have $p\nmid f(n)-f(i)=3n^2-3i^2=3(n-i)(n+i).$ Thus $p>2n$ (since $2n$ is even and not prime). Now for the sake of contradiction say more than $1$ prime satisfies this. Let two of them be $p,q.$ But $pq\mid 3n^2+1$ and $pq>4n^2\geq 3n^2+1,$ contradiction.

Suppose on the contrary that there exists $m\in\mathbb N$ such that $f(1),f(2),...,f(m)$ has at least $M+1$ distinct prime divisors $p_1,p_2,...,p_{m+1}$. Then for every prime number $p$, let $g(p)$ be the smallest integer $n$ such that $p|f(n)$.(If such integer doesn't exist then define $g(p)=\infty$) CLAIM. $2g(p)\leq p$ for all prime $p$ with $g(p)\neq \infty$. Proof. Suppose on the contrary that there exists $p$ such that $2g(p)>p$. Then $g(p)>p-g(p)$. Notice that $f(p-g(p))\equiv f(g(p))\equiv 0\mod p$ which contradicts the minimality of $g(p)$ Now for each $1\leq i\leq m+1$, $g(p_i)\leq m$. By pigeonhole principle there exists $1\leq i<j\leq m+1$ such that $g(p_i)=g(p_j)=k$. Then $$p_ip_j|3k^2+1$$From the claim, $p_i\geq 2k$,$p_j\geq 2k$ hence $4k^2\leq p_ip_j\leq 3k^2+1$ Hence $k=1$, but $f(1)=4$ has only one prime divisor, hence $p_i=p_j=2$, contradict to the assumption that they are distinct.

In fact quite interestingly, this proposition Quote: Say $f(1)\cdot f(2)\cdot \cdots f(n-1)$ has $k$ prime divisors. Then $f(1)\cdot f(2)\cdot \cdots f(n)$ has at most $k+1$ prime divisors. always is true for $f(x)$ with positive integer coefficients, because a similar inequality can be established. It's just that sometimes $f(1)$ has more than one prime factor. If $f(x)=ax^2+bx+c$ for positive integer $a,b,c$ this is true iff $a+b+c$ is the power of a prime. I really like this problem.

We use induction . Say $f(n)$ has a prime divisor that doesn't divide $f(i)$ for all $1\le{i}\le{n-1}$. Then $\bullet$ if $p<n$ , then $p\mid{f(n-p)}$ , absurd. $\bullet$ if $n<p<2n$ , then $p\mid{f(p-n)}$ , absurd. And note that $p\neq{n}$ , so $p>2n$ and if there's another $q\neq{p}$ satisfying this condition $\implies$ $q>2n$ and $4n^2<pq\le{3n^2+1}$ , contradiction. $\blacksquare$

dchenmathcounts wrote: If $f(x)=ax^2+bx+c$ for positive integer $a,b,c$ this is true iff $a+b+c$ is the power of a prime. Wait but don't you need $a \leq 4$ for this to 'eventually' hold, at least with the given inequalities? For example, $f(n)=(2n+1)(8n+1)$ satisfies your conditions probably fails a few times (eg. 30 i think)

Note that any unique prime divisor of $f(n)$ does not divide $3(n-m)(n+m)$ for any $1\leq m\leq n-1$, implying $p\geq 2n$. However, there is at most 1 such $p$, so we are done by inducting on $n$.

mira74 wrote: dchenmathcounts wrote: If $f(x)=ax^2+bx+c$ for positive integer $a,b,c$ this is true iff $a+b+c$ is the power of a prime. Wait but don't you need $a \leq 4$ for this to 'eventually' hold, at least with the given inequalities? For example, $f(n)=(2n+1)(8n+1)$ satisfies your conditions probably fails a few times (eg. 30 i think) Oops I figured out where I went wrong. My argument was the following: Say $p\mid f(n)$ and $p\nmid f(i)$ for $0<i<n.$ Then $p\nmid f(n)-f(i)=a(x-i)(x+i)+b(x-i)=(x-i)(ax+ai+b).$ I was going to vary $i$ but just noticed it doesn't cover everything oops. Edit: Maybe this makes the following problem viable? Find max $f(2020)$ that meets the requirement.

We can prove it by induction on $n$. The case of $n=1$ is obvious. Now suppose that for some fixed $n-1$ the statement of the problem is true. NOw suppose that there exist distinct primes $p$ and $q$ such that $pq \mid f(n)$ and $pq \nmid \prod_{m=1}^{n}f(m)$. The latter implies that $p, q\nmid f(m) \forall m<n$ and $p,q \mid f(n)$. Hence $p,q \nmid f(n)-f(m)=3(n-m)(n+m) \forall m<n \implies p,q \nmid 1,2,3,\dots,2n-1$, hence both $p$ and $q$ are greater or equal $2n$. Since they are distinct, $pq \geq 4n^2 \mid 3n^2+1$, which is impossible when $n>1$. This contradiction completes the proof. $\square$

Claim: If $p$ is a prime number, then the set $S=\{f(1),f(2),...,f(\frac{p-1}{2})\}$ contains a multiple of $p$. Proof: Observe that if we have $x,y \in S$ with $x\neq y$ such that $f(x) \equiv f(y) \pmod{p}$, then $3x^2+1 \equiv 3y^2+1 \pmod{p} \implies x^2 \equiv y^2 \pmod{p}$, since $p$ can not be $3$. Thus, $x \equiv y \pmod{p}$ or $x \equiv -y$. In both cases, we get a contradiction since $-\frac{p-3}{2} \leq x-y \leq \frac{p-3}{2}$ and $3 \leq x+y \leq p-2$. $\square$ Now, we induct on $n$, the case $n=1$ is trivial. Now, suppose that there are primes $p\neq q$ such that $pq|f(n+1)$ and $p,q \not| f(1),f(2),...,f(n)$. Then, from the claim, if we have $n \geq \frac{p-1}{2}$ then there exist $m \in \{1,2,...,\frac{p-1}{2}\}$ such that $p|f(m)$, contradiction. Hence, we have that $\frac{p-1}{2},\frac{q-1}{2} \geq n+1 \implies p,q \geq 2n+3$ and since $pq|f(n+1)$, then $(2n+3)^2 \leq pq \leq f(n+1)=3n^2+6n+4 \implies 4n^2+12n+9 \leq 3n^2+6n+4$, a contradiction for $n \geq 2$. Thus, there is at most one prime number $p$ such that $p|f(n+1)$ and $p \not| f(1),f(2),...,f(n)$, so since $f(1)f(2)...f(n)$ has at most $n$ distinct prime factors by the inductive hypothesis, then $f(1)f(2)...f(n+1)$ has at most $n+1$ distinct prime divisors, as desired. $\blacksquare$

All the prime divisior of $f(n) =3n^2+1$ except at most one are less than $2n$.Indeed, if $p, q$ are 2 different prime divisior of $f(n)$ greater than $2n$ then $f(n) \ge(2n) ^2$.Contradiction. Now as for all prime divisior less than $2n$ of $f(n)$, $-\frac{1}{3}$ is a quadratic residue of $p$ so,we get an integer $a<\frac{p-1}{2}<n$ such that $a^2\equiv -\frac{1}{3} \pmod {p}$.So for this $a$ we have $p|3a^2+1$. So each $f(k)$ has at most one prime divisior which are not prime divisior of $f(i)$ for some $i<k$. ${\blacksquare}$

Call a prime $p$ $n$-pristine if it divides $f(n)$, but not $f(1), f(2), \dots f(n-1)$. The key claim is that $p \geq 2n$ for all $n$-pristine primes. This follows immediately from the fact that $p$ divides $f(p-n)$, so $p-n \geq n$. Now suppose that $f(n)$ has two $n$-pristine prime divisors $p$ and $q$. Then \[ 3n^2 + 1 = f(n) \geq pq > 4n^2, \]which is clearly ridiculous. The conclusion follows immediately by induction.

A truely excellent problem, with a clear and crisp statement. This also would have been a good IMO problem #1 or #4. A slightly harder version would have been: Slightly harder version wrote: Let $f(x) = 3x^2 + 1$. Prove that for any integer $n\ge4$, the product $$f(1)\cdot f(2)\cdot\dots\cdot f(n)$$has at most $n-1$ distinct prime divisors.

MarkBcc168 wrote: Let $f(x) = 3x^2 + 1$. Prove that for any given positive integer $n$, the product $$f(1)\cdot f(2)\cdot\dots\cdot f(n)$$has at most $n$ distinct prime divisors. Proposed by Géza Kós Let us say that given a prime $p$, $\exists$ a unique natural number $k$ between $1$ and $n$, both inclusive such that $p \mid f(k)$. So for all naturals between $l$ betweenv$1$ and $n$, $f(k) - f(l) = 3(k-l)(k+l) \not\equiv 0 \pmod{p}$. Now if $0 < p \leq k$, just choose $l = p - k$ and you'll get a contradiction, and if $k < p < 2k$, just choose $l = 2p-k$. Hence, $p > 2k$. So, $p > 2k \mid 3k+1 \implies$ there can be only $1$ such $p$ that can divide $f(k)$ or if there exists two such primes $p, q$, then $pq > 4k^2$ and $pq \mid f(k) < 4k^2$, contradiction. So each $f(n)$ contribute at most $1$ such $p$ which finishes our problem. @above Our bound can be easily changed to $n - \epsilon$ for sufficiently large $n$ instead of $4$ and $f(k) = \left \lfloor (4-\epsilon)k^2 + 1 \right \rfloor$ would also do for $\epsilon \geq 0$ (not sure about the equality) @above version works because $f(1) = 4, f(3) = 28$ and $f(4)=49$ contribute only $2$ prime factors

By QR, if $p|3k^2+1$, $p=2$ or $6t+1$ case 1: $3k^2+1$ is composite: $\leq \sqrt{3n^2+1}/6+1$ possible primes case 2: $3k^2+1$ is prime: $k$ even so $\leq n/2$ primes

Cute problem. We'll prove that each $f(n)$ will contribute at most $1$ prime divisor $p$ such that $p \mid f(n)$ but $p \nmid f(i)$ for all $i < n$. Call such prime primitive. Suppose otherwise, that $f(n)$ has 2 primitive prime $p$ and $q$. Claim 01. We have the bound $p > 2n$. Proof. If $n > p$, then $p \mid 3(n - p)^2 + 1$, hence $p$ is not the primitive divisor of $f(n)$. If $\frac{p}{2} < n < p$, then $p \mid 3(p - n)^2 + 1$, and $p - n < \frac{p}{2} < n$, which forces $p$ not being the primitive divisor of $f(n)$. Now, if $f(n)$ has $2$ primitive primes, we must have $pq \mid 3n^2 + 1$. However, by our bound, we have \[ 4n^2 < pq \le 3n^2 + 1 \]forcing a contradiction.

I will prove the claim that if $f(1)f(2)\ldots f(n-1)$ has $k$ prime divisors, then $f(1)f(2)\ldots f(n)$ has at most $k+1$ prime divisors, which finishes as $f(1)=4$ has one prime divisor. Let $p$ be a prime dividing $f(n)$ but none of $f(1),\ldots,f(n-1)$. The key claim is that $p \geq 2n$. To prove this, we will bound $n$ in terms of $p$. First note that if $n>p$, then $f(n-p)\equiv f(n) \equiv 0 \pmod{p}$, so $p$ divides $f(n-p)$. Thus we require $n<p$, as $n=p$ clearly fails. Further, if $p>n>\tfrac{p}{2}$, then $f(p-n)\equiv 3n^2+1\equiv f(n) \pmod{p}$, and since $0<p-n<n$, $p$ divides one of $f(1),\ldots,f(n-1)$. This is enough to force $n \leq \tfrac{p}{2} \implies p \geq 2n$ as desired. To finish, suppose that there exist two distinct primes $p,q$ which divide $f(n)$ but none of $f(1),\ldots,f(n-1)$. Since $p,q \geq 2n$, we have $$pq \geq 2n(2n+1)=4n^2+2n>4n^2+1>3n^2+1=f(n),$$which is absurd, so there is at most one prime $p$ dividing $f(n)$ but none of $f(1),\ldots,f(n)$ as desired. $\blacksquare$

Define $g(n)=f(1) \cdot f(2) \dots \cdot f(n)$. Say it has $k$ distinct prime divisors. I claim that $g(n+1)$ has no more than $k+1$ prime divisors, which finishes since $g(1)$ has only one prime divisor (intuitively, one could think of it as saying that $f(n+1)$ can bring in a maximum of one "new" prime divisor.) Assume that $p \mid 3(n+1)^2+1$ but $p$ does not divide $3k^2+1 \forall k$ satisfying $n \geq k \geq 1$. This means that $p \nmid 3(n+1+k)(n+1-k)$ or that $p \nmid (n+1+k), p \nmid (n+1-k)$ for all natural $k$ less than $n+1$. It follows that $p$ cannot be any of $1,2, \dots,n,n+2, \dots, 2n+1$. However if it is $n+1$ then we have $p \mid 3p^2+1$, contradiction. In conclusion $p \geq 2n+2$, and if we can find two such primes, $3(n+1)^2+1 \geq (2n+2)^2$ which fails for all $n$

We can compute $f(1)=4=2^2$. Suppose that for some $m\ge 2$, $f(m)$ has two distinct prime factors $p,q$ that aren't factors of $\prod\limits_{i=1}^{m-1}f(i)$. This means that $3m^2\equiv -1\pmod{pq}$ by CRT, so $m^2>\frac{pq}{3}-1>\frac{p^2}{4}$ as $p\ge 5$ implies $\frac{p^2}{12}>1$. Hence, $m>\frac{p}{2}$ and $f(p-m)$ (for obvious reasons $m<p$) is also a multiple of $p$.

We proceed by induction on $n$, base cases $n=1,2$ being obvious. Suppose it was true for all $n<k$, where $k>2$. We will show that $f(k)$ has at most one distinct prime divisor that doesn't divide \[f(1)\cdot f(2)\cdot \cdots \cdot f(k-1)\]Suppose not, and we had two primes $p<q$ satisfying this. Notice that $p< \sqrt{3k^2 + 1}\le 2k$. Clearly $k\ne p$ because $k\nmid 3k^2 + 1$. If $k>p$, then $p$ divides $f(k-p)$ and if $k<p$, then $p$ divides $f(p-k)$, contradiction. Thus, \[f(1)\cdot f(2)\cdot \cdots \cdot f(k)\]has at most $(k-1) + 1 = k$ distinct prime divisors.

Let $S_k$ denote the number of distinct primes in the prime factorization of $f(1)f(2)\dots{}f(k)$. We will now prove that $|S_{k+1}|-|S_k|$ is at most $1$. FTSOC, assume that the set $E=S_{n}-S_{n-1}$ for some integer $n$ has at least two odd primes (We don't have to consider $2$ since $2$ will be in $S_{n-1}$ no matter the $n$ since $f(1)=4$). Let two of these primes be $p_1$ and $p_2$ for $p_1\ne{}p_2$. Notice that we have $p_1$, $p_2>n$, because if we have that $p_1\mid{}3n^2+1$ with $p_1<n$, we would also have that $p_1\mid{}3(n-p_1)^2+1$, which would mean that $p_1$ is not in $E$ (also, notice that $p_1$ is obviously not $n$). We can use this proof similarly for $p_2$. Therefore, we have that $cp_1p_2=3n^2+1$ for some integer $c$. From the above observation, we only have two cases, where $c=1$ and $c=2$. Taking modulo $4$, since $p_1$ and $p_2$ are odd, we find that the latter case is impossible, we consider the former case. Notice that one of $p_1$ or $p_2$ must be less than $2n$, since $3n^2+1\geq{}4n^2$. WLOG, let the smaller prime be $p_1$. Notice that $0<p_1-n<n$, implying that $p_1\mid{}3(p_1-n)^2+1$, which would mean that $p_1$ is not in $E$, a contradiction! Therefore $f(1)f(2)\dots{}f(n)$ always has at most $n$ distinct prime factors, and we are done.

Cute little problem. Assume ftsoc that for any $a$, $f(a)$ has two prime factors $p$ and $q$ such that $p,q\nmid f(b)$ for any $1\le b\le a-1$. Then \[p,q\nmid f(a)-f(b)=3(a+b)(a-b)\]so $p,q\nmid a+b$ and $p,q\nmid a-b$. Thus $p,q\nmid 1,2,\ldots,a-1,a+1,\ldots,2a-1$. As $\gcd(3a^2+1,a)=1$, $p,q\nmid a$ as well. Thus, $p,q\ge 2a$. And thus $f(a)=3a^2+1\ge pq\ge 4a^2$, which is impossible for $a\ge 1$. Thus for $a\ge 1$, $f(a)$ can gain at most one new prime factor that is not yet among $f(1),\ldots,f(a-1)$. As $f(1)=2^2$ has only one prime factor, the product $f(1)\ldots f(n)$ can have at most $n$ distinct prime factors, as desired.

Pretty straightforward if you think about the problem inductively; regardless it's quite nice. We show that for any positive integer $n$, there exists at most one prime $p \mid f(n)$ such that $p \nmid f(k)$ for any $k \leq n$. Claim. Any such prime divisor $p$ satisfies $p > 2n$. Proof. Fix a prime $p$. Then, note that the smallest $k$ such that $p \mid 3k^2 + 1$ satisfies $k \leq \frac{p-1}2$. Hence if $p \leq 2n$, then $k = \frac{p-1}2 < n$ and thus $p \mid f(k)$ for this $k$, contradiction. $\blacksquare$ Thus, if there existed two primes $p, q$ for this $n$, then $f(n) = pq > 4n^2$, which is an obvious contradiction.

We'll only need to prove that there exists at most one prime such that $p \mid f(n)$ and $p \nmid f(k)$ for all $1 \le k < n$. (Then induction kills it) Assume the contrary, there exists two such primes, namely $p$ and $q$. Obviously we have $p > n$. Note that $p \mid f(p - n)$, thus we have $p - n > n$, which means $2n + 1 \le p$. Similarly we get $2n + 1 \le q$. But $(2n+1)^2 \le pq \le f(n) = 3n^2 + 1$, a contradiction. $\blacksquare$

If we can prove that there do not exist distinct primes $p,q$ such that $p,q \mid f(n)$ and $p,q \nmid f(k)$ for any $1\le k\le n$ for $n>1$ then we finish by induction (base case $n=1$ is easy). If $p<n$ we see $f(n-p)\equiv f(n)\equiv 0\pmod p,$ if $p=n$ we have $p\nmid f(p)$ and if $n<p<2n$ we have $f(p-n)\equiv f(n)\equiv 0\pmod p$ and $p-n<n,$ so $p\ge 2n$ and similarly for $q$ so $f(n)\ge pq\ge 4n^2>3n^2+1,$ contradiction.

We claim that for any $n$, there is at most one new prime factor which divides $f(n)$ but not $f(1),f(2),\ldots, f(n-1)$. This claim finishes the problem. Suppose for contradiction there are two primes or more, say $p,q$. WLOG let $p<q$. Note, $pq\leq f(n)$, but $pq>p^2$ which means $p<\sqrt{3n^2+1}$. Now, note that $4n^2\geq3n^2+1$, which forces $p<2n$. So, there exists some $r$ (not necessarily positive) with $|r|<n$, such that $n\equiv r\pmod{p}$. Note that $n^2\equiv r^2\pmod{p}$, which means $f(|r|)\equiv f(n)\pmod{p}$. But this is a contradiction as $1\leq |r|<n$.

We induct. Suppose FTSOC for $n\geq 2$ that there are two primes $p$ and $q$ that divide $3n^2+1$ but do not divide $3k^2+1$ for any $k<n$. Note that since $3n^2\equiv -1\pmod{p}$ is even, if there is a solution at all, the smallest one must be at most $p/2$. Thus, $p,q\geq 2n$, so $pq\geq 4n^2>3n^2+1$, contradiction. Remark: Really the only idea here is that once you write a lot of examples you realize that "new" prime factors are going to be large which prevents $n$ from contributing much else, since small prime factors should have shown up already, and this just solves by showing that having two "new" primes is already larger than $3n^2+1$.

Nice Clearly, it is true for $n = 1$, so say $f(1) \cdot f(2) \cdots f(k - 1)$ has $\leq k - 1$ n distinct prime divisors. SFTSOC, $f(k)$ introduces $2$ new prime divisors $p_1, p_2$ such that $p_1, p_2 \nmid f(1), f(2), \dots f(n)$. Firstly, notice that that if $p_1, p_2 < n$, then we have $f(n - p_1) \equiv 0\mod{p_1}$, which is clearly amongst $f(1), f(2), \dots, f(n)$. Repeating this for $p_2$ yields the same, which means that $p_1, p_2$ must be greater than $n$. (any prime being $= n$ is impossible as $n \nmid 3n^2 + 1$.) Now, if $n < p_1, p_2 < 2n$, then we have $f(p_1 - n) \equiv 0\mod{p_1}$, similarly for $p_2$, which again is amongst $f(1), f(2), \dots f(n)$, impossible. This means that both $p_1, p_2 \geq 2n$, impossible as $p_1 \cdot p_2 > 4n^2 > 3n^2 + 1$. So $f(n)$ introduces at most $1$ new prime factor, so we are done.

Cyber 2020 We have that for any integer $n$, there exist a $p$ prime st $p|f(n)$ but $p$ doesn't divide $f(m)$ for $m \leq n$. We show that such $p$ has the property $p>2n$. the rest is easy.

Please contact westskigamer@gmail.com if there is an error with my solution for cash bounties by 3/18/2025.