typedef unsigned int uint32;
typedef unsigned long long uint64;

#define UINT64USE
//#define UINT128USE

const uint32 N = 1000; // max number is ~7131 for 64 bit values ( 18 446 744 073 709 551 616 )

#include <chrono>
#include <string>
#include <vector>
#include <iostream>
#include <stdlib.h>

typedef unsigned long long mainType;

typedef std::chrono::high_resolution_clock high_resolution_clock;
typedef std::chrono::milliseconds milliseconds;

// Array of powers
mainType powers[N];

mainType p5(mainType x)
{
	return x * x * x * x * x;
}

milliseconds duration_cast_ms(high_resolution_clock::time_point minus)
{
	return std::chrono::duration_cast<milliseconds>(high_resolution_clock::now() - minus);
}

void clearLine()
{
	for (int i = 0; i < 77; ++i)
	{
		std::cout << " ";
	}
	std::cout << "\r";
}

int main()
{
	high_resolution_clock::time_point _start = high_resolution_clock::now();
	milliseconds speedTime;
	std::vector<uint32> foundItems;
	std::cout << "Building table of powers 1 - " << N << "^5\n";
	uint32 mpow = 0;

	for (uint32 i = 1; i < N; ++i)
	{
		powers[i] = p5(i);
	}

	speedTime = duration_cast_ms( _start );
	std::cout << "Table ready. Building time: " << ((double)speedTime.count() / 1000 ) << "s, starting search...\n\n";

	uint64 counter = 1, speed = 0, hitsspeed = 0;
	uint32 foundVal = 0, nextIndex = 0;
	mainType sum = 0U, baseSum = 0U;

	uint32 lastRangeIndex = 5;

	uint32 ix0 = 0x01;
	uint32 ix1 = 0x01;
	uint32 ix2 = 0x01;
	uint32 ix3 = 0x01;
	uint32 fVal;

	for (ix0 = 1; ix0 < N; ++ix0)
	{
		for (ix1 = 1; ix1 < ix0; ++ix1)
		{
			for (ix2 = 1; ix2 < ix1; ++ix2)
			{
				baseSum = powers[ix2] + powers[ix1] + powers[ix0];
				while (lastRangeIndex > 0 && powers[lastRangeIndex] > baseSum)
				{
					--lastRangeIndex;
				};
				for (ix3 = 1; ix3 < ix2; ++ix3)
				{
					fVal = (ix3 + ix2 + ix1 + ix0 - lastRangeIndex) % 30;
					if ( fVal )
					{
						ix3 += 30 - fVal;
					}
					if (ix3 >= ix2)
					{
						break;
					}
					sum = baseSum + powers[ix3];

					/* 128 only
					nextIndex = sum.GetL();
					if (((nextIndex & 0xF) > 0) && ((nextIndex & 0x1) == 0))
					{
						// filter odd values
						continue;
					}
					*/

					while (lastRangeIndex < (N - 1) && powers[lastRangeIndex] < sum)
					{
						++lastRangeIndex;
					};
					if (lastRangeIndex == (N - 1))
					{
						break;
					}
					foundVal = sum == powers[lastRangeIndex] ? lastRangeIndex : 0;
					if (foundVal > 0)
					{
						// clear line
						clearLine();
						for (auto ind : foundItems)
						{
							if ((foundVal % ind) == 0)
							{
								// duplicate
								//foundVal = 0;
								break;
							}
						}
						if (foundVal != 0)
						{
							std::cout << "found: ";
							std::cout << ix0 << "^5 ";
							std::cout << ix1 << "^5 ";
							std::cout << ix2 << "^5 ";
							std::cout << ix3 << "^5 ";
							speedTime = duration_cast_ms(_start);
							// it/ms: iterations per millisecond, it: total iterations, spd:
							std::cout << "it/ms: " << (counter / (uint64)speedTime.count()) << " it: " << counter << "\n";
						}
						else
						{
							std::cout << "duplicate";
						}
					}
					else
					{
						if (( 30 + ix3) >= ix2)
						{
							break;
						}
					}
					// displaying some progress
					counter++;
					if ((counter & 0xFFFFFFF) == 0)
					{
						clearLine();
						std::cout << ix0 << "^5 ";
						std::cout << ix1 << "^5 ";
						std::cout << ix2 << "^5 ";
						std::cout << ix3 << "^5 ";

						speedTime = duration_cast_ms(_start);
						// it/ms: iterations per millisecond, it: total iterations, spd:
						std::cout << "it/ms: " << (counter / (uint64)speedTime.count()) << " it: " << counter << "\r";
					}
				}
			}
		}
	}

	clearLine();

	milliseconds time = duration_cast_ms(_start);
	std::cout << "\nDone in: " << ( double(time.count()) / 1000 ) << "s\n" << "Total iterations: " << counter << "\n";
	speed = counter / (uint64)time.count();
	std::cout << "cnt/ms: " << speed << " itr/ms \n";


	getchar();
	return 0;
}