An optimization of this problem may actually center around M and not d. If the range of M includes a number with only small prime factors, then that will be a candidate for max d within the range of M.
if 2^k is within the range, then it is a candidate. 3 * 2^k-1 would have more total divisors 9 * 2^k-2 even more 15 * ... and so on. There is probably a mathematical way of determining the minimum power of 2 that should be considered, but by optimizing M, there is a fairly small number of trial multiplications that need be examined. ----- 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
