Re: euler function problem

Try using:

Code:

`if (gcd(num, a).equals(BigInteger.ONE)) {`

count++;

}

instead of

Code:

`if (gcd(num, a) == BigInteger.ONE) {`

count++;

}

Regards,

Jim

Re: euler function problem

... and a similar construct in line 25.

db

Re: euler function problem

Quote:

Originally Posted by

**jim829** Try using:

Code:

`if (gcd(num, a).equals(BigInteger.ONE)) {`

count++;

}

instead of

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.

Re: euler function problem

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

db

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

Re: euler function problem

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

Regards,

Jim

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

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

Re: euler function problem

Quote:

Originally Posted by

**CodeX Pro** I fear that BigInteger is not big enough to hold the numbers

Read the API. Quote:

BigIntegers are made as large as necessary to accommodate the results of an operation.

db

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)

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

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

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

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

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

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

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