Problems & Puzzles: Puzzles

Puzzle 618. GCD(1+P, S) Sebastián Martín Ruiz sent the following puzzle. Let G(n)=GCD(1+Product[Prime[i],{i,1,n}] , Sum[Prime[i],{i,1,n}])G(n)=1 for all n=1,2,3,….,10000,  except  G(61)= 307. Q. Find the following one G(n)>1 or prove that don’t exist.

---

Contributions came from Jan van Delden, Farideh Firoozbakht & Jahangeer Jhon (kholdi)

***

Jan wrote:

I checked untill n=586020, p=8736617, no further solutions with gcd(1+P,S)>1.

 

If a solution exists we must have that 1+P has a divisor q, since S<1+P, such a divisor q>p[n]. Furthermore the gcd(1+P,S) will probably only consist of one primefactor q: We have that p[n] grows like n.ln(n) and the sum S has order  n^2.ln(n)/2 (roughly !). Since q is larger than p[n], which has order n.ln(n), we can’t have two factors q1,q2  (large n).

 

However I see no reason why other solutions might not exist.

***

FF & JJ wrote:

We didn't find another such number up to 110000. we guess that there is no

any other ones. Also we think there is no any proof for this claim.

 

We found the following similar functions with the similar properties.

 

1. f1(n) = GCD (1+Product[Prime[i],{i,1,n}],1+Sum[Prime[i],{i,1,n}]),  It's obvious that f1(1) >1.

 We did'nt find another number n (up to 160000) such that f1(n)>1. 

 

2. f2(n) = GCD (1+Product[Prime[i],{i,1,n}],-1+Sum[Prime[i],{i,1,n}]),   f2(7) = 19 and we did'nt find another number n (up to 95000) such that f2(n)>1. 

 

3. f3(n) = GCD (-1+Product[Prime[i],{i,1,n}],1+Sum[Prime[i],{i,1,n}]), We did'nt find any number n (up to 20000) such that f3(n)>1. 

 

 4. If instead of 1+Sum[Prime[i],{i,1,n}] we write m+Sum[Prime[i],{i,1,n}] for integers m we will obtain infinitely many such functions. ",

***

Emmanuel wrote on Jan 3, 2012:

About puzzle 618 : if one replaces the primorial by factorial n  and the sum of all primes by the sum of all numbers up to  n, then you have a nice reformulation of Wilson's theorem :

         GCD(1 + n! , 1+2+ ... + n) > 1   iff  n+1  is prime

         and, if  n+1  is prime, then  GCD(1 + n! , 1+2+ ... + n) = n+1 .

***