A270877 Numbers surviving a decaying sieve.

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, 50, 51, 52, 56, 59, 60, 61, 64, 65, 68, 71, 72, 73, 74, 80, 89, 92, 94, 95, 96, 104, 107, 109, 113, 116, 118, 128, 131, 134, 137, 139, 142, 149, 151, 155

Offset: 1

Author

Sean A. Irvine, Mar 24 2016

Keywords

• nonn
• nice

Comments

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.

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

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

Examples

			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.
		

Links

• Sean A. Irvine, Table of n, a(n) for n = 1..5000
• Peter Munn, Historical image of Fortran II source program listing
• Index entries for sequences generated by a sieve

Crossrefs

Cf. A281256 for tabulation of its runs of consecutive integers.

Cf. A066680, A136259, A286013.

Programs

Java

int limit = 15707; //highest number in the sieve (inclusive)
boolean[] n = new boolean[limit + 1];
int index = 1;
for ( int i = 1; i < n.length; i++ ) {
if ( !n[i] ) {
System.out.println(index++ + " " + i);
int j = i, k = i;
while ( k + j - 1 < n.length && j > 0 ) {
k += --j;
n[k] = true;
}
}
}
// Griffin N. Macris, Mar 24 2016

Mathematica

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

Formula

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

Extensions

Essential qualification added to definition by Peter Munn, Jan 19 2017