Let's go back to logs 139. Heuristic breakthrough and 140. gPEAC to 1 million.
Now that the gPEAC inner loop is optimised, it's time to build the distributed scanner to hack through a mountain of numbers... It should be faster with the optimised code, the program spread across 24 threads and the enhanced pre-sieving, which has been determined manually up to 131. More acceleration could come from more pre-sieving and the current aim is to reach 1 million, but we should be able to better exploit the existing census up to 131K, that is : 1000 times more than the manual exploration. More software needs to be written and used...
So far the sieve has been found to be
* base=5 : exclude 2 * base=11 : exclude 3 & 7 (coincidence ?) * base=19 : exclude 4 & 14 * base=29 : exclude 5 & 23 * base=31 : exclude 12 & 18 * base=41 : exclude 6 & 34 * base=59 : exclude 25 & 33 * base=61 : exclude 17 & 43 * base=71 : exclude 8 & 62 * base=79 : exclude 29 & 49 * base=89 : exclude 9 & 79 * base=101 : exclude 22 & 78 * base=109 : exclude 10 & 98 * base=131 : exclude 11 & 119
I could have continued but the manual operation was getting annoying.
I used a dumb bash script to get the raw data but it was limited by the uniq utility that I invoked. In fact I would need a UNIX program that performs a histogram and eventually tell me how many entries are empty, and which. Both informations are important and uniq doesn't get far. The full histogram is important too because I suspect a symmetry, but we'll see later.
Creating a histogram is probably one of the most basic algorithms out there but I don't want to write a utility... Instead let's look at the script, with the hint that it uses sort.
[yg]$ for base in $(seq 2 101); do
echo base=$base;
cat parfaits.txt |sed "s/$/ %$base/"|bc|sort -g|uniq
done
So I let bc do the modulo operations and then sort the results. uniq shows which values appear but not which do not. That may be the key.
Now the trick I just found is to forget uniq and parse the output of sort, linearly, as it will give an ascending sequence of numbers. I don't know which language to choose but the algo is simple:
- get a new number
- if this number is equal to the previous one, increment the counter
- else subtract the previous from the new, if the result is not one, emit a message.
That sounds feasible with bash, right ?
Discussions
Become a Hackaday.io Member
Create an account to leave a comment. Already have an account? Log In.