Efficient way for generating coprime pairs












-3















I need to print the number of coprime pairs (a,b), 0 < a <= b <= n and for n = 10^8 the program should run in less than 10 seconds. I have used this method : http://mathworld.wolfram.com/CarefreeCouple.html



But the program isn't as fast as I expected.
I have heard about an effient way of solving this problem by using something called 'Farey Sequence' but the code was written in PHP and I can only understand C.



So which method can help me solve the problem? thanks for the time.










share|improve this question



























    -3















    I need to print the number of coprime pairs (a,b), 0 < a <= b <= n and for n = 10^8 the program should run in less than 10 seconds. I have used this method : http://mathworld.wolfram.com/CarefreeCouple.html



    But the program isn't as fast as I expected.
    I have heard about an effient way of solving this problem by using something called 'Farey Sequence' but the code was written in PHP and I can only understand C.



    So which method can help me solve the problem? thanks for the time.










    share|improve this question

























      -3












      -3








      -3


      1






      I need to print the number of coprime pairs (a,b), 0 < a <= b <= n and for n = 10^8 the program should run in less than 10 seconds. I have used this method : http://mathworld.wolfram.com/CarefreeCouple.html



      But the program isn't as fast as I expected.
      I have heard about an effient way of solving this problem by using something called 'Farey Sequence' but the code was written in PHP and I can only understand C.



      So which method can help me solve the problem? thanks for the time.










      share|improve this question














      I need to print the number of coprime pairs (a,b), 0 < a <= b <= n and for n = 10^8 the program should run in less than 10 seconds. I have used this method : http://mathworld.wolfram.com/CarefreeCouple.html



      But the program isn't as fast as I expected.
      I have heard about an effient way of solving this problem by using something called 'Farey Sequence' but the code was written in PHP and I can only understand C.



      So which method can help me solve the problem? thanks for the time.







      primes greatest-common-divisor






      share|improve this question













      share|improve this question











      share|improve this question




      share|improve this question










      asked Nov 28 '18 at 21:25









      SADBOYSSADBOYS

      892




      892
























          1 Answer
          1






          active

          oldest

          votes


















          1














          Your stated interest is in co-prime pairs (a, b). The carefree couple adds an additional restriction that a is square-free. Therefore it is not the same problem, though some of the math is similar. As I understand your problem it is equivalent to summing the Euler totient function from 1 to n, the so-called Totient Summatory Function.



          I do not know of any tricks that give one a simple closed form solution to come up with the answer. However, I think modifying a straightforward Sieve of Eratosthenes (SoT) should get you an answer in much less than 10 seconds in most programming languages.



          Normally running the SoT simply yields a list of the primes <= n. Our goal will change, however, to computing the complete prime-power factorization of each integer between 1 and n inclusive. To do that we must store more than a single bit of information for each sieve entry, we must store a list. As we sieve a prime p through the array, we add (p, 1) to the list already stored at that entry. Then we sieve by p2 and change the (p,1) entries in each location we hit to (p,2), and so one for each power of p <= n and every p <= n. When it finishes, you
          can compute the Totient function quickly for every value 0 <= x <= n and sum them up.



          EDIT:

          I see that there is already a much better set of answers to the question on math.stackexchange.com here. I'll leave this answer up for awhile until the disposition of the question is settled.






          share|improve this answer


























          • I have heard about a recursive way of solving my problem

            – SADBOYS
            Nov 30 '18 at 15:29











          • S(n)= (n*(n+1) )/2 -Σ{i=2..n}(S(n/i)) where S(x)=sum{i=1..x}(phi(x))

            – SADBOYS
            Nov 30 '18 at 15:30












          Your Answer






          StackExchange.ifUsing("editor", function () {
          StackExchange.using("externalEditor", function () {
          StackExchange.using("snippets", function () {
          StackExchange.snippets.init();
          });
          });
          }, "code-snippets");

          StackExchange.ready(function() {
          var channelOptions = {
          tags: "".split(" "),
          id: "1"
          };
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function() {
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled) {
          StackExchange.using("snippets", function() {
          createEditor();
          });
          }
          else {
          createEditor();
          }
          });

          function createEditor() {
          StackExchange.prepareEditor({
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: true,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: 10,
          bindNavPrevention: true,
          postfix: "",
          imageUploader: {
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          },
          onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          });


          }
          });














          draft saved

          draft discarded


















          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53528353%2fefficient-way-for-generating-coprime-pairs%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown

























          1 Answer
          1






          active

          oldest

          votes








          1 Answer
          1






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          1














          Your stated interest is in co-prime pairs (a, b). The carefree couple adds an additional restriction that a is square-free. Therefore it is not the same problem, though some of the math is similar. As I understand your problem it is equivalent to summing the Euler totient function from 1 to n, the so-called Totient Summatory Function.



          I do not know of any tricks that give one a simple closed form solution to come up with the answer. However, I think modifying a straightforward Sieve of Eratosthenes (SoT) should get you an answer in much less than 10 seconds in most programming languages.



          Normally running the SoT simply yields a list of the primes <= n. Our goal will change, however, to computing the complete prime-power factorization of each integer between 1 and n inclusive. To do that we must store more than a single bit of information for each sieve entry, we must store a list. As we sieve a prime p through the array, we add (p, 1) to the list already stored at that entry. Then we sieve by p2 and change the (p,1) entries in each location we hit to (p,2), and so one for each power of p <= n and every p <= n. When it finishes, you
          can compute the Totient function quickly for every value 0 <= x <= n and sum them up.



          EDIT:

          I see that there is already a much better set of answers to the question on math.stackexchange.com here. I'll leave this answer up for awhile until the disposition of the question is settled.






          share|improve this answer


























          • I have heard about a recursive way of solving my problem

            – SADBOYS
            Nov 30 '18 at 15:29











          • S(n)= (n*(n+1) )/2 -Σ{i=2..n}(S(n/i)) where S(x)=sum{i=1..x}(phi(x))

            – SADBOYS
            Nov 30 '18 at 15:30
















          1














          Your stated interest is in co-prime pairs (a, b). The carefree couple adds an additional restriction that a is square-free. Therefore it is not the same problem, though some of the math is similar. As I understand your problem it is equivalent to summing the Euler totient function from 1 to n, the so-called Totient Summatory Function.



          I do not know of any tricks that give one a simple closed form solution to come up with the answer. However, I think modifying a straightforward Sieve of Eratosthenes (SoT) should get you an answer in much less than 10 seconds in most programming languages.



          Normally running the SoT simply yields a list of the primes <= n. Our goal will change, however, to computing the complete prime-power factorization of each integer between 1 and n inclusive. To do that we must store more than a single bit of information for each sieve entry, we must store a list. As we sieve a prime p through the array, we add (p, 1) to the list already stored at that entry. Then we sieve by p2 and change the (p,1) entries in each location we hit to (p,2), and so one for each power of p <= n and every p <= n. When it finishes, you
          can compute the Totient function quickly for every value 0 <= x <= n and sum them up.



          EDIT:

          I see that there is already a much better set of answers to the question on math.stackexchange.com here. I'll leave this answer up for awhile until the disposition of the question is settled.






          share|improve this answer


























          • I have heard about a recursive way of solving my problem

            – SADBOYS
            Nov 30 '18 at 15:29











          • S(n)= (n*(n+1) )/2 -Σ{i=2..n}(S(n/i)) where S(x)=sum{i=1..x}(phi(x))

            – SADBOYS
            Nov 30 '18 at 15:30














          1












          1








          1







          Your stated interest is in co-prime pairs (a, b). The carefree couple adds an additional restriction that a is square-free. Therefore it is not the same problem, though some of the math is similar. As I understand your problem it is equivalent to summing the Euler totient function from 1 to n, the so-called Totient Summatory Function.



          I do not know of any tricks that give one a simple closed form solution to come up with the answer. However, I think modifying a straightforward Sieve of Eratosthenes (SoT) should get you an answer in much less than 10 seconds in most programming languages.



          Normally running the SoT simply yields a list of the primes <= n. Our goal will change, however, to computing the complete prime-power factorization of each integer between 1 and n inclusive. To do that we must store more than a single bit of information for each sieve entry, we must store a list. As we sieve a prime p through the array, we add (p, 1) to the list already stored at that entry. Then we sieve by p2 and change the (p,1) entries in each location we hit to (p,2), and so one for each power of p <= n and every p <= n. When it finishes, you
          can compute the Totient function quickly for every value 0 <= x <= n and sum them up.



          EDIT:

          I see that there is already a much better set of answers to the question on math.stackexchange.com here. I'll leave this answer up for awhile until the disposition of the question is settled.






          share|improve this answer















          Your stated interest is in co-prime pairs (a, b). The carefree couple adds an additional restriction that a is square-free. Therefore it is not the same problem, though some of the math is similar. As I understand your problem it is equivalent to summing the Euler totient function from 1 to n, the so-called Totient Summatory Function.



          I do not know of any tricks that give one a simple closed form solution to come up with the answer. However, I think modifying a straightforward Sieve of Eratosthenes (SoT) should get you an answer in much less than 10 seconds in most programming languages.



          Normally running the SoT simply yields a list of the primes <= n. Our goal will change, however, to computing the complete prime-power factorization of each integer between 1 and n inclusive. To do that we must store more than a single bit of information for each sieve entry, we must store a list. As we sieve a prime p through the array, we add (p, 1) to the list already stored at that entry. Then we sieve by p2 and change the (p,1) entries in each location we hit to (p,2), and so one for each power of p <= n and every p <= n. When it finishes, you
          can compute the Totient function quickly for every value 0 <= x <= n and sum them up.



          EDIT:

          I see that there is already a much better set of answers to the question on math.stackexchange.com here. I'll leave this answer up for awhile until the disposition of the question is settled.







          share|improve this answer














          share|improve this answer



          share|improve this answer








          edited Nov 29 '18 at 0:06

























          answered Nov 28 '18 at 23:43









          James K PolkJames K Polk

          30.5k116997




          30.5k116997













          • I have heard about a recursive way of solving my problem

            – SADBOYS
            Nov 30 '18 at 15:29











          • S(n)= (n*(n+1) )/2 -Σ{i=2..n}(S(n/i)) where S(x)=sum{i=1..x}(phi(x))

            – SADBOYS
            Nov 30 '18 at 15:30



















          • I have heard about a recursive way of solving my problem

            – SADBOYS
            Nov 30 '18 at 15:29











          • S(n)= (n*(n+1) )/2 -Σ{i=2..n}(S(n/i)) where S(x)=sum{i=1..x}(phi(x))

            – SADBOYS
            Nov 30 '18 at 15:30

















          I have heard about a recursive way of solving my problem

          – SADBOYS
          Nov 30 '18 at 15:29





          I have heard about a recursive way of solving my problem

          – SADBOYS
          Nov 30 '18 at 15:29













          S(n)= (n*(n+1) )/2 -Σ{i=2..n}(S(n/i)) where S(x)=sum{i=1..x}(phi(x))

          – SADBOYS
          Nov 30 '18 at 15:30





          S(n)= (n*(n+1) )/2 -Σ{i=2..n}(S(n/i)) where S(x)=sum{i=1..x}(phi(x))

          – SADBOYS
          Nov 30 '18 at 15:30




















          draft saved

          draft discarded




















































          Thanks for contributing an answer to Stack Overflow!


          • Please be sure to answer the question. Provide details and share your research!

          But avoid



          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.


          To learn more, see our tips on writing great answers.




          draft saved


          draft discarded














          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53528353%2fefficient-way-for-generating-coprime-pairs%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown





















































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown

































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown







          Popular posts from this blog

          A CLEAN and SIMPLE way to add appendices to Table of Contents and bookmarks

          Calculate evaluation metrics using cross_val_predict sklearn

          Insert data from modal to MySQL (multiple modal on website)