- --- On Wed, 10/8/08, Sebastian Martin <sebi_sebi@...> wrote:
> Coprimes Puzzle

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:

>

> 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.

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. - Phil Carmody wrote:
> i=0;ps=0;pr=1;pend=1;p=1;while(p<400000000,i++;p=nextprime(p+1);

A simple optimisation follows from your post:

> 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))

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

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

> possible factor did save a small amount of time. This technique

> might be amenable to a tree-sieve and fewer bigger multiplies. Jens?)

implementing it.

--

Jens Kruse Andersen