Article 12761 of sci.math:
Newsgroups: sci.math
From: jeanmarc@ecrc.de (Jean-Marc Andreoli)
Subject: Re: u(v^n)w prime puzzle
Reply-To: jeanmarc@ecrc.de
Organization: European Computer industry Research Centre GmbH.
Date: Wed, 19 Aug 1992 14:19:57 GMT

In article 14274@wri.com, roach@bikini.wri.com (Kelly Roach) writes:
>
>
>
>     Prove or disprove:  There are three non-empty
>     strings of digits u,v,w such that all the
>     numbers in
>          L = {u(v^n)w | n is a natural number}
>            = {uw, uvw, uvvw, uvvvw, uvvvvw, ...}
>     are prime numbers.
>
>
>     Time to say a few more words about my u(v^n)w prime
>puzzle which I posted yesterday.  I am definitely not looking
>for any solutions involving u=v="0".  Ordinary syntax only
>please.  No leading zeros in u.
>     Some interesting patterns:
>
>     u="3",v="3",w="1"
>     31, 331, 3331, 33331, 333331, 3333331, 33333331
>
>     u="1",v="36",w="1"
>     11, 1361, 136361, 13636361, 1363636361, 136363636361
>
>     u="17",v="57",w="09"
>     1709, 175709, 17575709, 1757575709, 175757575709,
>     17575757575709, 1757575757575709, 175757575757575709
>
>Below each line giving u,v,w values appear a lot of prime
>numbers.  These patterns do eventually fail:
>
>     333333331 = 17*19607843
>     13636363636361 = 17*1321*5693*106661
>     17575757575757575709 = 232433*75616446785773
>
>The question is, are there any {u,v,w} examples which do
>not fail?  That always give prime numbers?
>     I know the solution to this puzzle.  I think the
>solution can be understood fairly easily by anyone that
>has had a first course in number theory.  See if you
>can discover it.
>

Let x_n be the number u(v^n)w.
Let r be the number of digits in v and z be the sequence of r zeros.

x_{n+1}  = uv ........... vvw
            <-- n times -->

10^r x_n = uv ........... vwz
            <-- n times -->

Notice that the sequences vw and wz at the end of each number have the same 
length hence x_{n+1} - 10^r x_n = (vw - wz)

More generally, we have x_{n+1} = a x_n + b
and we have to prove that such a sequence is either constant or contains at 
least one composite, for any integral values of x_0,a,b (with a>1).

This is a well known result, but, just in case, here is a proof.

If (a x_0 + b = x_0), then all the term in the sequence are equal to x_0. 
This is obviously not the case in the proposed sequence u(v^n)w. 
Now, if not(a x_0 + b = x_0), then the sequence is monotone and we can 
assume without loss of generality that it is positive increasing 
(that's the case of the proposed sequence).

Assume that x_n contains only (positive) primes.

Let p be a prime such that neither p|a nor p|a-1

Since not(p|a-1), there exists c such that (a-1) c = 1 (mod p)

hence a c = c+1 (mod p) and a b c = b + b c (mod p)

x_{n+1} + b c = a x_n + b + b c = a x_n + a b c (mod p)

hence x_{n+1} + b c = a(x_n + b c)  (mod p)
and, for all k
x_{n+k} + b c = a^k (x_n + b c)  (mod p)

For k = p-1, by Fermat's theorem and not(p|a), we have a^k = 1 (p)

Hence x_{n+p-1} = x_n (mod p)

Hence, not(x_n = p) otherwise x_{n+p-1} which is strictly greater that x_n
would be divisible by x_n and wouldn't be prime.

Therefore,

for all p, if p prime and not(p|a) and not(p|a-1) then for all n not(x_n=p)

which is equivalent to

for all p, if p prime and (exists n, p=x_n)  then p|a or p|a-1

By hypothesis, x_n is prime for all n. Hence

for all n, x_n|a or x_n|a-1

and the sequence cannot be ever increasing, a contradiction.
QED

Now, I propose the following question:

Is it true that any sequence x_{n+1} = a x_n + b is either constant or 
contains *infinitely many* composite ? *almost only* composite 
(i.e. it contains only a finite number of primes) ?

---
Jean-Marc Andreoli
---
Standard disclaimer.