Problems & Puzzles: Puzzles

Puzzle 479. P+1 & P+1+S are primes JM Bergot sent the following nice puzzle: 3*4*5 + 1=61 and 61+3+4+5=73 are both primes. ¿How rare is this? (you are allowed to use any starting n number and any quantity of consecutive of them)

---

Contributions came from: Giovanni Resta, Jacques Tramu, Fred Schneider, Farideh Firoozbakht, Matt Maden, Antoine Verroken, J. K. Andersen & W. Edwin Clark

***

Giovanni Resta

A few observations.

First of all, the example
"3*4*5*6 + 1=361 and 361+3+4+5+6=379 are both primes."
is not appropriate, since 361 = 19 x 19 is not prime...

In general P+1 and P+1+S are both primes quite often.
To be a little more formal
I considered the two functions and the couple:
P(n,k) = n*(n+1)*...*(n+k-1) + 1
S(n,k) = P(n,k) + n + (n+1) + ... + (n+k-1).
C(n,k) = {P(n,k), S(n,k)}

so, n is the starting point and k is the number
of terms and C(n,k) is the pair of numbers we want to be
primes.

I considered the cases with small k from 1 to 10.

K=1
(Quite trivial) here C(n,1) = {n+1, 1+2n}.
The pair is of primes for n = 1,2,6,18,30,36,78,96,...

K=2
here factorizing, C(n,2) ={n^2+n+1,(n+1)(n+2)},
so the last term is never prime.

K=3
We have primes for
n = 1,3,5,9,49,83,91,101,133,241,255,271,...

K=4
Here the P(n,4) = (n^2+3n+1)^2 so
we cannot have pairs of primes.

K=5
Here n=852,904,1050,1498,1722,1996,2184,2208,...

K=6
It is easy to see that S(n,6) is always even,
and moreover divisible by n^2+4n+2

k=7
Here n=225, 277, 433, 535, 637, 2851,...

k=8
This is the smallest even K for which there
are solutions.
n = 93,136,235,373,474,525,676,931,1405,...

k=9
n = 26, 50, 88, 180, 626, 1164, 1466,...

k=10
Also in this case S(n,10) is always even.

In general, it is easy to see that,
when k = 4*t+2 (k=2,6,10,14,18,...),
the second member of the pair is always even,
since the sum of the numbers from
n to n+4t+2-1 is equal to (2t+1)(2n+4t+1) which
is odd, and thus added to P(n,k) which is
odd, gives always an even number.

Here are the smallest pairs for k from 11 to 20:
C(85,11), C(26,12), C(6,13), C(453,15),
C(67,16), C(1000,17), C(133,19), C(900,20).

some larger pairs are
C(10554,100) Here the two primes have 403 digits each.
C(351,300) with 808 digits.

***

Jacques Tramu
1 + a*(a+1)*(a+2)*(a+3)
= 1 + 6 a + 11 a^2 + 6 a^3 + a^4
= ((a+1)^2 +a)^2 = perfect square

So : 1 + a*(a+1)*(a+2)*(a+3) is NEVER prime .

On the contrary, we have a lot of examples, if the chain length is not 4 .

Well, I tried sequences lengths from 3 to 100
and found fhe following :

for example :
length = 5
starter = 852

S1 = 1 + 852*853*854*855*856 = 454241046813121 (prime)
S2 = S1 + 852+853+854+855+856 = 454241046817391 (prime)

Length starter
------------------------

3 1
4 NOT POSSIBLE
5 852
6 ?
7 225
8 93
9 26
10 ?
11 85
12 52
13 6
14 ?
15 453
16 67
17 1000
18 ?
19 133
20 900
21 712
22 ?
23 11455
24 100
25 13984
26 ?
27 9091
28 598
29 1950
30 ?
31 11095
32 951
33 90
34 ?
35 4629
36 536
37 12252
38 ?
39 3123
40 3006
41 3708
42 ?
43 11733
44 2269
45 12274
46 ?
47 2997
48 519
49 23916
50 ?
51 3105
52 8001
53 ?
54 ?
55 39067
56 217
57 1606
58 ?
59 7443
60 33821
61 30208
62 ?
63 251
64 21928
65 16224
66 ?
67 16017
68 52443
69 25180
70 ?
71 42547
72 9630
73 ?
74 ?
75 25655
76 8445
77 27478
78 ?
79 60181
80 46102
81 ?
82 ?
83 ?
84 28059
85 15190
86 0
87 50273
88 15535
89 24106
90 ?
91 25171
92 31645
93 12058
94 ?
95 ?
96 16183
97 ?
98 ?
99 51241
100 10554

------------------------------------------
Questions :
Any sequence of length 6 ?
Given l > 4, does exist any sequence of length l ?
------------------------------------------------------------------------

Scope of search:

For length L <= 18 I tried all possibe starters up to 10^7 .
For other length L I tried all possible starters up to 10^6 . (new results for L = 53, L=73 , L=81 ,see below)

if L = 4 - NO SOLUTION (see below)

if L = 4*K + 2

Let S1 = 1 + n*(n+1)*...*(n+L-1) , prime,odd .
Let S2 = n + (n+1) + (n+2) . ... (n+L-1) = L*n + (2 *k +1)*(4*k +3) == odd .
So S1(prime) + S2 cannot be prime -
So, no solution for L == 2 (mod 4) (L=6,10,14,...)

For the other L , may be the lack of computing power

***

Fred Schneider

Below "solution" stands for a prime p such that p plus the sum (of p-1's factors) is also prime.

If there are p primes and s solutions between the numbers a and b, we make the calculations of (b-a+1)/p and p/s, to show
the frequency of primes and the frequency of primes which are solutions, respectively.

Between 1 and 10, there was 1 solution. There are 4 primes between 1 and 10: 10/4=2.5, and 4/1=4

Between 10 and 100, there were 5 solutions. There are 21 primes between 10 and 100: 91/21=4.33, and 21/5=4.2

Between 100 and 1000, there were 17 solutions. There are 143 primes between 100 and 1000: 901/143=6.3 and 143/17=8.41

Between 1000 and 10000, there were 145 solutions. There are 1061 primes between 1000 and 10000: 9001/1061=8.48 and 1061/145=7.31

Between 10000 and 100000, there were 809 solutions. There are 8363 primes between 10000 and 100000: 90001/8363=10.76 and 8363/809=10.34

Between 100000 and 1000000, there were 5254 solutions. There are 68906 primes between 100000 and 1000000: 900001/68906=13.06 and 68906/5254=13.11

Between 1000000 and 10000000, there were 37971 solutions. There are 586081 primes between 1000000 and 10000000: 9000001/586081=15.36 and 586081/37971=15.43

Between 10000000 and 100000000, there were 284876 solutions. There are 5096876 primes between 10000000 and 100000000: 90000001/5096876=17.66 and 5096876/284876=17.89

Between 100000000 and 1000000000, there were 2211149 solutions. There are 45086079 primes between 100000000 and 1000000000: 900000001/45086079=19.96 and 45086079/2211149=20.39

So , we see that as times goes on the proportion of primes which have solutions to this puzzle is slightly less than the proportion of primes themselves.

***

Farideh

There exists many such pair of primes.
Some of them which obtaining by more than ten consecutive numbers are as follows.


p1 = 26*27*...*37+1 = 37!/25!+1 = 887342319056793601
p2 = p1+ (26+27+...+37) = 37!/25!+379 = 887342319056793979

p1= 52*53* ...*63 +1 = 63!/51!+1 = 1278179579224720972801
p2 = p1 + (52+53+...+63) = 1278179579224720973491

p1 = 67*68*...*82+1 = 82!/66!+1 = 873277768517390163008040960001
p2 = p1 + (67+68+...+82) = 873277768517390163008040961193

***

Matt Maden

I'd say it is slightly rare.

Out of the starting values 1 to 50, I found the following n's with the necessary condition:

1: {1, 2, 3}
2: {2}
3: {3, 4, 5}
5: {5, 6, 7}
6: {6}
9: {9, 10, 11}
18: {18}
30: {30}
36: {36}
49: {49, 50, 51}

That is 10/50.

Now I have two questions of my own for this problem.

Given the puzzle as it is:

1. Are there any numbers that have more than one solution?
2. Are there any numbers that have a solution that is not of length 1 or 3?

***

Antoine Verroken

A heuristic estimate ( = educated guess,not real mathematics ) for the number of primes “A” of
the form w = (a-i) * a * (a+i) + 1 , [ i = 1 .. inf. ; a = 0 ..inf.] if v = w + r * a , [ r number of a’s in
w ] is also prime is : A = k * N / ( ln N )^2 k : constant;a measure of how far
from independly random the values are.

Limit ( N à infinity ) of A ~= infinit ~ there are probably infinitely many such primes ( this is not
a proof that there are infinitely many primes of the form w,v ).

Computer search :

N A P primes
i = 1 % P i = 2 % P i = 3 % P

10^6 5134 6.54 1310 1.67 840 1.07 72.498
3*10^6 13051 6.52 3291 1.65 2142 1.07 200.000
5*10^6 19985 6.15 5147 1.58 3295 1.01 325.000~
7*10^6 26646 5.92 6866 1.53 4463 0.99 450.000~
9*10^6 32957 5.9 8561 1.53 5338 0.99 560.000~
10*10^6 36265 5.8 9411 1.51 6092 0.97 625.000~

Probably the sum of “ % P “ for i and N à infinity is 100%

***

J. K. Andersen

There are no solutions with length 4 because:
n*(n+1)*(n+2)*(n+3)+1 = (n^2+3*n+1)^2.
There are no solutions with length of form 4m+2, because the sum S will
always contain an odd amount (2m+1) of odd numbers, and then S becomes odd.
This means P+1+S is even, since P is even for all lengths above 1.
I guess all other lengths than 4 and 4m+2 have infinitely many solutions.

Below is the smallest solution (k, n) for all lengths k from 1 to 155,
except the impossible lengths 4 and 4m+2.
n is the first of the k consecutive numbers.
PrimeForm/GW proved all primes P+1. Marcel Martin's Primo proved all P+1+S.

(1, 1), (3, 1), (5, 852), (7, 225), (8, 93), (9, 26), (11, 85), (12, 26),
(13, 6), (15, 453), (16, 67), (17, 1000), (19, 133), (20, 900), (21, 712),
(23, 11455), (24, 100), (25, 13984), (27, 9091), (28,598), (29, 1950),
(31, 11095), (32, 951), (33, 90), (35, 4629), (36, 536), (37, 12252),
(39, 3123), (40, 3006), (41, 3708), (43, 11733), (44, 2269), (45, 12274),
(47, 2997), (48, 519), (49, 23916), (51, 3105), (52, 8001), (53, 83890),
(55, 39067), (56, 217), (57, 1606), (59, 7443), (60, 33821), (61, 30208),
(63, 251), (64, 21928), (65, 16224), (67, 16017), (68, 52443), (69, 25180),
(71, 42547), (72, 9630), (73, 207466), (75, 25655), (76, 8445), (77, 27478),
(79, 60181), (80, 46102), (81, 100538), (83, 399733), (84, 28059),
(85, 15190), (87, 50273), (88, 15535), (89, 24106), (91, 25171),
(92, 31645), (93, 12058), (95, 97795), (96, 16183), (97, 464196),
(99, 51241), (100, 10554), (101, 17482), (103, 675249), (104, 29806),
(105, 10884), (107, 24375), (108, 57115), (109, 247230), (111, 136471),
(112, 7722), (113, 122820), (115, 44415), (116, 708), (117, 17020),
(119, 104083), (120, 13168), (121, 2206), (123, 105193), (124, 23569),
(125, 186634), (127, 6613), (128, 37875), (129, 1054), (131, 13173),
(132, 25096), (133, 27534), (135, 69791), (136, 7420), (137, 2386),
(139, 253005), (140, 85656), (141, 2546), (143, 56409), (144, 17103),
(145, 135126), (147, 203555), (148, 61813), (149, 671920), (151, 1581907),
(152, 4683), (153, 53716), (155, 3879)

The largest n was 1581907 for k = 151.

***
W. Edwin Clark


I interpret the question as follows:

Define for each positive integer k two
polynomials in the variable t as follows:

p_k(t) = t(t + 1)(t + 2)...(t + k - 1) + 1
q_k(t) = p(k) + t + (t + 1) + (t + 2) + ... + (t + k - 1):

We seek integers k and n such that

p_k(n) and q_k(n) are both primes.

I can prove that for k from 1 to 100 there is no n such
that p_k(n) and q_k(n) are both primes precisely when k is in the set:

{2, 4, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50,
54, 58, 62, 66, 70, 74, 78, 82, 86, 90, 94, 98}

[Note: This is not http://www.research.att.com/~njas/sequences/A139544
since if k = 101, n = 17482, then p_k(n) and q_k(n) are both primes.]

In the lists below a pair [k,n] indicates that n = smallest
positive integer such that p_k(n) and q_k(n) are both primes,
or "none" if I can prove there is no such n. In this list
except for k = 4 the values of k for which no n exists are
those congruent to 2 mod 4. Perhaps someone can prove it in
general?

[ 1, 1], [ 2, none], [ 3, 1], [ 4, none],
[ 5, 852], [ 6, none], [ 7, 225], [ 8, 93],
[ 9, 26], [ 10, none], [ 11, 85], [ 12, 26],
[ 13, 6], [ 14, none], [ 15, 453], [ 16, 67],
[ 17, 1000], [ 18, none], [ 19, 133], [ 20, 900],
[ 21, 712], [ 22, none], [ 23, 11455], [ 24, 100],
[ 25, 13984], [ 26, none], [ 27, 9091], [ 28, 598],
[ 29, 1950], [ 30, none], [ 31, 11095], [ 32, 951],
[ 33, 90], [ 34, none], [ 35, 4629], [ 36, 536],
[ 37, 12252], [ 38, none], [ 39, 3123], [ 40, 3006],
[ 41, 3708], [ 42, none], [ 43, 11733], [ 44, 2269],
[ 45, 12274], [ 46, none], [ 47, 2997], [ 48, 519],
[ 49, 23916], [ 50, none], [ 51, 3105], [ 52, 8001],
[ 53, 83890], [ 54, none], [ 55, 39067], [ 56, 217],
[ 57, 1606], [ 58, none], [ 59, 7443], [ 60, 33821],
[ 61, 30208], [ 62, none], [ 63, 251], [ 64, 21928],
[ 65, 16224], [ 66, none], [ 67, 16017], [ 68, 52443],
[ 69, 25180], [ 70, none], [ 71, 42547], [ 72, 9630],
[ 73, 207466], [ 74, none], [ 75, 25655], [ 76, 8445],
[ 77, 27478], [ 78, none], [ 79, 60181], [ 80, 46102],
[ 81, 100538], [ 82, none], [ 83, 399733], [ 84, 28059],
[ 85, 15190], [ 86, none], [ 87, 50273], [ 88, 15535],
[ 89, 24106], [ 90, none], [ 91, 25171], [ 92, 31645],
[ 93, 12058], [ 94, none], [ 95, 97795], [ 96, 16183],
[ 97, 464196], [ 98, none], [ 99, 51241], [100, 10554],


I skipped over many values and searched around k = 500 to
find the pair [503, 6999].

This problem is related to Schinzel's Hypothesis H:

http://en.wikipedia.org/wiki/Schinzel's_hypothesis_H

Schinzel's Hypothesis H for two polynomials over Z:
If f(x) and g(x) are irreducible polynomials over Q and there is no
m > 1 such that f(n)g(n)/m is an integer for all integers n,
then there are infinitely many values of n such that both
f(n) and g(n) are primes.

I believe my methods show that for values of k from
1 to 100 in the above list for which there is one value
of n, IF Schinzel's Hypothesis H is true, there will
be infinitely many n such that p_k(n) and q_k(n) are both primes.
If not we will have a counter-example to this famous conjecture

***