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/8422 - Release Date: 10/20/14
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
