Problems & Puzzles: Puzzles

Puzzle 206.  (N-k)/k primes

Ken Wilke sent the following puzzle, as a companion piece to Puzzle 181:

Find the smallest positive integer N such that (N - k)/k is prime for k = 1, 2, ..., n, for a given value of n.

Here are the first Wilke's results:

n

 N

1

 3

2

 6

3

 12

4

 12

5

 174600

6

 7224840

7

 10780560

8

 10780560

9

 2360150402400

10

 50060257410240

11

 7720634052774720

Needless to say that these results are not coming from a totally brute force approach.

Question: Can you extend the above table using your own approach?


Solution:

J. K. Andersen and J. Wiesenbauer found a smaller solution for n=9 than the reported by Ken Wilke. Andersen also found solutions for n=12, 13 & 14.

This what Andersen wrote:

I found a single smaller solution than Wilke for n=9: N=1086338816640 I agree with the rest of his results and add these:

n=12: N=227457297898150320

n=13: N=7272877497848202240

n=14: N=7272877497848202240 (~ 7.27*10^18)

n=15: N>10^21

I wrote a C program to eliminate candidates with small factors. prp-testing (and finally primality proving) of remaining candidates was done with PrimeForm/GW but the time for this was insignificant. I prefer to write N/k-1. N is obviously divisible by 1, 2, ..., n. For n=12, N is then divisible by 2^3, 3^2, 5, 7, 11, plus 16 because N/8-1 must be odd. So 16*9*5*7*11=55440 divides N. Let N =A*x, where A=55440 Then N/k-1 = (A/k)*x-1 = ak*x-1, where a1=A/1, ..., a12=A/12 are constants. A prime p divides N/k-1 if ak*x-1 == 0 (mod p). The value of x (mod p) decides this. For all small p, all remainders making p divide one of N/k-1 can be computed and stored during initialization. I used this for a mix of wheeling, sieving and trial factoring, making optimizations along the way. Some were only for n=15 without result so far, but I will let it run some days if nobody else finds it. The speed is around 5*10^19 pr hour but my heuristics say it could still take months. n=14 was lucky and I hope for more luck. For n=15, I use a big wheel to reduce the candidates. Only 1261568 x's out of 3706662405 = 3*5*17*19*23*29*31*37 consecutive numbers, or 1/2938, have no N/k-1 divisible by one of 3,5,17,19,23,29,31,37. These x's modulo 3706662405 are stored and this means only one N must be tested for every 2938*(55440*13) ~ 2 billion integers. These tests could be faster and I may optimize them unless the solutions show a sieve expert (maybe Phil Carmody?) has already searched much longer.

I stopped my search for n=15 at N=25*10^21 without finding a solution.

***

 

 



Records   |  Conjectures  |  Problems  |  Puzzles