first 10 digit prime in consecutive digits of e

The One-Liner

or, without highlighting:

echo -e "scale=1000 \\0073 e(1)" | bc -l | tr -d [\\\\\\n] | cut -c 3- | sed 's/\(..........\)\(..........\)/\1\n\1\2\n\2/g' | sed 's/\(....................\)/A\1\nB\1\nC\1\nD\1\nE\1\nF\1\nG\1\nH\1\nI\1\nJ\1/' | sed 's/A//' | sed 's/B.//' | sed 's/C..//' | sed 's/D...//' | sed 's/E....//' | sed 's/F.....//' | sed 's/G......//' | sed 's/H.......//' | sed 's/I........//' | sed 's/J.........//' | sed 's/^\(..........\).*/\1/' | factor | grep -v ": [0-9]* " | head -1 | sed 's/:.*//'

And so it begins

Although technically it is still a one-liner if you use semi-colons inside strings, I wanted to be extra strict and avoid the use of them altogether. This is significant in the arguments to the initial echo because the string argument to it could have been scale=1000 ; e(1), but I replaced the semi-colon with its ASCII number in octal, 073. This was possible because I used the handy -e feature of echo which is the option to “enable interpretation of backslash escapes” and if you backslash escape 0NNN you get the character whose ASCII code is NNN (octal).

This string, then, is piped into bc which is, according to the man page, An arbitrary precision calculator language. The semi-colon that it receives separates the two commands scale=1000, which tells the calculator to support 1000 digit numbers, and e(1) which calculates the constant e (raised to the power 1). So the output of the second command, and the input to the second pipe is thus:

2.718281828459045235360287471352662497757247093699959574966967627724\ 07663035354759457138217852516642742746639193200305992181741359662904\ 35729003342952605956307381323286279434907632338298807531952510190115\ 73834187930702154089149934884167509244761460668082264800168477411853\ 74234544243710753907774499206955170276183860626133138458300075204493\ 38265602976067371132007093287091274437470472306969772093101416928368\ 19025515108657463772111252389784425056953696770785449969967946864454\ 90598793163688923009879312773617821542499922957635148220826989519366\ 80331825288693984964651058209392398294887933203625094431173012381970\ 68416140397019837679320683282376464804295311802328782509819455815301\ 75671736133206981125099618188159304169035159888851934580727386673858\ 94228792284998920868058257492796104841984443634632449684875602336248\ 27041978623209002160990235304369941849146314093431738143640546253152\ 09618369088870701676839642437814059271456354906130310720851038375051\ 01157477041718986106873969655212671546889570350354

From this it is clear that bc does not trust your terminal to display a number the way you want, and thinks it can do a better job by munging its output. Fortunately this can be worked around by adding a command to remove all backslashes and new lines, which tr is good at. Unfortunately, to specify a backslash to tr you need to backslash it, and a new line to tr is \n, so that suggests the argument should be \\\n. Even more unfortunately, however, the argument then has to be escaped again, so it becomes \\\\\\n. Then, unfortunately to the point of tragedy, my blogging software condenses double backslashes into single backslashes (sometimes), so I actually had to use 12 backslashes to write that last sentence.

The output is then one long line, but for cleanliness, I wanted to remove everything before the decimal point (or decimal comma), inclusive. As 2 < e < 3, this meant cutting off the first two characters, or equivalently taking everything from the third character inclusive (treating the number as a string). After the cut, the output is then a long string of decimal digits, to be manipulated by the many seds, but that’s the really confusing bit, so I will focus on the ending before dealing with them.

Decomposition

Trust me for now that the input into factor is a series of lines each of which is a 10 digit number whose consecutive digits are consecutive digits of e. The question is which of these are prime, but that is where factor is useful, because it outputs the prime factor decomposition of a number passed to it as input. For example, the number 6965521267 given as input to factor produces an output of:

6965521267: 5987 1163441

whereas for a prime number like 7, the output is:

7: 7

The difference between the output for prime numbers and for composite numbers, then, is that prime numbers don’t produce output which has “a colon then a space then a (perhaps multi-digit) number then a space”. There is no need for a space after the first factor of a prime number, because that first factor is the only factor (apart from 1, which factor never outputs). So grep can be used to select just the lines that have prime numbers in.

The puzzle asks for the “first” prime number found, so the output stream can stop after the first line found by grep, and for that head is used, specifying 1 lines. Finally, because the output of factor is not ideal for this puzzle, sed is used to cut off everything after the colon, inclusive, leaving just the number, on its own line.

The difficult bit

So, the input of a long string of decimal digits of e has to be split into chunks of 10 digit numbers, but simply adding a line break every 10 digits would mean that not every 10 digit substring of e would get tested for primality. For instance, if the first 10 digit prime were made of the 5th to 14th digits, then it would be missed, because only the numbers made of the 1st to 9th and 10th to 19th digits (and so on) would be checked. To generate every possible substring took a level of cunning which I apparently didn’t have when I first tried this, and even this time it took me a while, but then I had my moment of inspiration. What I needed was a two step process, where the first step involved creating duplicated information, and the second step involved trimming that information down. Previously I had been focusing on the trimming and then being unable to imagine a step to add the extra information I needed, but once I had created a stream of duplicated information and looked at it, I could easily imagine the process needed to trim it down.

The step of creating duplicate information was itself a two step process, but both used a clever trick with sed which is worth mentioning. When doing a regular expression match and replace with sed, the replacement is allowed to contain “special escapes \1 through \9 to refer to the corresponding matching sub-expressions in the regexp”. These sub-expressions in the regular expression are sections contained within brackets (which naturally have to be backslashed).

To begin the duplication, then, the input string of digits is considered in blocks of 20, with the first 10 being captured as one sub-expression and the other 10 being captured as a second, and these sub-expressions are used like building blocks to build an even bigger block. For clarity, I will assign the first sub-expression to the letter A and the second sub-expression to the letter B. The building block made from these letters takes this shape:

#A AB B#

where the hashes are gaps to filled by the next match. Since the sed uses the g flag, it acts “globally”, that is, on each consecutive block of 20 digits, so the next match gets turned into the same shape, tessellating. Overall the result is a sequence of lines that go AB, BC, CD and so on, which means each block of 10 digits has a chance to be at the start of a line with its following 10 digits after it.

Carrying on the duplication process, the next step is to create 10 copies of each of these lines, but each clone must be identifiable, so a letter prefix is used (ignoring the fact that I used letters to explain the previous step). When replacing a matched regular expression, sed allows you to include new lines and arbitrary copies of the matched input, so it is easy to match the whole 20 character line each time (perhaps a little verbosely) and output 10 copies of it with a different prefix and a new line separating each copy. This produces as many output lines as there are 10 digit substrings of the input, and there is a one-to-one mapping between output lines and substrings such that a given substring is mapped to an output line which contains it. The only problem is that these output lines are all 20 digits long, not 10, so they need to be trimmed.

The type of trimming that needs to be done is different for each of the 10 rows that were created in the last step, but as these lines each have a unique prefix, this means there are just 10 rules needed, each one specific to a single prefix. So the seds from A to J trim off various amounts of digits from the left of the 20 digit lines, starting with zero digits and building up to 9 digits. There is no point removing 10 digits, because this would just leave the last 10 digits of the 20, which is the same as the first 10 digits of the 20 on the next line. These seds also remove the prefixes, because once all lines start at the correct digit, the next sed can act indiscriminately.

Here is what a block of 10 duplicate lines look like before these seds:

A71828182845904523536 B71828182845904523536 C71828182845904523536 D71828182845904523536 E71828182845904523536 F71828182845904523536 G71828182845904523536 H71828182845904523536 I71828182845904523536 J71828182845904523536

and after:

71828182845904523536 1828182845904523536 828182845904523536 28182845904523536 8182845904523536 182845904523536 82845904523536 2845904523536 845904523536 45904523536

The indiscriminate sed then only needs to capture the first 10 digits of each line, and discard the rest, although I suppose a cut could have done just as well. Anyway, the result of this is that all lines are 10 digits long, and each line is like the previous line shifted along by one character. This is precisely what needs to be passed into factor, as described above, which completes my explanation of that rather complex one-liner.

Conclusion

You may have noticed that the script contains one hard-coded number, the number 1000, specifying how many digits of e to look through to find this prime number. I originally picked a bigger value than 1000, but reduced it after using a bit of grep -n magic. In the general case, though, choosing a random number is unlikely to be the best strategy, as there are an infinite number of numbers and most of them would require a prohibitively long execution time. One alternative is to require a human to keep adjusting the value higher and higher until a result is found, but making a human part of the algorithm seems no more elegant than doing the whole thing by hand.

Taking a more mathematical approach, one could consider that the distribution of primes tends towards x / ln(x), so the number of primes between, 10…0 (n-1 zeros) and 99…9 (n nines) can be approximated. Assuming that the digits of e approximate a random sequence, the probability of a given n digit number being prime can be approximately calculated. The one-liner should then be hard-coded with the reciprocal of this probability as the number of digits to check.

The only remaining question is, since I excluded the initial 2 before the decimal point, how often is this method going to miss a prime of n digits which starts with it?