APL Hacking: Project Euler (#23)
Sunday, April 10, 2011 10:02:01 PM
∇R←PETWENTYTHREE;ABDP;N;X ⍝ Find the sum of all the positive integers ⍝ which cannot be written as the sum ⍝ of two abundant numbers. ⊣⎕FX 'R←ABDP N' 'R←N<+/(0=(⍳N-1)|N)/⍳N-1' R←+/(~N∊X∘.+X←(ABDP¨N)/N)/N←⍳28123 ∇
Alright, I admit it, I'm really lazy on this one. I have been thinking about this one for too long, and I know that the bottleneck here is in my lazy use of the remainder function to compute the divisors, but I'm putting it off to another day. Additionally, my use of the outer product to compute the set of abundant sums is not exactly clever either. Indeed, this solution, while within my memory usage limits, it far too slow to really count as a good solution.
Edit: I have managed to think up some major improvements to this approach, and my function now looks like this:
∇R←PRMS∆EXPS N;P;L;I;⎕IO ⎕IO←1 ⍝ Compute the Prime Factorization of a given N. ⍝ ⍝ E1 E2 E3 ... ⍝ P1 P2 P3 ... ⍝ ⍝ Where EI is the exponent of PI. L←⌊N*0.5 ⋄ R←2 L↑(1 L)⍴⍳L ⋄ I←1 LP:I←I+1 ⋄ →((1=N)∨I>L)/FINAL DIV:→(0≠I|N)/LP ⋄ R[2;I]←R[2;I]+1 ⋄ N←N÷I ⋄ →DIV FINAL:→(N≤1)/DONE ⋄ R←R,N 1 ⋄ L←L+1 DONE:R←R[;(0≠R[2;])/⍳L] ∇ ∇R←SUM∆DIVS N;X;⎕IO ⎕IO←1 ⍝ Compute the sum of the divisors of N R←×/(-1+X[1;]*1+X[2;])÷-1+X[1;]⊣X←PRMS∆EXPS N ∇ ∇R←PETWENTYTHREE;ABDP;F;T;A;N;C;⎕IO ⎕IO←1 ⍝ Find the sum of all the positive integers ⍝ which cannot be written as the sum ⍝ of two abundant numbers. C←28123 ⊣⎕FX 'R←ABDP N' 'R←(N+N)<SUM∆DIVS N' R←+/(F⊣F[(C≥T)/T←,A∘.+A←(ABDP¨N)/N]←0⊣F←C⍴1)/N←⍳C ∇
With this code, at least the running time is sub-minute, but it's still far less than preferable, especially since I believe there is a solution that could get my in the millisecond range, and not the seconds and half minutes range.
Profiling indicates that the bottleneck of the above is now the prime factorization algorithm rather than anything in the main PE function.