Largest Integer Divisible by Two Primes

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)$.

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:
s += primeList[i]*primeList[j]*(N//(primeList[i]*primeList[j]))
return s


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 Game
Matrix Sum
Strong Repunits

Error 403 The request cannot be completed because you have exceeded your quota. : quotaExceeded


Recent Posts

Don't Miss Out! Sign Up Now!

Sign up now to get started for free!