OFFSET
1,1
COMMENTS
Also called weakly primes of 2nd order in base 2.
Formal definition: let P = set of prime numbers, XOR(x,y) = bitwise x xor y, set of witnesses for an integer x>1 w(x) := Union_{1<=k<=floor(log_2(x)), 0<=j<k}{XOR(x, 2^k+2^j)}; then a is in the sequence iff (a in P)&( Intersection(w(a), P) = {}).
There are only 6 terms < 10^11 (exhaustive search). But several larger terms of a special form are known (Wagstaff primes, A000979). The smallest of them are:
a(6+)=2932031007403,
a(7+)=768614336404564651,
a(8+)=201487636602438195784363. - Terentyev Oleg
EXAMPLE
a(3)=2731 is in the sequence because it is prime and all its witnesses are composite numbers :
2731 = 101010101011 -> 10101011 = 171 = 3^2 * 19
1000101011 = 555 = 3 * 5 * 37
1010001011 = 651 = 3 * 7 * 31
1010100011 = 675 = 3^3 * 5^2
1010101001 = 681 = 3 * 227
1010101010 = 682 = 2 * 11 * 31
1010101111 = 687 = 3 * 229
1010111011 = 699 = 3 * 233
1011101011 = 747 = 3^2 * 83
1110101011 = 939 = 3 * 313
11010101011 = 1707 = 3 * 569
100000101011 = 2091 = 3 * 17 * 41
100010001011 = 2187 = 3^7
100010100011 = 2211 = 3 * 11 * 67
100010101001 = 2217 = 3 * 739
100010101010 = 2218 = 2 * 1109
100010101111 = 2223 = 3^2 * 13 * 19
100010111011 = 2235 = 3 * 5 * 149
100011101011 = 2283 = 3 * 761
100110101011 = 2475 = 3^2 * 5^2 * 11
101000001011 = 2571 = 3 * 857
101000100011 = 2595 = 3 * 5 * 173
101000101001 = 2601 = 3^2 * 17^2
101000101010 = 2602 = 2 * 1301
101000101111 = 2607 = 3 * 11 * 79
101000111011 = 2619 = 3^3 * 97
101001101011 = 2667 = 3 * 7 * 127
101010000011 = 2691 = 3^2 * 13 * 23
101010001001 = 2697 = 3 * 29 * 31
101010001010 = 2698 = 2 * 19 * 71
101010001111 = 2703 = 3 * 17 * 53
101010011011 = 2715 = 3 * 5 * 181
101010100001 = 2721 = 3 * 907
101010100010 = 2722 = 2 * 1361
101010100111 = 2727 = 3^3 * 101
101010101000 = 2728 = 2^3 * 11 * 31
101010101101 = 2733 = 3 * 911
101010101110 = 2734 = 2 * 1367
101010110011 = 2739 = 3 * 11 * 83
101010111001 = 2745 = 3^2 * 5 * 61
101010111010 = 2746 = 2 * 1373
101010111111 = 2751 = 3 * 7 * 131
101011001011 = 2763 = 3^2 * 307
101011100011 = 2787 = 3 * 929
101011101001 = 2793 = 3 * 7^2 * 19
101011101010 = 2794 = 2 * 11 * 127
101011101111 = 2799 = 3^2 * 311
101011111011 = 2811 = 3 * 937
101100101011 = 2859 = 3 * 953
101110001011 = 2955 = 3 * 5 * 197
101110100011 = 2979 = 3^2 * 331
101110101001 = 2985 = 3 * 5 * 199
101110101010 = 2986 = 2 * 1493
101110101111 = 2991 = 3 * 997
101110111011 = 3003 = 3 * 7 * 11 * 13
101111101011 = 3051 = 3^3 * 113
110010101011 = 3243 = 3 * 23 * 47
111000101011 = 3627 = 3^2 * 13 * 31
111010001011 = 3723 = 3 * 17 * 73
111010100011 = 3747 = 3 * 1249
111010101001 = 3753 = 3^3 * 139
111010101010 = 3754 = 2 * 1877
111010101111 = 3759 = 3 * 7 * 179
111010111011 = 3771 = 3^2 * 419
111011101011 = 3819 = 3 * 19 * 67
111110101011 = 4011 = 3 * 7 * 191
MATHEMATICA
isWPof2ndOrderBase2[x_] := Module[{j = 1, k = 2, flag = x <= 3 || ! BitAnd[x - 3, x - 4] == 0, bitlen = BitLength@x}, While[flag && k < bitlen, While[flag && j < k, flag = !PrimeQ@BitXor[x, BitShiftLeft[1, j] + BitShiftLeft[1, k]]; j++]; j = 1; k++]; flag]; Select[Prime[Range[20000]], isWPof2ndOrderBase2]
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Terentyev Oleg, Dec 22 2011
STATUS
approved