Essays/Divisors

A positive integer a is a divisor of positive integer n if n%a is an integer. For example, 6 is a divisor of 36, and all the divisors of 36 can be computed by

   }. I. (= <.) (% i.@>:) 36
1 2 3 4 6 9 12 18 36

A shorter (but more than 10 times less efficient) computation uses the builtin GCD (+.) to compute each divisor.

   (+. i.) 36
36 1 2 3 4 1 6 1 4 9 2 1 12 1 2 3 4 1 18 1 4 3 2 1 12 1 2 9 4 1 6 1 4 3 2 1
   /:~ ~. (+. i.) 36     NB. sorted nub
1 2 3 4 6 9 12 18 36
   ~. |. (+. i.) 36      NB. reverse the list, then nub
1 2 3 4 6 9 12 18 36

Primes and Exponents

__ q: n gives a 2-row table of the primes and exponents, and is useful in calculations involving the divisors of a number.

   __ q: 360
2 3 5
3 2 1

The product of 1 plus the exponents gives the number of divisors.

   {: __ q: 360
3 2 1

   ndiv=: */ @: >: @: {: @: (__&q:)

   ndiv 360
24

The actual divisors are all the products of the prime powers.

   i.@>:&.> 3 2 1
┌───────┬─────┬───┐
│0 1 2 3│0 1 2│0 1│
└───────┴─────┴───┘
   2 3 5 ^&.> i.@>:&.> 3 2 1
┌───────┬─────┬───┐
│1 2 4 8│1 3 9│1 5│
└───────┴─────┴───┘
   */&.>/ 2 3 5 ^&.> i.@>:&.> 3 2 1
┌──────┐
│ 1   5│
│ 3  15│
│ 9  45│
│      │
│ 2  10│
│ 6  30│
│18  90│
│      │
│ 4  20│
│12  60│
│36 180│
│      │
│ 8  40│
│24 120│
│72 360│
└──────┘
   , > */&.>/ 2 3 5 ^&.> i.@>:&.> 3 2 1
1 5 3 15 9 45 2 10 6 30 18 90 4 20 12 60 36 180 8 40 24 120 72 360
   /:~ , > */&.>/ 2 3 5 ^&.> i.@>:&.> 3 2 1
1 2 3 4 5 6 8 9 10 12 15 18 20 24 30 36 40 45 60 72 90 120 180 360

   div=: /:~ @: , @: > @: (*/&.>/) @: ((^ i.@>:)&.>/) @: (__&q:)

   div 360
1 2 3 4 5 6 8 9 10 12 15 18 20 24 30 36 40 45 60 72 90 120 180 360

   # div 360
24
   ndiv 360
24

Odometer

The divisors can also be computed using the odometer function as a component.

   odometer=: #: i.@(*/)

   __ q: 360
2 3 5
3 2 1
   >: 3 2 1
4 3 2
   odometer >: 3 2 1
0 0 0
0 0 1
0 1 0
0 1 1
0 2 0
0 2 1
1 0 0
1 0 1
1 1 0
1 1 1
1 2 0
1 2 1
2 0 0
2 0 1
2 1 0
2 1 1
2 2 0
2 2 1
3 0 0
3 0 1
3 1 0
3 1 1
3 2 0
3 2 1
   2 3 5 */ .^"1 odometer >: 3 2 1
1 5 3 15 9 45 2 10 6 30 18 90 4 20 12 60 36 180 8 40 24 120 72 360
   /:~ 2 3 5 */ .^"1 odometer >: 3 2 1
1 2 3 4 5 6 8 9 10 12 15 18 20 24 30 36 40 45 60 72 90 120 180 360

   div1=: /:~ @ ((*/ .^"1 odometer@:>:)/) @ (__&q:)

   div1 360
1 2 3 4 5 6 8 9 10 12 15 18 20 24 30 36 40 45 60 72 90 120 180 360

   (div -: div1) 360
1

Sum of Divisors

If the prime factorization of $n=\prod _{i}p_{i}^{e_{i}}$ then the sum of the divisors $\sigma (n)=\prod _{i}{\frac {p_{i}^{{e_{i}}+1}-1}{p_{i}-1}}=\prod _{i}\sum _{j=0}^{e_{i}}p_{i}^{j}$

sumdiv0=: __ ((^>:) */@:%&:<: [)/@q: ]
sumdiv1=: (*//.~ (* %&<: ]) ~.)&.q:
sumdiv2=: >:@#.~/.~&.q:

   sumdiv0 360
1170
   sumdiv1 360
1170
   sumdiv2 360
1170
   +/ div 360
1170

   sumdiv0 !20x
13891399238731734720
   sumdiv1 !20x
13891399238731734720
   sumdiv2 !20x
13891399238731734720
   +/ div !20x
13891399238731734720

Collected Definitions

ndiv    =: */ @: >: @: {: @: (__&q:)

div     =: /:~ @: , @: > @: (*/&.>/) @: ((^ i.@>:)&.>/) @: (__&q:)

odometer=: #: i.@(*/)
div1    =: /:~ @ ((*/ .^"1 odometer@:>:)/) @ (__&q:)

sumdiv0 =: __ ((^>:) */@:%&:<: [)/@q: ]
sumdiv1 =: (*//.~ (* %&<: ]) ~.)&.q:
sumdiv2 =: >:@#.~/.~&.q:

---

See also

• Totient Function
• On-line Encyclopedia of Integer Sequences A000005
• Factorings
• Rosettacode's Factors of an integer task

---

Contributed by Roger Hui. sumdiv2 is by Henry Rich in a J Forum message on 2014-06-10.