## divisors

APL-related discussions - a stream of APL consciousness.
Not sure where to start a discussion ? Here's the place to be
Forum rules
This forum is for discussing APL-related issues. If you think that the subject is off-topic, then the Chat forum is probably a better place for your thoughts !

### divisors

Motivated by a query on the J Forum earlier today, I looked at the computation of the divisors of an integer, and discovered that such a function is not in the dfns workspace. However, the function pco is in the dfns workspace, and is a good place to start.

`      )copy dfns pco      2 pco 3602 3 53 2 1      ×/ 2 3 5 * 3 2 1360`

2 pco ⍵ returns a 2-row matrix of the prime factors and corresponding exponents. If e are the exponents, then the number of divisors of ⍵ is ×/1+e.

`      ndiv←{×/1+1⌷2 pco ⍵}      ndiv 36024`

And the divisors:

`      div ← {{⍵[⍋⍵]} , ⊃∘.×⌿ ⊃{⍺*⍳¨1+⍵}⌿ ↓2 pco ⍵}      div 3601 2 3 4 5 6 8 9 10 12 15 18 20 24 30 36 40 45 60 72 90 120 180 360      ≢div 36024      divBF ← {1+⍸0=⍵|⍨1+⍳⍵}       ⍝ brute force solution      divBF 3601 2 3 4 5 6 8 9 10 12 15 18 20 24 30 36 40 45 60 72 90 120 180 360      (div ≡ divBF)¨ 1+?4 5⍴1e7    ⍝ check some random arguments1 1 1 1 11 1 1 1 11 1 1 1 11 1 1 1 1`

Inspection of the intermediate results in div illustrates why and how it (and ndiv) work:

`      2 pco 360               ⍝ start with the primes and exponents2 3 53 2 1      ↓ 2 pco 360             ⍝ split into primes and exponents┌─────┬─────┐│2 3 5│3 2 1│└─────┴─────┘      (p e)← ↓ 2 pco 360      ⍝ name them to facilitate explanation      p2 3 5      e3 2 1      ⍳¨1+e                   ⍝ all the different ways a prime can contribute┌───────┬─────┬───┐│0 1 2 3│0 1 2│0 1│└───────┴─────┴───┘      p*⍳¨1+e                 ⍝ the actual contributions┌───────┬─────┬───┐│1 2 4 8│1 3 9│1 5│└───────┴─────┴───┘      ⊃ {⍺*⍳¨1+⍵}⌿ p e        ⍝ the preceding lines combined into one┌───────┬─────┬───┐│1 2 4 8│1 3 9│1 5│└───────┴─────┴───┘      ⊃∘.×⌿ ⊃{⍺*⍳¨1+⍵}⌿ p e   ⍝ all possible products of prime powers 1   5 3  15 9  45       2  10 6  3018  90       4  2012  6036 180       8  4024 12072 360       , ⊃∘.×⌿ ⊃{⍺*⍳¨1+⍵}⌿ p e           ⍝ ravel the products1 5 3 15 9 45 2 10 6 30 18 90 4 20 12 60 36 180 8 40 24 120 72 360      {⍵[⍋⍵]} , ⊃∘.×⌿ ⊃{⍺*⍳¨1+⍵}⌿ p e    ⍝ sort them1 2 3 4 5 6 8 9 10 12 15 18 20 24 30 36 40 45 60 72 90 120 180 360      div 3601 2 3 4 5 6 8 9 10 12 15 18 20 24 30 36 40 45 60 72 90 120 180 360`

(Misalignments in the display are due to defects in the APL Chat Forum software.)

Aside: "Tacit" fans will note that the snippet {⍺*⍳¨1+⍵} in div can be written as *∘(⍳¨∘(1∘+)), but in this instance it is not as clear as the dfn, in my opinion. The balance may tip the other way if there is an increment primitive function, such as ≥⍵ ←→ 1+⍵, whence the tacit version becomes *∘(⍳¨∘≥).

From the ideas in the J Wiki Essay Divisors, 2005-11-17.
Roger|Dyalog

Posts: 231
Joined: Thu Jul 28, 2011 10:53 am

### Re: divisors

Tacit train fan here.

While {⍺*⍳¨1+⍵} as a purely derived non-train function is indeed awkward, the train ⊣*∘⍳¨1+⊢ looks fine, I think. Unfortunately, depending on the cleverness of the interpreter, performance might suffer due to * not using vectorising code, but ⊣*1(⍳¨+)⊢ fixes that. In 18.0 we can write ⊣*1⍳¨⍤+⊢ instead. Of course, an increment function ≥ would allow us to write *∘⍳¨∘≥ or your *∘(⍳¨∘≥) for full performance.

Posts: 94
Joined: Thu Jun 25, 2015 1:13 pm

### Re: divisors

I know it's brute-forcier than brute force, but as a tacit fan I like
`      ⎕IO←0{∪⍵∨1+⍳⍵}(∪⊢∨1+⍳)`

Or
`      ⎕IO←1{∪⍵∨⍳⍵}(∪⊢∨⍳)`

Some might consider this code golf, but I think its use of GCD suggests "divisors". It basically says "unique divisors".

Somewhat related, I have a small question about APL implementation:
Is it more desirable that the APLer has an accurate view of the computational complexity of an expression based on the primitives used, or that the APLer can write whatever and hope that one day all expressions are interpreted to the most efficient version that will produce the same result?
RichardP|Dyalog

Posts: 9
Joined: Fri Oct 12, 2018 3:05 pm