Thursday 15 April 2021

Anatomy of a Search

As someone who attended high school in the 1960s, I'm still impressed by the mathematical feats that can nowadays be accomplished in seconds and that would have been impossible in that decade. Take for instance, this sequence from the OEIS:


 A258166

Indices of the start of 10 successive distinct digits in the decimal expansion of e (2.718281828...).


My attention was drawn to this sequence because 26310, my diurnal age today, happens to be a member of this sequence. In other words, in the decimal expansion of e there is a run of ten consecutive distinct digits starting at position 26310. Remember that the position count in 2.718 ... begins after the decimal point, so the 7 is in position 1, the 1 is in position 2, the 8 is in position 3 etc. The sequence, up to 26310, runs as follows:
1730, 2031, 2032, 3682, 4655, 5445, 5836, 9756, 10607, 11496, 11497, 11576, 17724, 17951, 18935, 18936, 20948, 21488, 21489, 22519, 26310, ...


I don't think this sequence could have been generated in the 1960s by a lone person like myself with access to just everyday tools like log tables and slide rules. It may have been possible for a researcher who had access to an IBM computer of the day. How can I generate this sequence now in 2021 using readily available tools?

I'm going to use SageMathCell to accomplish the task, using nothing more than an Internet connection and a web browser. Firstly, let's state in general terms what needs to be done:

begin
    generate the decimal expansion of e up to a certain point
    generate a list of all permutations of the digits 1234567890 
    check through successive blocks of ten in the decimal expansion of e 
    record initial position of any block that is in the list of permutations
end

Fortunately, SageMathCell will be able to handle all of these tasks. To generate the decimal expansion of e, we'll use:

str(e.n(digits=26320)) --> 2.71828182845904523536...

Of course, it's not necessary to view this expansion. It's sufficient to let D = str(e.n(digits=26320)) and then the digits are stored in active memory for later use by the program. Remember we need to go ten positions past 26310 so that's the reason for the 26320 limit. 

Now what about all the permutations of the digits 1234567890. There are 10! = 3,628,800 of them which is quite a lot. To find the permutations, it's necessary to separate 1234567890 into its separate digits and then shuffle them in every possible way:

1234567890.digits() --> [0, 9, 8, 7, 6, 5, 4, 3, 2, 1] 

For programming purposes, I'll let ID = 1234567890.digits() 

Permutations(ID) --> lists all 10! arrangements

It's then just a question of picking successive groups of digits in the decimal expansion of e and seeing if they match any of the 3,628,800 permutations. For example, the first group of ten digits would be:

[7, 1, 8, 2, 8, 1, 8, 2, 8, 4] which isn't a match

The next group of ten digits is:

[1, 8, 2, 8, 1, 8, 2, 8, 4, 5] which again isn't a match

The SageMath program will continue creating these groups of ten and trying to find a match. Figure 1 shows the actual code together with a permalink:

Figure 1

The output from this program is exactly as listed in the OEIS. It's interesting to note however, that the members of this sequence often come in pairs:
1730, 2031, 2032, 3682, 4655, 5445, 5836, 9756, 10607, 11496, 11497, 11576, 17724, 17951, 18935, 18936, 20948, 21488, 21489, 22519, 26310, 26311, ...
The program is flexible in that we can search for permutations of 1234567890 in the decimal expansion of other numbers e.g. \( \sqrt{2} \). All that's needed is to replace e with \( \sqrt{2} \). It's also easy to search for permutations of other sets of digits e.g. 24680. All that's needed is to replace 1234567890 with 24680. 

That's how easy it is. The only slightly difficult part is to write the code but the more familiar you become with SageMath the easier it gets.

No comments:

Post a Comment