# Brute-force search for solution to an unsolved mathematical inequality

From this Wikipedia article, the following unsolved problem is presented as a result of Waring's problem: It has been proven that a finite number of k exist, and so far none are known. The follow code is meant to brute-force search for a solution:

#include <boost/multiprecision/cpp_dec_float.hpp>
//#include <cmath>
#include <iostream>

typedef boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1000>> arbFloat;

enum returnID {success = 0, precisionExceeded = 1};

int main(){
arbFloat k;

for(k = 6; pow(3, k) - (pow(2, k) * floor(pow(1.5, k))) <= pow(2, k) - floor(pow(1.5, k)) - 2; ++k);

if(pow(3, k) - (pow(2, k) * floor(pow(1.5, k))) <= pow(2, k) - floor(pow(1.5, k)) - 2){
std::cout << "Solution at k = " << k << ".\n";
return returnID::success;
} else {
std::cout << "Error: Precision exceeded at k = " << k << ".\n";
return returnID::precisionExceeded;
}
}


I am using the Boost multiprecision library cpp_dec_float, which works for large integers and decimals. The data type needs to be able to work with integers, because the solution for k needs to be a positive integer. The data type needs to work with decimals because (3/2)^k (equivalently 1.5^k) returns a decimal.

In the code I have commented out the cmath library, because it appears to be included in boost/multiprecision/cpp_dec_float.

In the for-loop, I use <= to be equivalent to the pseudocode !>.

After the for-loop, I re-check if it is a solution because currently if the precision is exceeded, it breaks the for-loop. The if-else checks if it is has either exceeded precision or is an actual solution.

The precision in this example code is 1000 (line 5), but this is changed manually as I search for larger and larger numbers that may be a solution.

I am trying to squeeze every ounce of speed out of this code, so any optimizations that make it quicker will be of great help!

I am running this code on Ubuntu 16.04, and I compile it using g++ with the -Ofast flag for the highest possible optimization during compilation.

Thanks!

• The wikipedia article says "there can only be a finite number of such k", not that there exist a finite number of k. Therefore I would think that it is likely for no such k to exist at all. Additionally, according to this wikipedia page, it is proven that if k exists, it must be > 471,600,000. So you should start from there instead of 6. – JS1 Feb 26 '17 at 0:34
• You may consider openmp/mpi to parallel the computation. – cqdjyy01234 Feb 26 '17 at 3:01
• @JS1 It is conjectured, but not proven, that no k exist. While I understand that in practical use I would start from k≈471600000, I set k=6 for simplicity, which I thought would result in the best answers regarding my code. – esote Feb 26 '17 at 7:16

Secondly, I would drop the floating point arithmetic altogether. You have integer bases with integer exponents, so use integers. $(\frac{3}{2})^k$ = $\frac{3^k}{2^k}$ and applying floor also results in an integer.