On Sunday, March 16, 2014 8:52:35 PM UTC+1, Stefan Schwarz wrote:
>
> Hello,
>
> I started with Julia last week and to get into tracks I tried to implement
> some of the Project Euler question, that I've already done in Mathematica
> (being a Mathematica developer for ~10 years)
>
> The specifics of this question is about problem #21:
>
> Let d(*n*) be defined as the sum of proper divisors of *n* (numbers less
> than *n* which divide evenly into *n*).
> If d(*a*) = *b* and d(*b*) = *a*, where *a* [image: ≠] *b*, then *a* and
> *b* are an amicable pair and each of *a* and *b* are called amicable
> numbers.
>
> For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22,
> 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1,
> 2, 4, 71 and 142; so d(284) = 220.
>
> Evaluate the sum of all the amicable numbers under 10000.
>
>
> In Mathematica this was done very easily with:
>
> DivSum[n_] := DivisorSigma[1, n] - n
> AmicableQ[n_Integer] := DivSum[n] != n && DivSum[DivSum[n]] == n
> Plus @@ Select[Range[9999], AmicableQ] // Timing
>
>
> Yielding a tuple of time and the result: {0.178553, 31626}
>
> Which is correct. So I tried to achieve the same in Julia:
>
> function divisors(n::Int, prop::Bool=false)
> if(!prop)
> filter((x) -> rem(n, x) == 0, [1:n])
> else
> filter((x) -> rem(n, x) == 0, [1:n-1])
> end
> end
>
>
>
> function divsum(n::Int)
> sum(divisors(n, true))
> end
>
>
>
> function amicable(n::Int)
> divsum(n) != n && divsum(divsum(n)) == n
> end
>
>
>
> This yielded the correct result, but awful timing:
>
> @time sum(filter(x -> amicable(x),[1:9999]))
>
>
> elapsed time: 24.025008574 seconds (4310013792 bytes allocated)
>
>
> So. I did something wrong, apparently. Rats.
>
> So I started to think about, where the hot spot was and
> decided to pick the divisors function to be the suspect.
>
> So I rewrote it:
>
> function factors(n)
> f = [one(n)]
> for (p,e) in factor(n)
> f = reduce(vcat, f, [f*p^j for j in 1:e])
> end
> return f
> end
>
>
>
> function sum_prop_factors(n)
> sum(factors(n))-n
> end
>
>
>
> I did even left out the sorting before returning f back, since it isn't
> needed at all.
>
> Executing this:
>
> @time sum(filter(x -> sum_prop_factors(x) != x &&
> sum_prop_factors(sum_prop_factors(x))==x, [2:9999]))
>
>
> yielded:
>
> elapsed time: 0.207550349 seconds (39478048 bytes allocated)
>
>
>
>
(Accidentally sent this off before really finishing it...my fault.)
Although there is a huge speedup to my former implementation, there is
still a measurable distance to Mathematica's
execution speed (and yes. I cleared system caches etc.)
So the question I like to ask is, does anybody have a better idea to
implement this in Julia?
The problem I have is, that I did not use specific Mathematica
functionality, but a straight forward implementation.
>From what I've seen so far, there is the gospel that Julia is always faster
approaching even the
execution speed of C. I claim, that there is a better and even faster
solution to my Mathematica implementation.
If someone can enlighten me on that matter would be wonderful.
Cheers
Stefan
