login
Numbers surviving a decaying sieve.
6

%I #31 May 19 2023 14:18:21

%S 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 50,51,52,56,59,60,61,64,65,68,71,72,73,74,80,89,92,94,95,96,104,107,

%U 109,113,116,118,128,131,134,137,139,142,149,151,155

%N Numbers surviving a decaying sieve.

%C 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 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 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 Sean A. Irvine, <a href="/A270877/b270877.txt">Table of n, a(n) for n = 1..5000</a>

%H Peter Munn, <a href="/A270877/a270877.jpg">Historical image of Fortran II source program listing</a>

%H <a href="/index/Si#sieve">Index entries for sequences generated by a sieve</a>

%F 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 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 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 (Java)

%o int limit = 15707; //highest number in the sieve (inclusive)

%o boolean[] n = new boolean[limit + 1];

%o int index = 1;

%o for ( int i = 1; i < n.length; i++ ) {

%o if ( !n[i] ) {

%o System.out.println(index++ + " " + i);

%o int j = i, k = i;

%o while ( k + j - 1 < n.length && j > 0 ) {

%o k += --j;

%o n[k] = true;

%o }

%o }

%o }

%o // _Griffin N. Macris_, Mar 24 2016

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

%Y Cf. A066680, A136259, A286013.

%K nonn,nice

%O 1,2

%A _Sean A. Irvine_, Mar 24 2016

%E Essential qualification added to definition by _Peter Munn_, Jan 19 2017