## Sieving primo-factorials

Expand Messages
• 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
Message 1 of 9 , Feb 8, 2005
• 0 Attachment
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]
• ... What? You prp all the candidates? _Never_ do that. If you don t have something better like a sieve then always use pfgw -f The recent development versions
Message 2 of 9 , Feb 8, 2005
• 0 Attachment
Décio Luiz Gazzoni Filho wrote:

> As you may recall, I resumed Mike Oakes' search for primo-factorials, primes
> of the form n! +/- n# +/- 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.

What? You prp all the candidates?
_Never_ do that.
If you don't have something better like a sieve then always use pfgw -f
The recent development versions of pfgw will factor around 50% of the candidates
with the default trial factor limit.
-sn can be used to start factoring at n but it makes little difference on
average.

C:>pfgw -f -q10000!-10000#+1
PFGW Version 20041023.Win_Dev (Beta 'caveat utilitor') [FFT v23.8]

trial factoring to 127407975
10000!-10000#+1 has factors: 1535323

It first factors to 10^9 for n=34338:
trial factoring to 1000048612
34338!+34338#+1 has factors: 42709

A number with 140840 digits:
len(34338!+34338#+1): 140840

I doubt a "true" sieve is possible for this form but a custom made individual
trial factoring program would probably be a lot faster than pfgw -f.
A simple algorithm keeping track of moduli after each multiplication by n:
(dots to prevent space deletions)

for each prime p below trial factor limit
..modf=1
..modp=1
..for n from 1 to nmax
....modf = modf*n mod p
....if n is prime then modp = modp*n mod p
....if modf+/-modp+/-1 is 0 mod p then mark n as factored for that +/-

Several optimisations are possible. n should of course not be primality tested
in each loop.

--
Jens Kruse Andersen
• ... I think the situation isn t so clear-cut for primes of this form. Consider the values I computed for Mertens theorem: even if trial factoring up to 1e9
Message 3 of 9 , Feb 8, 2005
• 0 Attachment
On Tuesday 08 February 2005 22:54, you wrote:
> Décio Luiz Gazzoni Filho wrote:
> > As you may recall, I resumed Mike Oakes' search for primo-factorials,
> > primes of the form n! +/- n# +/- 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.
>
> What? You prp all the candidates?
> _Never_ do that.

I think the situation isn't so clear-cut for primes of this form. Consider the
values I computed for Mertens' theorem: even if trial factoring up to 1e9
were just a little more costly than PRP-ing the integer, then nothing is
gained. But apparently trial factoring to 127e6 is already 3/4 as costly as
the PRP test itself. So I don't think trial factoring makes sense in this
case.

> If you don't have something better like a sieve then always use pfgw -f
> The recent development versions of pfgw will factor around 50% of the
> candidates with the default trial factor limit.

Given that we need to look for large factors, shouldn't we ditch trial
factoring for Pollard rho and maybe a little Pollard p-1?

Unfortunately using PARI/GP or GMP-ECM for the job would be hopeless, as GMP
is much slower than George Woltman's code, and this would probably negate any

Are there any implementations of these algorithms using Woltman's FFTs?

> <snip>
>
> I doubt a "true" sieve is possible for this form but a custom made
> individual trial factoring program would probably be a lot faster than pfgw
> -f. A simple algorithm keeping track of moduli after each multiplication by
> n: (dots to prevent space deletions)
>
> for each prime p below trial factor limit
> ..modf=1
> ..modp=1
> ..for n from 1 to nmax
> ....modf = modf*n mod p
> ....if n is prime then modp = modp*n mod p
> ....if modf+/-modp+/-1 is 0 mod p then mark n as factored for that +/-

Actually one can do better:
-use Legendre's theorem to enumerate the factors of n;
-subtract 1 for each prime up to n, thus obtaining the prime factorization of
n!/n#;
-evaluate this by modular powering, call it a;
-compute b = a +/- 1, according to the form desired;
-compute c = a*n# mod p;
-finally, the result is given by b*c +/- 1 mod p (again the sign is chosen
according to the form desired).

To see why this is faster, consider that the prime factorization of a typical
n!/n# factor is

2^e_1 3^e_2 5^e_3 7^e_4 ...

Then your method does e_1 + e_2 + e_3 + e_4 + ... multiplications, while mine
does something like O(log e_1) + O(log e_2) + O(log e_3) + O(log e_4) + ...,
these being the cost of modular exponentiations with exponent e_1, e_2, e_3,
e_4, ...

Also, one might cache results from a computation to another. If one caches the
intermediate computations for n! +/- n# +/- 1 mod p, at most two modmuls are
required to find (n+1)! +/- (n+1)# +/- 1 mod p.

In fact, this is a very good idea. I'm off to implement it in PARI/GP. Thanks
very much for the motivation (: (though I still believe that Pollard rho and
perhaps p-1 would be more efficient)

Décio

[Non-text portions of this message have been removed]
• ... Trial factoring almost always makes sense if nothing else is used. I did consider your case carefully and you may want to think twice before dismissing me.
Message 4 of 9 , Feb 8, 2005
• 0 Attachment
Décio Luiz Gazzoni Filho wrote:
> On Tuesday 08 February 2005 22:54, you wrote:
> > Décio Luiz Gazzoni Filho wrote:
> > > As you may recall, I resumed Mike Oakes' search for primo-factorials,
> > > primes of the form n! +/- n# +/- 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.
> >
> > What? You prp all the candidates?
> > _Never_ do that.
>
> I think the situation isn't so clear-cut for primes of this form. Consider the
> values I computed for Mertens' theorem: even if trial factoring up to 1e9
> were just a little more costly than PRP-ing the integer, then nothing is
> gained. But apparently trial factoring to 127e6 is already 3/4 as costly as
> the PRP test itself. So I don't think trial factoring makes sense in this
> case.

Trial factoring almost always makes sense if nothing else is used.
I did consider your case carefully and you may want to think twice before
dismissing me. I have written a lot of both sieves and individual trial
factoring programs. My sieves hold around 70 different current prime records:
http://hjem.get2net.dk/jka/math/myrecords.htm (2 records did not use my sieves)
Sorry for bragging but knowing what somebody has done may be helpful when
deciding whether to follow their advice or spend time studying their writings.

The default trial factor depth in pfgw -f tries to be near optimal, i.e. stop
when the "expected" factoring time matches prp time (although different prp
times for different forms is not taken into account).

I wrote:
> The recent development versions of pfgw will factor around 50% of the
> candidates with the default trial factor limit.

A recent development version can be found at
http://groups.yahoo.com/group/openpfgw/files/
It has _much_ faster trial factoring of large numbers, by the way based on my
TreeSieve code.
Factoring to 127e6 is not 3/4 but 1/8 as costly as the prp test itself.
That is definitely worth the effort when around 50% of candidates are factored.

pfgw versions slower at factoring will also choose a suitable default limit for
pfgw -f, e.g.:

C:>pfgw -f -o -q10000!+10000#+1
PFGW Version 20041129.Win_Stable (v1.2 RC1d) [FFT v23.8]

trial factoring to 11300619
10000!+10000#+1 has no small factor.

Factoring to 11.3e6 with this version also took around 1/8 of prp time.
Around 43% of your candidates near n=10000 will be factored by 11.3e6.
Also definitely worth 1/8 of the prp time (less when a factor is found).

> Given that we need to look for large factors, shouldn't we ditch trial
> factoring for Pollard rho and maybe a little Pollard p-1?

Maybe, after trial factoring to some point (above 10000). It depends on the
available programs and whether you want to set it up. Adding -f in a pfgw call
is extremely easy and should always be done if no other factoring has been
performed.

> > for each prime p below trial factor limit
> > ..modf=1
> > ..modp=1
> > ..for n from 1 to nmax
> > ....modf = modf*n mod p
> > ....if n is prime then modp = modp*n mod p
> > ....if modf+/-modp+/-1 is 0 mod p then mark n as factored for that +/-

> Actually one can do better:
> -use Legendre's theorem to enumerate the factors of n;
...

> Also, one might cache results from a computation to another. If one caches the
> intermediate computations for n! +/- n# +/- 1 mod p, at most two modmuls are
> required to find (n+1)! +/- (n+1)# +/- 1 mod p.

Read my code again. This caching is exactly what I did, but in a practical
order:
> > for each prime p below trial factor limit
> > ..for n from 1 to nmax

If you swap the (for p, for n) order then you have to store 2 residues for every
prime below the trial factor limit.
That may require more than 1 GB for a high limit.

Can you combine this fast caching method with using the prime factorization of n
as you suggest (except for initialization if you don't start at n=1)?
I considered the factorization method but thought my suggestion would be much
faster.

--
Jens Kruse Andersen
• ... I m not doubting your claims, rest assured (: Problem is, I m seeing some unusually slow timings for PFGW trial factoring. Both David and Jim wrote me
Message 5 of 9 , Feb 8, 2005
• 0 Attachment
On Wednesday 09 February 2005 01:59, you wrote:
> Décio Luiz Gazzoni Filho wrote:
> > On Tuesday 08 February 2005 22:54, you wrote:
> > > Décio Luiz Gazzoni Filho wrote:
> > > > As you may recall, I resumed Mike Oakes' search for primo-factorials,
> > > > primes of the form n! +/- n# +/- 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.
> > >
> > > What? You prp all the candidates?
> > > _Never_ do that.
> >
> > I think the situation isn't so clear-cut for primes of this form.
> > Consider the values I computed for Mertens' theorem: even if trial
> > factoring up to 1e9 were just a little more costly than PRP-ing the
> > integer, then nothing is gained. But apparently trial factoring to 127e6
> > is already 3/4 as costly as the PRP test itself. So I don't think trial
> > factoring makes sense in this case.
>
> Trial factoring almost always makes sense if nothing else is used.
> I did consider your case carefully and you may want to think twice before
> dismissing me. I have written a lot of both sieves and individual trial
> factoring programs. My sieves hold around 70 different current prime
> records: http://hjem.get2net.dk/jka/math/myrecords.htm (2 records did not
> use my sieves) Sorry for bragging but knowing what somebody has done may be
> their writings.

I'm not doubting your claims, rest assured (:

Problem is, I'm seeing some unusually slow timings for PFGW trial factoring.
Both David and Jim wrote me off-list to point that out. In the context of
slow timings and the expected removal rate, I believe my comment makes sense.

> The default trial factor depth in pfgw -f tries to be near optimal, i.e.
> stop when the "expected" factoring time matches prp time (although
> different prp times for different forms is not taken into account).

Except that it doesn't take into account the fact that n! +/- n# +/- 1 isn't
divisible by primes up to n; Jim suggested that I try -f35 instead of the
default, as that's near optimal according to his experiments.

> I wrote:
> > The recent development versions of pfgw will factor around 50% of the
> > candidates with the default trial factor limit.
>
> A recent development version can be found at
> http://groups.yahoo.com/group/openpfgw/files/
> It has _much_ faster trial factoring of large numbers, by the way based on
> my TreeSieve code.
> Factoring to 127e6 is not 3/4 but 1/8 as costly as the prp test itself.
> That is definitely worth the effort when around 50% of candidates are
> factored.

Yes, in that case it is.

> pfgw versions slower at factoring will also choose a suitable default limit
> for pfgw -f, e.g.:
>
> C:>pfgw -f -o -q10000!+10000#+1
> PFGW Version 20041129.Win_Stable (v1.2 RC1d) [FFT v23.8]
>
> trial factoring to 11300619
> 10000!+10000#+1 has no small factor.

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.

> Factoring to 11.3e6 with this version also took around 1/8 of prp time.
> Around 43% of your candidates near n=10000 will be factored by 11.3e6.
> Also definitely worth 1/8 of the prp time (less when a factor is found).
>
> > Given that we need to look for large factors, shouldn't we ditch trial
> > factoring for Pollard rho and maybe a little Pollard p-1?
>
> Maybe, after trial factoring to some point (above 10000). It depends on the
> available programs and whether you want to set it up. Adding -f in a pfgw
> call is extremely easy and should always be done if no other factoring has
> been performed.
>
> > > for each prime p below trial factor limit
> > > ..modf=1
> > > ..modp=1
> > > ..for n from 1 to nmax
> > > ....modf = modf*n mod p
> > > ....if n is prime then modp = modp*n mod p
> > > ....if modf+/-modp+/-1 is 0 mod p then mark n as factored for that +/-
> >
> > Actually one can do better:
> > -use Legendre's theorem to enumerate the factors of n;
>
> ...
>
> > Also, one might cache results from a computation to another. If one
> > caches the intermediate computations for n! +/- n# +/- 1 mod p, at most
> > two modmuls are required to find (n+1)! +/- (n+1)# +/- 1 mod p.
>
> Read my code again. This caching is exactly what I did, but in a practical
>
> order:

Sorry about that. I should really get some sleep. Turns out that I reinvented

> > > for each prime p below trial factor limit
> > > ..for n from 1 to nmax
>
> If you swap the (for p, for n) order then you have to store 2 residues for
> every prime below the trial factor limit.
> That may require more than 1 GB for a high limit.

Correct. Although I didn't realize that I had even specified a particular loop
order! But as I was writing my code (before receiving this email) I was
already using the (for p, for n) order.

> Can you combine this fast caching method with using the prime factorization
> of n as you suggest (except for initialization if you don't start at n=1)?
> I considered the factorization method but thought my suggestion would be
> much faster.

I'm writing the code right now. Hope I don't fall asleep over my keyboard
before finishing it, though.

Using the explicit prime factorization of n! (from Legendre's theorem) is only
useful if you're not starting from n = 1, otherwise the result cache does the
job. As the range n <= 10000 is already done, I believe it's worth it.

Décio

[Non-text portions of this message have been removed]
• ... I coded the sieve (code reproduced below). Despite the fact that it segfaults with gp2c, so that I had to run it interpreted instead of compiled, it s
Message 6 of 9 , Feb 8, 2005
• 0 Attachment
On Wednesday 09 February 2005 01:59, you wrote:
> Can you combine this fast caching method with using the prime factorization
> of n as you suggest (except for initialization if you don't start at n=1)?
> I considered the factorization method but thought my suggestion would be
> much faster.

I coded the sieve (code reproduced below). Despite the fact that it segfaults
with gp2c, so that I had to run it interpreted instead of compiled, it's
still a speed demon. With 10 minutes of CPU time (P4 2.6 GHz here) I
eliminated nearly 4000 composites. I shudder to think that this could
probably have cost me somewhere in the vicinity of 10 CPU-days.

I'm sure I commited a few egregious errors down there, not to mention some
ugly hacks, so please refrain from flaming me (:

I wonder, at what point should I switch back to trial factoring?

Décio

---
primorial(x) =
{
local(a);
a = 1;
forprime(p=2,x,a*=p);
return(a);
}

\\ Reverse indexes the primes -- the inverse of PARI's prime() function
init_invprime(nmax) =
{
local(last,k);
global(invprime);
invprime = vector(nmax);
last = 1;
k = 0;
forprime(p=2,nmax,
k++;
for(i=last,p-1,
invprime[i] = k-1;
);
last = p;
);
}

\\ Computes the prime factorization of n!/n#
legendre_factorial(n) =
{
local(v,i,k);
\\ v[] is initialized with -1 to simulate division by n#
v = vector(invprime[n],i,-1);
i = 0;
forprime(p=2,n,
i++;
k = 1;
while((cont = floor(n/p^k)) > 0,
v[i] += cont;
k++;
);
);
return(v);
}

sieve(nmin,nmax,pmax) =
{
local(v,i,j,a,b,apb,amb);
\\ Integers of the form n! +/- n# +/- 1 are not divisible by any
\\ prime up to n, and since the minimum value of n that we're
\\ considering is nmin, then we'll start there. Sure, we'll waste
\\ a little time checking whether the primes from nmin to a given n
\\ divide n! +/- n# +/- 1, for n > nmin, but that's not too costly
\\ anyway.
j = 0;
forprime(p=nmin,pmax,
if(bitand(j++,255)==0,
print("Sieving "p"...");
);
v = legendre_factorial(nmin);

\\ a == nmin!/nmin# (mod p)
a = Mod(1,p);
i = 0;
forprime(q=2,floor(nmin/2),
a *= Mod(q,p)^v[i++];
);

\\ b == nmin# (mod p)
b = Mod(1,p);
forprime(q=2,nmin,
b *= Mod(q,p);
);

\\ Now a == nmin! (mod p)
a *= b;

for(i=nmin,nmax,
apb = a + b;
amb = a - b;

if(apb == Mod(p-1,p),
write("composite_"nmin"_"nmax, i"! + "i"# + 1, "p);
);
if(apb == Mod(1,p),
write("composite_"nmin"_"nmax, i"! + "i"# - 1, "p);
);
if(amb == Mod(p-1,p),
write("composite_"nmin"_"nmax, i"! - "i"# + 1, "p);
);
if(amb == Mod(1,p),
write("composite_"nmin"_"nmax, i"! - "i"# - 1, "p);
);

a *= Mod(i+1,p);
if(isprime(i+1),
b *= Mod(i+1,p);
);
);
);
}

[Non-text portions of this message have been removed]
• One other issue Décio is running into, is that our binary linux builds have a static linked GMP which may or may not be optimal for a certain CPU. Now
Message 7 of 9 , Feb 8, 2005
• 0 Attachment
One other issue Décio is running into, is that our "binary" linux
builds have a static linked GMP which may or may not be optimal
for a certain CPU. Now with gmp playing a much heavier roll
(espcially when dealing with factoring), it might be wise to
have more than one build, or build linux binaries with dynamic

Under Win32, I did this by making a truely stand along GMP system
for PFGW which has a built in "default" gmp (for the masses), and
has special built GMP dll's for the speed freaks, with DLL's
optimally tuned for many CPU families.

GMP is now used in exponetation under a certain set of sizes (depends
on CPU and type of number), and also in factoring. The latest
experimental alpha, also now has GMP in the exponentation in the
N-1 proofs (again for numbers under a certain set of bit sizes)

Thus, getting a correct GMP for the CPU running on, is becoming
MUCH more critical than it was in the past (although, I have always
considered it critical ;)

Jim.

--- In primenumbers@yahoogroups.com, Décio Luiz Gazzoni Filho
<decio@d...> wrote:
> On Wednesday 09 February 2005 01:59, you wrote:
> > Décio Luiz Gazzoni Filho wrote:
> > > On Tuesday 08 February 2005 22:54, you wrote:
> > > > Décio Luiz Gazzoni Filho wrote:
> > > > > As you may recall, I resumed Mike Oakes' search for primo-
factorials,
> > > > > primes of the form n! +/- n# +/- 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.
> > > >
> > > > What? You prp all the candidates?
> > > > _Never_ do that.
> > >
> > > I think the situation isn't so clear-cut for primes of this
form.
> > > Consider the values I computed for Mertens' theorem: even if
trial
> > > factoring up to 1e9 were just a little more costly than PRP-ing
the
> > > integer, then nothing is gained. But apparently trial factoring
to 127e6
> > > is already 3/4 as costly as the PRP test itself. So I don't
think trial
> > > factoring makes sense in this case.
> >
> > Trial factoring almost always makes sense if nothing else is used.
> > I did consider your case carefully and you may want to think
twice before
> > dismissing me. I have written a lot of both sieves and individual
trial
> > factoring programs. My sieves hold around 70 different current
prime
> > records: http://hjem.get2net.dk/jka/math/myrecords.htm (2 records
did not
> > use my sieves) Sorry for bragging but knowing what somebody has
done may be
time studying
> > their writings.
>
> I'm not doubting your claims, rest assured (:
>
> Problem is, I'm seeing some unusually slow timings for PFGW trial
factoring.
> Both David and Jim wrote me off-list to point that out. In the
context of
> slow timings and the expected removal rate, I believe my comment
makes sense.
>
> > The default trial factor depth in pfgw -f tries to be near
optimal, i.e.
> > stop when the "expected" factoring time matches prp time (although
> > different prp times for different forms is not taken into
account).
>
> Except that it doesn't take into account the fact that n! +/- n# +/-
1 isn't
> divisible by primes up to n; Jim suggested that I try -f35 instead
of the
> default, as that's near optimal according to his experiments.
>
> > I wrote:
> > > The recent development versions of pfgw will factor around 50%
of the
> > > candidates with the default trial factor limit.
> >
> > A recent development version can be found at
> > http://groups.yahoo.com/group/openpfgw/files/
> > It has _much_ faster trial factoring of large numbers, by the way
based on
> > my TreeSieve code.
> > Factoring to 127e6 is not 3/4 but 1/8 as costly as the prp test
itself.
> > That is definitely worth the effort when around 50% of candidates
are
> > factored.
>
> Yes, in that case it is.
>
> > pfgw versions slower at factoring will also choose a suitable
default limit
> > for pfgw -f, e.g.:
> >
> > C:>pfgw -f -o -q10000!+10000#+1
> > PFGW Version 20041129.Win_Stable (v1.2 RC1d) [FFT v23.8]
> >
> > trial factoring to 11300619
> > 10000!+10000#+1 has no small factor.
>
> 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.
>
> > Factoring to 11.3e6 with this version also took around 1/8 of prp
time.
> > Around 43% of your candidates near n=10000 will be factored by
11.3e6.
> > Also definitely worth 1/8 of the prp time (less when a factor is
found).
> >
> > > Given that we need to look for large factors, shouldn't we
ditch trial
> > > factoring for Pollard rho and maybe a little Pollard p-1?
> >
> > Maybe, after trial factoring to some point (above 10000). It
depends on the
> > available programs and whether you want to set it up. Adding -f
in a pfgw
> > call is extremely easy and should always be done if no other
factoring has
> > been performed.
> >
> > > > for each prime p below trial factor limit
> > > > ..modf=1
> > > > ..modp=1
> > > > ..for n from 1 to nmax
> > > > ....modf = modf*n mod p
> > > > ....if n is prime then modp = modp*n mod p
> > > > ....if modf+/-modp+/-1 is 0 mod p then mark n as factored for
that +/-
> > >
> > > Actually one can do better:
> > > -use Legendre's theorem to enumerate the factors of n;
> >
> > ...
> >
> > > Also, one might cache results from a computation to another. If
one
> > > caches the intermediate computations for n! +/- n# +/- 1 mod p,
at most
> > > two modmuls are required to find (n+1)! +/- (n+1)# +/- 1 mod p.
> >
> > Read my code again. This caching is exactly what I did, but in a
practical
> >
> > order:
>
> Sorry about that. I should really get some sleep. Turns out that I
reinvented
> the wheel for lack of concentration to properly read your code!
>
> > > > for each prime p below trial factor limit
> > > > ..for n from 1 to nmax
> >
> > If you swap the (for p, for n) order then you have to store 2
residues for
> > every prime below the trial factor limit.
> > That may require more than 1 GB for a high limit.
>
> Correct. Although I didn't realize that I had even specified a
particular loop
> order! But as I was writing my code (before receiving this email) I
was
> already using the (for p, for n) order.
>
> > Can you combine this fast caching method with using the prime
factorization
> > of n as you suggest (except for initialization if you don't start
at n=1)?
> > I considered the factorization method but thought my suggestion
would be
> > much faster.
>
> I'm writing the code right now. Hope I don't fall asleep over my
keyboard
> before finishing it, though.
>
> Using the explicit prime factorization of n! (from Legendre's
theorem) is only
> useful if you're not starting from n = 1, otherwise the result
cache does the
> job. As the range n <= 10000 is already done, I believe it's worth
it.
>
> Décio
>
>
> [Non-text portions of this message have been removed]
• ... Avoiding divisibility by small primes is irrelevant for the trial factor limit. After n is passed, every prime p has estimated chance 1/p of being a factor
Message 8 of 9 , Feb 9, 2005
• 0 Attachment
I wrote:
> > The default trial factor depth in pfgw -f tries to be near optimal, i.e.
> > stop when the "expected" factoring time matches prp time (although
> > different prp times for different forms is not taken into account).

Décio wrote:
> Except that it doesn't take into account the fact that n! +/- n# +/- 1 isn't
> divisible by primes up to n; Jim suggested that I try -f35 instead of the
> default, as that's near optimal according to his experiments.

Avoiding divisibility by small primes is irrelevant for the trial factor
limit. After n is passed, every prime p has estimated chance 1/p of being a
factor in a sufficiently "random" form without special factor properties.

The default -f is much better than no factoring, but experimentation can
sometimes find a better limit.
A lot of things play in so it is hard for pfgw to guess the best limit when it
doesn't first time a partial factoring and prp'ing of the particular number
(and pfgw shouldn't start doing that).
I wrote "different prp times for different forms is not taken into account".
This is one thing pfgw could do but it requires analyzing the form before
factoring.

> 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.

--
Jens Kruse Andersen
• ... The point Jens is making, can not be stressed enough. While I am very partial to the current experimental developement version of PFGW, and that is
Message 9 of 9 , Feb 9, 2005
• 0 Attachment
--- In primenumbers@yahoogroups.com, "Jens Kruse Andersen"
<jens.k.a@g...> wrote:
>Décio wrote:
>>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.

The point Jens is making, can not be stressed enough. While I am
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.
Your message has been successfully submitted and would be delivered to recipients shortly.