[seqfan] Re: Binary Primes In Binary Primes

Charles Greathouse charles.greathouse at case.edu
Tue Mar 16 05:42:06 CET 2010


I would guess that this sequence is a permutation of the primes.  If
nothing else, prime gaps will get large enough (on average) that
finding a prime with S as a subsequence would require arbitrarily many
additional bits of padding, in which yet-unused primes could be
hidden.

I can verify your hand-calculated terms.  I calculate
2, 5, 11, 3, 7, 23, 47, 191, 31, 127, 383, 3067, 13, 29, 59, 239, 479,
223, 479, 991, 61, 251, 503, 2039, 509, 1019, 2039, 4079, 16319,
65407, 1021, 4091, 24571, 4093, 16381, 98299, 6143, 63487, 3583,
15359, 63487, 3967, 16127, 98047, 1531, 7159, 1789, 7159, 30703,
126943, 7933, 24317, 379, 1783, 5879, 367, 1471, 7039, 109, 439, 1759,
7039, 97151, 12143, 94063, 2939, 5879, 14071, 3517, 14071, 112571,
443, 887, 3823, 751, 3823, 7919, 1979, 4027, 8123, 106427, 19, 79,
317, 829, 103, 359, 89, 179, 359, 719, 1439, 2879, 11071, 43, 107, 53,
107, 431, 863, 6907, 23291, 181, 727, 2909, 349, 1373, 7517, 1879,
7517, 30071, 1399, 11197, 27581, 1723, 7867, 491, 983, 7127, 757,
7127, 15319, 113623, 24043, 113623, 768983, 6007, 22391, 89567,
716543, 7103, 14207, 113657, 48121, 113657, 506873, 1031161, 16111,
81647, 2551, 20411, 40823, 81647, 850879, 3323, 26591, 59359, 463,
1487, 743, 1487, 9679, 37, 101, 229, 919, 151, 607, 4703, 73, 293,
587, 2351, 4703, 51581, 182653, 1231229, 601, 3251, 11443, 27827,
13913, 27827, 126131, 7883, 15767, 64303, 6959, 39727, 9931, 39727,
105263, 52631, 105263, 210527, 842111, 1684223, 45823, 733169, 17, 71,
199, 797, 3191, 571, 2287, 9151, 36607, 429823, 163, 419, 839, 2887,
6983, 3491, 6983, 13967, 55871, 3359, 6719, 26879, 1151, 9209, 73673,
457, 1481, 2963, 5927, 1831, 5927, 44623, 351391, 21961, 175691, 3659,
14639, 47407, 356959, 2978399, 1721, 3769, 15077, 2789, 11159, 1483,
11159, 89273, 3257, 31091, 971, 3019, 15307, 1913, 15307, 3557, 15307,
61231, 28463, 61231, 489851, 1213, 5309, 41, 83, 167, 1447, 211, 467,
233, 467, 1871, 3919, 15679, 3391, 7487, 15679, 32063, 2003, 4007,
32057, 313, 3301, 31973, 487, 1511, 3023, 6047, 1951, 6047, 48383,
1279, 5119, 20477, 151549, 1212397, 2029, 8117, 1973, 3947, 15791,
31583, 15199, 31583, 129887, 4021, 8117, 32693, 196459, 785839, 16087,
65239, 260959, 1043837, 8350697, 3049, 12197, 421, 1867, 331, 1327,
5309, 42473, 84947, 864077, 3917, 12109, 28493, 61261, 257869, 31699,
130003, 32233, 130003, 523219, 8371507, 307, 1229, 2459, 4919, 311,
823, 1847, 461, 1847, 10039, 26423, 183919, 45979, 183917, 892123,
105691, 473527, 14797, 31181, 63949, 499, 1523, 761, 1523, 3571,
15859, 3833, 15859, 63439, 1999, 12239, 45007, 11251, 45007, 110543,
221087, 966463, 3865853, 1277, 10223, 92143, 737147, 8059, 24443,
228847, 1787, 7151, 14303, 28607, 228859, 32251, 97787, 228859,
491003, 245501, 491003, 3928027, 2011, 12251, 57271, 253879, 61403,
253879, 516023, 1032047, 3129199, 14647007, 32479, 129917, 64381,
129917, 1039343, 28151, 60919, 252911, 505823, 1030111, 6254527,
1563631, 6254527, ...

The first primes not appearing are 67, 97, 113, etc.

Charles Greathouse
Analyst/Programmer
Case Western Reserve University

On Mon, Mar 15, 2010 at 4:20 PM, Leroy Quet <q1qq2qqq3qqqq at yahoo.com> wrote:
> Let a(1) = 2.
> Let a(n) = either:
>  The smallest prime not yet occurring in the sequence that, when written in binary, it is a substring in the binary representation of a(n-1);
> Or, if no such prime exists,
>  The smallest prime not yet occurring that when written in binary, a(n-1) is contained as a substring within it.
>
> The sequence begins:
> 2,5,11,3,7,23,47,191,31,127,...
>
> (I did this by hand, and may have made an error, even though I double-checked the terms.)
>
> Written in binary, the sequence begins:
> 10,101,1011,11,111,10111,101111,10111111,11111,1111111
>
> I was thinking without proof that the (decimal) sequence must certainly be a permutation of the primes.
> But looking at the binary representations of the terms, I am not so sure now.
>
> Is this sequence a permutation of the primes?
>
> What about the sequence -- which starts with the same terms I give above -- that is defined the same, but the first "smallest" in the definition is replaced with "largest"?
>
> In other words, this sequence:
>
> Let b(1) = 2.
> Let b(n) = either:
>  The largest prime not yet occurring in the sequence that, when written in binary, it is a substring in the binary representation of b(n-1);
> Or, if no such prime exists,
>  The smallest prime not yet occurring that when written in binary, b(n-1) is contained as a substring within it.
>
> Thanks,
> Leroy Quet
>
>
> [ ( [ ([( [ ( ([[o0Oo0Ooo0Oo(0)oO0ooO0oO0o]]) ) ] )]) ] ) ]
>
>
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>




More information about the SeqFan mailing list