Essays/Factorings
A factoring of n>1 is a vector v of integers >1 such that n=*/v . For example, 2 2 2 3 and 3 8 are factorings of 24 . We wish to find all factorings of n .
ext=: [: ~. ,&.> , ;@:(tu&.>) tu =: ] <@:(/:~)@:*"1 [ ^ </\"1@=@] af =: ext/ @ q: af 24 ┌───────┬─────┬─────┬────┬───┬───┬──┐ │2 2 2 3│2 2 6│2 3 4│2 12│4 6│3 8│24│ └───────┴─────┴─────┴────┴───┴───┴──┘
If n is the m-th power of a prime, then the number of factorings of n is exactly the number of partitions of m .
af 3^5 ┌─────────┬───────┬──────┬─────┬────┬────┬───┐ │3 3 3 3 3│3 3 3 9│3 3 27│3 9 9│3 81│9 27│243│ └─────────┴───────┴──────┴─────┴────┴────┴───┘ 3 ^.&.> af 3^5 ┌─────────┬───────┬─────┬─────┬───┬───┬─┐ │1 1 1 1 1│1 1 1 2│1 1 3│1 2 2│1 4│2 3│5│ └─────────┴───────┴─────┴─────┴───┴───┴─┘
How it works
It is encouraged to do this excercise on your own, however it is presented here in order to draw parallels between this algorithm and the iterative algorithm for set partitions.
Verb ext, inserted into the list of prime factors of the argument (q:), iteratively builds the list of factorings
2 ext 3 ┌───┬─┐ │2 3│6│ └───┴─┘ 2 ext 2 ext 3 ┌─────┬───┬───┬──┐ │2 2 3│2 6│3 4│12│ └─────┴───┴───┴──┘
It takes the nub of (for each previous factoring)
- left argument prepended to factoring items
- box-razed result of the verb tu
The verb tu is the most interesting part. It takes the left argument of ext and a factoring.
For each nub item of the factoring it forms a new list by
- copying the factoring
- multiplying the nub item by left argument
- sorting the result (for nub in ext to work)
If we multiplied each item of the factoring
(2*3),3 5 3, (2*3),5 3 3, (2*5)
we'd obtain redundant results if the factoring contained non-unique items
2 ((^ =@i.@#) ([ ; *"1) ]) 3 3 5 ┌─────┬──────┐ │2 1 1│6 3 5│ │1 2 1│3 6 5│ │1 1 2│3 3 10│ └─────┴──────┘
Thus instead of (^ =@i.@#), a (^ </\"1@=) is used, where "self-sieve" </\"1@= is a cross between a self-classify = and nub-sieve ~: .
([ ; ~: ; = ; (~: *."1 =) ; </\"1@=) 3 3 5 ┌─────┬─────┬─────┬─────┬─────┐ │3 3 5│1 0 1│1 1 0│1 0 0│1 0 0│ │ │ │0 0 1│0 0 1│0 0 1│ └─────┴─────┴─────┴─────┴─────┘ 2 ((^ </\"1@=) ([ ; *"1) ]) 3 3 5 ┌─────┬──────┐ │2 1 1│6 3 5│ │1 1 2│3 3 10│ └─────┴──────┘
Parallels with Set Partitions. If the prime factors are unique, the number of factorings is the number of set partitions:
#af */2 3 5 7 15 #setpart #2 3 5 7 15
The step of the iterative algorithm of set partitions is similar to ext. In nextpart there we append nub +1 indices, where nub indices correspond to the tu verb, and the +1 to the prepending in the ext verb.
See also
Contributed by Roger Hui.[Category:divisors]]