Diophantine | Topcoder Archive

Problem Statement

This problem has a nonstandard time limit: 7 seconds.

Let p[] be the sequence of all primes in increasing order: p[0]=2, p[1]=3, p[2]=5, and so on.

Let D be a positive integer constant. For each i >= 0, let q[i] = p[i] * p[i+D].

Consider the following equation: V + W + X + Y = Z.

You are given ints N and D. Count the number of solutions to this equation such that V <= W <= X <= Y and all numbers V,W,X,Y,Z are in the set Q_N = { q[0], q[1], ..., q[N-1] }.

Definition

Class:: Diophantine
Method:: countSolutions
Parameters:: int, int
Returns:: long
Method signature:: long countSolutions(int N, int D)
(be sure your method is public)

Notes

A positive integer is a prime if it has exactly two positive integer divisors. Note that 1 is not a prime.

Constraints

N will be between 1 and 2,500, inclusive.
D will be between 0 and 2,500, inclusive.

Examples

```
15
```
```
1
```
```
Returns: 2
```
The two solutions are: 6 + 15 + 323 + 323 = 667 6 + 143 + 221 + 1147 = 1517 Note that the first solution uses the value 323 twice.
```
2470
```
```
0
```
```
Returns: 0
```
No solutions at all.
```
30
```
```
500
```
```
Returns: 1
```
One solution. In it, the right-hand side of the equation is 406,279.
```
47
```
```
7
```
```
Returns: 14
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.