X = 90112354687
This X is also the smallest 11 digit pan-digital prime (pdp-11)
beginning with 9.
Here is an example, where, as they must,
the leading digits count down.
prime index on list
starting w/ n n.txt
-------------------------------
90112354687 1 X
81021436759 90784 W
72230865149 152049 V
64354078291 343488 U
53405127869 306236 T
45673981021 441761 S
36587209411 371610 R
28746510379 760545 Q
17869742503 549971 P
I imagine that there are plenty more examples,
but I did not explore further. The program is
here.
Method:
Having made nine sorted lists which together comprised all pdp-11s,
with the lists having leading digit (1..., 2..., ..., 9... ) while solving
set to just knock this problem off. Actually, it was just the
beginning of my troubles.
Due to the length (0.5 10^6 - 1.0 10^6) of each list
(e.g., there are 813303 starting with 2...) combing
through them all in nested loops would take centuries. I greatly
shortened the process by making a grand file index which listed
entry points in each n.txt list for the leading 5 digits. e.g.
the sequence 28746...... in 2.txt begins on line 760360
and ends on line 851987, where primes 28747... begin on the
next line. To use some old terminology, this turned
my search from serial access to random access. Since I knew
where to look in the lists for unfulfilled digits in each column
I could exclude, on-the-fly, the need to look at all the primes in
a list, but rather look through the (10 Choose m) groups in the
list where m = 11 - r, and r is the row number being tried.
But still, the task had not shrunk enough to be even remotely
tractable. The index data structure alone took 1 Gbyte of memory.
This problem had become a "search algorithm" problem.
I was completely stuck until I took a closer look at
the solution to the 5-Pandigit problem:
PDP Place on PDP
n n-list
------------------------------------
14355809627 1 269863 T
23440687159 2 228957 U
32204158967 3 131977 V
41021563897 4 92582 W
50112346789 5 1 X
Here, not only was X the smallest of all the 5-leading
pdp-11 numbers (first on its list), but,
the digits in columns 2,3,4,5 of the solution list (in italics)
all stayed in the 0-5 range. So, perhaps a "solution set"
in the 9-row problem might start with 5 rows where
each prime was located in this select domain, and a proof
of the smallest 9... could be found located equally "high up"
on the respective lists?
If true, altering the search to focus on this much smaller domain
would shorten the search area by (0.4)^5, reducing the needed
time from a cpu-weeks to cpu-hours. Indeed, it was true and
worked. A solution using the smallest 9... prime was actually
found so very high on the first 5 file lists that the code succeeded
in less than 2-hours.
This is the first time I have solved a problem using optimism!
(NASA calls this "Success Oriented Project Management"
- to refrain from checking every remote possibility, concentrating
instead on optimistic outcomes (in unmanned missions).
But, it's also dismissed as the "streetlight effect", named after the
proverbial drunk searching for his keys under the lamppost.
Finally, as a trivial aside, I recall the PDP-11 as a great
mini-computer of yore.
Edited on December 11, 2023, 4:29 pm
soln
