The largest integer $\le 100$ that is only divisible by both the primes $2$ and $3$ is $96$, as $96=32\times 3=2^5 \times 3$.
For two distinct primes $p$ and $q$ let $M(p,q,N)$ be the largest positive integer $\le N$ only divisible by both $p$ and $q$ and $M(p,q,N)=0$ if such a positive integer does not exist.
E.g. $M(2,3,100)=96$.
$M(3,5,100)=75$ and not $90$ because $90$ is divisible by $2$, $3$ and $5$.
Also $M(2,73,100)=0$ because there does not exist a positive integer $\le 100$ that is divisible by both $2$ and $73$.
Let $S(N)$ be the sum of all distinct $M(p,q,N)$.
$S(100)=2262$.
Find $S(10\,000\,000)$.
This problem is a number theory problem and can be best solved by prime number concepts.
Firstly, note that M(p, q, N) can only exist for distinct prime pairs whose product pq <= N. So, we only need to consider prime pairs up to a maximum value such that pq <= 10000000.
The largest integer ≤ N divisible by p and q (let's call it X) must have the form X = kpq for some integer k. Since X is maximized, k is also maximized. Since k = X/(pq) and X ≤ N, we have k ≤ N/(pq). Since k is an integer, we take the floor of N/(pq). Hence, we have:
X = pq*floor(N/(pq)).
Therefore, to solve for S(10,000,000), we need to iterate over all such possible prime pairs (p,q), compute X for each pair and sum up all the X's. However, this numerical approach may be impractical due to the large number of prime pairs and the compute-intensive task of checking for prime-ness of each possible pair.
To sum up all distinct M(p,q,N), ensure to not double count values for pairs (p,q) and (q,p) as they result in the same value.
For python, pseudo code of the above given approach:
```python
def primes(n):
numbers = set(range(n, 1, -1))
primes = []
while numbers:
p = numbers.pop()
primes.append(p)
numbers.difference_update(set(range(p*2, n+1, p)))
return primes
def S(N):
s = 0
primeList = primes(int(N**0.5)+1)
for i in range(len(primeList)):
for j in range(i+1, len(primeList)):
if primeList[i]*primeList[j] > N:
break
else:
s += primeList[i]*primeList[j]*(N//(primeList[i]*primeList[j]))
return s
print(S(10000000))
“`
In this script, function primes(n) generates all primes less than or equal to n, the function S(N) implements the above given approach to find out all pairs of primes (p, q), computes the largest number divisible by p and q and less than or equal to N for each pair and adds them up.
More Answers:
Silver Dollar GameMatrix Sum
Strong Repunits