cp's OEIS Frontend

A108696 Generated by a sieve: see comments.

%I A108696 #17 Dec 10 2023 17:42:27
%S A108696 1,2,3,5,7,11,13,19,23,31,35,43,49,59,61,79,83,103,109,119,133,151,
%T A108696 155,175,193,211,215,241,259,275,283,323,331,361,373,403,419,443,455,
%U A108696 499,511,541,571,613,623,649,673,719,733,781,803,841,871,919
%N A108696 Generated by a sieve: see comments.
%C A108696 Start with the natural numbers:
%C A108696 1 2 3 4 5 6 7 8 9 10 11 ...
%C A108696 Accept the 2nd number, 2 and erase every 2nd number after it, giving:
%C A108696 1 2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 ...
%C A108696 Accept the 3rd number, 3 and erase every 3rd number after it, giving:
%C A108696 1 2 3 5 7 11 13 17 19 23 25 29 31 35 ...
%C A108696 Accept the 4th number, 5 and erase every 4th number after it, giving:
%C A108696 1 2 3 5 7 11 13 19 23 25 31 35 ...
%C A108696 Repeat!
%H A108696 Reinhard Zumkeller, <a href="/A108696/b108696.txt">Table of n, a(n) for n = 1..10000</a>
%H A108696 <a href="/index/Si#sieve">Index entries for sequences generated by sieves</a>
%o A108696 (Tcl) source /tclutils/utils.tcl
%o A108696 set l [range 0 10000]; set z z
%o A108696 for {set i 2} {$i*2 <= [llength $l]} {incr i} {
%o A108696 set k [expr {[llength $l]-1}]
%o A108696 set k [expr {$k - ($k % $i)}]
%o A108696 while {$k > $i} {
%o A108696 set l [lreplace $l $k $k]
%o A108696 incr k -$i
%o A108696 }
%o A108696 puts "after $i: length [llength $l], prefix [join [lrange $l 0 10] { }]"
%o A108696 }
%o A108696 (Haskell)
%o A108696 a108696 n = a108696_list !! (n-1)
%o A108696 a108696_list = 1 : sieve' 2 [2..] where
%o A108696    sieve' n (x:xs) = x : (sieve' (n+1) $ sieving xs) where
%o A108696       sieving xs = (take (n-1) xs) ++ (sieving $ drop n xs)
%o A108696 -- _Reinhard Zumkeller_, Jul 04 2011
%Y A108696 Equals A007952 + 2 or equally A002491(n) + 1.
%K A108696 nonn
%O A108696 1,2
%A A108696 _David Applegate_, Oct 11 2007