It's the palindromic primes which only use digits 1 and 0! There are 49 of them below 10^20-1 and probably an infinite number above 10^20-1. Here's the first 49…

If you are wondering what palindromic means, with respect to numbers it refers to a number which reads the same forwards as backwards (like 12321).  A palindromic prime is a prime number which reads the same forwards as backwards (like 313).

I was factoring some large numbers this weekend, and I noticed a few primes that had very similar forms: 9901, 99990001, 999999000001, and 9999999900000001.  Essentially, these primes are the values produced by the formula (10^y – 1) x (10^y) + 1 for the following values of y: 2, 4, 6, and 8…

I was curious to know if there are any other values of y for which (10^y – 1) x (10^y) + 1 is prime.  I have since tested all values of y up to 550 and have found no further primes of this form.  I am starting to wonder if there are no others.  I find it odd that it works for all the even numbers between 1 and 9 and then nothing all the way up to 550.

If there are no other primes of this form, I'm sure a number theorist or accomplished mathematician would be able to explain why.  Any experts out there want to take a crack at this one?

I began to wonder if the number I'm raising to y somehow puts a limit on the value of y that will yield a prime… in this case the number is 10 and the only values of y that work (that I have found) are less than 10.  So I substituted a variable “b” for 10 in the formula making it: (b^y – 1) x (b^y) + 1.

Now I can try different values for b, and see if I get results that follow a pattern.  First I tried b=16 because it is bigger than 10.  For b=16 (testing all values of y up to 100), there are only two primes at y=1 (241), and y=8 (18446744069414584321).  So maybe b does limit the maximal value of y that yields a prime?  Next I tried b=5 (testing all values of y up to 100) and got these results:

y=2 (601)
y=4 (390001)
y=8 (152587500001)
y=18 (14551915228363037109375001)
y=48 (12621774483536188886587657044524576122057624161243438720703125000001)
y=64 (293873587705571876992184134305561419454666388650920794134435709565877914428710937500000001)

Interesting, but it also shoots down the “b is the maximal working value of y” idea.  However b may still be limiting the maximal working value of y in some way, it's just not obvious how, to me.

Just for the heck of it, I tested y up to 100 for all values of b between 1 and 16.  Here are the results:

I'm not at all surprised that for b=1 there are no results.  No matter what the value of y is, 1^y is still 1, and thus the formula always evaluates to (1 + 1) * (1) – 1 which equals 1, which is not a prime.

I find it intriguing how often powers of 2 show up (2, 4, 8, 16, 32, 64… all of these appear, some of them several times.)  Look at 15… all of the working values are squares.  Note that for 3 the values 6 (3×2), 12 (3×4), and 18 (3×6) all work.  I pushed on 3 all the way out to y=600 without finding any other working values.

Part of me intuits that simply because the set of integers is infinite, there must be other values of y that work when b is 10… but they may be awesomely large.  Another part of me intuits that there may be a simple rule at play which forces the number of working values of y to be finite based on the value of b as evidenced by the highly patternistic results I am seeing, and the fact that I have pushed out fairly far without finding anything else (after all (10^550-1)*(10^550)+1 is 1,099 digits long!)

I'm baffled. Can anyone help?

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:

1. 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, …
    

2. b(n) = the values in a() which are records (all primes up to 287117 tested):

   0, 5, 9, 14, 15, …
    

3. 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!