mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2020-12-16, 02:28   #1
bhelmes
 
bhelmes's Avatar
 
Mar 2016

5448 Posts
Default a prime sieve for f(n)=n⁴+1

A peaceful night,


the sieve algorithm for the function f(n)=2n²-1 was too slow,
even with some improvements.


The function f(n)=n^p-1 increase too fast for practical use.



Does it make more sense to use a function like f(n)=n⁴+1
for a presieve for Mersenne numbers ?



The actual used presieve reduces 1/p primes for Mp, as far as I can see.


Two questions:
Is there an algorithm known for a prime sieve for the function f(n)=n⁴+1,
(from whom)

Does the t with t | f(n) grows faster and how fast.


Thanks in advance if you spend me some lines.


Greetings from corona time,

Bernhard
bhelmes is offline   Reply With Quote
Old 2020-12-16, 02:43   #2
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

5×7×11×13 Posts
Default

Quote:
Originally Posted by bhelmes View Post
Does it make more sense to use a function like f(n)=n⁴+1
for a presieve for Mersenne numbers ?
No. We have a really good trial factoring algorithm, taking advantage of the fact that factors of Mersenne candidates are of form 2kp+1.
VBCurtis is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Fast multithreaded Prime Sieve jzakiya Miscellaneous Math 3 2020-08-22 21:55
How do you efficiently sieve for prime 3/4-tuples? Puzzle-Peter Software 156 2019-06-03 20:19
GPU Prime Sieve tapion64 GPU Computing 7 2014-04-10 06:15
Sieve depth vs. prime probability Unregistered Information & Answers 2 2010-05-25 20:51
Prime in Riesel Sieve Project Sloth Prime Sierpinski Project 1 2006-05-10 02:02

All times are UTC. The time now is 03:43.


Tue Oct 26 03:43:59 UTC 2021 up 94 days, 22:12, 0 users, load averages: 2.11, 2.37, 2.23

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.