123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869 |
- #!/usr/bin/ruby
- # Daniel "Trizen" Șuteu
- # Date: 15 April 2019
- # https://github.com/trizen
- # Represent a given number as a product of primorials (if possible).
- # The sequence of numbers that can be represented as a product of primorials, is given by:
- # https://oeis.org/A025487
- # Among other terms, the sequence includes the factorials and the highly composite numbers.
- # See also:
- # https://oeis.org/A181815 -- "primorial deflation" of A025487(n)
- # https://oeis.org/A108951 -- "primorial inflation" of n
- func primorial_deflation (n) {
- var prod = 1
- while (n > 1) {
- var g = n.gpf # greatest prime factor
- var p = g.primorial
- n /= p
- n.is_int || return nil
- prod *= g
- }
- return prod
- }
- func primorial_deflation_bag(n) {
- var prod = 1
- var f = Bag(n.factor...)
- while (f) {
- var p = f.max
- f -= p.primes
- prod *= p
- }
- return prod
- }
- func primorial_deflation_fast (n) {
- n.factor_prod {|p,e|
- (p / (p > 2 ? p.prev_prime : 1))**e
- }
- }
- var arr = 15.of { primorial_deflation(_!) } # https://oeis.org/A307035
- say arr #=> [1, 1, 2, 3, 12, 20, 60, 84, 672, 1512, 5040, 7920, 47520, 56160, 157248]
- say arr.map {|n| n.factor_prod {|p,e| p.primorial**e } } #=> [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200]
- assert_eq(15.of { primorial_deflation(_!) }, 15.of { primorial_deflation_bag(_!) })
- assert_eq(15.of { primorial_deflation(_!) }, 15.of { primorial_deflation_fast(_!) })
- var n = 14742217487368791965347653720647452690286549052234444179664342042930370966727413549068727214664401976854238590421417268673037399536054005777393104248210539172848500736334237168727231561710827753972114334247396552090671649834020135652920430241738510495400044737265204738821393451152066370913670083496651044937158497896720493198891148968218874744806522767468280764179516341996273430700779982929787918221844760577694188288275419541410142336911631623319041967633591283303769044016192030492715535641753600000
- say primorial_deflation(n) #=> 52900585920
- say primorial_deflation_bag(n) #=> 52900585920
- say primorial_deflation_fast(n) #=> 52900585920
|