20181122, 14:01  #1 
Jun 2003
Oxford, UK
1,877 Posts 
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 
20181123, 10:54  #2 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2·2,861 Posts 
Is there an efficient way of calculating the nth Lucky number or determining whether n is a lucky number?

20181123, 13:09  #3  
"Forget I exist"
Jul 2009
Dumbassville
10000011000000_{2} Posts 
Quote:
Code:
my(a=apply(r>2*r1,[1..1000]));for(x=2,100,a=select(q>vecsearch(a,q)%a[x]!=0,a));a Last fiddled with by science_man_88 on 20181123 at 13:49 Reason: realized I can't do math lol 

20181124, 08:33  #4 
Romulan Interpreter
Jun 2011
Thailand
2·3·31·47 Posts 
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 67 CVs from the stack and tore them to pieces. "I do not need unlucky people in my company". Last fiddled with by LaurV on 20181124 at 08:33 
20181127, 22:49  #5  
Feb 2017
Nowhere
2^{2}·3·17^{2} Posts 
Quote:


20181128, 01:13  #6 
May 2018
192_{10} Posts 
The sequence of record gaps between lucky numbers is very interesting. It is in OEIS.

20181128, 06:01  #7 
Aug 2006
13445_{8} Posts 

20181130, 04:46  #8 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
905_{10} Posts 
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. 
20181211, 18:41  #9 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
1611_{8} Posts 
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 32bit vs. 64bit types makes a significant performance difference on x86. Wilson's code defaults to 64bit, Hugo's to 32bit. Wilson's needs a doublelength type for an intermediate calculation, so it doesn't really help to use 32bit. 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) 
20181211, 19:08  #10  
"Dana Jacobsen"
Feb 2011
Bangkok, TH
905_{10} Posts 
Quote:
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 notdissimilar 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 nonlucky tests akin to things like the Fermat compositeness test? Last fiddled with by danaj on 20181211 at 20:20 

20181211, 19:30  #11  
"Forget I exist"
Jul 2009
Dumbassville
20300_{8} Posts 
Quote:
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 20181211 at 19:53 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Gaps between maximal prime gaps  Bobby Jacobs  Prime Gap Searches  52  20200822 15:20 
Fun with the Lucky Numbers of Euler  ewmayer  Probability & Probabilistic Number Theory  0  20151018 01:37 
Lucky ECM hit  Dubslow  Factoring  3  20141019 19:10 
Lucky gmpecm curve...  WraithX  GMPECM  4  20090112 16:29 
Gaps and more gaps on <300 site  gd_barnes  Riesel Prime Search  11  20070627 04:12 