A270877 - OEIS

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

(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 + (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

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

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;