%I M2636 N1048 #105 Jan 02 2023 12:30:46

%S 1,3,7,13,19,27,39,49,63,79,91,109,133,147,181,207,223,253,289,307,

%T 349,387,399,459,481,529,567,613,649,709,763,807,843,927,949,1009,

%U 1093,1111,1189,1261,1321,1359,1471,1483,1579,1693,1719,1807,1899,1933,2023

%N Flavius Josephus's sieve: Start with the natural numbers; at the k-th sieving step, remove every (k+1)-st term of the sequence remaining after the (k-1)-st sieving step; iterate.

%C a(n) is never divisible by 2 or 5. - _Thomas Anton_, Nov 01 2018

%D V. Brun, Un procédé qui ressemble au crible d'Eratosthène, Analele Stiintifice Univ. "Al. I. Cuza", Iasi, Romania, Sect. Ia Matematica, 1965, vol. 11B, pp. 47-53.

%D Problems 107, 116, Nord. Mat. Tidskr. 5 (1957), 114-116.

%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).

%H T. D. Noe, <a href="/A000960/b000960.txt">Table of n, a(n) for n = 1..10000</a>

%H M. E. Andersson, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa85/aa8542.pdf">Das Flaviussche Sieb</a>, Acta Arith., 85 (1998), 301-307.

%H L. Carlitz and Chr. U. Jansen, <a href="https://www.jstor.org/stable/24524630">Solution to Problem 115 and 116</a>, Nord. Mat. Tidskr. 5 (1957), 159-161.

%H V. 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 (1955), 117-119.

%H H. Killingbergtro, <a href="https://www.jstor.org/stable/24524554">Solution to Problem 107</a>, Nord. Mat. Tidskr. 5 (1957), 203-205.

%H D. Wilson et al., <a href="http://list.seqfan.eu/oldermail/seqfan/2016-November/thread.html">Interesting sequence</a>, SeqFan list, Nov. 2016

%H <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>

%H <a href="/index/Si#sieve">Index entries for sequences generated by sieves</a>

%F Let F(n) = number of terms <= n. Andersson, improving results of Brun, shows that F(n) = 2 sqrt(n/Pi) + O(n^(1/6)). Hence a(n) grows like Pi*n^2 / 4.

%F To get n-th term, start with n and successively round up to next 2 multiples of n-1, n-2, ..., 1 (compare to Mancala sequence A002491). E.g.: to get 11th term: 11->30->45->56->63->72->80->84->87->90->91; i.e., start with 11, successively round up to next 2 multiples of 10, 9, .., 1. - _Paul D. Hanna_, Oct 10 2005

%F As in Paul D. Hanna's formula, start with n^2 and successively move down to the highest multiple of n-1, n-2, etc., smaller than your current number: 121 120 117 112 105 102 100 96 93 92 91, so a(11) = 91, from moving down to multiples of 10, 9, ..., 1. - _Joshua Zucker_, May 20 2006

%F Or, similarly for n = 5, begin with 25, down to a multiple of 4 = 24, down to a multiple of 3 = 21, then to a multiple of 2 = 20 and finally to a multiple of 1 = 19, so a(5) = 19. - _Joshua Zucker_, May 20 2006

%F This formula arises in A119446; the leading term of row k of that triangle = a(prime(k)/k) from this sequence. - _Joshua Zucker_, May 20 2006

%F a(n) = 2*A073359(n-1) + 1, cf. link to posts on the SeqFan list. - _M. F. Hasler_, Nov 23 2016

%F a(n) = 1 + A278484(n-1). - _Antti Karttunen_, Nov 23 2016, after _David W. Wilson_'s posting on SeqFan list Nov 22 2016

%e Start with

%e 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ... (A000027) and delete every second term, giving

%e 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 ... (A005408) and delete every 3rd term, giving

%e 1 3 7 9 13 15 19 21 25 27 ... (A056530) and delete every 4th term, giving

%e 1 3 7 13 15 19 25 27 ... (A056531) and delete every 5th term, giving

%e .... Continue forever and what's left is the sequence.

%e (The array formed by these rows is A278492.)

%e For n = 5, 5^2 = 25, go down to a multiple of 4 giving 24, then to a multiple of 3 = 21, then to a multiple of 2 = 20, then to a multiple of 1 = 19, so a(5) = 19.

%p S[1]:={seq(i,i=1..2100)}: for n from 2 to 2100 do S[n]:=S[n-1] minus {seq(S[n-1][n*i],i=1..nops(S[n-1])/n)} od: A:=S[2100]; # _Emeric Deutsch_, Nov 17 2004

%t del[lst_, k_] := lst[[Select[Range[Length[lst]], Mod[ #, k] != 0 &]]]; For[k = 2; s = Range[2100], k <= Length[s], k++, s = del[s, k]]; s

%t f[n_] := Fold[ #2*Ceiling[ #1/#2 + 1] &, n, Reverse@Range[n - 1]]; Array[f, 60] (* _Robert G. Wilson v_, Nov 05 2005 *)

%o (PARI) a(n)=local(A=n,D);for(i=1,n-1,D=n-i;A=D*ceil(A/D+1));return(A) \\ _Paul D. Hanna_, Oct 10 2005

%o (Haskell)

%o a000960 n = a000960_list !! (n-1)

%o a000960_list = sieve 1 [1..] where

%o sieve k (x:xs) = x : sieve (k+1) (flavius xs) where

%o flavius xs = us ++ flavius vs where (u:us,vs) = splitAt (k+1) xs

%o -- _Reinhard Zumkeller_, Oct 31 2012

%o (Python)

%o def flavius(n):

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

%o while j <= len(L):

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

%o j+=1

%o return L

%o flavius(100)

%o # _Robert FERREOL_, Nov 08 2015

%Y Cf. A056526, A056530, A056531, A100002, A190732, A003881.

%Y Cf. A000012, A002491, A000959, A003309, A099259, A112557, A112558, A113742, A113743, A113744, A113745, A113746, A113747, A113748; A113749, A278484.

%Y Cf. A119446 for triangle whose leading diagonal is A119447 and this sequence gives all possible values for A119447 (except A119447 cannot equal 1 because prime(n)/n is never 1).

%Y Cf. A100617 (a left inverse), A100618.

%Y Cf. A278169 (characteristic function).

%Y Main diagonal of A278492, leftmost column of A278505, positions of zeros in A278528 & A278529.

%K nonn,easy,nice

%O 1,2

%A _N. J. A. Sloane_

%E More terms and better description from _Henry Bottomley_, Jun 16 2000

%E Entry revised by _N. J. A. Sloane_, Nov 13 2004

%E More terms from _Paul D. Hanna_, Oct 10 2005