

A000960


Flavius Josephus's sieve: Start with the natural numbers; at the kth sieving step, remove every (k+1)st term of the sequence remaining after the (k1)st sieving step; iterate.
(Formerly M2636 N1048)


73



1, 3, 7, 13, 19, 27, 39, 49, 63, 79, 91, 109, 133, 147, 181, 207, 223, 253, 289, 307, 349, 387, 399, 459, 481, 529, 567, 613, 649, 709, 763, 807, 843, 927, 949, 1009, 1093, 1111, 1189, 1261, 1321, 1359, 1471, 1483, 1579, 1693, 1719, 1807, 1899, 1933, 2023
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

a(n) is never divisible by 2 or 5.  Thomas Anton, Nov 01 2018


REFERENCES

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. 4753.
Problems 107, 116, Nord. Mat. Tidskr. 5 (1957), 114116.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS



FORMULA

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.
To get nth term, start with n and successively round up to next 2 multiples of n1, n2, ..., 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
As in Paul D. Hanna's formula, start with n^2 and successively move down to the highest multiple of n1, n2, 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
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
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


EXAMPLE

Start with
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ... (A000027) and delete every second term, giving
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 ... (A005408) and delete every 3rd term, giving
1 3 7 9 13 15 19 21 25 27 ... (A056530) and delete every 4th term, giving
1 3 7 13 15 19 25 27 ... (A056531) and delete every 5th term, giving
.... Continue forever and what's left is the sequence.
(The array formed by these rows is A278492.)
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.


MAPLE

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


MATHEMATICA

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
f[n_] := Fold[ #2*Ceiling[ #1/#2 + 1] &, n, Reverse@Range[n  1]]; Array[f, 60] (* Robert G. Wilson v, Nov 05 2005 *)


PROG

(PARI) a(n)=local(A=n, D); for(i=1, n1, D=ni; A=D*ceil(A/D+1)); return(A) \\ Paul D. Hanna, Oct 10 2005
(Haskell)
a000960 n = a000960_list !! (n1)
a000960_list = sieve 1 [1..] where
sieve k (x:xs) = x : sieve (k+1) (flavius xs) where
flavius xs = us ++ flavius vs where (u:us, vs) = splitAt (k+1) xs
(Python)
def flavius(n):
L = list(range(1, n+1)); j=2
while j <= len(L):
L = [L[i] for i in range(len(L)) if (i+1)%j]
j+=1
return L
flavius(100)


CROSSREFS

Cf. A000012, A002491, A000959, A003309, A099259, A112557, A112558, A113742, A113743, A113744, A113745, A113746, A113747, A113748; A113749, A278484.
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).
Cf. A278169 (characteristic function).


KEYWORD

nonn,easy,nice


AUTHOR



EXTENSIONS



STATUS

approved



