TopCoder Statistics - Problem Statement

Problem Statement

A non-negative integer n is said to be a sum of two perfect powers if there exist two non-negative integers a and b such that a^m + b^k = n for some positive integers m and k, both greater than 1. Given two non-negative integers lowerBound and upperBound, return the number of integers between lowerBound and upperBound, inclusive, that are sums of two perfect powers.

Definition

Class:: SumsOfPerfectPowers
Method:: howMany
Parameters:: int, int
Returns:: int
Method signature:: int howMany(int lowerBound, int upperBound)
(be sure your method is public)

Constraints

lowerBound will be between 0 and 5000000, inclusive.
upperBound will be between lowerBound and 5000000, inclusive.

Examples

0

1

Returns: 2

0 and 1 are both sums of two perfect powers since 0 = 0 + 0 and 1 = 12 + 02.
5

6

Returns: 1

5 is a sum of two perfect powers since 5 = 22 + 12 while 6 is not.
25

30

Returns: 5

Only 30 is not a sum of two perfect powers.
103

103

Returns: 0

There may be no desired integers in the range.
1

100000

Returns: 33604
0

0

Returns: 1
1

1

Returns: 1
1

1000

Returns: 499
1000

1001

Returns: 2
5000000

5000000

Returns: 1
0

41

Returns: 29
500

1300

Returns: 350
1093

3511

Returns: 1081
1

4999999

Returns: 1272866
1

5000000

Returns: 1272867
0

5000000

Returns: 1272868
69

69

Returns: 0
41

4981533

Returns: 1268478
134

4973500

Returns: 1266539
269

4984276

Returns: 1268998
278

4970642

Returns: 1265775
462

4975536

Returns: 1266833
305

4971855

Returns: 1266033
181

4983173

Returns: 1268778
361

4999509

Returns: 1272538
295

4988058

Returns: 1269874
827

4994564

Returns: 1271166
2667120

3527738

Returns: 211125
1447812

2897593

Returns: 364444
1509740

3873701

Returns: 586521
70088

3803618

Returns: 961553
3545190

4072450

Returns: 127519
226763

2070163

Returns: 487065
3952400

4313097

Returns: 87126
1867681

4809766

Returns: 720422
281184

4357230

Returns: 1031970
1820093

4747784

Returns: 717718
2624342

3835559

Returns: 296334
267522

2962291

Returns: 697094
1490827

2343501

Returns: 215753
3113484

3239106

Returns: 30850
1318964

1396710

Returns: 20028
4123011

4149008

Returns: 6315
2945815

4930466

Returns: 479860
1134330

4554822

Returns: 847735
3475578

4900017

Returns: 343004
1219657

2669365

Returns: 367018
531848

4997073

Returns: 1114349
78519

3380880

Returns: 856218
500261

2875919

Returns: 610244
515113

3994422

Returns: 878572
228245

1422401

Returns: 321461
1478864

1910053

Returns: 110073
1504852

4742856

Returns: 797104
2006872

4899147

Returns: 706193
802207

1391400

Returns: 154490
814108

3232936

Returns: 612453
2050366

2063834

Returns: 3424
1631031

3563653

Returns: 480212
1037805

3165895

Returns: 536356
930067

2916795

Returns: 503818
403573

2289857

Returns: 491462
1306841

4528650

Returns: 796792
1894513

3926061

Returns: 500955
1448325

4596886

Returns: 776673
3138210

3158712

Returns: 4988
489869

2142282

Returns: 430606
2805201

3472427

Returns: 163501
4174086

4568588

Returns: 94859
113146

2716803

Returns: 682403
2151306

4580820

Returns: 594039
100

10000

Returns: 4114
0

4999998

Returns: 1272867
7

4999993

Returns: 1272861
1

500000

Returns: 149070
2

4999992

Returns: 1272864
0

4999999

Returns: 1272867
0

1000

Returns: 500
43097

4872343

Returns: 1227070
0

4

Returns: 4
27

467

Returns: 246
3836417

3965197

Returns: 31136
4000004

4000004

Returns: 1
25

25

Returns: 1
1

27

Returns: 17
0

3333333

Returns: 871442

Statistics

Problem Statement for "SumsOfPerfectPowers"

Problem Statement

Definition

Constraints

Examples