TopCoder Statistics - Problem Statement

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
1

0

Returns: 0
280

2333

Returns: 11
2500

802

Returns: 6315
2310

466

Returns: 6659
1245

1085

Returns: 1122
2288

1619

Returns: 3684
1059

1932

Returns: 517
32

697

Returns: 0
1873

1290

Returns: 2751
433

1417

Returns: 69
705

2160

Returns: 154
2117

973

Returns: 4164
2064

1367

Returns: 3349
749

135

Returns: 1010
2474

1371

Returns: 4993
1842

2492

Returns: 1661
2285

2355

Returns: 2725
2050

1486

Returns: 3023
2260

2212

Returns: 2912
2049

929

Returns: 3993
2414

2274

Returns: 3397
2180

256

Returns: 6524
1699

91

Returns: 5029
2473

2285

Returns: 3645
2416

1035

Returns: 5443
2129

2472

Returns: 2276
884

753

Returns: 728
362

1924

Returns: 30
2111

1929

Returns: 2750
2381

451

Returns: 7293
2122

144

Returns: 7217
2500

15

Returns: 10713
2500

2500

Returns: 3380
2262

1583

Returns: 3777
1182

995

Returns: 1030
306

1818

Returns: 10
2183

1811

Returns: 3145
1887

813

Returns: 3592
2191

1447

Returns: 3636
2500

3

Returns: 11191
2450

978

Returns: 5741
2000

1080

Returns: 3486
2472

1071

Returns: 5448
2290

1751

Returns: 3528
2307

1400

Returns: 4147
2200

167

Returns: 7497
2267

2105

Returns: 3047
2194

1988

Returns: 2849
2407

1714

Returns: 4031
2490

991

Returns: 5965
2395

1706

Returns: 4033
2247

1278

Returns: 4133
2500

89

Returns: 10473
2337

96

Returns: 9016
2321

848

Returns: 5287
2182

2181

Returns: 2724
2500

0

Returns: 0
2289

164

Returns: 8110
262

403

Returns: 57
2004

1292

Returns: 3160
2133

2127

Returns: 2710
2017

2297

Returns: 2144
2220

2267

Returns: 2754
2345

1172

Returns: 4808
2370

2239

Returns: 3246
2309

1446

Returns: 4164
2409

904

Returns: 5827
2500

4

Returns: 10813
1

1947

Returns: 0
2490

419

Returns: 7859
2500

13

Returns: 10633
2296

1571

Returns: 3751
1121

339

Returns: 1735
153

1088

Returns: 6
2232

2337

Returns: 2651
2175

1054

Returns: 4329
976

1784

Returns: 450
2482

1972

Returns: 3957
1048

2239

Returns: 395
2499

2499

Returns: 3509
2500

1250

Returns: 5327
2499

3

Returns: 11182
2500

1325

Returns: 4974

Statistics

Problem Statement for "Diophantine"

Problem Statement

Definition

Notes

Constraints

Examples