thanks everybody (I actually knew most of that, but thanks anyhow)...

I had not known about William Paulsen. Paulsen apparently conjectured

that 67607 is the least prime such that changing any bit (including leading 0s)

always yields a composite(?). This would improve a lot versus 2131099

(which he also knew about).

Unfortunately for his conjecture,

67607 + 2^16389

is prime (says MAPLE9 -- is it right?).

This prime shows as a side effect of proposition 2 in Paulsen's article that 67607 is not a Sierpinski number (or if it is, not one having a proof based on covering congruences)

which I think was not previously known.

Wm Paulsen: the prime numbers maze, Fibonacci Quart. 40 (2002) 272-279.

http://www.fq.math.ca/Scanned/40-3/paulsen.pdf
Paulsen also notes a candidate is 19249.

However, 19249*2^13018586+1 is prime

which defeats his argument although the conjecture per se is not refuted (yet).

That is, we know 19249 is not a Sierpinski number, and hence there can be no proof

based on covering congruences that 19249+2^k is always composite.

Hence it is plausible there exists a prime 19249+2^k (although I do not know one).

We can indeed kill quite a few Sierpinski candidates from the page

http://en.wikipedia.org/wiki/Seventeen_or_Bust
in the same way:

* 10223 + 2^k is prime if k=19, 103, or 3619

hence 10223 is not Sierpinski-via-covering-congruences.

* 21181 + 2^k is prime for k=28, 196, 268, and 316

hence 21181 is not Sierpinski-via-covering-congruences.

* 22699 + 2^k is prime for k=26 and 1250

hence is not Sierpinski-via-covering-congruences.

* 24737 + 2^k is prime for k=17

hence is not Sierpinski-via-covering-congruences.

* 55459 + 2^k is prime for k=14, 746, and 854

hence is not Sierpinski-via-covering-congruences.

This in fact kills every undecided case in the "seventeen or bust" project -- none

of them are Sierpinski-via-covering-congruences.

It is still possible they could be Sierpinski for some other reason (i.e. luck), though.

Paulsen also notes the prime bit-alteration graph is bipartite,

the "parity" of a prime (number of 1s in its binary representation is even or odd?)

governs that...