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 then the sum of the divisors
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.