Project Euler task 49

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

-----------------------------------------------------------------

#include < iostream >

#include < conio.h >

#include < string >

#include < vector >

#include < algorithm >

#include < map >

using namespace std;

const int ciMax = 10000;

int iEratArray[ciMax];

vector< int > vNums;

void subset(int nElements, int nSubElements, int nCurrent, int nPrevious, int nNum) {

if (nCurrent >= nSubElements) {

vNums.push_back(nNum);

return;

}

for(int i = nPrevious; i <= nElements; i++)

subset(nElements, nSubElements, nCurrent + 1, i, nNum * 10 + i);

}

vector< unsigned long long int > permutations(vector< unsigned int > _v) {

vector< unsigned long long int > vRes;

unsigned int * piTemp = new unsigned int[_v.size()];

memset(piTemp, 0, sizeof(int) * _v.size());

for (unsigned int k = 0; k < _v.size(); k++)

piTemp[k] = k;

unsigned long long int iDec = 1;

unsigned long long iRes = 0;

for (int k = _v.size() - 1; k >= 0; k--) {

iRes += _v[piTemp[k]] * iDec;

iDec *= 10;

}

while (1) {

int j;

// j

// |

// 0 1 2 3 4 5 6

// Find element, whose value is less than

// the value of the next element (5 < 6).

for (j = _v.size() - 1; j >= 1; j--)

if (piTemp[j] > piTemp[j - 1]) {

j--;

break;

}

// Nothing to process.

if (j < 0)

break;

// find the minimal element that is greater than piTemp[j]

int i = _v.size() - 1;

int iTempValue = -1;

for (int k = _v.size() - 1; k > j; k--)

if (piTemp[k] > piTemp[j] && (iTempValue < 0 || iTempValue > piTemp[k])) {

iTempValue = piTemp[k];

i = k;

}

if (iTempValue == -1)

break;

iTempValue = 0;

// swap (i, j)

int iTemp = piTemp[i];

piTemp[i] = piTemp[j];

piTemp[j] = iTemp;

int iSwaps = 1;

while (iSwaps) {

iSwaps = 0;

for (int k = _v.size() - 2; k > j; k--) {

if (piTemp[k] > piTemp[k + 1]) {

int iTmp = piTemp[k + 1];

piTemp[k + 1] = piTemp[k];

piTemp[k] = iTmp;

iSwaps++;

}

}

}

iDec = 1;

iRes = 0;

for (int k = _v.size() - 1; k >= 0; k--) {

iRes += _v[piTemp[k]] * iDec;

iDec *= 10;

}

vRes.push_back(iRes);

}

delete piTemp;

return vRes;

}

int main() {

int N = 9;

memset(iEratArray, 0, ciMax);

// eratosphene's sieve

iEratArray[0] = 1;

iEratArray[1] = 1;

for (int k = 2; k < ciMax; k++) {

if (iEratArray[k]) // if not prime, continue

continue;

for (int j = 2; k * j < ciMax; j++)

iEratArray[k * j] = 1; // mark as not prime

}

subset(N, 4, 0, 1, 0);

// cycle through subsets

for (int i = 0; i < vNums.size(); i++) {

int iTemp = vNums[i];

vector< unsigned int > vTemp;

while (iTemp) {

vTemp.push_back(iTemp % 10);

iTemp /= 10;

}

// sort the digit set

sort(vTemp.begin(), vTemp.end());

// get permutations for the given digit set

vector< unsigned long long int > vRes = permutations(vTemp);

// define a map

map< unsigned int, unsigned int > mMap;

for (int j = 0; j < vRes.size(); j++) {

if (iEratArray[vRes[j]] == 1)

continue;

for (int k = 0; k < vRes.size(); k++) {

if (iEratArray[vRes[k]] == 1)

continue;

int nDiff = abs(vRes[k] - vRes[j]);

if (mMap.find(nDiff) == mMap.end())

mMap[nDiff] = 1;

else

mMap[nDiff]++;

}

}

for (map< unsigned int, unsigned int >::iterator it = mMap.begin(); it != mMap.end(); it++) {

if (it->first == 0)

continue;

if (it->second <= 2)

continue;

unsigned long long int nAdd = it->first;

// try to find the numbers

for (int j = 0; j < vRes.size(); j++) {

unsigned long long int nTemp = vRes[j] + nAdd;

unsigned long long int nTemp2 = vRes[j] + 2 * nAdd;

if (nTemp2 > 10000)

continue;

if (iEratArray[vRes[j]] || iEratArray[nTemp] || iEratArray[nTemp2])

continue;

bool flag1 = false;

for (int k = 0; k < vRes.size(); k++)

if (nTemp == vRes[k])

flag1 = true;

bool flag2 = false;

for (int k = 0; k < vRes.size(); k++)

if (nTemp2 == vRes[k])

flag2 = true;

if (flag1 && flag2)

cout << vRes[j] << " " << nTemp << " " << nTemp2 << endl;

}

}

mMap.clear();

}

return 0;

}