cp's OEIS Frontend

A000959 Lucky numbers.

%I A000959 M2616 N1035 #233 Jul 27 2025 18:06:03
%S A000959 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 A000959 111,115,127,129,133,135,141,151,159,163,169,171,189,193,195,201,205,
%U A000959 211,219,223,231,235,237,241,259,261,267,273,283,285,289,297,303
%N A000959 Lucky numbers.
%C A000959 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 A000959 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-Keating (2006) article, _Joerg Arndt_, Jan 04 2014)
%C A000959 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 A000959 The Mersenne primes 2^p - 1 (= A000668, p in A000043) are in this sequence for p = 2, 3, 5, 7, 13, 17, and 19, but not for the following exponents p = 31, 61, and 89. - _M. F. Hasler_, May 06 2025
%D A000959 Martin Gardner, Gardner's Workout, Chapter 21 "Lucky Numbers and 2187" pp. 149-156 A. K. Peters MA 2002.
%D A000959 Richard K. Guy, Unsolved Problems in Number Theory, C3.
%D A000959 C. S. Ogilvy, Tomorrow's Math. 2nd ed., Oxford Univ. Press, 1972, p. 99.
%D A000959 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000959 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A000959 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 A000959 James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 116.
%D A000959 David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, 114.
%H A000959 Hugo van der Sanden, <a href="/A000959/b000959.txt">Table of n, a(n) for n = 1..200000</a> (terms 1..10000 from T. D. Noe, terms 10001..30981 from R. J. Mathar)
%H A000959 José Juan Barco, <a href="/A000959/a000959.c.txt">Highly efficient C implementation with O(n log n) time and O(n) space (n bits) using hierarchical Fenwick trees and bitmaps to optimize memory access. Based on: J. Bille, I. Larsen, I. L. Gørtz et al., "Succinct Partial Sums and Fenwick Trees," ESA 2017.</a>
%H A000959 José Juan Barco, <a href="/A000959/a000959.hs.txt">Very fast O(n log n) sequence generating program in Haskell</a>
%H A000959 H. M. Bui and J. P. Keating, <a href="https://doi.org/10.1016/j.jnt.2005.11.015">On twin primes associated with the Hawkins random sieve</a>, J. Number Theory 119(2) (2006), 284-296.
%H A000959 H. M. Bui and J. P. Keating, <a href="http://arxiv.org/abs/math/0607196">On twin primes associated with the Hawkins random sieve</a>, arXiv:math/0607196 [math.NT], 2006-2010.
%H A000959 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; Zbl 0071.27002.
%H A000959 Martin Gardner, <a href="http://dx.doi.org/10.1007/BF03024427">Lucky numbers and 2187</a>, Math. Intellig., 19(2) (1997), 26-29.
%H A000959 David Hawkins, <a href="http://www.jstor.org/stable/3029322">The random sieve</a>, Math. Mag. 31 (1958), 1-3.
%H A000959 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 A000959 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 A000959 Ivars Peterson and 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 A000959 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 A000959 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 A000959 Walter Schneider, <a href="http://web.archive.org/web/20070509185315/http://www.wschnei.de/number-theory/lucky-numbers.html">Lucky Numbers</a>, personal web site "Mathews: the Archive of Recreational Mathematics" (no more available: snapshot on web.archive.org as of May 2007), updated Dec 24, 2002.
%H A000959 Torsten Sillke, <a href="http://www.mathematik.uni-bielefeld.de/~sillke/SEQUENCES/series013">S. M. Ulam's Lucky Numbers</a>
%H A000959 Hugo van der Sanden, <a href="http://crypt.org/hv/maths/lucky_1e8.bz2">Lucky numbers up to 1e8</a>. [Broken link]
%H A000959 G. Villemin's Almanach of Numbers, <a href="http://villemin.gerard.free.fr/Wwwgvmm/Iteration/Chanceux.htm">Nombre Chanceux</a>.
%H A000959 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/LuckyNumber.html">Lucky number</a>.
%H A000959 Wikipedia, <a href="http://en.wikipedia.org/wiki/Lucky_number">Lucky number</a>.
%H A000959 David W. Wilson, <a href="/A000959/a000959.txt">Fast space-efficient sequence generating program in C++</a>.
%H A000959 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%H A000959 <a href="/index/Lu#lucky_numbers">Index entries for sequences related to lucky numbers</a>
%H A000959 <a href="/index/Si#sieve">Index entries for sequences generated by sieves</a> [From _Reinhard Zumkeller_, Oct 15 2008]
%F A000959 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 A000959 a(n) = A254967(n-1, n-1). - _Reinhard Zumkeller_, Feb 11 2015
%F A000959 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 A000959 A145649(a(n)) = 1; complement of A050505. - _Reinhard Zumkeller_, Oct 15 2008
%F A000959 Other identities from _Antti Karttunen_, Feb 26 2015: (Start)
%F A000959 For all n >= 1, A109497(a(n)) = n.
%F A000959 For all n >= 1, a(n) = A000040(n) + A032600(n).
%F A000959 For all n >= 2, a(n) = A255553(A000040(n)). (End)
%p A000959 ## 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; typo fixed by _Robert Israel_, Nov 19 2014
%p A000959 # Alternative
%p A000959 A000959List := proc(mx) local i, L, n, r;
%p A000959 L:= [seq(2*i+1, i=0..mx)]:
%p A000959 for n from 2 while n < nops(L) do
%p A000959   r:= L[n];
%p A000959   L:= subsop(seq(r*i=NULL, i=1..nops(L)/r), L);
%p A000959 od: L end:
%p A000959 A000959List(10^3); # _Robert Israel_, Nov 19 2014
%t A000959 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 A000959 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 A000959 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 A000959 (Haskell)
%o A000959 a000959 n = a000959_list !! (n-1)
%o A000959 a000959_list =  1 : sieve 2 [1,3..] where
%o A000959    sieve k xs = z : sieve (k + 1) (lucky xs) where
%o A000959       z = xs !! (k - 1 )
%o A000959       lucky ws = us ++ lucky vs where
%o A000959             (us, _:vs) = splitAt (z - 1) ws
%o A000959 -- _Reinhard Zumkeller_, Dec 05 2011
%o A000959 (Haskell) -- Also see links.
%o A000959 (C++) // See Wilson link, Nov 14 2012
%o A000959 (PARI) A000959_upto(nMax)={my(v=vectorsmall(nMax\2,k,2*k-1),i=1,q);while(v[i++]<=#v,v=vecextract(v,2^#v-1-(q=1<<v[i])^(#v\v[i])\(q-1)<<(v[i]-1) ));v} \\ _M. F. Hasler_, Sep 22 2013, improved Jan 20 2020
%o A000959 (Python)
%o A000959 def lucky(n):
%o A000959     L = list(range(1, n + 1, 2))
%o A000959     j = 1
%o A000959     while j <= len(L) - 1 and L[j] <= len(L):
%o A000959         del L[L[j]-1::L[j]]
%o A000959         j += 1
%o A000959     return L
%o A000959 # _Robert FERREOL_, Nov 19 2014, corrected by _F. Chapoton_, Mar 29 2020, performance improved by _Ely Golden_, Aug 18 2022
%o A000959 (Scheme)
%o A000959 (define (A000959 n) ((rowfun_n_for_A000959sieve n) n)) ;; Code for rowfun_n_for_A000959sieve given in A255543.
%o A000959 ;; _Antti Karttunen_, Feb 26 2015
%Y A000959 Main diagonal of A258207.
%Y A000959 Column 1 of A255545. (cf. also arrays A255543, A255551).
%Y A000959 Cf. A050505 (complement).
%Y A000959 Cf. A145649 (characteristic function).
%Y A000959 Cf. A137164-A137185, A039672, A045954, A249876.
%Y A000959 Cf. A031883 (first differences), A254967 (iterated absolute differences), see also A054978.
%Y A000959 Cf. A109497 (works as a left inverse function).
%Y A000959 The Gilbreath transform is A054978 - see also A362460, A362461, A362462.
%Y A000959 Cf. also A000040, A003309, A032600, A219178, A255553, A264940, A265859.
%K A000959 nonn,easy,nice,core
%O A000959 1,2
%A A000959 _N. J. A. Sloane_; entry updated Mar 07 2008