See also http://oeis.org/A002182
Also Roger Hui's point about a sieve is probably a good one since this problem only needs you to consider prime factors less than 10000. Still, those 1229 prime factors multiplied by the 1e8 limit means we would need something on the order of several terabytes of memory for intermediate results if we were to store the entire sieve in the obvious way. So some extra work would be needed, and I'm not sure how that would pan out. -- Raul On Tue, Oct 21, 2014 at 5:27 PM, 'Pascal Jasmin' via Programming < [email protected]> wrote: > a followup, > > q: 83160 > 2 2 2 3 3 3 5 7 11 > > that is the highest d under 100k > > d 83160 *2 > 160 > d 83160 *4 > 192 > d 83160 *5 > > 192 > d 83160 *6 > 200 > d 83160 *8 > 224 > d 83160 *10 > > 240 > d 83160 *13 > 256 > d 83160 *16 > 256 > d 83160 *20 > > 288 > d 83160 *26 > 320 > > > There may be a fairly quick algorithm that allows you to leap from all the > way to 100M, based on such jumps and some likely interesting conjectures ... > > For a number that has a local max of divisors, it is the maximum over the > range 100k below, and 100k above or until next overlapping local max. > There are local spikes along the way, but overall fewer than 2000 (fewer > than 1000 if you get very fancy) numbers to check with d to determine S > over 100M. > > > ----- Original Message ----- > From: 'Pascal Jasmin' via Programming <[email protected]> > To: "[email protected]" <[email protected]> > Cc: > Sent: Tuesday, October 21, 2014 4:37 PM > Subject: Re: [Jprogramming] An easy Euler Project one (485) > > 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 > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
