Primes with strokes
This update wants to clarify the landscape I've obfuscated myself (as I often do – my apologizes to every one).
The idea is to submit a sequence S of distinct terms to the OEIS that hides in a certain way a succession P of primes. Such a hidden prime appears when the digits between two strokes are concatenated – and the strokes themselves appear (by a kind of spontaneous generation) immediately behind every prime digit of S.
To give an example, let's imagine an S starting like this:
S = 1, 3, 2, 4, 6, 7, 5, 8, 9, 10, 11, 14, 16, 18, 17, 13, ...
Stroke time:
S = 1, 3/, 2/, 4, 6, 7/, 5/, 8, 9, 10, 11, 14, 16, 18, 17/, 13/, ...
Prime time:
P = 13, 2, 467, 5, 89101114161817, 13, ...
(yes, 467 and 89101114161817 are primes – says the wonderful Alpertron. )
We see that P, at this stage, shows the prime 13 twice. This is allowed as we require only S to avoid duplicates.
This means that we could extend S with 23, for instance, as 23 is available and produces perfectly sound primes, despite the duplication of the prime 2 in P:
S = .........., 18, 17, 13, 23, ...
S = .........., 18, 17/, 13/, 2/3/, ...
P = ... 89101114161817, 13, 2, 3, ...
But as we want S to be the lexicographically earliest sequence of distinct positive terms with this property, we will not extend S at this stage with 23 – but rather with 19.
And this 19 will not be followed by 20, of course (as this would imply a term of P with a leading zero, which we forbid), nor by 21, 22, 23, ... 29 (as 192 is not a prime), nor by 30 (leading zero in P again), but by 31 (because 193 is prime), etc.
S is not a permutation of the integers > 0 (as some of them will never show – like 12 for instance).
Voilà, I hope the landscape is a bit clearer now (but I don't guarantee that the above S is the lexicofirst-one I am looking for – help, please!)
Best,
(and many thanks to David Sycamore who warned me and made me think a lot after I had submitted my first wrong Ss).
É.
____________________
Update nov 28th 2019
Read this on SeqFan yesterday – many thanks to David Seal!
> First, a quick disclaimer: I am not the "David S." that Éric refers to.
> Moving on to the sequence, I assume that while the terms of S pretty obviously are not to be written with leading zeros, it is not a problem if the sequences of digits between the strokes have leading zeros. This makes a difference to e.g. the question of whether 302 can ever appear in S: it will have strokes 3\02\, so it can potentially appear in S if leading zeros are OK in the sequences between strokes, since 02=2 is prime, but cannot do so if such leading zeros are not allowed. My assumption implies that 302 and other such integers can appear in S.
The digits 2 and 5 are special, since an occurrence of them implies that the preceding digits must be a prime digit (2, 3, 5 or 7) or a string of one or more 0s preceded by a prime digit. In the first case, the prime digit can either be in the same term of S as the 2 or 5, or at the end of the preceding term, but in the second, the 0s and the prime digit must either all be in the same term of S or all be in the preceding term, since otherwise there would be a term of S with leading zeros. This implies that:
* 2 can only appear in a term of S at its start, or as the rightmost digit of one of the digit pairs 22, 32, 52 and 72, or as the rightmost digit of one of the longer digit sequences formed from those pairs by inserting a sequence of one or more zeros into their middles;
* 5 can only appear in a term of S at its start, or as the rightmost digit of one of the digit pairs 25, 35, 55 and 75, or as the rightmost digit of one of the longer digit sequences formed from those pairs by inserting a sequence of one or more zeros into their middles.
Note that the digit pairs 22, 25, 52 and 55, and the longer digit sequences formed from them by inserting zeros, only make their rightmost digit 2 or 5 OK. For them to be fully OK, their leftmost 2 or 5 must also be made OK by being at the start of the term or by being the rightmost digit of another such pair or longer sequence.
Application of this rule makes it impossible for various integers to appear in S, the first of which is 12. Integers can also be ruled out from ever appearing in S if they contain two or more prime digits and any of the sequences of digits between the strokes they imply is composite: for that to happen, the integer must have at least three digits, the first and last of which are prime and the second neither prime nor zero, and for it not to be made impossible by the rules about 2s and 5s, the last must be 3 or 7. That makes 263 the smallest integer that cannot appear in S because of this rule about having two or more prime digits but not also because of the rules about 2s and 5s.
All of this allows one to list the candidates for inclusion in S in numerical order. With their strokes, they are:
1, 2\, 3\, 4, 5\, 6, 7\, 8, 9, 10, 11, 13\, 14, 16, 17\, 18, 19, 2\0, 2\1, 2\2\, 2\3\, 2\4, 2\5\, 2\6, 2\7\, 2\8, 2\9, 3\0, 3\1, 3\2\, 3\3\, 3\4, 3\5\, 3\6, 3\7\, 3\8, 3\9, 40, 41, 43\, 44, 46, 47\, 48, 49, ...
To form S, we want to start with a length-0 sequence containing a single stroke (to ensure that the first digit of the sequence lies between strokes) and repeatedly append the first integer on this list that adheres to both of the following:
A) It has not already been used.
B) If it contains a stroke, appending it does not lead to an immediate contradiction because the integer formed from any digits after the last stroke of the digits of the sequence so far and the digits before its first stroke is composite. As a special case of this rule, it rules out candidates starting with 2 or 5 if any nonzero digit appears after the last stroke of the digits of the sequence so far.
At every stage of this process:
* S is a finite sequence with the property about the sequences of digits between strokes, on the understanding that there is no requirement about the sequence of digits after the last stroke, and is lexicographically less than or equal to any such finite sequence of the same length.
* I believe that S is always extendable to an infinite sequence with the property about the sequences of digits between strokes. This depends on it always being possible to extend a finite sequence of digits with a sequence of zero or more non-prime digits followed by a 3 or 7 to form a prime - something which I think is probabilistically certain given known results about the distribution of primes, but whether it can actually be proved goes beyond my level of knowledge and competence in the area.
If the second part of that is actually true, then the full sequence S generated by that process is the lexicographically least infinite sequence with the property about the sequences of digits between strokes. I.e. provided one avoids the immediate contradictions mentioned in B), later contradictions do not arise.
It should be noted though that that doesn't necessarily imply that every digit in S lies between strokes, since it is conceivable that from some point onwards, the process only appends strokeless integers to S. I'm not certain that possibility can be ruled out even probabilistically, due to the fact that the size of the numbers that need to be prime to end a sequence of strokeless integers grows rapidly as the length of that sequence increases.
Given all of that, my mostly-hand calculation of the first 30 terms of S goes:
* 1 is strokeless, to make S so far be \1.
* 2\ produces an immediate contradiction because 12 is composite, but 3\ is OK because 13 is prime, to make S so far be \1, 3\.
* 2\ is OK because 2 is prime, to make S so far be \1, 3\, 2\.
* 4 is strokeless, to make S so far be \1, 3\, 2\, 4.
* 5\ produces an immediate contradiction because 45 is composite, but 6 is strokeless, to make S so far be \1, 3\, 2\, 4, 6.
* 5\ produces an immediate contradiction because 465 is composite, but 7\ is OK because 467 is prime, to make S so far be \1, 3\, 2\, 4, 6, 7\.
* 5\ is OK because 5 is prime, to make S so far be \1, 3\, 2\, 4, 6, 7\, 5\.
* 8 is strokeless, to make S so far be \1, 3\, 2\, 4, 6, 7\, 5\, 8.
* 9 is strokeless, to make S so far be \1, 3\, 2\, 4, 6, 7\, 5\, 8, 9.
* 10 is strokeless, to make S so far be \1, 3\, 2\, 4, 6, 7\, 5\, 8, 9, 10.
* 11 is strokeless, to make S so far be \1, 3\, 2\, 4, 6, 7\, 5\, 8, 9, 10, 11.
* 13\ produces an immediate contradiction because 89101113 is divisible by 3, but 14 is strokeless, to make S so far be \1, 3\, 2\, 4, 6, 7\, 5\, 8, 9, 10, 11, 14.
* 13\ produces an immediate contradiction because 8910111413 is divisible by 7, but 16 is strokeless, to make S so far be \1, 3\, 2\, 4, 6, 7\, 5\, 8, 9, 10, 11, 14, 16.
* 13\ produces an immediate contradiction because 891011141613 is divisible by 3, and 17\ produces an immediate contradiction because 891011141617 is divisible by 19, but 18 is strokeless, to make S so far be \1, 3\, 2\, 4, 6, 7\, 5\, 8, 9, 10, 11, 14, 16, 18.
* 13\ produces an immediate contradiction because 89101114161813 is divisible by 3, but \17 is OK because 89101114161817 is prime (not by hand!), to make S so far be \1, 3\, 2\, 4, 6, 7\, 5\, 8, 9, 10, 11, 14, 16, 18, 17\.
* 13\ is OK because 13 is prime, to make S so far be \1, 3\, 2\, 4, 6, 7\, 5\, 8, 9, 10, 11, 14, 16, 18, 17\, 13\.
* 19\ is OK because 19 is prime, to make S so far be \1, 3\, 2\, 4, 6, 7\, 5\, 8, 9, 10, 11, 14, 16, 18, 17\, 13\, 19\.
* 2\0 is OK because 2 is prime, to make S so far be \1, 3\, 2\, 4, 6, 7\, 5\, 8, 9, 10, 11, 14, 16, 18, 17\, 13\, 19\, 2\0.
* 2\1 is OK because 02=2 is prime, to make S so far be \1, 3\, 2\, 4, 6, 7\, 5\, 8, 9, 10, 11, 14, 16, 18, 17\, 13\, 19\, 2\0, 2\1.
* All of 2\2\ to 2\9 produce an immediate contradiction because 12 is composite, but 3\0 is OK because 13 is prime, to make S so far be \1, 3\, 2\, 4, 6, 7\, 5\, 8, 9, 10, 11, 14, 16, 18, 17\, 13\, 19\, 2\0, 2\1, 3\0.
* 2\2\ is OK because 02=2 is prime, to make S so far be \1, 3\, 2\, 4, 6, 7\, 5\, 8, 9, 10, 11, 14, 16, 18, 17\, 13\, 19\, 2\0, 2\1, 3\0, 2\2\.
* 2\3\ is OK because 2 is prime, to make S so far be \1, 3\, 2\, 4, 6, 7\, 5\, 8, 9, 10, 11, 14, 16, 18, 17\, 13\, 19\, 2\0, 2\1, 3\0, 2\2\, 2\3\.
* 2\4 is OK because 2 is prime, to make S so far be \1, 3\, 2\, 4, 6, 7\, 5\, 8, 9, 10, 11, 14, 16, 18, 17\, 13\, 19\, 2\0, 2\1, 3\0, 2\2\, 2\3\, 2\4.
* All of 2\5\ to 2\9 produce an immediate contradiction because 42 is composite, but 3\1 is OK because 43 is prime, to make S so far be \1, 3\, 2\, 4, 6, 7\, 5\, 8, 9, 10, 11, 14, 16, 18, 17\, 13\, 19\, 2\0, 2\1, 3\0, 2\2\, 2\3\, 2\4, 3\1.
* All of 2\5\ to 2\9 produce an immediate contradiction because 12 is composite, but 3\2\ is OK because 13 is prime, to make S so far be \1, 3\, 2\, 4, 6, 7\, 5\, 8, 9, 10, 11, 14, 16, 18, 17\, 13\, 19\, 2\0, 2\1, 3\0, 2\2\, 2\3\, 2\4, 3\1, 3\2\.
* 2\5\ is OK because 2 is prime, to make S so far be \1, 3\, 2\, 4, 6, 7\, 5\, 8, 9, 10, 11, 14, 16, 18, 17\, 13\, 19\, 2\0, 2\1, 3\0, 2\2\, 2\3\, 2\4, 3\1, 3\2\, 2\5\.
* 2\6 is OK because 2 is prime, to make S so far be \1, 3\, 2\, 4, 6, 7\, 5\, 8, 9, 10, 11, 14, 16, 18, 17\, 13\, 19\, 2\0, 2\1, 3\0, 2\2\, 2\3\, 2\4, 3\1, 3\2\, 2\5\, 2\6.
* All of 2\7\ to 3\9 produce an immediate contradiction because 62 and 63 are divisible by 2 and 3, but 40 is strokeless, to make S so far be \1, 3\, 2\, 4, 6, 7\, 5\, 8, 9, 10, 11, 14, 16, 18, 17\, 13\, 19\, 2\0, 2\1, 3\0, 2\2\, 2\3\, 2\4, 3\1, 3\2\, 2\5\, 2\6, 40.
* All of 2\7\ to 3\9 produce an immediate contradiction because 6402 and 6403 are divisible by 2 and 19, but 41 is strokeless, to make S so far be \1, 3\, 2\, 4, 6, 7\, 5\, 8, 9, 10, 11, 14, 16, 18, 17\, 13\, 19\, 2\0, 2\1, 3\0, 2\2\, 2\3\, 2\4, 3\1, 3\2\, 2\5\, 2\6, 40, 41.
* All of 2\7\ to 3\9 produce an immediate contradiction because 640412 and 640413 are divisible by 2 and 3, and 43\ produces one because 6404143 is divisible by 23, but 44 is strokeless, to make S so far be \1, 3\, 2\, 4, 6, 7\, 5\, 8, 9, 10, 11, 14, 16, 18, 17\, 13\, 19\, 2\0, 2\1, 3\0, 2\2\, 2\3\, 2\4, 3\1, 3\2\, 2\5\, 2\6, 40, 41, 44.
David
Commentaires
Enregistrer un commentaire