PARI's commands

[3.14159]

Originally Posted by CRGreathouse

No. I wrote the key calculations for the script, in the scripting language. I did not write the script that would contain those calculations. (If it's not worth your time to do it, why would it be worth mine?)

You failed to specify that.

Also: It would be a difficult task to write a sieve for k * n! + 1 in PARI/GP

[3.14159]

You suggested the use of lift(Mod(-1,x)/(n!)) and lift(Mod(1,x)/(n!))

[CRGreathouse]

Originally Posted by 3.14159

You failed to specify that.

I think I was pretty clear, but if it didn't come across that way I suppose that speaks to my communications skills.

Somehow I really just don't enjoy writing sieves. I just wrote one today (on a project with Vladimir Shevelev) and I've been working on a specialized siever for one of my sequences in the OEIS. The quick ones (yours and the one I made for Vladimir) aren't too bad, but this other one has been just draining... it's a pain, since this one needs to be really efficient (since it will run over the course of several months).

[CRGreathouse]

Originally Posted by 3.14159

You suggested the use of lift(Mod(-1,x)/(n!))

Yes, I think that's the right calculation. Check it with an example before trusting me, though... I've already messed up one siever today. Ugh, lost 6 hours of work with that one.

For my earlier sieve the calculations were essentially

b=znorder(Mod(2,p));
a=znlog(2293,Mod(2,p),b);

once I strip out all the unrelated junk. But that's variable-exponent, not variable-factor.

[3.14159]

Originally Posted by CRGreathouse

Somehow I really just don't enjoy writing sieves. I just wrote one today (on a project with Vladimir Shevelev) and I've been working on a specialized siever for one of my sequences in the OEIS. The quick ones (yours and the one I made for Vladimir) aren't too bad, but this other one has been just draining... it's a pain, since this one needs to be really efficient (since it will run over the course of several months).

What sequence is it that you have been working for?

Originally Posted by CRGreathouse

Yes, I think that's the right calculation. Check it with an example before trusting me, though... I've already messed up one siever today. Ugh, lost 6 hours of work with that one.

Ouch.

Mod(-1,p)/(n!) gives the smallest k for which (k * n! + 1)%p=0, and Mod(1,p)/(n!) gives the smallest k for which (k * n! -1)%p=0.

I'm searching for k * n! + 1. Mod(-1,p)/(n!) will help me a bit more here.

[CRGreathouse]

Originally Posted by 3.14159

What sequence is it that you have been working for?

http://oeis.org/classic/A176494 -- see the seqfan archives if you're interested.

Originally Posted by 3.14159

Mod(-1,p)/(n!) gives the smallest k for which (k * n! + 1)%p=0, and Mod(1,p)/(n!) gives the smallest k for which (k * n! -1)%p=0.

I'm searching for k * n! + 1. Mod(-1,p)/(n!) will help me a bit more here.

Right. So start at the place where k * n! + 1 is 0, and repeatedly add on the k-value where k * n! = 1 mod p. Yes?

[3.14159]

Since the point of a sieve is to avoid trial division: (forstep) loops.

At this point, I can get rid of specific divisors, but not groups of them.

Originally Posted by CRGreathouse

Right. So start at the place where k * n! + 1 is 0, and repeatedly add on the k-value where k * n! = 1 mod p. Yes?

Ex: 229.
>Mod(-1, 229)/(22!)
%1 = Mod(105, 229)

105 * 22! + 1 = 0 mod 229. In other words, 105 * 22! + 1 is divisible by 229.

>Mod(1, 229)/(22!)
%1 = Mod(124, 229)

So the forstep= (n=105,a,124,..) ?

[3.14159]

If so, that is incorrect, because it would also kick out prime numbers. (Ex: 9405 * 22! + 1 is prime.)

[CRGreathouse]

Maybe the step size just needs to be the prime itself?

[3.14159]

Originally Posted by CRGreathouse

Maybe the step size just needs to be the prime itself?

Yep. Step = 229.

(Verified, every k value after 105 that was of the form 105 + 229a yielded a k * 22! + 1 value that was divisible by 229.)

[3.14159]

So, the forstep is set.

forstep(n=105,a,229,if((n*22!+1)%229==0,print(n)))

But that only gets rid of one divisor, 229. What if we wished to get rid of 229 and 233?

One suggestion I received was to write two or more separate commands within one script: One for each divisor.

A forstep command for 229, and a separate forstep command for 233, within the same script. Excellent.