mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2013-02-07, 10:36   #1
Sam Kennedy
 
Sam Kennedy's Avatar
 
Oct 2012

10100102 Posts
Default 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?
Sam Kennedy is offline   Reply With Quote
Old 2013-02-07, 11:16   #2
axn
 
axn's Avatar
 
Jun 2003

124348 Posts
Default

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.
axn is offline   Reply With Quote
Old 2013-02-07, 11:35   #3
Sam Kennedy
 
Sam Kennedy's Avatar
 
Oct 2012

1228 Posts
Default

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.
Sam Kennedy is offline   Reply With Quote
Old 2013-02-07, 11:42   #4
axn
 
axn's Avatar
 
Jun 2003

22×7×193 Posts
Default

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
axn is offline   Reply With Quote
Old 2013-02-07, 11:53   #5
Sam Kennedy
 
Sam Kennedy's Avatar
 
Oct 2012

2·41 Posts
Default

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?
Sam Kennedy is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Reserved for MF - Sequence 276 kar_bon Aliquot Sequences 164 2022-08-15 15:46
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

All times are UTC. The time now is 21:01.


Sun Sep 25 21:01:52 UTC 2022 up 38 days, 18:30, 0 users, load averages: 1.00, 0.92, 0.93

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔