PARI's commands

[science_man_88]

got it working.

sievex(kmin,kmax,b,n,pmax)=a=0;for(k=kmin,kmax,forprime(p=1,pmax,if((k*b!^n+1)%p==0 && (k*b!^n+1)!=p,a=a+1));if(a==0,print("no factor found for"k"*"b"!^"n"+1 in this range"));a=0)

[3.14159]

Originally Posted by Karsten

The '!' was not the factorial-sign!

An integer followed by an exclamation point is taken as a factorial to me.

[science_man_88]

!

factorial
factorial
combinatorics
n! means the product 1 × 2 × ... × n. 4! = 1 × 2 × 3 × 4 = 24
logical negation
not
propositional logic
The statement !A is true if and only if A is false.

A slash placed through another operator is the same as "!" placed in front.

(The symbol ! is primarily from computer science. It is avoided in mathematical texts, where the notation ¬A is preferred.) !(!A) ⇔ A
x ≠ y ⇔ !(x = y)

according to wikipedia's table.

[3.14159]

Yes, yes, I know the connotations of the "!", symbol.

I can cite a few quick examples:

7! = 5040
6 * 6 != 7.

[CRGreathouse]

Originally Posted by 3.14159

It is a sieve that kicks out bad k-values for numbers of the form k * b!ⁿ + 1 which are divisible by small primes, where the user is allowed to choose the k-range, the factorial base and the exponent, as well as the largest prime it will sieve up to. The output will be written to a file for testing. The user will have to make the modifications to ensure that the range will be testable, preferably with a decent or advanced text editor that is capable of doing so.

Where k < b!ⁿ, and where k, b, and n are positive integers.

I've given up trying to explain this. Here's my off-the-top-of-my-head code, with some basic comments:

vk(lim,kmin,kmax,b,n,c=-1)={
  my(v=vectorsmall(kmax,j,j>=kmin),start,vv,i=0);
  forprime(p=2,lim,
    trap(,next, \\ if p can't divide any of the members, just go on the next prime
      start=lift(Mod(c,p)/Mod(b,p)^n); \\ start * b^n = c (mod p)
    );
    start += p*ceil((kmin-start)/p); \\ start >= kmin
    forstep(j=start,kmax,p,
      v[j]=0 \\ j * b^n = c (mod p)
    )
  );
  vv=vector(sum(i=1,#v,v[i])); \\ vector for the numbers found, rather than 0/1
  for(j=1,#v,if(v[j],vv[i++]=j)); \\ fill vector
  vv \\ output
};
addhelp(vk, "vk(lim,kmin,kmax,b,n,{c=-1}): Returns those k with kmin <= k <= kmax for which k * b^n - c has no prime divisors up to lim.");

Test code for k * 19!^6 + 1, k <= 10^4:

vk(1e6,1,10^4,19!,6,-1)

This takes 200 ms. Comparable trial division takes 1 minute 29 seconds:

B=19!^6;for(k=1,1e4,forprime(p=2,1e6,if((k*B+1)%p==0,break)))

[kar_bon]

Impressive job CRG: 200ms for k<10000!

So I've made my first script for WinPFGW, but it uses only trial factoring for small primes and PRP-test the k-values where no factor was found for.

It creates a log-file like this (found primes/PRP are stored in "pfgw.log", too):

146*19!^6+1: factor 47
147*19!^6+1: factor 31
148*19!^6+1: factor 41
149*19!^6+1: factor 23
150*19!^6+1: is PRP/PRIME.
151*19!^6+1: no factor found.
152*19!^6+1: factor 6269
153*19!^6+1: no factor found.
154*19!^6+1: factor 883
155*19!^6+1: factor 523
156*19!^6+1: factor 65581
157*19!^6+1: factor 113
158*19!^6+1: factor 12583
159*19!^6+1: factor 31707989

You can choose min-k, max-k, factorial-n, exponent, +/-1 and factor-bound.
There is no code to prevent using false parameters, but that should not be a problem.

Timing: 1 <= k <= 10000, factor-bound = 100000
The script run 24s (here a AMD XP +2500, 1.8GHz) and found 247 PRP/primes.

[science_man_88]

wow even with minimal primelimit and trying a near maximal amount before length overflow with my max memory it's working up to 10^7 in under 17 seconds.

[3.14159]

Originally Posted by CRGreathouse

I've given up trying to explain this. Here's my off-the-top-of-my-head code, with some basic comments:

No need to be rude. I repeatedly said that I was unable to do it on my own.

[3.14159]

Originally Posted by science_man_88

wow even with minimal primelimit and trying a near maximal amount before length overflow with my max memory it's working up to 10^7 in under 17 seconds.

It's a nice script, but I still failed in the end. It's a double-edged sword. I can only write basic scripts.

Only 1.5 minutes for 500 million. Nice.

[3.14159]

Originally Posted by Karsten

You can choose min-k, max-k, factorial-n, exponent, +/-1 and factor-bound.
There is no code to prevent using false parameters, but that should not be a problem.

Timing: 1 <= k <= 10000, factor-bound = 100000
The script run 24s (here a AMD XP +2500, 1.8GHz) and found 247 PRP/primes.

Can you give us the timings for sieving to a certain prime? (Ex: Time it takes to sieve to 10⁶ for a certain range)

Also: Is it directly input to WinPFGW?

[kar_bon]

Originally Posted by 3.14159

Can you give us the timings for sieving to a certain prime? (Ex: Time it takes to sieve to 10⁶ for a certain range)

Also: Is it directly input to WinPFGW?

Start WinPFGW.exe and input in the line under "Standard "PFGW compatible" command line" the name of the script-file (in same folder).

That's all.

You can edit the parameters you need in the script.

(Need for sieve to 10^6 and 1<k<10000 about 50 seconds; window minimized!)