|
| |
|
|
A000960
|
|
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.
(Formerly M2636 N1048)
|
|
52
|
|
|
|
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
|
|
|
REFERENCES
|
M. E. Andersson, Das Flaviussche Sieb, Acta Arith., 85 (1998), 301-307.
V. Brun, Un proc\'{e}d\'{e} qui ressemble au crible d'Eratosthene, Analele Stiintifice Univ. "Al. I. Cuza", Iasi, Romania, Sect. Ia Matematica, 1965, vol. 11B, pp. 47-53.
L. Carlitz, Solution to Problem 115, Nord. Mat. Tidskr. 5 (1957), 159-160.
V. Gardiner, R. Lazarus, N. Metropolis and S. Ulam, On certain sequences of integers defined by sieves, Math. Mag., 29 (1955), 117-119.
Problems 107, 116, Solutions, Nord. Mat. Tidskr. 5 (1957), 114-116, 160-161 and 203-205.
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
|
T. D. Noe, Table of n, a(n) for n=1..10000
Index entries for sequences generated by sieves
|
|
|
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 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 11-th 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 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
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 for ever and what's left is the sequence.
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[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)
|
|
|
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] (from Robert G. Wilson v, Nov 05 2005)
|
|
|
PROG
|
(PARI) a(n)=local(A=n, D); for(i=1, n-1, D=n-i; A=D*ceil(A/D+1)); return(A) (Hanna)
(Haskell)
a000960 n = a000960_list !! (n-1)
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
-- Reinhard Zumkeller, Oct 31 2012
|
|
|
CROSSREFS
|
Cf. A056526, A056530, A056531, A100002.
Cf. A000012, A002491, A000960, A112557, A112558, A113742, A113743, A113744, A113745, A113746, A113747, A113748; A113749.
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).
Sequence in context: A202117 A100458 A193765 * A147614 A171747 A031215
Adjacent sequences: A000957 A000958 A000959 * A000961 A000962 A000963
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
EXTENSIONS
|
More terms and better description from Henry Bottomley, Jun 16 2000
Entry revised by N. J. A. Sloane, Nov 13 2004.
More terms from Paul D. Hanna, Oct 10 2005
|
|
|
STATUS
|
approved
|
| |
|
|
