Show Problem 72
This code took about 30 minutes to run on my computer. I tried to implement the same logic in Java; however, it took hours to get an answer.However, an efficient Java solution with prime sieving is HERE.(Runs under 1 seconds). Here is the logic the totient function of a number gives how many reduced fractions a number has if it is included. Actually, the totient function gives the number of integers coprime with the input.[given n=p1^e1*p2^e2...pk^ek,(p stands for prime factor) totient(n)=n(1-1/p1)(1-1/p2)...(1-1/pk)]So if a number is not coprime with the input it means that the fraction formed with those two numbers has already been presented before. Thus, we do not count those numbers. Unfortunatelly, the answer is out of range of integer in Matlab. In Matlab there is no natural implementation of big integers as in java so I had to download and install an m file from Matlab Snack Bar Working with big integers decreases the speed but it was the only solution I could find.
Here is the code in MATLAB
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | sum = bigint('0'); for i = 2:1000000 f = factor(i); hey = i; b = unique(f); for j = 1:length(b) hey=hey*(b(j)-1)/b(j); end am =bigint(int2str(hey)); sum=plus(sum,am); fprintf('i = %g\n', i); end display( sum); |
Hope this helps. 
I don’t think you need bigint for this one.
The final result is roughly 3 X 10^12 and a MATLAB “DOUBLE” has 64 bits so it can store roughly 21 digits of decimal precision so it is well able to handle the job:
function euler72(n)
sum=0;
for i=2:n
sum = sum+totient(i);
end
format rat;sum
function tot=totient(n)
tot=n;
fac = unique(factor(n));
for i=1:length(fac)
tot = tot*(fac(i)-1)/fac(i);
end
This took 108 seconds on my 2200 MHz laptop.
I also implemented the faster prime sieve method and it took about 0.23 seconds.
[...] site is called Javaist blog and its MATLAB session can be located through this link here… Posted in Engineering • Tags: MATLAB [...]
[...] Euler problems in the scope with MATLAB [...]