// ////////////////////////////////////////////////////////
// # Title
// Prime connection
//
// # URL
// https://projecteuler.net/problem=425
// http://euler.stephan-brumme.com/425/
//
// # Problem
// Two positive numbers `A` and `B` are said to be connected (denoted by `A \leftrightarrow B`) if one of these conditions holds:
// (1) `A` and `B` have the same length and differ in exactly one digit; for example, `123 \leftrightarrow 173`.
// (2) Adding one digit to the left of `A` (or `B`) makes `B` (or `A`); for example, `23 \leftrightarrow 223` and `123 \leftrightarrow 23`.
//
// We call a prime `P` a 2's relative if there exists a chain of connected primes between 2 and `P` and no prime in the chain exceeds `P`.
//
// For example, 127 is a 2's relative. One of the possible chains is shown below:
// `2 \leftrightarrow 3 \leftrightarrow 13 \leftrightarrow 113 \leftrightarrow 103 \leftrightarrow 107 \leftrightarrow 127`
// However, 11 and 103 are not 2's relatives.
//
// Let `F(N)` be the sum of the primes `<= N` which are not 2's relatives.
// We can verify that `F(10^3) = 431` and `F(10^4) = 78728`.
//
// Find `F(10^7)`.
//
// # Solved by
// Stephan Brumme
// August 2017
//
// # Algorithm
// My solution consists of four parts:
// 1. run a prime sieve (up to `10^7`)
// 2. find which primes are directly connected to each prime
// 3. find the paths between 2 and every prime where the highest number along the path is minimized
// 4. count all number that are either not connected to 2 or where the highest number along the path exceed that prime
//
// Step 1 can be solved easily by copying my standard prime sieve from my [toolbox](/toolbox/).
//
// Step 2 is encapsulated in the ''findEdges'' function. It iterates over all prime numbers and increments each digit until it reaches 9.
// There is no need to decrement a digit because those were already processes in previous iterations.
// For example, 103 is connected to 113. When processed 103, it will encounter 113 and add that connection ''103 ==> 113'' as well ''113 ==> 103'' in ''connected''.
// Then 113 only has to look at 123, 133, 143, ... (as well as playing around with the first and last digit).
// Prepending a digit is the same as pretending that the current number has a leading zero and treating it like any other digit.
// Note: initially I worked with ''std::string''s instead of my current "numbers only" approach but that was obviously very slow.
//
// Step 3 is performed by ''findLowestPaths'': beginning with 2 I trace the paths to all prime numbers.
// A priority queue is initially filled with 2 only and then all its connected primes are added.
// Each iteration picks the lowest number from the priority queue and adds its connected prime numbers if their path to 2 either
// wasn't observed so far or is optimized in the current iteration.
//
// The final step adds those numbers that don't exist in ''best'' or where ''best[x] > x'', that means the best path to 2 contains a higher number.
#include
#include
#include
#include
#include
#include
// ---------- standard prime sieve from my toolbox
// odd prime numbers are marked as "true" in a bitvector
std::vector sieve;
// return true, if x is a prime number
bool isPrime(unsigned int x)
{
// handle even numbers
if ((x & 1) == 0)
return x == 2;
// lookup for odd numbers
return sieve[x >> 1];
}
// find all prime numbers from 2 to size
void fillSieve(unsigned int size)
{
// store only odd numbers
const unsigned int half = size >> 1;
// allocate memory
sieve.resize(half, true);
// 1 is not a prime number
sieve[0] = false;
// process all relevant prime factors
for (unsigned int i = 1; 2 * i*i < half; i++)
// do we have a prime factor ?
if (sieve[i])
{
// mark all its multiples as false
unsigned int current = 3 * i + 1;
while (current < half)
{
sieve[current] = false;
current += 2 * i + 1;
}
}
}
// ---------- problem specific code ----------
typedef std::unordered_map> Edges;
// create graph
Edges findEdges(unsigned int limit)
{
Edges connected;
// pre-allocate some memory
connected.reserve(limit / 10);
for (unsigned int i = 2; i < limit; i++)
{
if (!isPrime(i))
continue;
const unsigned int MaxPos = 7;
// split i into its digits but keep their ten's exponents
// e.g. 1234 => split = { 4, 30, 200, 1000, 0, 0, 0 };
unsigned int split[MaxPos] = { 0,0,0,0,0,0,0 };
unsigned int shift = 1;
auto reduced = i;
for (unsigned int pos = 0; pos < MaxPos; pos++)
{
shift *= 10;
split[pos] = reduced % shift;
reduced -= reduced % shift;
}
shift = 1;
for (unsigned int pos = 0; shift < 10*i && shift < limit; pos++, shift *= 10)
{
auto current = i;
// analyze all bigger numbers
for (unsigned int digit = split[pos] + shift; digit <= 9 * shift; digit += shift)
{
current += shift;
if (isPrime(current))
{
// add if not existing (A => B)
if (std::find(connected[i].begin(), connected[i].end(), current) == connected[i].end())
connected[i].push_back(current);
// add if not existing (B => A)
if (std::find(connected[current].begin(), connected[current].end(), i) == connected[current].end())
{
// pre-allocate some memory
connected[current].reserve(8);
connected[current].push_back(i);
}
}
}
}
}
return connected;
}
typedef std::unordered_map Best;
// return the minimized highest number between 2 and every prime
Best findLowestPaths(const Edges& connected)
{
// best[x] is the lowest number on the path between 2 and x
Best best;
std::priority_queue, std::greater > todo;
todo.push(2);
while (!todo.empty())
{
auto current = todo.top();
todo.pop();
// highest number so far
auto top = best[current];
// include current number, too
if (top < current)
top = current;
auto connections = connected.find(current);
if (connections == connected.end())
continue;
for (auto edge : connections->second)
{
auto high = best[edge];
// no path or a worse path ?
if (high == 0 || top < high)
{
// update with best value so far
best[edge] = top;
// re-evaluate
todo.push(edge);
}
}
}
return best;
}
int main()
{
unsigned int limit = 10000000;
std::cin >> limit;
// generate enough primes
fillSieve(limit);
// create graph
auto connected = findEdges(limit);
// find best path from 2 to each prime
auto best = findLowestPaths(connected);
// count primes with a connection to 2
// or a path containing too high numbers
unsigned long long result = 0;
for (unsigned int i = 3; i < limit; i += 2)
if (isPrime(i) && (best[i] == 0 || best[i] > i))
result += i;
// that's it !
std::cout << result << std::endl;
return 0;
}