

A270877


Numbers surviving a decaying sieve.


4



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


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 + (p1), p + (p1) + (p2), ..., p + (p1) + (p2) + ... + 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 kth 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


LINKS

Sean A. Irvine, Table of n, a(n) for n = 1..5000


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


EXAMPLE

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.


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


PROG

(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


CROSSREFS

Cf. A281256 for tabulation of its runs of consecutive integers.
Cf. A286013.
Sequence in context: A255577 A245319 A037081 * A303909 A110277 A176654
Adjacent sequences: A270874 A270875 A270876 * A270878 A270879 A270880


KEYWORD

nonn,nice


AUTHOR

Sean A. Irvine, Mar 24 2016


EXTENSIONS

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


STATUS

approved



