Don Guinn's factors verb, which I renamed "ldiv" for "list divisors" is quite efficient (way more than my brute force approach):
* ldiv=:,@>@(*/&.>/)@(<@(1,*/\)/.~)@q:* * ] ldiv each 10 47 360 2357047123200* *│1 5 2 10│1 47│1 5 3 15 9 45 2 10 6 30 18 90 4 20 12 60 36 180 8 40 24 120 72 360│1 11 7 77 5 55 35 385 25 275 175 1925 3 33 21 231 15 165 105 1155 75 825 525 5775 9 99 63 693 45 495 315 3465 225 2475 1575 17325 27 297 189 2079 135 1485 945 10395 675 7425 ...* * ts 'ldiv each 10 47 360 2357047123200'* *5.24e_5 41792* Here was my original divisor-listing verb, which I mis-named "fac": * fac* *3 : 'a#~0=(a=.1+i.y)|y'* * fac each 10 47 360 2357047123200 * *|out of memory: fac* *| a#~0=(a=.1+ i.y)|y* This blew up memory right out of the gate. Skip Skip Cave Cave Consulting LLC On Sat, Apr 25, 2020 at 5:19 PM Don Guinn <[email protected]> wrote: > factors=:,@>@(*/&.>/)@(<@(1,*/\)/.~)@q: > > factors each 10 47 360 2357047123200 > > > +--------+----+------------------------------------------------------------------+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------... > > |1 5 2 10|1 47|1 5 3 15 9 45 2 10 6 30 18 90 4 20 12 60 36 180 8 40 24 120 > 72 360|1 11 7 77 5 55 35 385 25 275 175 1925 3 33 21 231 15 165 105 1155 75 > 825 525 5775 9 99 63 693 45 495 315 3465 225 2475 1575 17325 27 297 189 > 2079 135 1485 945 10395 675 7425 ... > > > +--------+----+------------------------------------------------------------------+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------... > > ts 'factors each 10 47 360 2357047123200' > > 1.93e_5 41792 > > On Sat, Apr 25, 2020 at 1:23 PM Skip Cave <[email protected]> wrote: > > > So far, Roger's solution for counting the divisors of any integer using > __ > > q: seems the most efficient. > > > > * div=:3 :'*/>:{:__ q:y'* > > > > > > Test it: > > > > > > * >div each 10 47 360 2357047123200* > > > > *4 2 24 1620* > > > > > > * ts '>div each 10 47 360 2357047123200' * > > > > *2.89e_5 10944* > > > > > > Finding and listing the actual divisors is much more resource-intensive > in > > both time and space. > > > > > > Skip Cave > > Cave Consulting LLC > > > > > > On Sat, Apr 25, 2020 at 5:47 AM 'Michael Day' via Programming < > > [email protected]> wrote: > > > > > Yes, that works as expected. > > > > > > BUT consider: > > > > > > __ q: 360 NB. generate a table of primes and powers: > > > 2 3 5 > > > 3 2 1 > > > ((3+3*>:i._10),:~p:i.10) NB. set up a bigger table > > > 2 3 5 7 11 13 17 19 23 29 > > > 33 30 27 24 21 18 15 12 9 6 > > > NB. generate a number from it: > > > __ q: N NB. __ q: factors it quite fast > > > 2 3 5 7 11 13 17 19 23 29 > > > 33 30 27 24 21 18 15 12 9 6 > > > _ q: N NB. so does _ q: > > > 33 30 27 24 21 18 15 12 9 6 > > > > > > ts'__ q: N' > > > 0.0001254 45504 > > > ts'_ q: N' > > > 0.0001236 61696 > > > */>:_ q: N NB. the number of divisors is quite large! > > > 4490309824000 > > > > > > */>: 33 30 27 24 21 18 15 12 9 6 NB. checking result > > > 4490309824000 > > > > > > The performance of q: in its various guises will of course deteriorate > > > with the > > > > > > presence of large prime factors! > > > > > > Anyway, it's advisable not to generate all divisors here unless you > > > really need them! > > > > > > Cheers, > > > > > > Mike > > > > > > Note - I've trimmed the history below here... > > > > > > On 25/04/2020 03:47, Devon McCormick wrote: > > > > I found this one in my bag of tricks: > > > > allFactors=: */&>@{@((^ i.@>:)&.>/)@q:~&__ > > > > #,allFactors */p:i.10 > > > > 1024 > > > > > > > > > > > > On Fri, Apr 24, 2020 at 7:15 PM 'Mike Day' via Programming < > > > > [email protected]> wrote: > > > > > > > >> Numbers of divisors below, not the divisors themselves... the thread > > had > > > >> split! I was attempting to comment on Hauke Rehr’s post. > > > >> M > > > >> > > > >> Sent from my iPad > > > >> > > > >>> On 24 Apr 2020, at 23:52, 'Jon' via Programming < > > > >> [email protected]> wrote: > > > >>> This is missing a few divisors. It seems Skip's original method > would > > > be > > > >> difficult to beat. It's O(n) in time and space. You could improve > > space > > > >> complexity by doing a simple loop, but as far as I can see there are > > no > > > >> shortcuts, and the best way is to just "brute force" it. > > > >>> Sent from BlueMail > > > >>> > > > >>>> On Apr 25, 2020, 5:35 AM, at 5:35 AM, 'Mike Day' via Programming < > > > >> [email protected]> wrote: > > > >>>> I think this is near to the approved way: > > > >>>> > > > >>>> (*/"1@:>:@(_& q:))24 360 4711 > > > >>>> 8 24 4 > > > >>>> > > > >>>> Mike > > > >>>> > > > >>>> Sent from my iPad > > > >>>> > > > >>>>> On 24 Apr 2020, at 21:13, Hauke Rehr <[email protected]> > > wrote: > > > >>>>> > > > >>>>> I now have an answer for the number of results: > > > >>>>> > > > >>>>> */ >: +/"1 (=/~ ~.) q: 4711 > > > >>>>> 4 > > > >>>>> */ >: +/"1 (=/~ ~.) q: 42 > > > >>>>> 8 > > > >>>>> > > > >>>>> I hesitate using =/~ (it’s actually deprecated) > > > >>>>> but I wouldn’t know a better way in this case > > > >>>>> > > > >>>>> > > > >>>>> > > > > > > -- > > > This email has been checked for viruses by Avast antivirus software. > > > https://www.avast.com/antivirus > > > > > > ---------------------------------------------------------------------- > > > 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
