mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Prime Gap Searches

Reply
 
Thread Tools
Old 2019-02-15, 20:55   #23
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

16068 Posts
Default

Quote:
Originally Posted by Bobby Jacobs View Post
Is there any way to find out if a number is lucky without testing all of the numbers up to it?
Yes, quite a bit faster, albeit I don't know anything as simple as modern primality testing. It still has a terrible growth rate so gets quite slow if you're spoiled by how fast we can do primality tests.

You can view it as trial division up to the lucky number count of n (approximately n/log(n)). We generate lucky numbers only up to that (at most).


For a concrete example take n = 2^23 = 8388608 and call is_lucky(n+x) for x = 1..100. There are 8 lucky numbers in the range. Only 14 of the 100 values require anything beyond looking at the first 48 lucky numbers. After that we could sieve to ~ 520000. Along the way check if the number we're interested in would be removed.

Times on a Macbook in milliseconds:

2300 Time to generate lucky numbers to 2^23
12 Time to generate lucky numbers to 520000

160 Time for is_lucky(2^23+x) for x=1..100
120 Time for nth_lucky(517138+x) for x=1..8

These are measuring 100 and 8 (respectively) independent calls. If we really wanted the numbers in the sequential range we could just sieve once (to the lucky count of the max value needed). But that isn't the "is_lucky" predicate, which is usually thought of as a single call with an arbitrary integer input.

Last fiddled with by danaj on 2019-02-15 at 21:01
danaj is offline   Reply With Quote
Old 2019-08-23, 20:45   #24
Bobby Jacobs
 
Bobby Jacobs's Avatar
 
May 2018

2728 Posts
Default

When are we going to try to find the next maximal lucky gap?
Bobby Jacobs is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Gaps between maximal prime gaps Bobby Jacobs Prime Gap Searches 51 2020-07-09 07:49
Fun with the Lucky Numbers of Euler ewmayer Probability & Probabilistic Number Theory 0 2015-10-18 01:37
Lucky ECM hit Dubslow Factoring 3 2014-10-19 19:10
Lucky gmp-ecm curve... WraithX GMP-ECM 4 2009-01-12 16:29
Gaps and more gaps on <300 site gd_barnes Riesel Prime Search 11 2007-06-27 04:12

All times are UTC. The time now is 09:44.

Mon Jul 13 09:44:44 UTC 2020 up 110 days, 7:17, 0 users, load averages: 1.50, 1.50, 1.50

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