Results 1 to 18 of 18
  1. #1
    CodeX Pro is offline Member
    Join Date
    Dec 2012
    Posts
    32
    Rep Power
    0

    Default euler function problem

    Below is the question and my code. I don't know why its not working need some help

    Question
    Let S(n,m) = ∑φ(n i) for 1 ≤ i ≤ m. (φ is Euler's totient function)
    You are given that S(510510,10^6 )= 45480596821125120.

    Find S(510510,10^11).

    Java Code:
    import java.math.BigInteger;
    
    public class TotientSum {
    
        private static final int n = 510510;
    
        private static String calculateSum(){
            BigInteger sum = null;                
            for(BigInteger i= BigInteger.valueOf(10).pow(11);i.compareTo(BigInteger.ONE)>0;i =i.subtract(BigInteger.ONE)){
                sum=sum.add(totient(i.multiply(BigInteger.valueOf(n))));
            }
            return sum.toString();
        }
        private static BigInteger totient(BigInteger num) { 
            int count = 0;
            for (BigInteger a = BigInteger.ONE; a.compareTo(num)<0; a=a.add(BigInteger.ONE)) { 
                if (gcd(num, a) == BigInteger.ONE) {  
                    count++;
                }
            }
            return (BigInteger.valueOf(count));
        }
    
        private static BigInteger gcd(BigInteger p, BigInteger q) {
            while (q != BigInteger.ZERO) {
                BigInteger temp = q;
                q = p.mod(q);
                p = temp;
            }
            return p;
        }
    
        public static void main(String[] args) {
            System.out.println(calculateSum());
        }
    }
    Last edited by CodeX Pro; 06-16-2013 at 04:25 PM.

  2. #2
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,764
    Rep Power
    5

    Default Re: euler function problem

    Try using:
    Java Code:
    if (gcd(num, a).equals(BigInteger.ONE)) {
      count++;
    }
    instead of

    Java Code:
    if (gcd(num, a) == BigInteger.ONE) {
      count++;
    }
    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  3. #3
    DarrylBurke's Avatar
    DarrylBurke is offline Forum Police
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    11,404
    Rep Power
    20

    Default Re: euler function problem

    ... and a similar construct in line 25.

    db
    If you're forever cleaning cobwebs, it's time to get rid of the spiders.

  4. #4
    CodeX Pro is offline Member
    Join Date
    Dec 2012
    Posts
    32
    Rep Power
    0

    Default Re: euler function problem

    Quote Originally Posted by jim829 View Post
    Try using:
    Java Code:
    if (gcd(num, a).equals(BigInteger.ONE)) {
      count++;
    }
    instead of

    Java Code:
    if (gcd(num, a) == BigInteger.ONE) {
      count++;
    }
    Regards,
    Jim
    Didn't work. Its taking very long to run. Tell me one thing whether I have implemented the functions properly or not. I think its okay.

    Will you please to help me with this.

  5. #5
    DarrylBurke's Avatar
    DarrylBurke is offline Forum Police
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    11,404
    Rep Power
    20

    Default Re: euler function problem

    Get this straight: using == or != to compare object types is just plain wrong. Use equals(...) and !...equals(...).

    db
    If you're forever cleaning cobwebs, it's time to get rid of the spiders.

  6. #6
    CodeX Pro is offline Member
    Join Date
    Dec 2012
    Posts
    32
    Rep Power
    0

    Default Re: euler function problem

    Quote Originally Posted by DarrylBurke View Post
    Get this straight: using == or != to compare object types is just plain wrong. Use equals(...) and !...equals(...).

    db
    yes I did didn't work. I would ask you to run this code and see the problem that I am facing

  7. #7
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,764
    Rep Power
    5

    Default Re: euler function problem

    Good catch! I didn't see that first time thru. Was getting ready to respond....

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  8. #8
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,764
    Rep Power
    5

    Default Re: euler function problem

    When I have problems like this I usually put print statements thru out the program to see if they are even close to satisfying my conditionals (among other things). What type of debugging have you done?

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  9. #9
    CodeX Pro is offline Member
    Join Date
    Dec 2012
    Posts
    32
    Rep Power
    0

    Default Re: euler function problem

    Quote Originally Posted by jim829 View Post
    When I have problems like this I usually put print statements thru out the program to see if they are even close to satisfying my conditionals (among other things). What type of debugging have you done?

    Regards,
    Jim
    I have used print statements but they are taking very long to print and this can be understood very well from the maths applied here. So are there better approaches. Also I fear that BigInteger is not big enough to hold the numbers

  10. #10
    DarrylBurke's Avatar
    DarrylBurke is offline Forum Police
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    11,404
    Rep Power
    20

    Default Re: euler function problem

    Quote Originally Posted by CodeX Pro View Post
    I fear that BigInteger is not big enough to hold the numbers
    Read the API.
    BigIntegers are made as large as necessary to accommodate the results of an operation.
    db
    If you're forever cleaning cobwebs, it's time to get rid of the spiders.

  11. #11
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,651
    Blog Entries
    7
    Rep Power
    21

    Default Re: euler function problem

    I think you should apply a bit of math instead of trying to solve that bloody thing by brute force; for one thing: phi(n*m) == phi(n)*phi(m)*g/phi(g) where g == gcd(n, m), also 10^11 == 2^11*5^11 ... and phi(2) == 1 and phi(5) == 4

    kind regards,

    Jos (<--- extremely lazy on a Sunday)
    cenosillicaphobia: the fear for an empty beer glass

  12. #12
    CodeX Pro is offline Member
    Join Date
    Dec 2012
    Posts
    32
    Rep Power
    0

    Default Re: euler function problem

    Quote Originally Posted by JosAH View Post
    I think you should apply a bit of math instead of trying to solve that bloody thing by brute force; for one thing: phi(n*m) == phi(n)*phi(m)*g/phi(g) where g == gcd(n, m), also 10^11 == 2^11*5^11 ... and phi(2) == 1 and phi(5) == 4

    kind regards,

    Jos (<--- extremely lazy on a Sunday)
    Java Code:
    import java.math.BigInteger;
    
    /**
     *
     * @author CodeX Pro
     */
    
    public class TotientSum {
    
        private static BigInteger n = BigInteger.valueOf(510510);
    
        private static String calculateSum() {
            BigInteger sum = BigInteger.ZERO;
            for (BigInteger i = BigInteger.ONE; i.compareTo(BigInteger.valueOf(10).pow(11)) < 0; i = i.add(BigInteger.ONE)) {
                BigInteger m = (totient(n).multiply(totient(i))).multiply((gcd(n, i).divide(totient(gcd(n, i)))));
                //System.out.println(m);
                sum = sum.add(m);
                //System.out.println(sum);
            }
            return sum.toString();
        }
    
        private static BigInteger totient(BigInteger num) {
            int count = 0;
            for (BigInteger a = BigInteger.ONE; a.compareTo(num) < 1; a = a.add(BigInteger.ONE)) {
                if (gcd(num, a).equals(BigInteger.ONE)) {
                    count++;
                }
            }
            return (BigInteger.valueOf(count));
        }
    
        private static BigInteger gcd(BigInteger p, BigInteger q) {
            while (!q.equals(BigInteger.ZERO)) {
                BigInteger temp = q;
                q = p.mod(q);
                p = temp;
            }
            return p;
        }
    
        public static void main(String[] args) {
            System.out.println(calculateSum());
        }
    }


    Okay I did so I have read it on wiki and used the formula still its not giving the output. Its taking a long time.


    What did you meant to say by this "also 10^11 == 2^11*5^11 ... and phi(2) == 1 and phi(5) == 4" , I didn't get this part
    Last edited by CodeX Pro; 06-16-2013 at 08:01 PM.

  13. #13
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,764
    Rep Power
    5

    Default Re: euler function problem

    Quote Originally Posted by CodeX Pro View Post
    I have used print statements but they are taking very long to print and this can be understood very well from the maths applied here. So are there better approaches.
    If they're taking to long to print then you are putting them in the wrong place. Try moving them to where they will print. Like inside a loop.

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  14. #14
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,651
    Blog Entries
    7
    Rep Power
    21

    Default Re: euler function problem

    This message has been deleted by jim829.

    ReasonDecided to let Jos explain it
    Please don't; I didn't give this problem much thought except for the suggestions in my previous reply. Especially phi(a*b) == phi(a)*phi(b)*gcd(a,b)/phi(gcd(a,b)) should do the trick (just my gut feeling)

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  15. #15
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,764
    Rep Power
    5

    Default Re: euler function problem

    Sorry. I started to provide some review on algebra and number theory but I was going down a black hole. And I couldn't tie what you said to an immediate solution at the time. So I didn't want to mislead the OP. And it was midnight here and I was tired.

    I enjoy this stuff so I will work on it some. But after putting in some print statements I am uncertain this would finish in my lifetime. Iterating from 1 to 510510 x 10E11 by itself could take a while (I didn't time it). But to successively do that over and over again using the GCD and PHI algorithms just looked like it would take forever.

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  16. #16
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,651
    Blog Entries
    7
    Rep Power
    21

    Default Re: euler function problem

    I'm too lazy for this puzzle; all I figured out was phi(10^n) == 4*10^(n-1) (all numbers ending with a 1, 3, 7 or 9 are odd and relatively prime to 5) but I fear the untangled mess for the other number ;-) but I don't think BigIntegers are needed; longs will do (<--- lazy guess)

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  17. #17
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,764
    Rep Power
    5

    Default Re: euler function problem

    OK, I did the following simple loop with no internal calculations:

    Java Code:
    long time = System.nanoTime();
    for (long k = 0; k < 510_510_000L; k++) {
             
    }
    System.out.printf("%5.2f%n", ((double)System.nanoTime() - time)/1_000_000_000);
    On my machine (which is old) it took 2.09 seconds.
    Assuming I understand the problem, the number you are trying to find involves 510_510_000 x 10e8 time consuming iterations. But to just run an empty loop would take:

    2 seconds * 10E8 = approx 63 years.

    So you need to find a better algorithm.

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  18. #18
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,651
    Blog Entries
    7
    Rep Power
    21

    Default Re: euler function problem

    Quote Originally Posted by jim829 View Post
    So you need to find a better algorithm.
    Yep, that many calculations are a waste of time; I found a few other things that might help: a simple one: 510510 == 2*3*5*7*11*13*17 (the first seven prime numbers) and a more general one:
    let p1, p2, p3 ... be the unique prime divisors of n, then phi(n) == n*(1-1/p1)*(1-1/p2)*(1-1/p3) ...

    this little problem is nagging me and a brute force approach as suggested by the OP is a nono ...

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. paintComponent function problem
    By max1 in forum AWT / Swing
    Replies: 8
    Last Post: 02-22-2012, 01:05 AM
  2. Problem regarding function
    By sudarson in forum New To Java
    Replies: 8
    Last Post: 02-26-2011, 10:28 PM
  3. Project Euler #4 - Palindromes
    By Awk34 in forum New To Java
    Replies: 12
    Last Post: 12-19-2010, 10:28 AM
  4. Problem with split function
    By a.tajj in forum New To Java
    Replies: 4
    Last Post: 04-14-2009, 03:30 AM
  5. [SOLVED] project euler #19
    By matzahboy in forum New To Java
    Replies: 14
    Last Post: 12-14-2008, 06:53 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •