This one took way longer than expected. I initially misunderstood the question to require 4-digit numbers unique digits (because that's what the example has!) and I went crazy trying to figure out why the only answer I was getting was the example in the question. Anyway I later realized I'd over-complicated my solution and I just needed to look at numbers between 1000 and 9999. Given this, it's absurd to have a class called "FourDigits" (duh), but I figured there's no point hiding my initial mistake :)
The code fragment below is bloated because I've left in old code from my first attempt (the functions suffixed with ...Old), and half the code here is dead code.
Statutory Warning: Spoilers Ahead (well, not really)
bool IsPrime(int n) {
// Rule out even numbers
if ((n > 2) && (n % 2 == 0)) return false;
// Check divisibility by odd numbers starting from 3, uptil the
// square root of the number.
const int lim = sqrt(n);
for (int i = 3; i <= lim; i+=2) {
if (n % i == 0) {
return false;
}
}
return true;
}
bool HasArithmeticSequence(const vector<int>& v) {
assert(v.size() >= 3);
// Assumes sorted vector of ints
struct diff {
int n1, n2, d;
};
vector<diff> diffs;
// Get the diffs between all elements, then find two pairs with the
// same diff (yes, N^2, but will do). The two pairs must share a
// number, i.e. V_i + d = V_j, and V_j + d = V_k.
for (int i = 0; i < v.size() - 1; ++i) {
for (int j = i+1; j < v.size(); ++j) {
assert(v[j] > v[i]);
diffs.push_back( { v[i], v[j], v[j] - v[i] } );
}
}
std::sort(diffs.begin(), diffs.end(),
[](const diff& df1, const diff& df2) {
return df1.d < df2.d;
});
// Now that we have grouped elements by their difference, we can
// analyze each 'cluster' to find the pairs we want.
for (int i = 0; i < diffs.size() - 1; ++i) {
// Yes, it's inefficient, but ...
int d = diffs[i].d;
for (int j = i + 1; diffs[j].d == d; ++j) {
if (diffs[i].n2 == diffs[j].n1) {
cout << "Found arithmetic progression: "
<< diffs[i].n1 << " -> "
<< diffs[i].n2 << " -> "
<< diffs[j].n2 << endl;
return true;
}
}
}
return false;
}
class FourDigitCombinator {
public:
FourDigitCombinator() : digits_({0,1,2,3}), number_(1000) {}
string GetDigitsOld() {
std::ostringstream stream;
for (int i = 0; i < kNumDigits; ++i) {
stream << digits_[i];
}
return stream.str();
}
bool NextOld() {
sanity_check();
// See if there is a prior number that can be incremented
for (int i = kNumDigits - 1; i >= 0; --i) {
// The last digit can go up to kMaxDigit, the previous one up to
// kMaxDigit - 1, and so on ...
const int digitMax = kMaxDigit - kNumDigits + i + 1;
int digitValue = digits_[i];
assert(digitValue <= digitMax);
if (digitValue == digitMax) {
// We've hit the limit for this digit. If this is the first
// digit, we've reached the end.
if (i == 0) {
return false;
}
// Otherwise, fall through to the previous digit ...
} else {
// Increment, and reset subsequent digits, if any.
for (int j = i; j < kNumDigits; ++j) {
++digitValue;
digits_[j] = digitValue;
}
return true;
}
}
assert(false); // We should not get here!
}
bool HasPrimePermutationsOld() {
array<int, kNumDigits> mutation = digits_;
vector<int> prime_mutations;
do {
// Skip permutations with a leading zero.
if (mutation[0] == 0) continue;
// Create the corresponding number
int number = 0;
for (int i = 0; i < kNumDigits; ++i) {
number = number * 10 + mutation[i];
}
if (IsPrime(number)) {
prime_mutations.push_back(number);
}
} while (std::next_permutation(mutation.begin(), mutation.end()));
if ((prime_mutations.size() >= 3) && HasArithmeticSequence(prime_mutations)) {
return true;
}
return false;
}
string GetDigits() {
std::ostringstream stream;
stream << number_;
return stream.str();
}
bool Next() {
if (number_ < 9999) {
++number_;
return true;
}
return false;
}
bool HasPrimePermutations() {
array<int, kNumDigits> mutation;
assert(number_ >= 1000 && number_ <= 9999);
// Convert number into an array of digits ...
int n = number_;
int digit_index = kNumDigits - 1;
while (n > 0) {
mutation[digit_index--] = n % 10;
n /= 10;
}
vector<int> prime_mutations;
do {
// ... then convert the array of digits back into a number!
int num = 0;
for (int i = 0; i < kNumDigits; ++i) {
num = num * 10 + mutation[i];
}
assert(num >= 1000 && num <= 9999);
if (IsPrime(num)) {
prime_mutations.push_back(num);
}
} while (std::next_permutation(mutation.begin(), mutation.end()));
if ((prime_mutations.size() >= 3) && HasArithmeticSequence(prime_mutations)) {
return true;
}
return false;
}
private:
static const int kNumDigits = 4;
static const int kMaxDigit = 9;
array<int, kNumDigits> digits_;
int number_;
void sanity_check() {
for (int i = 0; i < kNumDigits - 1; ++i) {
assert(digits_[i] < digits_[i+1]);
}
}
};
int main() {
cout << "Euler #49 ... \n";
set<string> candidates;
// Go over all sets of four digits, and consider the permutations of
// each to see if any group of three permutations is prime.
FourDigitCombinator four_digits;
do {
if (four_digits.HasPrimePermutations()) {
candidates.insert(four_digits.GetDigits());
}
} while (four_digits.Next());
// Debugging aid ... check if any combinations matched.
for (const auto& c : candidates) {
cout << "Debug: found : " << c << endl;
}
}
And it runs as ...
$ time ./Test
Euler #49 ...
Found arithmetic progression: 1487 -> 4817 -> 8147
Found arithmetic progression: 1487 -> 4817 -> 8147
Found arithmetic progression: 2969 -> 6299 -> 9629
Found arithmetic progression: 2969 -> 6299 -> 9629
Debug: found : 1478
Debug: found : 1487
Debug: found : 2699
Debug: found : 2969
real 0m0.019s
user 0m0.016s
sys 0m0.000s