Search
Recent Comments
cheap travel insurance
Nov-26 06:19 AM (EST)
By now any of my 3 regular readers would happily warn tell you that I am obsessed with extremely interested in numbers. As an amateur hobbyist my knowledge of number theory is very limited, but that doesn't stop me from playing with numbers and figuring things out. Here's one of the numeric excursions I've devoted some idle time to over the Thanksgiving Holiday...
Okay, "prime trajectory" is a term I made up. Which is not to say that the term doesn't have some meaning, there may very well be an accepted meaning for this term, but here's how I'm using it: A prime trajectory is a series of primes in which each member is the next prime that ends with all of the digits of the previous member. The first member is given.
In other words, pick a starting prime, in this case let's pick 3. (Yeah I know 2 is the first prime, but no primes end in 2, so the entire prime trajectory of 2 is: 2--not very exciting, is it?) Since 3 is the first prime in our trajectory, what is the next prime that ends in 3? That's easy 13. Okay, so what is the next prime that ends in 13? Well, we should try prefixing 13 with increasing digits until we find a prime (1 & 13 = 113, 2 & 13 = 213, 3 & 13 = 313, etc.). It turns out that we get our answer on the very first try... 113 is the next prime in this trajectory. Here are the first 10 terms of the prime trajectory of 3:
3 
13 113 2113 12113 612113 11612113 1611612113 111611612113 1111611612113
I've bolded the new digits added each time. In fact, we could express this series in terms of the digits added only: 1, 1, 2, 1, 6, 11, 16, 11, 1. Note how the first 5 terms (and the 10'th) of this trajectory require only 1 digit be prepended to the previous prime, while terms 7 through 9 each require two digits be prepended. Further note how the only digits appearing are 1, 2, 3, and 6.
Seeing this I asked myself some questions:
- Will the other digits appear in time if we continue the trajectory?
- Will some terms require prepending 3 digits? 4 digits? 5 digits?
To find the answers to these questions, I computed the trajectory out to the 97'th term. Here are the digits added in series:
1, 1, 2, 1, 6, 11, 16, 11, 1, 8, 21, 13, 11, 34, 41, 12, 4, 66, 24, 15, 17, 4, 122, 70, 96, 33, 2, 43, 5, 3, 100, 44, 28, 23, 27, 12, 4, 113, 10, 3, 90, 9, 162, 15, 9, 69, 146, 9, 145, 74, 3, 42, 99, 31, 93, 35, 259, 53, 79, 14, 285, 84, 1, 36, 78, 147, 78, 66, 246, 155, 624, 403, 297, 12, 137, 25, 45, 117, 297, 386, 6, 93, 13, 177, 209, 79, 267, 8, 286, 98, 48, 34, 5, 72, 531, 288 |
As you can see, ultimately all the digits will appear. The one we have to wait the longest for is 9 which appears in the 26'th term of the trajectory. Strangely the first time we prepend a 3 is in the thirteenth term... which happens to be 13... neat!
So far the largest prefix we've had to add was the 72'nd: 624. This means that all prefixes from 1 to 623 when prepended to the previous member yielded a composite (nonprime) number. I've seen no examples of 4 or 5 digit prefixes, but there may be some out there.
The 97'th prime in the trajectory has 195 digits:
2885317253448982868267792091771393638629711745251 3712297403624155246667814778361842851479532593593 3199423741459146699151629903101134122723284410035 432339670122417152466412413411132181111611612113 |
The next thing I wondered was if anyone else had toyed with this idea. I figured they surely must have, and a quick check of the OEIS (On-Line Encyclopedia of Integer Sequences) reveals that this computation has been done before.
Obviously, there are infinitely many such sequences, since there are infinitely many primes. For example, why not use 7 as the starting prime?
7 17 317 6317 26317 126317 2126317 72126317 372126317 5372126317
Not surprisingly, the sequence of prefixes in this example 1, 3, 6, 2, 1, 2, 7, 3, 5... does not appear in the OEIS. It is not surprising because there would be infinitely many such sequences when only one is necessary to capture the basic idea. Since the prime trajectory of 3 is the first, simplest case, it is the only case which needs to be added to the OEIS, as long as the idea itself is deemed to be of value.
But is there any interesting way to capture information about all such sequences? Well, note that in the prime trajectory of 3, the addition of only a single digit was required to get the first 5 terms, whereas in the prime trajectory of 7, prepending single digits yields the first 9 terms.
So we could determine for each prime how many times a single digit can be prepended to yield a new prime before multiple digits are required. For 2 and 5 this value is 0, for 3 it is 5, and for 7 it is 9. So the sequence would begin 0, 5, 0, 9 (anybody who knows me on a personal basis might find this amusing for reasons which I will not reveal on the internet.) For 11 the value is 5. 13 and 17 each in turn are the second terms in the trajectories of 3 and 7, so their values are one less than the values for 3 and 7. This makes the opening of our new sequence: 0, 5, 0, 9, 5, 4, 8... so, are there any prime trajectories where the first N steps require single digits only and N>=9?
The answer to that question is YES. I tested the first 25,000 primes (all primes up to 287117) and found that both 29 and 59 can also prepend a single digit 9 times to yield a new prime. The first prime to break this record is 73--a real whopper. You can prepend a single digit 14 times to yield a new prime (4818372912366173). This record isn't matched until we get to 4663 which can also yield 14 new primes simply by adding a single digit each time (686762315123164663). The next record breaker is 13799 which can produce 15 primes (21291981879276213799).
In the first 25,000 primes nothing breaks the record set by 13799, but there is one other prime that matches that record, 269209 (183792429193597269209).
This analysis yields 3 sequences:
- a(n) = beginning with the n'th prime, the number of times a new prime is formed by prepending the lowest additional single digit. For example a(2) is 5 because the 2'nd prime is 3, to which single digits can be prepended 5 times yielding a new prime each time--13, 113, 2113, 12113, 612113. (There is no single digit which can be prepended to 612113 to yield a new prime.)
0, 5, 0, 9, 5, 4, 8, 4, 5, 9, 4, 6, 2, 7, 6, 8, 9, 7, 6, 3, 14, 5, 5, 2, 4, 10, 1, 5, 7, 3, 4, 3, 5, 5, 0, 6, 5, 8, 5, 13, 4, 5, 4, 5, 3, 8, 4, 4, 5, 8, 3, 6, 1, 4, 4, 2, 5, 2, 2, 3, 4, 9, 8, 7, 4, 7, 3, 3, 5, 5, 7, 8, 4, 3, 3, 2, 1, 7, 0, 4, 3, 5, 3, 7, 9, 6, 6, 5, 6, 8, ...
- b(n) = the values in a() which are records (all primes up to 287117 tested):
0, 5, 9, 14, 15, ...
- c(n) = the first prime yielding the record value b(n)
2, 3, 7, 73, 13799, ...
Possibly one could include a fourth sequence showing the primes produced by prepending single digits for each of the record breakers: 2, 612113, 5372126317, 4818372912366173, 21291981879276213799.
One final note of interest about the prime produced by 73 (4818372912366173)... 73 itself is produced by adding a single digit to the prime 3. Thus 4818372912366173 is an "alternate trajectory" for 3, and is therefore a 16 digit number which yields a new prime every time the most significant digit is removed until only one digit remains. Such primes are called left-truncatable primes. Here's a list of them.
Since there are many primes on that list that are longer than 4818372912366173, you may be wondering why the analysis above does not detect them. That's simply because we only look at the FIRST single digit (starting from the lowest) which produces a prime. So for 3 we only look at 13, and yet 23, 43, 53, 73, and 83 are all primes formed by prepending single digits to 3.
If you don't allow primes containing the digit zero, the list of left-truncatable primes is finite. There are only 4260 of them, and the largest is 357686312646216567629137 (24 digits). Though my analysis doesn't allow the addition of 0 to the starting prime, any starting prime is allowed, even those which contain zeros. So in theory, there may well be primes out there to which more than 23 single digits can be prepended yielding a prime each time.
It's interesting, but not a problem I plan to look into further anytime soon! 