## Coprimes Puzzle

Expand Messages
• Coprimes 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   Find the
Message 1 of 3 , Oct 8, 2008
Coprimes 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

Find the following one G(n)>1 or prove that don’t exist.

Sincerely

Sebastian Martin Ruiz

[Non-text portions of this message have been removed]
• ... Nice puzzle. The heuristics were non-obvious. Each time I think I push the number of solutions towards infinity, I come up with a reason why it should be
Message 2 of 3 , Oct 8, 2008
--- On Wed, 10/8/08, Sebastian Martin <sebi_sebi@...> wrote:
> Coprimes 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
>
> Find the following one G(n)>1 or prove that don’t exist.

Nice puzzle. The heuristics were non-obvious. Each time I think I push the number of solutions towards infinity, I come up with a reason why it should be finite, and vice versa. Here are a few of my thoughts:

The number of solutions is strictly greater than the number of solutions to
Sum[Prime[i],{i,1,n}] | 1+Product[Prime[i],{i,1,n}]
(as that would make the GCD equal to the sum, which is not required.

Ignoring the q#+1 form of the product term, one would expect the number of solutions of that to grow roughly like Sum[1/(i*Prime[i])], which clearly converges. So it's greater than something that converges. Oh joy.

Flipping back to the GCD form, the q#+1 form means that any factor of the sum which is less than the current prime, q, can not be a factor. That means that only sums who have a prime factor > q can have a solution. That makes the solutions sparser, but only by a constant factor. (Is this true? Is it Erdos-Kac or similar?). Each sum can only have one of these prime factors, so if one could model the average (sloppy term) size of that factor, one could sum their reciprocals. This sum is between that of 1/p and 1/p^2. 1/p only just diverges, so it really won't take much to make the sum converge, and the expected number of solutions to be finite.

While I was pondering, I checked up n=350000 p=5023307, and found only your result. The program slows down quadratically, alas:

-- 8< -- Pari/GP script
i=0;ps=0;pr=1;pend=1;p=1;while(p<400000000,i++;p=nextprime(p+1);ps+=p;if(i%10000==0,print(i" "p));f=factor(ps);l=length(f~);if(f[l,1]>p,pr*=pend*p;pend=1;if((g=gcd(pr+1,ps))>1,print(i" "p" "ps" "factor(ps)" "g)),pend*=p))
-- 8< --
(The optimisation of only performing the * and % when there's possible factor did save a small amount of time. This technique might be amenable to a tree-sieve and fewer bigger multiplies. Jens?)

However, my money's on there being no others.
• ... A simple optimisation follows from your post: If gcd(pr+1,ps) 1 then gcd(pr+1,ps) must be f[l,1] (the largest prime factor of ps). So gcd(pr+1,ps) 1 can be
Message 3 of 3 , Oct 8, 2008
Phil Carmody wrote:
> i=0;ps=0;pr=1;pend=1;p=1;while(p<400000000,i++;p=nextprime(p+1);
> ps+=p;if(i%10000==0,print(i" "p));f=factor(ps);l=length(f~);
> if(f[l,1]>p,pr*=pend*p;pend=1;if((g=gcd(pr+1,ps))>1,
> print(i" "p" "ps" "factor(ps)" "g)),pend*=p))

A simple optimisation follows from your post:
If gcd(pr+1,ps)>1 then gcd(pr+1,ps) must be f[l,1] (the largest
prime factor of ps).
So gcd(pr+1,ps)>1 can be replaced by the faster (pr+1)%f[l,1]==0.
In my timings, using pr%f[l,1]==f[l,1]-1 was a few percent faster than
(pr+1)%f[l,1]==0.
I have tested to n=1000000, p=15485863 with no new solution.

> (The optimisation of only performing the * and % when there's
> possible factor did save a small amount of time. This technique
> might be amenable to a tree-sieve and fewer bigger multiplies. Jens?)

Yes, a tree-sieve should make it much faster but I'm not spending time
implementing it.

--
Jens Kruse Andersen
Your message has been successfully submitted and would be delivered to recipients shortly.