Close

More sieving

A project log for PEAC Pisano with End-Around Carry algorithm

Add X to Y and Y to X, says the song. And carry on.

yann-guidon-ygdesYann Guidon / YGDES 05/05/2023 at 00:270 Comments

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:

That sounds feasible with bash, right ?

Discussions