This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000959 Lucky numbers.
(Formerly M2616 N1035)

%I M2616 N1035

%S 1,3,7,9,13,15,21,25,31,33,37,43,49,51,63,67,69,73,75,79,87,93,99,105,

%T 111,115,127,129,133,135,141,151,159,163,169,171,189,193,195,201,205,

%U 211,219,223,231,235,237,241,259,261,267,273,283,285,289,297,303

%N Lucky numbers.

%C An interesting general discussion of the phenomenon of 'random primes' (generalizing the lucky numbers) occurs in Hawkins (1958). Heyde (1978) proves that Hawkins' random primes do not only almost always satisfy the Prime Number Theorem but also the Riemann Hypothesis. - Alf van der Poorten, Jun 27 2002

%C Bui and Keating establish an asymptotic formula for the number of k-difference twin primes, and more generally to all l-tuples, of Hawkins primes, a probabilistic model of the Eratosthenes sieve. The formula for k = 1 was obtained by Wunderlich [Acta Arith. 26 (1974), 59 - 81]. - _Jonathan Vos Post_, Mar 24 2009. (This is quoted from the abstract of the Bui-Heating (2006) article, _Joerg Arndt_, Jan 04 2014)

%C It appears that a 1's line is formed, as in the Gilbreath's conjecture, if we use 2 (or 4), 3, 5 (differ of 7), 9, 13, 15, 21, 25, ... instead of A000959 1, 3, 7, 9, 13, 15, 21, 25, ... - _Eric Desbiaux_, Mar 25 2010

%C a(n) = A254967(n-1,n-1). - _Reinhard Zumkeller_, Feb 11 2015

%D Martin Gardner, Gardner's Workout, Chapter 21 "Lucky Numbers and 2187" pp. 149-156 A. K. Peters MA 2002.

%D Richard K. Guy, Unsolved Problems in Number Theory, C3.

%D C. S. Ogilvy, Tomorrow's Math. 2nd ed., Oxford Univ. Press, 1972, p. 99.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D M. L. Stein and P. R. Stein, Tables of the Number of Binary Decompositions of All Even Numbers Less Than 200,000 into Prime Numbers and Lucky Numbers. Report LA-3106, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Sep 1964.

%D David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, 114.

%H T. D. Noe, R. J. Mathar, and Hugo v. d. Sanden, <a href="/A000959/b000959.txt">Table of n, a(n) for n = 1..200000</a> (first 10000 terms from T. D. Noe. Terms up to 30981 by R. J. Mathar)

%H H. M. Bui, J. P. Keating, <a href="http://arxiv.org/abs/math/0607196">On twin primes associated with the Hawkins random sieve</a>, version 2, Mar 24, 2009. J. Number Theory 119 (2006), 284-296.

%H Vema Gardiner, R. Lazarus, N. Metropolis and S. Ulam, <a href="http://www.jstor.org/stable/3029719">On certain sequences of integers defined by sieves</a>, Math. Mag., 29 (1956), 117-122. doi:10.2307/3029719. ISSN 0025-570X. Zbl 0071.27002.

%H Martin Gardner, <a href="http://dx.doi.org/10.1007/BF03024427">Lucky numbers and 2187</a>, Math. Intellig., 19 (No. 2, 1997), 26-29.

%H David Hawkins, <a href="http://www.jstor.org/stable/3029322">The random sieve</a>, Math. Mag. 31 (1958), 1-3.

%H D. Hawkins and W. E. Briggs, <a href="http://www.jstor.org/stable/3029213">The lucky number theorem</a>, Math. Mag. 31 1958 81-84.

%H C. C. Heyde, <a href="http://dx.doi.org/10.1214/aop/1176995433">A Log Log Improvement to the Riemann Hypothesis for the Hawkins Random Sieve</a>, Ann. Probability, 6 (1978), 850-875.

%H Ivars Peterson, MathTrek, <a href="http://web.archive.org/web/20130401223634/http://www.maa.org/mathland/mathtrek1.html">Martin Gardner's Lucky Numbers</a> (archived on Archive.org)

%H Ivars Peterson, <a href="http://archive.wikiwix.com/cache/?url=http://www.sciencenews.org/sn_arc97/9_6_97/mathland.htm&amp;title=">Martin Gardner's Lucky Numbers</a> (archived on Wikiwix.com)

%H Popular Computing (Calabasas, CA), <a href="/A003309/a003309.pdf">Sieves: Problem 43</a>, Vol. 2 (No. 13, Apr 1974), pp. 6-7. This is Sieve #7. [Annotated and scanned copy]

%H Walter Schneider, <a href="http://web.archive.org/web/2004/www.wschnei.de/number-theory/lucky-numbers.html">Lucky Numbers</a>

%H Torsten Sillke, <a href="http://www.mathematik.uni-bielefeld.de/~sillke/SEQUENCES/series013">S. M. Ulam's Lucky Numbers</a>

%H Hugo van der Sanden, <a href="http://crypt.org/hv/maths/lucky_1e8.bz2">Lucky numbers up to 1e8</a>

%H G. Villemin's Almanach of Numbers, <a href="http://villemin.gerard.free.fr/Wwwgvmm/Iteration/Chanceux.htm">Nombre Chanceux</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LuckyNumber.html">Lucky number.</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Lucky_number">Lucky number</a>

%H David W. Wilson, <a href="/A000959/a000959.cpp.txt">Fast space-efficient sequence generating program in C++</a>

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%H <a href="/index/Si#sieve">Index entries for sequences generated by sieves</a> [From _Reinhard Zumkeller_, Oct 15 2008]

%F Start with the natural numbers. Delete every 2nd number, leaving 1 3 5 7 ...; the 2nd number remaining is 3, so delete every 3rd number, leaving 1 3 7 9 13 15 ...; now delete every 7th number, leaving 1 3 7 9 13 ...; now delete every 9th number; etc.

%F a(n) = A258207(n,n). [Where A258207 is a square array constructed from the numbers remaining after each step described above.] - _Antti Karttunen_, Aug 06 2015

%F Other identities:

%F A145649(a(n)) = 1; complement of A050505. - _Reinhard Zumkeller_, Oct 15 2008

%F From _Antti Karttunen_, Feb 26 2015: (Start)

%F For all n >= 1, A109497(a(n)) = n.

%F For all n >= 1, a(n) = A000040(n) + A032600(n).

%F For all n >= 2, a(n) = A255553(A000040(n)).

%F (End)

%p ## luckynumbers(n) returns all lucky numbers from 1 to n. ## Try n=10^5 just for fun. luckynumbers:=proc(n) local k, Lnext, Lprev; Lprev:=[$1..n]; for k from 1 do if k=1 or k=2 then Lnext:= map(w-> Lprev[w],remove(z -> z mod Lprev[2] = 0,[$1..nops(Lprev)])); if nops(Lnext)=nops(Lprev) then break fi; Lprev:=Lnext; else Lnext:= map(w-> Lprev[w],remove(z -> z mod Lprev[k] = 0,[$1..nops(Lprev)])); if nops(Lnext)=nops(Lprev) then break fi; Lprev:=Lnext; fi; od; return Lnext; end: # _Walter Kehowski_, Jun 05 2008

%p # Alternative

%p L:= [seq(2*i+1,i=0..10^3)]:

%p for n from 2 while n < nops(L) do

%p r:= L[n];

%p L:= subsop(seq(r*i=NULL,i=1..nops(L)/r),L);

%p od:

%p L; # _Robert Israel_, Nov 19 2014

%t luckies = 2*Range@200 - 1; f[n_] := Block[{k = luckies[[n]]}, luckies = Delete[luckies, Table[{k}, {k, k, Length@luckies, k}]]]; Do[f@n, {n, 2, 30}]; luckies (* _Robert G. Wilson v_, May 09 2006 *)

%t sieveMax = 10^6; luckies = Range[1, sieveMax, 2]; sieve[n_] := Module[{k = luckies[[n]]}, luckies = Delete[luckies, Table[{i}, {i, k, Length[luckies], k}]]]; n = 1; While[luckies[[n]] < Length[luckies], n++; sieve[n]]; luckies

%t L = Table[2*i + 1, {i, 0, 10^3}]; For[n = 2, n < Length[L], r = L[[n++]]; L = ReplacePart[L, Table[r*i -> Nothing, {i, 1, Length[L]/r}]]]; L (* _Jean-Fran├žois Alcover_, Mar 15 2016, after _Robert Israel_ *)

%o (Haskell)

%o a000959 n = a000959_list !! (n-1)

%o a000959_list = 1 : sieve 2 [1,3..] where

%o sieve k xs = z : sieve (k + 1) (lucky xs) where

%o z = xs !! (k - 1 )

%o lucky ws = us ++ lucky vs where

%o (us, _:vs) = splitAt (z - 1) ws

%o -- _Reinhard Zumkeller_, Dec 05 2011

%o (PARI) A000959(nMax)={my(v=vector(nMax,i,i),i,k);while(v[i=!k+k++]<=#v,v=vecextract(v,2^#v-1-sum(j=1,#v\v[i],2^(v[i]*j-1))));v} \\ _M. F. Hasler_, Sep 22 2013

%o (Python)

%o def lucky(n):

%o ...L=list(range(1, n+1,2)); j=1

%o ...while L[j] <= len(L)-1:

%o ......L=[L[i] for i in range(len(L)) if (i+1)%L[j]!=0]

%o ......j+=1

%o ...return(L)

%o _Robert FERREOL_, Nov 19 2014

%o (Scheme)

%o (define (A000959 n) ((rowfun_n_for_A000959sieve n) n)) ;; Code for rowfun_n_for_A000959sieve given in A255543.

%o ;; _Antti Karttunen_, Feb 26 2015

%Y Main diagonal of A258207.

%Y Column 1 of A255545. (cf. also arrays A255543, A255551).

%Y Cf. A050505 (complement).

%Y Cf. A145649 (characteristic function).

%Y Cf. A137164-A137185, A039672, A045954, A249876.

%Y Cf. A031883 (first differences), A254967 (iterated absolute differences), see also A054978.

%Y Cf. A109497 (works as an left inverse function).

%Y Cf. also A000040, A003309, A032600, A219178, A255553, A264940, A265859.

%K nonn,easy,nice,core

%O 1,2

%A _N. J. A. Sloane_; entry updated Mar 07 2008

%E Typo in Walter Kehowski's Maple program fixed by _Robert Israel_, Nov 19 2014

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 16 04:52 EST 2018. Contains 317252 sequences. (Running on oeis4.)