correction and new findings to filtering numbers before checking for a perfect square

Randall Rathbun randallrathbun at protonmail.com
Wed Mar 9 21:49:49 CET 2022


To all:

I ask your apology for making a false claim that filtering possible squares by certain selected mods consequitively will be the product of their filtering values.

The claim was made that picking the best 5 values would result in a value around 10^-13. This is false.

The ONLY correct thing I could say (and should have said) is that the computer shows for ONE modulo value the reduction in possible squares after testing.

Now, after testing 85,222,284 triangles with sides ranging from 1 to 1006, I found that there are only 14,153 Heron triangles over this range, and only 6,129 are primitive, in essence testing 85+ million values for the area squared to have only 14K pass as perfect squares.

The interesting part (and I guessed this correctly) is that the best performing filtering mods changed completely from my previous run using square-sided triangles.

In particular, the prime 19 is very effective in filtering square sided triangles for some reason as yet unknown to me.

The top 10 performing mod values for the triangle distribution of area to check is

mod passed total percentage factors
5292 6921478 85222284 0.08121676251 2^2.3^3.7^2
7452 6944208 85222284 0.08148347679 2^2.3^4.23
8100 6989047 85222284 0.08200961852 2^2.3^4.5^2
6804 7017063 85222284 0.08233835883 2^2.3^5.7
6156 7097397 85222284 0.08328099960 2^2.3^4.19
9396 7211186 85222284 0.08461620203 2^2.3^4.29
6468 7411788 85222284 0.08697006994 2^2.3.7^2.11
9996 7637711 85222284 0.08962105498 2^2.3.7^2.17
3564 7650270 85222284 0.08976842254 2^2.3^4.117128 7650270 85222284 0.08976842254 2^3.3^4.11

This looks almost normal, primes 2, 3, 5, 7, 11 17, 19, 23 and 29 are seen.

The top 10 performing mod values for the square sided triangle distribution of area to check is

mod percentage factors
7695 0.003410382643 3^4.5.19
6460 0.003544007135 2^2.5.17.19
6859 0.003583176452 19^3
2565 0.003928560062 3^3.5.19
5130 0.003928560062 2.3^3.5.19
8740 0.004626263516 2^2.5.19.23
3420 0.004695013828 2^2.3^2.5.19
6840 0.004695013828 2^3.3^2.5.19
6156 0.004716434548 2^2.3^4.198721 0.004846590923 3^3.17.19

Here we see the primes 2,3, 5, 17 and 19 (19 is in all 10 mods)

This confirms my hunch that the "best" filtering primes will change depending upon the type of numbers being tested, which in my case is far from normal (uniform distribution)

I would like to concentrate on two things

- how to quickly find remainders using addition
- setting up a timing array under C language to correctly test the true speed of the filtering process.
- check to see if filtering by a product of primes instead of 1 prime at a time is faster.

I want to compare #1 with the integer % timing from my XEON chips for#3 to see which one is actually faster.

Randall


More information about the gmp-discuss mailing list