Results 1 to 18 of 18
Thread: euler function problem
 06162013, 02:27 PM #1Member
 Join Date
 Dec 2012
 Posts
 32
 Rep Power
 0
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; 06162013 at 04:25 PM.
 06162013, 04:07 PM #2Senior Member
 Join Date
 Jan 2013
 Location
 Northern Virginia, United States
 Posts
 4,912
 Rep Power
 7
Re: euler function problem
Try using:
Java Code:if (gcd(num, a).equals(BigInteger.ONE)) { count++; }
Java Code:if (gcd(num, a) == BigInteger.ONE) { count++; }
JimThe Java^{TM} Tutorials  SSCCE  Java Naming Conventions
Poor planning on your part does not constitute an emergency on my part
 06162013, 04:23 PM #3
Re: euler function problem
... and a similar construct in line 25.
dbIf you're forever cleaning cobwebs, it's time to get rid of the spiders.
 06162013, 04:26 PM #4Member
 Join Date
 Dec 2012
 Posts
 32
 Rep Power
 0
 06162013, 04:37 PM #5
Re: euler function problem
Get this straight: using == or != to compare object types is just plain wrong. Use equals(...) and !...equals(...).
dbIf you're forever cleaning cobwebs, it's time to get rid of the spiders.
 06162013, 04:45 PM #6Member
 Join Date
 Dec 2012
 Posts
 32
 Rep Power
 0
 06162013, 04:52 PM #7Senior Member
 Join Date
 Jan 2013
 Location
 Northern Virginia, United States
 Posts
 4,912
 Rep Power
 7
Re: euler function problem
Good catch! I didn't see that first time thru. Was getting ready to respond....
Regards,
JimThe Java^{TM} Tutorials  SSCCE  Java Naming Conventions
Poor planning on your part does not constitute an emergency on my part
 06162013, 04:53 PM #8Senior Member
 Join Date
 Jan 2013
 Location
 Northern Virginia, United States
 Posts
 4,912
 Rep Power
 7
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,
JimThe Java^{TM} Tutorials  SSCCE  Java Naming Conventions
Poor planning on your part does not constitute an emergency on my part
 06162013, 05:12 PM #9Member
 Join Date
 Dec 2012
 Posts
 32
 Rep Power
 0
 06162013, 06:05 PM #10
 06162013, 06:15 PM #11
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,131
 Blog Entries
 7
 Rep Power
 24
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)The only person who got everything done by Friday was Robinson Crusoe.
 06162013, 07:44 PM #12Member
 Join Date
 Dec 2012
 Posts
 32
 Rep Power
 0
Re: euler function problem
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 partLast edited by CodeX Pro; 06162013 at 08:01 PM.
 06172013, 01:44 AM #13Senior Member
 Join Date
 Jan 2013
 Location
 Northern Virginia, United States
 Posts
 4,912
 Rep Power
 7
Re: euler function problem
The Java^{TM} Tutorials  SSCCE  Java Naming Conventions
Poor planning on your part does not constitute an emergency on my part
 06172013, 09:25 AM #14
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,131
 Blog Entries
 7
 Rep Power
 24
Re: euler function problem
This message has been deleted by jim829.
ReasonDecided to let Jos explain it
kind regards,
JosThe only person who got everything done by Friday was Robinson Crusoe.
 06172013, 02:35 PM #15Senior Member
 Join Date
 Jan 2013
 Location
 Northern Virginia, United States
 Posts
 4,912
 Rep Power
 7
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,
JimThe Java^{TM} Tutorials  SSCCE  Java Naming Conventions
Poor planning on your part does not constitute an emergency on my part
 06172013, 04:12 PM #16
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,131
 Blog Entries
 7
 Rep Power
 24
Re: euler function problem
I'm too lazy for this puzzle; all I figured out was phi(10^n) == 4*10^(n1) (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,
JosThe only person who got everything done by Friday was Robinson Crusoe.
 06172013, 05:51 PM #17Senior Member
 Join Date
 Jan 2013
 Location
 Northern Virginia, United States
 Posts
 4,912
 Rep Power
 7
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);
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,
JimThe Java^{TM} Tutorials  SSCCE  Java Naming Conventions
Poor planning on your part does not constitute an emergency on my part
 06172013, 06:56 PM #18
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,131
 Blog Entries
 7
 Rep Power
 24
Re: euler function problem
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*(11/p1)*(11/p2)*(11/p3) ...
this little problem is nagging me and a brute force approach as suggested by the OP is a nono ...
kind regards,
JosThe only person who got everything done by Friday was Robinson Crusoe.
Similar Threads

paintComponent function problem
By max1 in forum AWT / SwingReplies: 8Last Post: 02222012, 02:05 AM 
Problem regarding function
By sudarson in forum New To JavaReplies: 8Last Post: 02262011, 11:28 PM 
Project Euler #4  Palindromes
By Awk34 in forum New To JavaReplies: 12Last Post: 12192010, 11:28 AM 
Problem with split function
By a.tajj in forum New To JavaReplies: 4Last Post: 04142009, 03:30 AM 
[SOLVED] project euler #19
By matzahboy in forum New To JavaReplies: 14Last Post: 12142008, 07:53 AM
Bookmarks