Fun Sequence

Sam Kennedy · 2013-02-07, 10:36

I've started searching this sequence for prime numbers:
$((n+1)\mathrm{!}\ - \ n\mathrm{!})k + 1$

I like this sequence because N-1 is easy to factor so proving primality is straight forward.

Are there any faster primality tests than rabin-miller for numbers like this?

Has anyone searched a sequence similar to this?

axn · 2013-02-07, 11:16

Your expression simplifies to k.n.n!+1. Why not ditch the extra n and search for k.n!+1? Anyways...

Are you doing any sieving?

I am not aware of anything faster than regular PRP tests (PFGW can do that). PFGW can also prove the primality with a -tm argument.

Sam Kennedy · 2013-02-07, 11:35

I'm not sure how sieving applies to this, I know it's used in the other prime searching projects but I've never understood how it's actually used.

The only thing I can think of is generating a bunch of the above factorials, trial dividing by small primes below a certain limit, then performing the primality tests on whichever don't divide.

axn · 2013-02-07, 11:42

Sieving is merely a more efficient mechanism for doing trial factoring across a bunch of candidates, exploiting redundancies. And yes, sieving is applicable for your form, though I am not aware of any existing software that can do this (maybe MultiSieve?). But there are people in this forum who are capable of writing a sieve for this.

Your search space is controlled by 2 parameters, k and n. What are the limits on these? Also, how do you plan to investigate them? Fix a k and search across different n's? Fix an n and search across different k's? Some other way? Depending upon your strategy, the sieving approach also would change.

You could cut down your total search time upto 50% with a good siever.

Sam Kennedy · 2013-02-07, 11:53

Depending on the complexity of the maths involved, I might be able to write my own sieve.

The way I'm searching is fixing k and incrementing n.

The limit for k is the same as the limit for an unsigned long, n is limited by the amount of memory needed to store the entire term.

Are there any good references which could give me some ideas of coding a sieve?

2013-02-07, 10:36	#1
Sam Kennedy Oct 2012 2×41 Posts	Fun Sequence I've started searching this sequence for prime numbers: $((n+1)\mathrm{!}\ - \ n\mathrm{!})k + 1$ I like this sequence because N-1 is easy to factor so proving primality is straight forward. Are there any faster primality tests than rabin-miller for numbers like this? Has anyone searched a sequence similar to this?

2013-02-07, 11:42	#4
axn Jun 2003 2²×3²×151 Posts	Sieving is merely a more efficient mechanism for doing trial factoring across a bunch of candidates, exploiting redundancies. And yes, sieving is applicable for your form, though I am not aware of any existing software that can do this (maybe MultiSieve?). But there are people in this forum who are capable of writing a sieve for this. Your search space is controlled by 2 parameters, k and n. What are the limits on these? Also, how do you plan to investigate them? Fix a k and search across different n's? Fix an n and search across different k's? Some other way? Depending upon your strategy, the sieving approach also would change. You could cut down your total search time upto 50% with a good siever. Last fiddled with by axn on 2013-02-07 at 11:47

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Reserved for MF - Sequence 276	kar_bon	Aliquot Sequences	169	2022-11-06 18:03
A new sequence	devarajkandadai	Miscellaneous Math	3	2020-12-01 22:08
Primes in n-fibonacci sequence and n-step fibonacci sequence	sweety439	sweety439	17	2017-06-13 03:49
A New Sequence	devarajkandadai	Math	3	2007-03-20 19:43
Sequence	Citrix	Puzzles	5	2005-09-14 23:33

2013-02-07, 11:16	#2
axn Jun 2003 2²×3²×151 Posts	Your expression simplifies to k.n.n!+1. Why not ditch the extra n and search for k.n!+1? Anyways... Are you doing any sieving? I am not aware of anything faster than regular PRP tests (PFGW can do that). PFGW can also prove the primality with a -tm argument.

2013-02-07, 11:35	#3
Sam Kennedy Oct 2012 2×41 Posts	I'm not sure how sieving applies to this, I know it's used in the other prime searching projects but I've never understood how it's actually used. The only thing I can think of is generating a bunch of the above factorials, trial dividing by small primes below a certain limit, then performing the primality tests on whichever don't divide.

2013-02-07, 11:53	#5
Sam Kennedy Oct 2012 82₁₀ Posts	Depending on the complexity of the maths involved, I might be able to write my own sieve. The way I'm searching is fixing k and incrementing n. The limit for k is the same as the limit for an unsigned long, n is limited by the amount of memory needed to store the entire term. Are there any good references which could give me some ideas of coding a sieve?