d2 =: */@:>:@:(#/.~)@:q:"0 is a bit quicker than the version you suggested, and though don't really know why, uses much less space.
----- Original Message ----- From: Mike Day <[email protected]> To: [email protected] Cc: Sent: Tuesday, October 21, 2014 7:33 PM Subject: Re: [Jprogramming] An easy Euler Project one (485) Yes, agreed - I started trying a sieve method earlier today. So far it wasn't doing better than the prime factoring approach using q: though it would no doubt benefit from more careful programming. As I've already got a solution I don't think I'll pursue the sieve method further now. I would have tried that, and also splitting the problem into smaller blocks. Sure you're not tempted to add a primitive for d ? Why is Pari GP quicker here? It's quicker even when my 6Gb machine isn't thrashing for memory. Pascal Jasmin's alternative for d is attractive. In tacit form */@:>:@:(#/.~)@:-.&0"1@:q: is quicker and leaner than */@:(>:@{:)"2@(__&q:) for >: i. 1000000 though slower albeit still leaner for >: i. 10000000 ... Cheers, Mike On 21/10/2014 21:47, Roger Hui wrote: > __ q: 30 > 2 3 5 > 1 1 1 > > The number of divisors are the possible vectors of exponents, which in this > case are {0 1;0 1;0 1. For each prime, if the maximum exponent is e, then > the possible exponents for that prime is 0 1 2 3 ... e-1,e, i.e. the number > of possible exponents is 1+e. > > That's why I suggested using a sieve. Factoring is hard. But if you are > computing the number of divisors of a range, you can avoid factoring > altogether. > > A few weeks ago I came across a neat (but inefficient) expression for the > divisors of n : > > n=. 144 > > ~. n +. 1+i.n > 1 2 3 4 6 8 9 12 16 18 24 36 48 72 144 > __ q: 144 > 2 3 > 4 2 > */ 1 + 4 2 > 15 > # ~. n +. 1+i.n > 15 > > > > On Tue, Oct 21, 2014 at 12:46 PM, 'Pascal Jasmin' via Programming < > [email protected]> wrote: > >> I don't completely understand number of divisors, but note: >> >> */@:(>:@{:)"2@(__&q:) 30 >> 8 >> q: 30 >> 2 3 5 >> >> I don't know why number of divisors of 39 would not be 3. Though I guess >> the divisors are 1 2 3 5 6 10 15 30 >> >> So, your d function looks like it should be efficient as long as __ & q: >> is comparable in speed to just q: >> >> */@:(>:@{:)"2@(__&q:) 105600 >> 96 >> >> If not, there is this alternative basis for d: >> >> */ >: #/.~ q: 105600 >> 96 >> >> >> >> >> ----- Original Message ----- >> From: Mike Day <[email protected]> >> To: [email protected] >> Cc: >> Sent: Tuesday, October 21, 2014 2:54 PM >> Subject: Re: [Jprogramming] An easy Euler Project one (485) >> >> No takers to the previous posting (below)? >> >> 0) Pari GP has a built-in function for number of divisors; >> J doesn't, although it seems a nice candidate for an extension of p: >> or q: >> >> 1) My fairly crude Pari GP function to solve this problem runs faster than >> the slightly more elegant although admittedly brute-force J verb(s). >> The Pari GP solution for the actual Project Euler problem 485 took >> just under 7 minutes, and is correct, so optimisation isn't really >> required. >> I've just received a J solution after 1 hour 20 minutes, also correct. >> Both run in interactive mode. >> >> 2) I did have a go at optimising the GP Pari, using a count array of >> d-values in the current window (of size 100 000 in the actual problem); >> that array can be considerably smaller than 100 000; I messed around >> with forward and backward pointers but it was slower, and buggy. >> >> 3) Running a smaller problem under jpm suggests that the bottleneck >> is the d (number of divisors) verb. >> S 1e6 1e4 takes about 6.5 seconds of which 6 seconds is spent in "d". >> >> 4) So is there a better d verb out there - capable of running efficiently >> on a vector argument? (Or a p: or q: extension as per 0 above?) >> >> Thanks, >> >> Mike >> >> On 20/10/2014 15:26, Mike Day wrote: >>> NB. Maximum number of divisors >>> >>> NB. Problem 485 >>> >>> NB. Published on Saturday, 18th October 2014, 04:00 pm >>> >>> NB. Let d(n) be the number of divisors of n. >>> >>> NB. Let M(n,k) be the maximum value of d(j) for n ≤ j ≤ n+k-1. >>> >>> NB. Let S(u,k) be the sum of M(n,k) for 1 ≤ n ≤ u-k+1. >>> >>> NB. >>> >>> NB. You are given that S(1000,10)=17176. >>> >>> NB. >>> >>> NB. Find S(100 000 000,100 000). >>> >>> >>> NB. A brute-force J method: >>> d =: */@:(>:@{:)"2@(__&q:) >>> >>> >>> S =: +/@:(>./\ d@>:@i.)~/ >>> >>> >>> timer'S 1000000 1000' NB. NOT the published problem! >>> >>> +-----+---------+ >>> >>> |7.769|140671058| >>> >>> +-----+---------+ >>> >>> timer'S 1000000 10000' >>> >>> +-----+---------+ >>> >>> |7.147|175757800| >>> >>> +-----+---------+ >>> >>> >>> These are faster in a pedestrian Pari GP script, >>> but it does use the built-in function, "numdiv": >>> >>> >>> (08:10) gp > S(1000000,1000) >>> time = 3,302 ms. >>> %5 = 140671058 >>> >>> >>> (15:13) gp > S(1000000,10000) >>> time = 2,889 ms. >>> %6 = 175757800 >>> >>> >>> Curious. >>> >>> Mike >>> >>> >>> PS The Pari script: >>> >>> S(u,k)= { >>> rv=vector(k,i,numdiv(i)); \\ rolling vector of "d" values >>> t=vecmax(rv);curmx=t; >>> ipos=0; >>> for(n= k+1, u, >>> oldrvi=rv[ipos+1]; >>> newrvi=numdiv(n); >>> rvi=rv[ipos+1]=newrvi; >>> if(curmx<rvi, curmx=rvi, >>> if(oldrvi==curmx,curmx=vecmax(rv)); >>> ); >>> t+=curmx; >>> ipos=(1+ipos)%k; >>> ); >>> t; >>> } >>> >>> >>> >>> >> >> --- This email is free from viruses and malware because avast! Antivirus protection is active. http://www.avast.com ----- No virus found in this message. Checked by AVG - www.avg.com Version: 2014.0.4765 / Virus Database: 4040/8428 - Release Date: 10/21/14 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
