Self-Complementary Sieve

[Joshua Zucker]

On Wed, Mar 12, 2008 at 3:15 PM,  <pauldhanna at juno.com> wrote:
> -------------------------------------------
> A138203
>
> Sieve: start with the natural numbers; at the n-th step in the sieve
> remove every A138204(n)-th term from the sequence remaining in the prior
> step,
> where A138204 is the complement to this sequence starting with A138204(1)=2.
>
> 1,3,5,9,11,17,19,21,25,27,33,...
>
> -------------------------------------------
>
> A138204
>
> Complement of sieve A138203 such that the n-th step of the sieve removes
> every a(n)-th term from the sequence remaining in the prior step, starting
> with a(1)=2.
>
> 2,4,6,7,8,10,12,13,14,15,16,18,...
> --------------------------------------------

Hi Paul and seqfans,
I think this is a cute idea, reminiscent of Hofstadter's
1,3,7,12,18,26 (A005228).  It feels like an interesting flavor of
self-reference combined with Eratosthenes-ish sieving.

If I understand your definition correctly, which I may not, I get
A138203: 1 3 5 9 11 17 21 27 33 37 43 51 59 69 81 91 97
A138204: 2 4 6 7 8 10 12 13 14 15 16 18 19

Since we disagree at a pretty early term, it should be easy to figure
out which one of us is confused.  Here's my process:
delete every 2nd term: (1 3 5 7 9 11 13 15 17 19 21 23 25 27 29)
4 is missing, so delete every 4th term (7, 15, 23, etc.): (1 3 5 9 11
13 17 19 21 25 27 29)
6 is missing, so delete every 6th term (13, 29): (1 3 5 9 11 17 19 21 25 27)
7 is missing, delete the 7th term (19): (1 3 5 9 11 17 21 25 27)
8 is missing, delete the 8th term (25): (1 3 5 9 11 17 21 27)
now future deletions won't hit any of those terms, so those at least
are guaranteed.  Since we already differ (you have 19 and I don't),
please let me know if I've misunderstood your process!

Just in case I did get it right, here are more terms.
For A138203, the first 205 terms gets us up to the last term under 10000:
1 3 5 9 11 17 21 27 33 37 43 51 59 69 81 91 97 105 117 133 137 149 169
181 195 211 213 235 259 273 297 307 313 339 361 369 403 409 435 465
481 485 515 539 565 581 627 641 665 689 707 739 755 785 821 853 873
913 917 963 993 1009 1051 1097 1121 1153 1173 1257 1259 1285 1301 1371
1411 1419 1481 1505 1557 1579 1625 1681 1685 1747 1777 1825 1849 1893
1953 2009 2019 2091 2117 2139 2225 2245 2291 2369 2387 2401 2441 2537
2561 2629 2657 2715 2755 2793 2837 2917 2971 3017 3075 3115 3187 3237
3285 3331 3393 3433 3505 3563 3635 3675 3739 3777 3861 3931 3989 4037
4153 4179 4243 4307 4309 4373 4489 4537 4547 4641 4667 4795 4859 4915
4955 5061 5129 5203 5253 5333 5387 5409 5513 5603 5643 5733 5841 5873
5941 6041 6091 6123 6251 6329 6421 6483 6611 6619 6697 6837 6867 6915
7027 7089 7257 7291 7349 7441 7475 7571 7689 7803 7817 7893 7953 8085
8153 8233 8321 8427 8533 8587 8741 8817 8875 8963 8969 9171 9189 9299
9441 9459 9571 9675 9817 9859 9973

and for A138204, well, it'll just be the complement, so that's simple
enough.  But we only need to go up to 205 to guarantee the above
sequence, so:
2 4 6 7 8 10 12 13 14 15 16 18 19 20 22 23 24 25 26 28 29 30 31 32 34
35 36 38 39 40 41 42 44 45 46 47 48 49 50 52 53 54 55 56 57 58 60 61
62 63 64 65 66 67 68 70 71 72 73 74 75 76 77 78 79 80 82 83 84 85 86
87 88 89 90 92 93 94 95 96 98 99 100 101 102 103 104 106 107 108 109
110 111 112 113 114 115 116 118 119 120 121 122 123 124 125 126 127
128 129 130 131 132 134 135 136 138 139 140 141 142 143 144 145 146
147 148 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164
165 166 167 168 170 171 172 173 174 175 176 177 178 179 180 182 183
184 185 186 187 188 189 190 191 192 193 194 196 197 198 199 200 201
202 203 204 205

--Joshua Zucker