🔢

Encoded Digits

Week 25

It's 1944 and you are working for your country's military - you come across some strange machine which seems to be used to generate daily decryption keys for some other cipher

Along with the machine, you find what appears to be a testing sheet - used for operators to enter example strings of digits and ensure their machine generates the same output - the format is [digits : generated key]

Unfortunately, your colleagues haven't been able to figure out how the key is derived from the digits - but perhaps you can?

Hint: you can scroll this textarea - there are a lot of examples! Unfortunately some browsers seem to hide the scrollbar by default...

123 : 2233 1234 : 2233 12345 : 22335 456 : 5 789 : 789 13 : 133 013 : 013133 1 : 11 : 11 111 : 1111 1111 : 111111 11111 : 11111111 222 : 222 333 : 333 444 : 555 : 555 666 : 777 : 777 888 : 999 : 13579 : 1335779 123456789 : 2232345678934567567789 3141592653589793 : 331314159141591415926535894141594159265358971592653559592653589726536535897553335897358979558975897958979389977793 987654321 : 77654354332

Since the results are from an official testing sheet, then you can assume that the blank keys are not mistakes - e.g. 1, 444, 666 etc won't result in any key output

For the challenge, you have to generate the key that corresponds to the following digits:

20266172596384

Note: you may notice the Enigma machine in the background - I simply chose that since I like the background. The algorithm here has nothing to do with the Enigma machine

A reminder, if you are completely stuck, hints will be released after 24 hours :)

Submit Answer

Hints

Hints will be released at the start of each of the following days - e.g. the start of day 3 is 48 hours after the challenge starts

Release Day	Hint
2	Look carefully at the digits that don't result in any key output - think about prime numbers
3	The digit strings with no key output contain no prime digits
4	If we examine more closely, at an example like 12345, we see the output is 22335 - that is a concatenation of all the prime substrings in the original number - e.g. 2, 23, 3, 5 and all substrings that are prime that exist in the original number. Note the order is important - we start on the 1st digit, then concatenate all prime substrings from this position, then move onto the 2nd digit and get all prime strings starting from there, then the 3rd and so on
5	You will first want a function that can determine whether any given number is prime - there a various ways to do this. A simple way is to loop from 2 to the square root of the number - if the original number mod by the loop index doesn't equal 0 for any value, then it is prime. There are of course more efficient ways of doing this - e.g. dynamic programming to avoid recalculating values you have already calculated
6	You can then loop over all substrings of the original number by converting it to a string, creating nested loops - the outer loop iterates through the starting digit position (1st char to last), while the inner loop iterates the length of the substring from 1 to the remaining length of string - e.g. assuming the original value 1234, this would be the order we would check for primes: 1, 12, 123, 1234, 2, 23, 234, 3, 34, 4