| >I'm now wondering about some harder problems. For instance, can we prove
>that for all n, there exists a positive k for which
>
> k
> 1<n > is composite.
I can't believe that there can be such a simple prime generator. Thus,
at least a few of the numbers in this sequence must be composite. :^|
Anyway, here's a partial solution.
Suppose n has d digits. Let p be a factor of 10**d-1, with n and p relatively
prime (if no such p exists, the following doesn't apply).
k
Define f(k) = 1<n > mod p. Then f(0) = 1, and f(k) = (10**d*f(k-1) + n) mod p.
But 10**d mod p = 1, so that f(k) = ( f(k-1) + n ) mod p. Solving this trivial
recurrence, we have f(k) = (k*n + 1) mod p. Since n and p are relatively prime,
we know the f(k) series cycles every p elements, and covers all the values from
0 to p-1. Thus, there is a f(k) = 0, and every p'th element following it is
also zero -- all these are multiples of p.
Suppose instead that there is no p such that p is a factor of 10**d-1, with
n and p relatively prime, then n must have all the prime factors of 10**d-1.
What can we get with this?
BTW, there seems to be some relation between this question and repeating
decimal expansions of rational numbers. I think there's a trivial proof of
the above assertion.
|
| The following terminology is from memory:
Fermat's Little Theorem states that if p is a prime, then
for all integers a relatively prime to p,
p-1
a = 1 (mod p)
Sometimes this is stated as, if p is a prime, then for all
integers a,
p
a = a (mod p)
n-1
An integer n is a pseudoprime if 2 = 1 (mod n). If n is
a prime, then it will also be a pseudoprime, by
Fermat's Little Theorem. But not all pseudoprimes are
necessarily primes.
k
For numbers of the form 1<3 > for 1 <= k <= 100, the number
is a pseudoprime for k = 1, 6, 15, 41, 83, 95. So, for
27
example, 1<3 > can not be a prime. Of the pseudoprimes,
the one with k=6 fails the test
n-1
3 = 1 (mod n)
and so it is not prime (in fact, 23 divides 1333333). The
rest (k = 1, 15, 41, 83, and 95) are primes:
k = 1: 13 is prime
k = 15: I verified this earlier (a low priority
background job took only three hours to divide
by all the odd numbers less than the sqrt!)
k = 41, 83, 95: The probabilistic primality testing
algorithm labelled as Algorithm P in Knuth's
Vol. 2 found these to be prime (20 trials each,
the probability of error per trial being at
most 1/4.)
k
So for 1 <= k <= 100, 1<3 > is definitely prime for k = 1, 15;
it is almost certainly prime for k = 41, 83, 95; and it is
definitely composite for all other k with 1 <= k <= 100.
Dan
|
| k
H<T > means the base b number HT...T with k T's, where
b
k and b are positive integers, b > 1, and H and T are
strings of base b digits that represent the numbers h and t,
respectively. Let T be a string of d digits, and let a be
d
equal to b . Then if f(H,T,k,b) is the number represented
by the base b digit string HT...T (k T's), we have
f(H,T,0,b) = h
f(H,T,k+1,b) = a * f(H,T,k,b) + t
Now let p be a prime larger than a, h, and t. Let g be the
residue of f modulo p. Then [leaving out H,T, and b]
0 < a < p
h < p
t < p
g(0) = h (mod p)
g(k+1) = ah + t (mod p)
Consider the mapping x -> ax + t (mod p), a non-zero. This
mapping is a permutation: given ax+t one can solve uniquely
for x, because a has a multiplicative inverse mod p. Write
this permutation as a product of cycles. One of the cycles
must contain the element 0 (mod p). If it happens that for
some value of k, f(H,T,k,b) (mod p) = g(k) = 0, then we must
have g(k+mr) = 0 for r = 1, 2, 3, ... where m is the length
of the cycle. So if one element of the sequence is
divisible by p, then infinitely many are.
How do we select p so that there is an element of the
sequence that is divisible by p? Well, take the element of
the sequence given by k=1, i.e. HT (base b). It is larger
than a, h, and t. If it is a prime, let p be this value;
then every m-th element [m the length of the cycle of the
permutation that contains 0] is greater than p and divisible
by p, and so is composite. If HT is not prime, well, then
it is the composite that we were looking for :-).
So only a single prime is needed for k>=1 to insure that
there are infinitely many composites in the sequence. If
there are no primes for k>=1, then that gives infinitely
many composites. As I suggested earlier, it is harder to
prove that the sequence contains primes.
Dan
|