SumsOfPerfectPowers | Topcoder Archive

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
```

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.