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
