Problems & Puzzles: Puzzles

Puzzle 185. Differences between consecutive nⁿ values

____________
* Nowadays it seems that the most appropriate tool for doing this is the Primo  code.

Solution:

Alireza Bakhtiari and Daniel Gronau have been working - by separate - in the same (unexpected) subject: identifying the general conditions for the compositeness of s(n).

Here is the Alireza's contribution:

The sequence S(n) produces an infinite number of composites.

I have proved that of S(n) is composite for every number of the form n = mp^2 - (m+2)p +2, where p is an arbitrary prime number and n a natural number. Below you can see the proof. Its very easy as it only uses Fermat's little theorem. Since mp^2 - (m+2)p +2 must be greater than zero, the following pairs of (p,m) : (2,1) , (2,2) , (3,1) are not allowed in the relation.

n = mp^2 - (m+2)p +2 = (p-1)(mp-2)

n = 2 mod(p) & n-1 = 1 mod(p)

S(n) = 2^((p-1)(mp-2)) - 1^(mp^2 - (m+2)p +1 ) mod(p)

and as you know for (a,p)=1 , a^(p-1) = 1 mod(p) so 2^((p-1)(mp-2)) = 1 mod(p)

then S(n) = 1 - 1 = 0 mod(p), that is S(n) is divisible by p.

But it must be mentioned that the relation does not produce all of the composites, for example when the prime number is 5 the relation says that all the numbers of the form 20k-8 or it's equivalent 20k+12 produce a composite. However for n=20k+19 there are also composites which cannot be deduced from this formula. Here are some examples of numbers which can't be found using the above relation

n=21k+9

n=42k+26

n=42k+38

It is easy to prove that these produce composites and I don't think it is necessary to write the proofs here. Anyhow the relation can be used in several ways, here are some applications for it:

1-If the last two digits of n are 12,32,52,72,92,19,39,59,79,99 , then S(n) is a composite.

If you solve the relation for p, you will find:

p=(m+2+ SQRT((m-2)^2 +4mn)) / 2m where p is a prime and m a natural number and n the number you want to examine. For m=1,2,3,.... the following concepts can be deduced:

2-For every integer n, if (1/2)(3+SQRT(1+4n)) is a prime, then S(n) is a composite.

3-For every integer n, if (1/6)(3+SQRT(1+4n)) is a prime, then S(n) is a composite.

4-For every integer n, if (1/10)(5+SQRT(1+12n)) is a prime, then S(n) is a composite.

5-For every integer n, if 1+(1/2)SQRT(2n)) is a prime, then S(n) is a composite.

and ... By following the pattern, you can find many relations to check S(n).

And now the Gronau's contribution to the same issue:

N(n) := n^n - (n-1)^(n-1)

It's easy to show that:
3|N(n) if n = 2 mod 6
5|N(n) if n is in {12,19} mod 20
7|N(n) if n is in {9,26,30,38} mod 42

If p is prime, we can always find such congruences in module p(p-1).

====================================

For some "special" values of n or (n-1) we can compute a factor immediately:
Suppose a = y^k. When we have luck, a+1 or a-1 is z*k. Set b := z*k.
Now we can factorize N with
N = | a^a - b^b |
We have:
N = | (y^a)^k - (b^z)^k |
Therefore N is composite with:
abs( b^z - y^a ) | N

Example:
Given: a = 64
a = 4^3, y = 4, k = 3
k|(64 - 1)
b = 64 - 1 = 3 * 21, z = 21
N := a^a - b^b =
3_91737_33160_04751_21672_99139_58780_64482_82678_92024_57429_55734_/
11833_86111_72454_05418_22064_75823_62345_21976_68790_03504_88519_63969
(y^a - b^z) = 4^64 - 63^21 = 2791_66843_08935_84313_05543_54661_08193_40993
and this is in fact a divisor of N (amazing: it is PRIME!)

***

On December 2005 J.K.Andersen wrote:

http://www.primenumbers.net/prptop/prptop.php  says:
7918^7918-7917^7917 (30870 digits) found by Henri Lifchitz in 2001.
I don't know whether there has been an exhaustive search to this.