Loading ...
Sorry, an error occurred while loading the content.
 

Coprimes Puzzle

Expand Messages
  • Sebastian Martin
    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 11:07 AM
      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
      perso.wanadoo.es/smaranda




      [Non-text portions of this message have been removed]
    • Phil Carmody
      ... 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 1:41 PM
        --- 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.
      • Jens Kruse Andersen
        ... 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 5:07 PM
          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.