Idea for this puzzle was proposed by Gaurav Kamath aka Moriarty - thanks a lot!
Note that it is really more about efficient data structure and algorithm rather than about math...
Look at the integer
997739719 - it has a funny property - any substring of
3 digits i.e.:
997739719 --------- 997 977 773 739 397 971 719
any of these
719 is a prime!
Such numbers built of chains of primes could be long enough, and they could be built using primes of more than
Of course it is important that prime substrings should be unique - since otherwise we can generate endless integers like
997399739... and so on.
For example let us search for integers built of
5-digit primes. Note that resulting chain could start with leading
zeroes, like this:
00002 is a valid prime number too.
You will be given hashes of several such prime-chain-integers - and your task is to print these integers themselves.
Since we are interested in long enough integers, please ignore any of them with length less than
(leading zeroes included).
We'll use the following simple algorithm to calculate the hash of a long
HASH = 0 for D in digits(NUMBER): HASH = (HASH * 13 + D) % 100000007 return HASH
D are decimal digits picked from the
NUMBER in order "left-to-right". For example the hash of the value
000233...333773 shown above is
Input data contain the amount of numbers to search for.
Next lines contain a single hash value each.
Answer should contain long prime-chain-number (of the length
48 digits or more) corresponding to each hash.
input data: 3 34475206 90962736 39728928 0000233331793979193911399793199139313339119333773 749031379939791939113997931991393133317939371999719 461031379939791939113997931991393133317939371999719
Values here are placed into separate lines since they are just too long to fit a single line! However you should simply separate them with spaces.