# euler function problem

• 06-16-2013, 03:27 PM
CodeX Pro
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).

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());     } }```
• 06-16-2013, 05:07 PM
jim829
Re: euler function problem
Try using:
Code:

```if (gcd(num, a).equals(BigInteger.ONE)) {   count++; }```

Code:

```if (gcd(num, a) == BigInteger.ONE) {   count++; }```
Regards,
Jim
• 06-16-2013, 05:23 PM
DarrylBurke
Re: euler function problem
... and a similar construct in line 25.

db
• 06-16-2013, 05:26 PM
CodeX Pro
Re: euler function problem
Quote:

Originally Posted by jim829
Try using:
Code:

```if (gcd(num, a).equals(BigInteger.ONE)) {   count++; }```

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.
• 06-16-2013, 05:37 PM
DarrylBurke
Re: euler function problem
Get this straight: using == or != to compare object types is just plain wrong. Use equals(...) and !...equals(...).

db
• 06-16-2013, 05:45 PM
CodeX Pro
Re: euler function problem
Quote:

Originally Posted by DarrylBurke
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
• 06-16-2013, 05:52 PM
jim829
Re: euler function problem
Good catch! I didn't see that first time thru. Was getting ready to respond....

Regards,
Jim
• 06-16-2013, 05:53 PM
jim829
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
• 06-16-2013, 06:12 PM
CodeX Pro
Re: euler function problem
Quote:

Originally Posted by jim829
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
• 06-16-2013, 07:05 PM
DarrylBurke
Re: euler function problem
Quote:

Originally Posted by CodeX Pro
I fear that BigInteger is not big enough to hold the numbers

Quote:

BigIntegers are made as large as necessary to accommodate the results of an operation.
db
• 06-16-2013, 07:15 PM
JosAH
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)
• 06-16-2013, 08:44 PM
CodeX Pro
Re: euler function problem
Quote:

Originally Posted by JosAH
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)

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
• 06-17-2013, 02:44 AM
jim829
Re: euler function problem
Quote:

Originally Posted by CodeX Pro
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
• 06-17-2013, 10:25 AM
JosAH
Re: euler function problem
Quote:

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
• 06-17-2013, 03:35 PM
jim829
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
• 06-17-2013, 05:12 PM
JosAH
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
• 06-17-2013, 06:51 PM
jim829
Re: euler function problem
OK, I did the following simple loop with no internal calculations:

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
• 06-17-2013, 07:56 PM
JosAH
Re: euler function problem
Quote:

Originally Posted by jim829
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