A056530 -id:A056530 - cp's OEIS frontend

A056531 Sequence remaining after a fourth round of Flavius Josephus sieve; remove every fifth term of A056530.

1, 3, 7, 13, 19, 25, 27, 31, 39, 43, 49, 51, 61, 63, 67, 73, 79, 85, 87, 91, 99, 103, 109, 111, 121, 123, 127, 133, 139, 145, 147, 151, 159, 163, 169, 171, 181, 183, 187, 193, 199, 205, 207, 211, 219, 223, 229, 231, 241, 243, 247, 253, 259, 265, 267, 271, 279

Offset: 1

Henry Bottomley, Jun 19 2000

Numbers {1, 3, 7, 13, 19, 25, 27, 31, 39, 43, 49, 51} mod 60.

Index entries for sequences related to the Josephus Problem
Index entries for linear recurrences with constant coefficients, signature (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1).

Compare A000027 for 0 rounds of sieve, A005408 after 1 round of sieve, A047241 after 2 rounds, A056530 after 3 rounds, A056531 after 4 rounds, A000960 after all rounds.

After n rounds the remaining sequence comprises A002944(n) numbers mod A003418(n+1), i.e. 1/(n+1) of them.

LinearRecurrence[{1,0,0,0,0,0,0,0,0,0,0,1,-1},{1,3,7,13,19,25,27,31,39,43,49,51,61},60] (* Harvey P. Dale, Mar 11 2019 *)

From Chai Wah Wu, Jul 24 2016: (Start)
a(n) = a(n-1) + a(n-12) - a(n-13) for n > 13.
G.f.: x*(9*x^12 + 2*x^11 + 6*x^10 + 4*x^9 + 8*x^8 + 4*x^7 + 2*x^6 + 6*x^5 + 6*x^4 + 6*x^3 + 4*x^2 + 2*x + 1)/(x^13 - x^12 - x + 1). (End)

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.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane

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

			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.

V. Brun, Un procédé qui ressemble au crible d'Ératosthène, Analele Stiintifice Univ. "Al. I. Cuza", Iasi, Romania, Sect. Ia Matematica, 1965, vol. 11B, pp. 47-53.
Problems 107, 116, Nord. Mat. Tidskr. 5 (1957), 114-116.
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).

T. D. Noe, Table of n, a(n) for n = 1..10000
M. E. Andersson, Das Flaviussche Sieb, Acta Arith., 85 (1998), 301-307.
L. Carlitz and Chr. U. Jansen, Solution to Problem 115 and 116, Nord. Mat. Tidskr. 5 (1957), 159-161.
V. Gardiner, R.Lazarus, N. Metropolis and S. Ulam, On certain sequences of integers defined by sieves, Math. Mag., 29 (1955), 117-119.
H. Killingbergtro, Solution to Problem 107, Nord. Mat. Tidskr. 5 (1957), 203-205.
D. Wilson et al., Interesting sequence, SeqFan list, Nov. 2016
Index entries for sequences related to the Josephus Problem
Index entries for sequences generated by sieves

Cf. A056526, A056530, A056531, A100002, A190732, A003881.
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. A100617 (a left inverse), A100618.
Cf. A278169 (characteristic function).
Main diagonal of A278492, leftmost column of A278505, positions of zeros in A278528 & A278529.

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

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

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 *)

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

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)
# Robert FERREOL, Nov 08 2015

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 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 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
a(n) = 2*A073359(n-1) + 1, cf. link to posts on the SeqFan list. - M. F. Hasler, Nov 23 2016
a(n) = 1 + A278484(n-1). - Antti Karttunen, Nov 23 2016, after David W. Wilson's posting on SeqFan list Nov 22 2016

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

A054995 A version of Josephus problem: a(n) is the surviving integer under the following elimination process. Arrange 1,2,3,...,n in a circle, increasing clockwise. Starting with i=1, delete the integer two places clockwise from i. Repeat, counting two places from the next undeleted integer, until only one integer remains.

Original entry on oeis.org

1, 2, 2, 1, 4, 1, 4, 7, 1, 4, 7, 10, 13, 2, 5, 8, 11, 14, 17, 20, 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 1, 4, 7, 10, 13, 16, 19, 22, 25

Offset: 1

John W. Layman, May 30 2000

nonn

If one counts only one place (rather than two) at each stage to determine the element to be deleted, the Josephus survivors (A006257) are obtained.

			a(5) = 4 because the elimination process gives (1^,2,3,4,5) -> (1,2,4^,5) -> (2^,4,5) -> (2^,4) -> (4), where ^ denotes the counting reference position.
a(13) = 13 => a(14) = (a(13) + 2) mod 14 + 1 = 2. - _Paul Weisenhorn_, Oct 10 2010

Arkadiusz Wesolowski, Table of n, a(n) for n = 1..10000
R. Baumann, Das Josephus-Problem, LOG IN, Heft Nr. 165, pp. 70-71, 2010 (in German).
Ph. Dumas, Algebraic aspects of B-regular series. [Broken link]
Philippe Dumas, Algebraic aspects of B-regular series, Research Report, RR-1931, INRIA, 1993.
Ph. Dumas, Algebraic aspects of B-regular series, in: International Colloquium on Automata, Languages and Programming, ICALP 1993 (A. Lingas, R. Karlsson, S. Carlsson, eds.), pp. 457-468, Lecture Notes in Computer Science, vol. 700, Springer, Berlin, 1993.
L. Halbeisen and N. Hungerbühler, The Josephus Problem, J. Théor. Nombres Bordeaux 9 (1997), no. 2, 303-318.
Alasdair MacFhraing, Aireamh Muinntir Fhinn Is Dhubhain, Agus Sgeul Josephuis Is An Da Fhichead Iudhaich, [Gaelic with English summary], Proc. Royal Irish Acad., Vol. LII, Sect. A., No. 7, 1948, 87-93.
A. M. Odlyzko and H. S. Wilf, Functional iteration and the Josephus problem, Glasgow Math. J. 33, 235-240, 1991.
Index entries for sequences related to the Josephus Problem

Cf. A032434, A005427, A005428, A006257, A007495, A000960, A056530.

Cf. A181281 (with s=5). - Paul Weisenhorn, Oct 10 2010

(* First do *) Needs["Combinatorica`"] (* then *) f[n_] := Last@ InversePermutation@ Josephus[n, 3]; Array[f, 70] (* Robert G. Wilson v, Jul 31 2010 *)
Table[Nest[Rest@RotateLeft[#, 2] &, Range[n], n - 1], {n, 72}] // Flatten (* Arkadiusz Wesolowski, Jan 14 2013 *)

a(n) = 3*n + 1 - floor(K(3)*(3/2)^(ceiling(log((2*n+1)/K(3))/log(3/2)))) where K(3) = (3/2)*K = 1.622270502884767... (K is the constant described in A061419); a(n) = 3n + 1 - A061419(k+1) where A061419(k+1) is the least integer such that A061419(k+1) > 2n.
a(1) = 1 and, for n > 1, a(n) = (a(n-1) + 3) mod n, if this value is nonzero, n otherwise.
a(n) = (a(n-1) + 2) mod n + 1. - Paul Weisenhorn, Oct 10 2010

A088333 A version of Josephus problem: a(n) is the surviving integer under the following elimination process. Arrange 1,2,3,...,n in a circle, increasing clockwise. Starting with i=1, delete the integer 3 places clockwise from i. Repeat, counting 3 places from the next undeleted integer, until only one integer remains.

Original entry on oeis.org

1, 1, 2, 2, 1, 5, 2, 6, 1, 5, 9, 1, 5, 9, 13, 1, 5, 9, 13, 17, 21, 3, 7, 11, 15, 19, 23, 27, 2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63, 67, 2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42

Offset: 1

N. J. A. Sloane, Nov 13 2003

If one counts only one place (resp. two places) at each stage to determine the element to be deleted, we get A006257 (resp. A054995).

See A054995 for references and links.

Index entries for sequences related to the Josephus Problem

Cf. A006257, A054995, A032434, A005427, A005428, A006257, A007495, A000960, A056530.

It is tempting (in view of A054995) to conjecture that a(1)=1 and, for n>1, a(n) = (a(n-1)+4) mod n. The conjecture is false; counterexample: a(21)=21; a(20)=17; (a(20)+4)mod 21=0; corrected formula: a(n)=(a(n-1)+3) mod n +1;
The conjecture is true. After removing the 4th number, we are reduced to the n-1 case, but starting with 5 instead of 1. - David Wasserman, Aug 08 2005
a(n) = A032434(n,4) if n>=4. - R. J. Mathar, May 04 2007

More terms from David Wasserman, Aug 08 2005

A278492 Square array where row n (n >= 0) gives the numbers remaining after the n-th round of the Flavius sieve, read by descending antidiagonals.

Original entry on oeis.org

1, 2, 1, 3, 3, 1, 4, 5, 3, 1, 5, 7, 7, 3, 1, 6, 9, 9, 7, 3, 1, 7, 11, 13, 13, 7, 3, 1, 8, 13, 15, 15, 13, 7, 3, 1, 9, 15, 19, 19, 19, 13, 7, 3, 1, 10, 17, 21, 25, 25, 19, 13, 7, 3, 1, 11, 19, 25, 27, 27, 27, 19, 13, 7, 3, 1, 12, 21, 27, 31, 31, 31, 27, 19, 13, 7, 3, 1, 13, 23, 31, 37, 39, 39, 39, 27, 19, 13, 7, 3, 1

Offset: 0

Antti Karttunen, Nov 23 2016, after David W. Wilson's posting on SeqFan-list Nov 22 2016

The terms of square array A(row,col) are read by descending antidiagonals as A(0,0), A(0,1), A(1,0), A(0,2), A(1,1), A(2,0), ...

			The top left corner of the array:
1, 2, 3,  4,  5,  6,  7,  8,  9, 10 (row 0: start from A000027)
1, 3, 5,  7,  9, 11, 13, 15, 17, 19 (after the 1st round, A005408 remain)
1, 3, 7,  9, 13, 15, 19, 21, 25, 27 (after the 2nd, A047241)
1, 3, 7, 13, 15, 19, 25, 27, 31, 37
1, 3, 7, 13, 19, 25, 27, 31, 39, 43
1, 3, 7, 13, 19, 27, 31, 39, 43, 49
1, 3, 7, 13, 19, 27, 39, 43, 49, 61
1, 3, 7, 13, 19, 27, 39, 49, 61, 63
1, 3, 7, 13, 19, 27, 39, 49, 63, 67
1, 3, 7, 13, 19, 27, 39, 49, 63, 79

Antti Karttunen, Table of n, a(n) for n = 0..10439; the first 144 antidiagonals of the array
D. Wilson et al., Interesting sequence, SeqFan list, Nov. 2016
Index entries for sequences generated by sieves
Index entries for sequences related to the Josephus Problem

One more than A278482.
Transpose: A278493.
Rows: A000027, A005408, A047241, A056530, A056531.
Main diagonal: A000960.
Cf. A278507 (the numbers removed at each round).
Similarly constructed arrays for other sieves: A258207, A260717.

(define (A278492 n) (A278492bi (A002262 n) (A025581 n)))
(define (A278492bi row col) (+ 1 (A278482bi row col)))

A(n,k) = 1 + A278482(n,k).

A104177 A variation on Flavius's sieve (A000960): Start with the natural numbers; at the k-th sieving step, remove every f-th term of the sequence remaining after the (k-1)-st sieving step, where f is the (k+2)-nd Fibonacci number, f=F(k+2); iterate.

Original entry on oeis.org

1, 3, 7, 9, 15, 19, 21, 31, 33, 37, 39, 45, 51, 61, 63, 67, 69, 75, 79, 81, 93, 97, 99, 109, 111, 121, 123, 127, 129, 135, 139, 141, 151, 157, 165, 169, 171, 181, 183, 189, 195, 199, 201, 211, 213, 219, 225, 229, 231, 241, 243, 247, 249, 255, 261, 271, 277, 279

Offset: 1

Tyler D. Rick (tyler.rick(AT)does.not.want.spam.com), Mar 11 2005

This sequence is approximately as dense as the lucky numbers or primes: there are 195 of these numbers, 153 lucky numbers and 168 primes less than 1000.

			Start with
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ... (A000027)
First sieving step: Delete every 2nd term (2=F(1+2)), giving
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 ... (A005408)
2nd sieving step: Delete every 3rd term (3=F(2+2)), giving
1 3 7 9 13 15 19 21 25 27 31 ... (A056530)
3rd sieving step: Delete every 5th (5=F(3+2)) term, giving
1 3 7 9 15 19 21 25 31 ...
4th sieving step: Delete every 8th (8=F(4+2)) term, giving
1 3 7 9 15 19 21 31 ...
Continue forever and whatever remains is the sequence.

Index entries for sequences related to the Josephus Problem

Cf. A000960, A000959, A099204, A000045.

cp's OEIS Frontend

A056531 Sequence remaining after a fourth round of Flavius Josephus sieve; remove every fifth term of A056530.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A278492 Square array where row n (n >= 0) gives the numbers remaining after the n-th round of the Flavius sieve, read by descending antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Scheme

Formula

A104177 A variation on Flavius's sieve (A000960): Start with the natural numbers; at the k-th sieving step, remove every f-th term of the sequence remaining after the (k-1)-st sieving step, where f is the (k+2)-nd Fibonacci number, f=F(k+2); iterate.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs