A136119 Limiting sequence when we start with the positive integers (A000027) and delete in step n >= 1 the term at position n + a(n).

1, 3, 4, 5, 7, 8, 10, 11, 13, 14, 15, 17, 18, 20, 21, 22, 24, 25, 27, 28, 29, 31, 32, 34, 35, 37, 38, 39, 41, 42, 44, 45, 46, 48, 49, 51, 52, 54, 55, 56, 58, 59, 61, 62, 63, 65, 66, 68, 69, 71, 72, 73, 75, 76, 78, 79, 80, 82, 83, 85, 86, 87, 89, 90, 92, 93, 95, 96, 97, 99, 100

Offset

1,2

Comments

Apparently a(n) = A001953(n-1)+1 = floor((n-1/2)*sqrt(2))+1 (confirmed for n < 20000) and a(n+1) - a(n) = A001030(n). From the definitions these conjectures are by no means obvious. Can they be proved? - Klaus Brockhaus, Apr 15 2008 [For an affirmative answer, see the Cloitre link.]

This is the s(n)-Wythoff sequence for s(n)=2n-1; see A184117 for the definition. Complement of A184119. - Clark Kimberling, Jan 09 2011

References

B. Cloitre, The golden sieve, preprint 2008

Links

Alois P. Heinz, Table of n, a(n) for n = 1..1000

D. X. Charles, Sieve Methods, July 2000, University of Wisconsin.

Benoit Cloitre, On the proof of Klaus Brockhaus's conjectures

R. Eismann, Decomposition of natural numbers into weight X level + jump and application to a new classification of prime numbers, arXiv:0711.0865 [math.NT], 2007-2010.

M. C. Wunderlich, A general class of sieve generated sequences, Acta Arithmetica XVI,1969, pp.41-56.

Index entries for sequences generated by sieves

Formula

a(n) = ceiling((n-1/2)*sqrt(2)). This can be proved in the same way as the formula given for A099267. There are some generalizations. For instance, it is possible to consider "a(n)+K*n" instead of "a(n)+n" for deleting terms where K=0,1,2,... is fixed. The constant involved in the Beatty sequence for the sequence of deleted terms then depends on K and equals (K + 1 + sqrt((K+1)^2 + 4))/2. K=0 is related to A099267. 1+A001954 is the complement sequence of this sequence A136119. - Benoit Cloitre, Apr 18 2008

a(n) = floor(1 + 2*sqrt(T(n-1))), with triangular numbers T(). - Ralf Steiner, Oct 23 2019

Lim_{n->inf}(a(n)/(n - 1)) = sqrt(2), with {a(n)/(n - 1)} decreasing. - Ralf Steiner, Oct 24 2019

Example

First few steps are:
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,...
n = 1; delete term at position 1+a(1) = 2: 2;
1,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,...
n = 2; delete term at position 2+a(2) = 5: 6;
1,3,4,5,7,8,9,10,11,12,13,14,15,16,17,18,19,20,...
n = 3; delete term at position 3+a(3) = 7: 9;
1,3,4,5,7,8,10,11,12,13,14,15,16,17,18,19,20,...
n = 4; delete term at position 4+a(4) = 9: 12;
1,3,4,5,7,8,10,11,13,14,15,16,17,18,19,20,...
n = 5; delete term at position 5+a(5) = 12: 16;
1,3,4,5,7,8,10,11,13,14,15,17,18,19,20,...
n = 6; delete term at position 6+a(6) = 14: 19;
1,3,4,5,7,8,10,11,13,14,15,17,18,20,...

Mathematica

f[0] = Range[100]; f[n_] := f[n] = Module[{pos = n + f[n-1][[n]]}, If[pos > Length[f[n-1]], f[n-1], Delete[f[n-1], pos]]]; f[1]; f[n = 2]; While[f[n] != f[n-1], n++]; f[n] (* Jean-François Alcover, May 08 2019 *)
T[n_] := n (n + 1)/2; Table[1 + 2 Sqrt[T[n-1]] , {n, 1, 71}] // Floor (* Ralf Steiner, Oct 23 2019 *)

Prog

(Haskell)
import Data.List (delete)
a136119 n = a136119_list !! (n-1)
a136119_list = f [1..] where
   f zs@(y:xs) = y : f (delete (zs !! y) xs)
-- Reinhard Zumkeller, May 17 2014
(Magma) [Ceiling((n-1/2)*Sqrt(2)): n in [1..100]]; // Vincenzo Librandi, Jul 01 2019
(PARI) apply( {A136119(n)=sqrtint(n*(n-1)*2)+1}, [1..99]) \\ M. F. Hasler, Jul 04 2022

Crossrefs

Cf. A000027, A001953 (floor((n+1/2)*sqrt(2))), A001030 (fixed under 1 -> 21, 2 -> 211), A136110, A137292.

Cf. A000959, A099267.

Cf. A242535.

Cf. A000217 (T).

Sequence in context: A184620 A039043 A116591 * A184618 A110882 A186499

Adjacent sequences: A136116 A136117 A136118 * A136120 A136121 A136122

Keyword

easy,nonn

Author

Ctibor O. Zizka, Mar 16 2008

Extensions

Edited and extended by Klaus Brockhaus, Apr 15 2008

An incorrect g.f. removed by Alois P. Heinz, Dec 14 2012

Status

approved