mersenneforum.org Lucky number gaps
 Register FAQ Search Today's Posts Mark Forums Read

 2018-11-22, 14:01 #1 robert44444uk     Jun 2003 Oxford, UK 5·13·31 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
 2018-11-23, 10:54 #2 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 2·52·7·17 Posts Is there an efficient way of calculating the nth Lucky number or determining whether n is a lucky number?
2018-11-23, 13:09   #3
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by henryzz 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

 2018-11-24, 08:33 #4 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 9,859 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 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
2018-11-27, 22:49   #5
Dr Sardonicus

Feb 2017
Nowhere

2×3×7×127 Posts

Quote:
 Originally Posted by LaurV 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."

 2018-11-28, 01:13 #6 Bobby Jacobs     May 2018 24310 Posts The sequence of record gaps between lucky numbers is very interesting. It is in OEIS.
 2018-11-28, 06:01 #7 CRGreathouse     Aug 2006 3·1,993 Posts
 2018-11-30, 04:46 #8 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 38D16 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.
 2018-12-11, 18:41 #9 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 11100011012 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 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)
2018-12-11, 19:08   #10
danaj

"Dana Jacobsen"
Feb 2011
Bangkok, TH

16158 Posts

Quote:
 Originally Posted by henryzz 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

2018-12-11, 19:30   #11
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by danaj 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

 Similar Threads Thread Thread Starter Forum Replies Last Post Bobby Jacobs Prime Gap Searches 52 2020-08-22 15:20 ewmayer Probability & Probabilistic Number Theory 0 2015-10-18 01:37 Dubslow Factoring 3 2014-10-19 19:10 WraithX GMP-ECM 4 2009-01-12 16:29 gd_barnes Riesel Prime Search 11 2007-06-27 04:12

All times are UTC. The time now is 05:11.

Mon Jan 17 05:11:20 UTC 2022 up 177 days, 23:40, 0 users, load averages: 2.06, 1.72, 1.36