login
Square array: row n gives the numbers remaining after the stage n of Lucky sieve.
6

%I #27 Apr 02 2017 01:06:43

%S 1,3,1,5,3,1,7,7,3,1,9,9,7,3,1,11,13,9,7,3,1,13,15,13,9,7,3,1,15,19,

%T 15,13,9,7,3,1,17,21,21,15,13,9,7,3,1,19,25,25,21,15,13,9,7,3,1,21,27,

%U 27,25,21,15,13,9,7,3,1,23,31,31,31,25,21,15,13,9,7,3,1,25,33,33,33,31,25,21,15,13,9,7,3,1,27,37,37,37,33,31,25,21,15,13,9,7,3,1,29,39,43,43,37,33,31,25,21,15,13,9,7,3,1

%N Square array: row n gives the numbers remaining after the stage n of Lucky sieve.

%C This square array A(row,col) is read by downwards antidiagonals as: A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), etc.

%C Lucky sieve starts with natural numbers: 1, 2, 3, 4, 5, 6, 7, ... from which at first stage the even numbers are removed, and on each subsequent stage n (n > 1) one sets k = <the n-th term of the preceding row> (these k will form the Lucky numbers) and removes every k-th term (from column positions k, 2k, 3k, etc.) of the preceding row to produce the next row of this array.

%C On each row n, the first term that differs from the n-th Lucky number (A000959(n)) occurs at the column position A000959(n+1) and that number is A219178(n) when n > 1.

%H Antti Karttunen, <a href="/A258207/b258207.txt">Table of n, a(n) for n = 1..10440; the first 144 antidiagonals of the array</a>

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

%e The top left corner of the array:

%e 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39

%e 1, 3, 7, 9, 13, 15, 19, 21, 25, 27, 31, 33, 37, 39, 43, 45, 49, 51, 55, 57

%e 1, 3, 7, 9, 13, 15, 21, 25, 27, 31, 33, 37, 43, 45, 49, 51, 55, 57, 63, 67

%e 1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 45, 49, 51, 55, 63, 67, 69, 73

%e 1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 55, 63, 67, 69, 73, 75

%e 1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79

%e ...

%e To get row 2 from row 1, we use the second term of the first row, which is 3, to remove every third term from row 1: 5, 11, 17, ... which leaves 1, 3, 7, 9, 13, ...

%e To get row 3 from row 2, we use the third term of row 2, which is 7, to remove every seventh term from row 2: 19, 39, ... which then results in the third row.

%o (Scheme)

%o (define (A258207 n) (A258207bi (A002260 n) (A004736 n)))

%o (define (A258207bi row col) ((rowfun_n_for_A000959sieve row) col))

%o ;; Uses definec-macro which can memoize also function-closures:

%o (definec (rowfun_n_for_A000959sieve n) (if (= 1 n) A005408shifted (let* ((prevrowfun (rowfun_n_for_A000959sieve (- n 1))) (everynth (prevrowfun n))) (compose-funs prevrowfun (nonzero-pos 1 1 (lambda (i) (modulo i everynth)))))))

%o (define (A005408shifted n) (- (* 2 n) 1))

%Y Cf. A000959 (Lucky numbers), which occur at the main and also any subdiagonal of this array. Also the rows converge towards A000959.

%Y Row 1: A005408. Row 2: A047241. Row 3: A258011.

%Y Transpose: A258208.

%Y Cf. also A219178, A255543, A260717.

%K nonn,tabl

%O 1,2

%A _Antti Karttunen_, Jul 27 2015