## Is This a Prime?

```Someone once asked me if 785645465756452 is a prime.  Presumably the
base of the representation is not 10, since otherwise the number is
obviously a multiple of 2.  On the other hand, we note that for ANY
base, the number is not divisible by 3.  Similarly, it cannot be
divisible by 17, 23, 41, 47, 53, etc...  regardless of what base is
assumed.

It isn't too hard to show that 23 is the only (positive) base less
than 100 for which the number is actually prime.  The next bases for
which the number is prime are 165, 189, 193, 345, 399, 455, etc.

Incidentally, converted from base 23 to base 10, the number is

85297610194238336897

Notice that each of the ten decimal digits 0,1,..,9 appears at least
once in this number.  In contrast, the original number has no 0, 1, 3,
or 9, whereas it contains five 5s in the pattern xx5xx5xx5x5xx5x.  The
overall digit frequency is

digit   0  1  2  3  4  5  6  7  8  9
occurrences   0  0  1  0  3  5  3  2  1  0

Can we infer anything from this about how the original digits were
selected?

A more interesting question is:  Given an irreducible polynomial P(x)
of degree > 0 with integer coefficients, does there necessarily exist
an integer n such that P(n) is a prime?  Of course, Dirichlet's Theorem
states that there are infinitely many such n for any irreducible
polynomial of degree 1.  According to Ribenboim, the answer to the
more general question is unknown.   For most (irreducible) polynomials
P(x) it's usually easy to find an integer n such that P(n) is prime,
but for certain polynomials it's surprisingly difficult.  For example,
the least positive n such that n^(12) + 488669 is prime is n = 616979.

It's also interesting to note that if exponential expressions are
allowed, we can have no primes at all in certain sequences. For
example, the number

2935363331541925531 * 2^n  +  1

is never a prime number (as can be proved by factoring the multipler
minus 1). See Richard Guy's Unsolved Problems in Number Theory for
more examples.