- As you may recall, I resumed Mike Oakes' search for primo-factorials, primes

of the form n! +/- n# +/- 1. Mike had stopped at n = 7039, and I picked up

the search until 10000. 2 PRPs were found, 8147! + 8147# - 1 and 9627! -

9627# - 1. Maybe I'll keep on searching for n > 10000, but I don't feel very

inclined to do so unless I can do better than PRP-ing all the candidates.

Specifically, I'm thinking of sieving them. However, the first sieve that

comes to mind (computing n! +/- n# +/- 1 mod 2, 3, 5, 7, ...) is largely

ineffective for the task, since n! +/- n# have as common factors all primes

up to n. One might argue `fine, let's sieve with primes larger than n them.'

However, this is a very inefficient sieve: by Mertens' theorem, only 6.1%

percent of random integers aren't divisible by primes up to 10,000, while

2.71% percent of random integers aren't divisible by primes up to a billion

(a very very optimistic sieve bound). Thus, using this sieve I could at best

eliminate 55.5% (= 1 - 2.71/6.1) of candidates, certainly not a worthwhile

effort for the time it would take to sieve up to a billion.

Thus I am led to ask the group for other strategies to sieve this sequence of

primes. Everything I've come up with until now relies on the following facts:

1. n! +/- n# +/- 1 = n#*(n!/n# +/- 1) +/- 1, where n!/n# is an integer.

2. For a given prime p, then n#*(n!/n# +/- 1) +/- 1 == 0 mod p implies

n#*(n!/n# +/- 1) == +/-1 mod p, so that n# or -n# is an inverse mod p of

(n!/n# +/- 1).

3. And of course, it's easy to perform reductions modulo p, as we can easily

enumerate the prime factors of n! using Legendre's theorem, then use

Basically what I'm looking for is something relating the congruence classes of

an integer and its inverse, so that I can figure out conditions n that will

have one of n! +/- n# +/- 1 divisible by a chosen prime. If such a result

could be found, then the sequence could actually be sieved in the usual sense

-- discarding the integers that are divisible by a given prime p with less

work than testing all of them.

I'm not placing much hope on the existence of such a method, but as it's been

repeatedly shown here, my knowledge is quite limited (:

Décio

[Non-text portions of this message have been removed] - --- In primenumbers@yahoogroups.com, "Jens Kruse Andersen"

<jens.k.a@g...> wrote:>Décio wrote:

The point Jens is making, can not be stressed enough. While I am

>>I should grab that version -- I was running the latest compiled

>>binary for Linux that was available in the files area of the

>>openpfgw group.

>

>Note that development versions at openpfgw are often less tested

>than released versions at primeform group.

>Factors can be trivially verified so a possibility is:

>Factor with development, verify factors, prp with release.

very "partial" to the current "experimental" developement version

of PFGW, and that is where I focus all of my developement time adding

new things, and enhancing performance, keep in mind that it IS

experimental code. The current dev version is so experimental that

it will not even build under Linux (due to running with 2 versions

of the Woltman FFT libraries while porting all of code over to use

the newest version of that library).

Also keep in mind, that the factoring code has been pretty much

re-written (as you see by the 10x speed improvement). However, just

a few days ago, I did fix a fatal bug in that code, which you can

demonstrate on your December Linux build, by simply doing a:

pfgw -f 5000#

That will crash, due to a division by zero problem (i.e. the WHOLE

tree was a factor of the number, and thus the whole tree's modulus

was zero). Thus, even though the tree-factorize code has been in

the dev version since day one (since the first "stable" 1.2 was

released, and the dev branch started off), it still has some nits

in it (thus, that is WHY it is not in the stable release, even

though it was running prior to the stable cut-off).

Also, the exponenation code, which was scattered throughout many

places in the source (but pretty well tested at each of those), is

now in a singlular function, and all of those "locations" in the

code call a common expmod() function. The exponentation code also

seems to be "pretty stable", and with only one set of code (vs a hand

full before), when there is a bug, fixing it is easier, due to

all processing filtering down into that single function. However,

just as was seen in the "pretty stable" tree factorize code, there

simply has not been enough testing to fully validate that everything

is correct.

Also, the N-1 proof has been totally re-written (porting the existing

stable N-1 test code was just too much of a nightmare into the v24

FFT library, so it was re-written). This code is WAY too fresh to

rely on. At the same time, the N+1 and "combined" (-tc) testing

code is also being re-written. Then about 20% of the "core" pfgw

code will be stripped out (all of the support code for the v23 FFT,

along with the older proving code which was integrated into the

expression engine).

That is why Jens made a "blanket" statement about when to use the

dev version, and when NOT to use it (or at least do not FULLY rely

on it). It is an experimental version. It may not work right, may

crash, may cause your computer to make a loud screeching sound and

catch fire, or might cause your TV to only receive re-runs of the

"Teli-Tubbies" (well, I am pretty sure the last 2 warnings can be

ignored :) However, many of the "recent" requests (such as faster

factoring, IBDWT, enhanced script features), are only available in

that version. Just use the version with caution, and keep me

informed of problems with it, and again, it should NOT be used

for testing at this time, without additional validation of anouther

application (including an older "stable" PFGW version).

Jim.