1. Member 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)){
}
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 05:25 PM.  Reply With Quote

2. Senior Member Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
14

## 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++;
}```
Regards,
Jim  Reply With Quote

3. ## Re: euler function problem

... and a similar construct in line 25.

db  Reply With Quote

4. Member Join Date
Dec 2012
Posts
32
Rep Power
0

## Re: euler function problem Originally Posted by jim829 Try using:
Java Code:
```if (gcd(num, a).equals(BigInteger.ONE)) {
count++;
}```

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.  Reply With Quote

5. ## Re: euler function problem

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

db  Reply With Quote

6. Member Join Date
Dec 2012
Posts
32
Rep Power
0

## Re: euler function problem 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  Reply With Quote

7. Senior Member Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
14

## Re: euler function problem

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

Regards,
Jim  Reply With Quote

8. Senior Member Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
14

## 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  Reply With Quote

9. Member Join Date
Dec 2012
Posts
32
Rep Power
0

## Re: euler function problem 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  Reply With Quote

10. ## Re: euler function problem Originally Posted by CodeX Pro I fear that BigInteger is not big enough to hold the numbers
BigIntegers are made as large as necessary to accommodate the results of an operation.
db  Reply With Quote

11. ## 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)  Reply With Quote

12. Member Join Date
Dec 2012
Posts
32
Rep Power
0

## Re: euler function problem 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)
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);
//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 09:01 PM.  Reply With Quote

13. Senior Member Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
14

## Re: euler function problem 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  Reply With Quote

14. ## 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  Reply With Quote

15. Senior Member Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
14

## 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  Reply With Quote

16. ## 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  Reply With Quote

17. Senior Member Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
14

## 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  Reply With Quote

18. ## Re: euler function problem 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  Reply With Quote

#### Posting Permissions

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