Largest Prime

Consider the sequence $n^2+3$ with $n \ge 1$.
If we write down the first terms of this sequence we get:
$4, 7, 12, 19, 28, 39, 52, 67, 84, 103, 124, 147, 172, 199, 228, 259, 292, 327, 364, \dots$ .
We see that the terms for $n=6$ and $n=7$ ($39$ and $52$) are both divisible by $13$.
In fact $13$ is the largest prime dividing any two successive terms of this sequence.

Let $P(k)$ be the largest prime that divides any two successive terms of the sequence $n^2+k^2$.

Find the last $18$ digits of $\displaystyle \sum_{k=1}^{10\,000\,000} P(k)$.

This question is related to the properties of quadratic sequences and a concept known as Quadratic Residue, which falls under number theory in math.

The answer to this problem requires some advanced knowledge of Quadratic residues and a computer program to execute the calculations. Here’s a detailed explanation.

1. We first need to realize that if a prime number p divides n^2+k^2 and (n+1)^2+k^2, it must also divide their difference 2n+1.

2. Thus, the largest possible prime to divide numbers in the sequence n^2+k^2 must be smaller than 2k+1 because the difference 2n+1 will not exceed 2k+1 for n=1.

3. Another prime property should be applied here. If p divides n^2+k^2 for some n, (where p is a prime), Then according to the law of Quadratic Residue, k is a Quadratic Residue modulo p. The property suggests that for any prime p, there exists a finite set of quadratic residues.

4. Based on this property, if a prime number p divides n^2+k^2, then k must be in the finite set of quadratic residues of p.

5. Looking for the largest prime p that has k as a Quadratic Residue If we assume that this largest prime is less than 2k+1, we can consider a descending order from 2k, checking whether k is a Quadratic Residue modulo p. If we find one, this is P(k).

6. Calculating this for a large range (to 10 million) is time-consuming even with computers. We can optimize it by making use of the fact that Quadratic Residues repeat when n is a multiple of p-1 (which is Fermat’s little theorem). Therefore, we don’t need to compute Quadratic Residues for each number up to 2k+1, but only for numbers up to 2k+1 mod (p-1).

7. The last 18 digits of the sum can be maintained during the computation because we only care integers modulo 10^18.

This can be implemented as a program using an efficient language like Python, C++ etc. This type of task is beyond standard handwritten calculations due to its complexity and scale. A computer algorithm is the most appropriate way to find an exact numerical solution.

More Answers: