cp's OEIS Frontend

A270877 Numbers surviving a decaying sieve.

%I A270877 #31 May 19 2023 14:18:21
%S A270877 1,2,4,5,6,8,13,16,17,19,22,23,24,27,28,29,32,34,38,39,40,41,42,44,49,
%T A270877 50,51,52,56,59,60,61,64,65,68,71,72,73,74,80,89,92,94,95,96,104,107,
%U A270877 109,113,116,118,128,131,134,137,139,142,149,151,155
%N A270877 Numbers surviving a decaying sieve.
%C A270877 In the normal sieve of Eratosthenes, for a given number p, we cross out all multiples of p; that is, p, p + p, p + p + p, ....  In this decaying sieve, we cross out p, p + (p-1), p + (p-1) + (p-2), ..., p + (p-1) + (p-2) + ... + 1 (a finite list of p numbers). The sequence gives those values which are not crossed out by a sum initiated by a lesser integer. They are the "primes" of this decaying sieve.
%C A270877 Geometrical interpretation: in the sieve of Eratosthenes, each surviving integer p can be seen as eliminating those numbers that enumerate a rectangular area dot pattern one side of which has length p. In this sieve, each surviving integer k eliminates each number that enumerates a trapezoidal area dot pattern (on a triangular grid) with longest side k, plus the limiting case of the triangular area dot pattern with side k (the k-th triangular number). - _Peter Munn_, Jan 05 2017
%C A270877 If such a pattern has m dots, the possible lengths (number of dots) for the longest side are the nonzero numbers that occur in row m of A286013 after the number m in column 1. Thus m is in this sequence if and only if none of the other numbers in row m of A286013 are in this sequence. - _Peter Munn_, Jun 18 2017
%H A270877 Sean A. Irvine, <a href="/A270877/b270877.txt">Table of n, a(n) for n = 1..5000</a>
%H A270877 Peter Munn, <a href="/A270877/a270877.jpg">Historical image of Fortran II source program listing</a>
%H A270877 <a href="/index/Si#sieve">Index entries for sequences generated by a sieve</a>
%F A270877 Lexicographically earliest sequence of positive integers such that for n >= 1, 1 <= m < n, k >= 1, A286013(a(n),k) <> a(m). - _Peter Munn_, Jun 19 2017
%e A270877 The sieve starts as follows. Initially no numbers are crossed out. Take a(1)=1 and cross it out. The next uncrossed number is 2, so a(2)=2. Now cross out 2 and 2+1. The next uncrossed number is 4, so a(3)=4. Then cross out 4, 4+3, 4+3+2, 4+3+2+1. The next uncrossed number is 5, and so on.
%t A270877 nn = 200; a = Range@ nn; Do[If[Length@a >= n, a = Complement[a, Function[k, Rest@ Map[Total, MapIndexed[Take[k, #] &, Range@ Max@ k]]]@ Reverse@ Range@ a[[n]]]], {n, 2, nn}]; a (* _Michael De Vlieger_, Mar 25 2016 *)
%o A270877 (Java)
%o A270877 int limit = 15707; //highest number in the sieve (inclusive)
%o A270877 boolean[] n = new boolean[limit + 1];
%o A270877 int index = 1;
%o A270877 for ( int i = 1; i < n.length; i++ ) {
%o A270877 if ( !n[i] ) {
%o A270877 System.out.println(index++ + " " + i);
%o A270877 int j = i, k = i;
%o A270877 while ( k + j - 1 < n.length && j > 0 ) {
%o A270877 k += --j;
%o A270877 n[k] = true;
%o A270877 }
%o A270877 }
%o A270877 }
%o A270877 // _Griffin N. Macris_, Mar 24 2016
%Y A270877 Cf. A281256 for tabulation of its runs of consecutive integers.
%Y A270877 Cf. A066680, A136259, A286013.
%K A270877 nonn,nice
%O A270877 1,2
%A A270877 _Sean A. Irvine_, Mar 24 2016
%E A270877 Essential qualification added to definition by _Peter Munn_, Jan 19 2017