| Comment: This is an interesting puzzle, where you have to look at the
function differently for each question posed. The first half of Q4,
remains open.
> Let x be an integer >= 2. Define s(x) to be the smallest prime
> factor of x, and let f(x) = x+s(x)-1.
>
> 1. Show that gcf(x, f(x)) = 1.
Let g(x)
= gcf(x, f(x))
= gcf(x,x+s(x)-1)
= gcf(x,s(x)-1)
Suppose p(x) is the smallest prime factor of g(x). Then p(x) is a
prime factor of x, but also p(x) | s(x)-1, and hence p(x) < s(x). This
contradicts the minimality of s(x). So no such p(x) exists, so g(x) = 1.
> Now, given integer x >= 2, define sequence a[x] by taking f
> repeatedly on x.
Remark: 1 cannot appear in any such a[x], nor can 2 in any position
apart from initially in a[2].
> a[2] begins with the values
>
> 2*, 3*, 5*, 9, 11*, 21, 23*, 45, 47*, 93, 95, 99, 101*, ...
>
> Note that a[2] is fairly heavily laced with primes. However,
>
> 2. Show that every a[x] contains an infinite number of
> composite elements
It is sufficient to show that given any x, the sequence a[x]
contains a composite element. Assume the contrary. Then there is a prime y
such that the sequence:
y, f(y), f(f(y)), f(f(f(y))), ...
consists entirely of primes. y >= 2, by the remark above. For p prime
s(p) = p, and hence f(p) = 2p-1. Thus writing z = y-1, the series is:
z+1, 2z+1, 4z+1, 8z+1, ...
Now, y | 2^z - 1, for all prime y > 2, by a well-known theorem, and hence:
y | z*(2^zk-1) + z+1 for all k >= 1
=> y | (2^zk)z + 1 for all k >= 1
Since a[y] is monotonically increasing, this means that every zth
term, after the initial, is composite. In particular the zth term is
composite, proving a contradiction.
Thus every sequence a[x] contains a composite, and hence an infinite
number of them.
> and, indeed
>
> 3. Show that for each N >= 0, there exists an x such that the
> first N elements of a[x] are all composite.
Let a[x](j) denote the jth term of a[x]. In particular a[x](0) = x.
Let m = a[2](N-1). Then the first N terms of a[m!+2] will be composite.
Proof:
I claim that a[m!+2](j) = m! + a[2](j), for j=0,...,N-1.
This is true by induction. For j=0, it is trivial, and so now assume that
we know it to be true of j-1.
a[m!+2](j) = f(m!+a[2](j-1)). s = s(a[2](j-1)) is the smallest prime
to divide a[2](j-1). s | m!, since s =< a[2](j-1) < m (by monotonicity of
the sequence a[.]). But for any prime p < s, p | m! for the same reason, and
so (mod p) m! + a[2](j-1) == a[2](j-1) <> 0, by definition of s. So s is
also the smallest prime to divide m!+a[2](j-1). Therefore f(m!+a[2](j-1))
= m! + a[2](j-1) + s - 1 = m! + a[2](j), as required.
From this we observe trivially that for j=0,...,N-1:
(i) a[2](j) < a[m!+2](j) and
(ii) a[2](j) | a[m!+2](j)
which together are enough to show that a[m!+2] is composite for the first N
terms.
> Finally
>
> 4. Does every a[x] contain a prime number? An infinite number
> of prime numbers?
Remark: Once again, if every a[x] contains a prime number, it must
contain an infinite number of prime numbers. So the answer to the second
question is the same as the answer to the first.
Let s[x] be a sequence derived from a sequence a[x], and defined as
s[x](j) = s(a[x](j)). Is it possible that s is periodic, and hence we can
avoid a[x] containing a prime in this way? The answer is no.
Suppose that s[x] only contains a finite number of different values, in
the set V = {v(i),i=1,...,I}. Then consider v = product(i) v(i). If
a[x](j) < kv, for some constant k, then there is no way that a[x](j') >= kv,
for any j' > j. To see this observe that if s(x) = s, then x =< kv - s (the
largest multiple of s less than kv) and hence f(x) =< kv - 1. But a[x] is
monotonically increasing to infinity (since a[x](j+1) >= a[x](j)+2), so we have
a contradiction. Hence, s[x] contains an infinite number of different values.
Let's extend this idea. Let p be any prime, and let p? denote the
product of all odd primes up to and including p. Any time that
f(x) div p? > x div p?, we must have that s(x) > p. This isn't sharp enough.
Any ideas? My guess is that every sequence must spit out a prime eventually,
but I can't show it.
Regards,
Andrew.
|