Problems & Puzzles: Puzzles

Puzzle 185. Differences between consecutive nn values

Enoch Haga sent (16/6/2002) the following puzzle:

Let to be s(n) = nn - (n-1)n-1, n=>2. What are the n values such that s(n) is prime?

As a matter of fact Enoch knew the first four solutions: n = 2, 3, 4, & 7

Using Ubasic I found the next four solutions: n = 11, 17, 106 and 120.

Then I switched to my old but beloved PRIMEFORM and found one more solution: n=1907 [BTW, s(1907) has 6256 digits, and currently it's only a probable prime]

I found no more solutions up to n=5300. See EIS A072164


1. Can you prove that s(1907) is prime?*

2. Can you find another probable prime in s(n)?

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


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




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

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 =
(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:  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.


Records   |  Conjectures  |  Problems  |  Puzzles