// ////////////////////////////////////////////////////////
// # Title
// Prime permutations
//
// # URL
// https://projecteuler.net/problem=49
// http://euler.stephan-brumme.com/49/
//
// # Problem
// 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?
//
// # Solved by
// Stephan Brumme
// February 2017
//
// # Algorithm
// My function ''fingerprint'' counts how often each digit occurs and produces an integer (which may have up to 10 digits).
// The n-th decimal digit of the result represents how often the digit n occurs in the input, e.g.
// ''fingerprint(454430) = 131001''
// because ''5'' appears once, ''4'' three times, ''3'' once, no ''2'', no ''1'' and a single zero.
// ''fingerprint'' has the nice property that two number with the same fingerprint are a permutation of each other.
//
// After generating all ''primes'', their ''fingerprints'' are stored.
//
// All permutations of a prime number, which are prime themselves, will be added to a list of ''candidates''.
// There must be at least ''sequenceLength'' (it's ''3'' in the original problem) candidates.
//
// However, some candidates may not have the proper distance to each other: that's why I compute the ''differences'' of each candidate prime to each other.
// Only if at least ''sequenceLength'' primes share the same distance to at least one other prime, then we may have a result.
// Unfortunately, pairs may have the same distance `diff = |p_a - p_b| = |p_c - p_d|` but are disjunct: `diff != |p_a - p_c|`.
// For example, the primes 3, 5, 17, 19 have a pair-wise distance of 2 (3-5 and 17-19) but there is no way to connect 3 and 5 to 17 and 19.
// Therefore the program tries to start at every candidate prime `p_i` and looks for the longest sequence `p_i + diff, p_i + 2 * diff, p_i + 3 * diff, ...`
// where each element `p_i + k * diff` is part of the candidates.
//
// If such a sequence was found, the program repeats the same process but connects all elements to a long string.
// All strings are stored in an ''std::set'' which is automatically ordered.
//
// # Hackerrank
// Substantial parts of my code are due to Hackerrank's modifications: the ''sequenceLength'' may be 3 or 4 and a user-defined upper ''limit'' exists.
// Default values for the original problem would be ''10000'' and ''3''.
#include
#include