mersenneforum.org  

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

Reply
 
Thread Tools
Old 2018-11-22, 14:01   #1
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

35238 Posts
Default Lucky number gaps

I wonder what the record gaps between lucky numbers are?

The gaps between the first few lucky numbers are shown at https://oeis.org/A031883
robert44444uk is offline   Reply With Quote
Old 2018-11-23, 10:54   #2
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

2×5×569 Posts
Default

Is there an efficient way of calculating the nth Lucky number or determining whether n is a lucky number?
henryzz is offline   Reply With Quote
Old 2018-11-23, 13:09   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by henryzz View Post
Is there an efficient way of calculating the nth Lucky number or determining whether n is a lucky number?
you can build a sieve, I made one in PARI/GP but forgot to post it, it went something like:

Code:
my(a=apply(r->2*r-1,[1..1000]));for(x=2,100,a=select(q->vecsearch(a,q)%a[x]!=0,a));a
all numbers of form 6x+5 are eliminated on the first pass, 42x+19 on the second I think it is, etc. I tried to make a sieve of sundaram style argument but failed.

Last fiddled with by science_man_88 on 2018-11-23 at 13:49 Reason: realized I can't do math lol
science_man_88 is offline   Reply With Quote
Old 2018-11-24, 08:33   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

5×11×157 Posts
Default

Lucky numbers sieve:

On the desk of the HR Manager there are stacked 20 CV applications for the new job that the company posted. The CEO walks in, sees the stack, then very fast and randomly selects 6-7 CVs from the stack and tore them to pieces. "I do not need unlucky people in my company".

Last fiddled with by LaurV on 2018-11-24 at 08:33
LaurV is offline   Reply With Quote
Old 2018-11-27, 22:49   #5
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

CF716 Posts
Default

Quote:
Originally Posted by LaurV View Post
Lucky numbers sieve:

On the desk of the HR Manager there are stacked 20 CV applications for the new job that the company posted. The CEO walks in, sees the stack, then very fast and randomly selects 6-7 CVs from the stack and tore them to pieces. "I do not need unlucky people in my company".
Many years ago, I saw a 3-panel cartoon where the instructor was orienting his students. In the first panel he said to them (IIRC), "You will be given homework, two hourly exams, and a final exam." In the second, he said (IIRC), "Points will be totaled and an average calculated." In the last panel, there was a "thought bubble" saying "Then I'll go down the roster and flunk every third student."
Dr Sardonicus is offline   Reply With Quote
Old 2018-11-28, 01:13   #6
Bobby Jacobs
 
Bobby Jacobs's Avatar
 
May 2018

22×47 Posts
Default

The sequence of record gaps between lucky numbers is very interesting. It is in OEIS.
Bobby Jacobs is offline   Reply With Quote
Old 2018-11-28, 06:01   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

133468 Posts
Default

https://oeis.org/A118126
CRGreathouse is offline   Reply With Quote
Old 2018-11-30, 04:46   #8
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2×11×41 Posts
Default

Does anyone have a copy of Hugo's lucky sieve? The links seem to be broken and Internet Archive doesn't link past his splash page.

I wrote a little C version of the lucky sieve that seems reasonably fast compared to Wilson's code, but it's still not particularly fast. 13 seconds to n < 10^7, but 14 minutes for n < 10^8.
danaj is offline   Reply With Quote
Old 2018-12-11, 18:41   #9
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2×11×41 Posts
Default

Following up on my own question, Hugo's code can be found in:

https://github.com/hvds/seq/tree/master/lucky

I will note that choosing 32-bit vs. 64-bit types makes a significant performance difference on x86. Wilson's code defaults to 64-bit, Hugo's to 32-bit. Wilson's needs a double-length type for an intermediate calculation, so it doesn't really help to use 32-bit.

There is a trivial bug in the limit calculation that sometimes generates one more value than requested. We can also choose n/log(n) as an initial array allocation making it almost never necessary to reallocate, and likely to use less overall memory.

His sieve is really straightforward and simple.

Generating lucky values under 1e9:

Wilson: est 200 hours, 376MB (8 bytes per element)
van der Sanden: 23 hours, 386MB (2 x 4 bytes, times n/log(n))
Jacobsen: 8 hours, 834MB (4 bytes, times n*322560/1547910)
danaj is offline   Reply With Quote
Old 2018-12-11, 19:08   #10
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2×11×41 Posts
Default

Quote:
Originally Posted by henryzz View Post
Is there an efficient way of calculating the nth Lucky number or determining whether n is a lucky number?
I don't know of any method for generating lucky[n] without generating a non-trivial number of previous values. You don't need a full sieve, but current methods seem to use all the lucky numbers <= n.

Determining if n is a lucky number .... what I've seen is an analogy of trial division. E.g. should be odd, should be {1,3} mod 6, etc. I haven't seen a clean bit of code for that either. I do something not-dissimilar when constructing my initial list, using a simple increment loop for the first two levels (odds and every 3rd) then a mask for the next 2 or 3 levels (every 7th, 9th, 13th). That isn't sufficient of course (just like trial division by the first 5 primes wouldn't be).

Q1: Could one make a constant space is_lucky(n) function?

Q2: Are there efficient non-lucky tests akin to things like the Fermat compositeness test?

Last fiddled with by danaj on 2018-12-11 at 20:20
danaj is offline   Reply With Quote
Old 2018-12-11, 19:30   #11
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by danaj View Post
I don't know of any method for generating lucky[n] without generating a non-trivial number of previous values. You don't need a full sieve, but current methods seem to use all the lucky numbers <= n.

Determining if n is a lucky number .... what I've seen is an analogy of trial division. E.g. should be odd, should be 1 or 3 mod 6 if >= 5, etc. I haven't seen a clean bit of code for that either. I do something not-dissimilar when constructing my initial list, using a simple increment loop for the first two levels (odds and every 3rd) then a mask for the next 2 or 3 levels (every 7th, 9th, 13th). That isn't sufficient of course (just like trial division by the first 5 primes wouldn't be).

Q1: Could one make a constant space is_lucky(n) function?

Q2: Are there efficient non-lucky tests akin to things like the Fermat compositeness test?
Yeah using linear polynomials sucks.
As to the main questions I'm not sure.

http://oeis.org/A161154 seems related in that it seems twice these +1 are likely ( not guaranteed) to be lucky but not all entries for indices in the odd numbers that are lucky are here.

Last fiddled with by science_man_88 on 2018-12-11 at 19:53
science_man_88 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 23:59.

Mon Aug 3 23:59:28 UTC 2020 up 17 days, 19:46, 0 users, load averages: 1.37, 1.37, 1.43

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.