dev.to staff

Posted on Jul 4, 2019

Daily Challenge #7 - Factorial Decomposition

#challenge

Today's challenge will require a bit of mathematical prowess. Those who were fans of the Project Euler challenges might have some fun with this one from user g964 from CodeWars:

The aim of this [challenge] is to decompose n!(factorial n) into its prime factors. Prime numbers should be in increasing order. When the exponent of a prime number is 1, don't print the exponent.

Examples:

n = 22; decomp(22) -> "2^19 * 3^9 * 5^4 * 7^3 * 11^2 * 13 * 17 * 19"
n = 25; decomp(25) -> "2^22 * 3^10 * 5^6 * 7^3 * 11^2 * 13 * 17 * 19 * 23"

Explanation:

n = 12; decomp(12) -> "2^10 * 3^5 * 5^2 * 7 * 11"
12! is divisible by 2 ten times, by 3 five times, by 5 two times and by 7 and 11 only once.

Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge for a future post? Email yo+challenge@dev.to with your suggestions!

Top comments (21)

Spacie • Jul 4 '19 • Edited

Woo 3 days in a row!

I'm not too good when it comes to maths and I'm sure there are loads of more efficient algorithms for finding prime factors, but I think this works!

require 'prime'
def decomp n
  return "1" if n == 1
  counts = Hash.new 0
  (n / 2).ceil.downto(1).each do |x|
    next if !Prime.prime? x
    until n % x > 0 or n == 0
      n /= x
      counts[x] += 1
    end
  end
  counts.to_a.reverse.map(&proc {|pair| pair[1] > 1 ? "#{pair[0]}^#{pair[1]}" : pair[0]}).join " * "
end
def test n
  fact = Math.gamma(n + 1).to_i
  puts "n = #{n}; n! = #{fact}; decomp(n!) = #{decomp(fact)}"
end
(1..10).each {|x| test x}

Output:

n = 1; n! = 1; decomp(n!) = 1
n = 2; n! = 2; decomp(n!) = 2
n = 3; n! = 6; decomp(n!) = 2 * 3
n = 4; n! = 24; decomp(n!) = 2^3 * 3
n = 5; n! = 120; decomp(n!) = 2^3 * 3 * 5
n = 6; n! = 720; decomp(n!) = 2^4 * 3^2 * 5
n = 7; n! = 5040; decomp(n!) = 2^4 * 3^2 * 5 * 7
n = 8; n! = 40320; decomp(n!) = 2^7 * 3^2 * 5 * 7
n = 9; n! = 362880; decomp(n!) = 2^7 * 3^4 * 5 * 7
n = 10; n! = 3628800; decomp(n!) = 2^8 * 3^4 * 5^2 * 7

Spacie • Jul 4 '19 • Edited

Turns out there's actually a built in method for this ... So just the formatting I guess...

require 'prime'
def decomp n
  fact = Math.gamma(n + 1).to_i
  "n = #{n}; n! = #{fact}; decomp(n!) = #{n == 1 ? "1" : Prime.prime_division(fact).map(&proc {|pair| pair[1] > 1 ? "#{pair[0]}^#{pair[1]}" : pair[0]}).join(" * ")}"
end
(1..10).each {|x| puts decomp x}

dawagnbr • Jul 5 '19 • Edited

C++

struct factor {
    long prime;
    long power;
};

auto decompose_factorial(long n) {
    std::vector<factor> result;
    for (long i = 2; i <= n; ++i) {
        auto prime = true;
        for (auto &f : result) {
            for (auto r = i; r % f.prime == 0; r /= f.prime) {
                prime = false;
                ++f.power;
            }
        }
        if (prime) {
            result.push_back({i, 1});
        }
    }
    return result;
}

int main() {
    long n = 25;
    auto decomposition = decompose_factorial(n);
    std::cout << "n = " << n << std::endl;
    std::cout << "decomp(n!) = ";
    for (auto &f : decomposition) {
        std::cout << f.prime;
        if (f.power > 1) {
            std::cout << "^" << f.power;
        }
        std::cout << " ";
    }
    std::cout << std::endl;
    return EXIT_SUCCESS;
}

Output:

n = 25
decomp(n!) = 2^22 3^10 5^6 7^3 11^2 13 17 19 23

Corey Alexander • Jul 4 '19 • Edited

Here is my Rust version! These are getting long including the tests, so I might have to find a better way to post em here! Maybe I'll start posting embeds to their Github repo 🤔 (But I don't know if I can embed a single file from a repo...)

Anyways here is today's!

I took a optimization, by never actually calculating the full factorial. Instead I do the prime decomposition, on each of the factorial values (2..n) and append those lists of prime numbers together. This list will be the same as a prime decomposition of the full factorial.

From here I count the occurrences of each of the prime numbers and the format a string matching the examples!

use std::collections::HashMap;

fn prime_decomposition(n: u32) -> Vec<u32> {
    let mut output = vec![];
    let mut curr = n;

    for i in 2..(n + 1) {
        while curr % i == 0 {
            output.push(i);
            curr = curr / i;
        }
    }

    output
}

fn count_occurances(list: Vec<u32>) -> Vec<(u32, u32)> {
    let mut counts: HashMap<u32, u32> = HashMap::new();

    for x in list {
        let count = counts.entry(x).or_insert(0);
        *count += 1;
    }

    counts
        .keys()
        .map(|key| (*key, *counts.get(key).unwrap()))
        .collect()
}

pub fn factorial_decomposition(n: u32) -> Vec<(u32, u32)> {
    if n == 0 || n == 1 {
        vec![(1, 1)]
    } else {
        let mut factors: Vec<u32> = vec![];

        for i in 2..(n + 1) {
            factors.append(&mut prime_decomposition(i));
        }

        let mut output = count_occurances(factors);
        output.sort();
        output
    }
}

// "n = 12; decomp(12) -> \"2^10 * 3^5 * 5^2 * 7 * 11\""
pub fn fac_decomp_string(n: u32) -> String {
    fn format_single_factorial(x: &(u32, u32)) -> String {
        if x.1 == 1 {
            format!("{}", x.0)
        } else {
            format!("{}^{}", x.0, x.1)
        }
    }

    let factorial_decomposition = factorial_decomposition(n);
    let fac_string = factorial_decomposition
        .iter()
        .map(format_single_factorial)
        .collect::<Vec<String>>()
        .join(" * ");

    format!(
        "n = {n}; decomp({n}) -> \"{decomp}\"",
        n = n,
        decomp = fac_string
    )
}

#[cfg(test)]
mod tests {
    use crate::*;

    fn sorted_counted_prime_decomp(n: u32) -> Vec<(u32, u32)> {
        let mut output: Vec<(u32, u32)> = count_occurances(prime_decomposition(n));
        output.sort();
        output
    }

    #[test]
    fn prime_decomposition_works_for_prime_numbers() {
        assert_eq!(sorted_counted_prime_decomp(2), vec![(2, 1)]);
        assert_eq!(sorted_counted_prime_decomp(3), vec![(3, 1)]);
        assert_eq!(sorted_counted_prime_decomp(5), vec![(5, 1)]);
        assert_eq!(sorted_counted_prime_decomp(7), vec![(7, 1)]);
        assert_eq!(sorted_counted_prime_decomp(11), vec![(11, 1)]);
    }

    #[test]
    fn prime_decomposition_works_for_factors_of_2() {
        assert_eq!(sorted_counted_prime_decomp(2), vec![(2, 1)]);
        assert_eq!(sorted_counted_prime_decomp(4), vec![(2, 2)]);
        assert_eq!(sorted_counted_prime_decomp(8), vec![(2, 3)]);
        assert_eq!(sorted_counted_prime_decomp(16), vec![(2, 4)]);
    }

    #[test]
    fn prime_decomposition_works_for_more_complex_numbers() {
        assert_eq!(sorted_counted_prime_decomp(10), vec![(2, 1), (5, 1)]);
        assert_eq!(sorted_counted_prime_decomp(6), vec![(2, 1), (3, 1)]);
        assert_eq!(sorted_counted_prime_decomp(15), vec![(3, 1), (5, 1)]);
    }

    #[test]
    fn simple_factorial_decomposition() {
        assert_eq!(factorial_decomposition(2), vec![(2, 1)]);
        assert_eq!(factorial_decomposition(3), vec![(2, 1), (3, 1)]);
        assert_eq!(factorial_decomposition(4), vec![(2, 3), (3, 1)]);
        assert_eq!(factorial_decomposition(5), vec![(2, 3), (3, 1), (5, 1)]);
    }

    #[test]
    fn factorial_decomposition_of_edge_cases() {
        assert_eq!(factorial_decomposition(1), vec![(1, 1)]);
        assert_eq!(factorial_decomposition(0), vec![(1, 1)]);
    }

    #[test]
    fn factorial_decomposition_of_examples() {
        assert_eq!(
            factorial_decomposition(12),
            vec![(2, 10), (3, 5), (5, 2), (7, 1), (11, 1)]
        );
        assert_eq!(
            factorial_decomposition(22),
            vec![
                (2, 19),
                (3, 9),
                (5, 4),
                (7, 3),
                (11, 2),
                (13, 1),
                (17, 1),
                (19, 1)
            ]
        );
        assert_eq!(
            factorial_decomposition(25),
            vec![
                (2, 22),
                (3, 10),
                (5, 6),
                (7, 3),
                (11, 2),
                (13, 1),
                (17, 1),
                (19, 1),
                (23, 1),
            ]
        );
    }

    #[test]
    fn formatting_works() {
        assert_eq!(fac_decomp_string(0), "n = 0; decomp(0) -> \"1\"");
        assert_eq!(fac_decomp_string(1), "n = 1; decomp(1) -> \"1\"");
        assert_eq!(
            fac_decomp_string(12),
            "n = 12; decomp(12) -> \"2^10 * 3^5 * 5^2 * 7 * 11\""
        );
        assert_eq!(
            fac_decomp_string(22),
            "n = 22; decomp(22) -> \"2^19 * 3^9 * 5^4 * 7^3 * 11^2 * 13 * 17 * 19\""
        );
        assert_eq!(
            fac_decomp_string(25),
            "n = 25; decomp(25) -> \"2^22 * 3^10 * 5^6 * 7^3 * 11^2 * 13 * 17 * 19 * 23\""
        );
    }
}

Arie Beresteanu • Jul 5 '19

Here is a FORTRAN 90 answer (the module and an example program):

MODULE decompose

IMPLICIT NONE

CONTAINS

SUBROUTINE decomp(n,primes,powers,factorial)
    INTEGER, INTENT(IN)                     :: n
    INTEGER, ALLOCATABLE, INTENT(OUT)       :: primes(:),powers(:)
    INTEGER, INTENT(OUT)                    :: factorial
    INTEGER                                 :: i,j,m,current
    INTEGER, DIMENSION(25)                  :: lowPrimes

    DATA lowPrimes /2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97/

    IF (n.GT.100) THEN !can't handle a too big number
        PRINT *, "Choose a number less than 100"
        RETURN
    END IF

    m=COUNT(lowPrimes.LE.n)  !how many integers less or equal to n

    !initial values
    ALLOCATE(primes(m),powers(m))
    primes=lowPrimes(1:m)
    powers=0 
    factorial = 1

    !decomposing n! number by number
    DO i=2,n
        factorial = factorial * i
        current=i
      DO j=1,m
        IF (MOD(current , primes(j)) .EQ. 0) THEN
            current = INT(current / primes(j))
            powers(j) = powers(j) +1
        END IF
        IF (current.EQ.1) EXIT ! we are done decomposing i
      END DO !j
    END DO !i

END SUBROUTINE decomp

END MODULE decompose


PROGRAM testDecompose

    USE decompose
    IMPLICIT NONE

    INTEGER                     :: myInt,m,i
    INTEGER, ALLOCATABLE        :: pr(:),po(:)
    INTEGER                     :: fa

    myInt = 12
    CALL decomp(n=myInt,primes=pr,powers=po,factorial=fa)

    !printing the result:
    WRITE (*,"(i3,a4,i12,a3)",advance='no') myInt,"! = ",fa," = "
    m = SIZE(pr)
    DO i=1,m
        IF (po(i).GT. 0) WRITE(*,"(i2,a1,i2)" , advance='no') pr(i),"^",po(i)
        IF (i.LT.m) WRITE(*,"(a3)" , advance='no') " + "
    END DO

    PRINT *," "
END PROGRAM testDecompose

The result looks like:
12! = 479001600 = 2^ 6 + 3^ 4 + 5^ 2 + 7^ 1 + 11^ 1

Note: I hard coded n=12 but I could made n be read from the command line

Timothy Foster • Jul 4 '19

I can use any language right? How about MATLAB ;)

factor(factorial(n))

Timothy Foster • Jul 4 '19

But here's a haskell solution just for fun:

import Data.List

prime_factors :: Int -> [Int]
prime_factors 1 = []
prime_factors n = next_factor : (prime_factors $ div n next_factor)
  where next_factor = head [i | i <- [2..n], 0 == mod n i]

decomp :: Int -> [Int]
decomp = sort . decomp'
  where
    decomp' 1 = []
    decomp' n = prime_factors n ++ decomp' (n - 1)

E. Choroba • Jul 4 '19 • Edited

Perl solution, not using any math libraries:

#!/usr/bin/perl
use warnings;
use strict;
use utf8;
use feature qw{ say };

use open OUT => ':encoding(UTF-8)', ':std';

sub is_prime {
    my ($p) = @_;
    for my $d (2 .. sqrt $p) {
        return if 0 == $p % $d;
    }
    return 1
}

sub factor {
    my ($n) = @_;
    my @f;
    for my $p (2 .. $n) {
        next unless is_prime($p);
        if (0 == $n % $p) {
            push @f, $p;
            $n = $n / $p;
            redo
        }
    }
    return @f
}

{   my %digit;
    @digit{0 .. 9} = qw( ⁰ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ );
    sub exponent {
        join "", map $digit{$_}, split //, shift
    }
}

my %exponent;
my $n = shift;
for my $p (2 .. $n) {
    ++$exponent{$_} for factor($p);
}

say join ' * ',
    map $_ . ($exponent{$_} == 1 ? "" : exponent($exponent{$_})),
    sort { $a <=> $b }
    keys %exponent;

For 22, it prints 2¹⁹ * 3⁹ * 5⁴ * 7³ * 11² * 13 * 17 * 19.

Alvaro Montoro • Jul 5 '19 • Edited

JavaScript

const decomp = number => {

  // function that adds the dividers of a number to a "dividers object"
  const subdecomp = (number, subdividers) => {
    let remainder = number

    // from 2 to square root of the number
    for (x = 2; x <= Math.sqrt(number); x++) {
      // check if it can divide the number
      if (remainder % x === 0) {
        // add it as a key to a results object
        if (!subdividers[x]) subdividers[x] = 0;
        // while it can be a divisor, add +1 to the key and update number
        while (remainder % x === 0) {
          subdividers[x]++;
          remainder = remainder / x;
        }
      }
    }
    // if after all there's still a remaining number, it is a divisor too
    if (remainder > 1) {
      if (!subdividers[remainder]) subdividers[remainder] = 1;
      else subdividers[remainder] += 1;
    }
    return subdividers;
  }

  // initial dividers: none!
  let dividers = {}

  // calculate the dividers for each number used in the factorial
  for (let x = 2; x <= number; x++)
    dividers = subdecomp(x, dividers);

  // generate a html string with the result
  return Object.keys(dividers).reduce((acc, curr) => dividers[curr] === 1 
                                      ? `${acc} ${curr}` 
                                      : `${acc} ${curr}<sup>${dividers[curr]}</sup>`
                                      , `decomp(${number}) = `);
}

Not perfect, but it seems to work now. The previous answer I deleted only calculated for the number itself, and not the factorial.

And here is a demo on CodePen.

Rohit Prasad • Feb 23 '20

Python

import math

var = int(input("Enter the number: "))
fac = math.factorial(var)

def prime(x):
        for i in range(3,x-1,2):
                if x%i == 0:
                        return False
        return True

def decomp(x,fac):
        for i in range(fac):
                if fac % x**i != 0:
                        return i-1

print('2^' + str(decomp(2,fac)), end='')
for i in range(3,var+1,2):
        if prime(i) == True:
                e = decomp(i,fac)
                if e != 1:
                        print(' * ' + str(i) + '^' + str(e), end='')
                else:
                        print(' * ' + str(i), end='')
        else:
                continue

print('\n')

peter279k • Jun 17 '20

Here is my simple solution to finish this problem with PHP:

function decomp($n) {
  $result = [];
  $index = 2;

  for($index=2; $index <= $n; $index++) {
    $number = $index;
    $numberIndex = 2;
    if (isPrime($number) === false) {
      while (isPrime($number) === false) {
        if ($number % $numberIndex === 0) {
          if (array_key_exists((string)$numberIndex, $result) === true) {
            $result[(string)$numberIndex] += 1;
          } else {
            $result[(string)$numberIndex] = 1;
          }

          $number = (int)($number / $numberIndex);
        } else {
          $numberIndex += 1;
        }
      }

      if (array_key_exists((string)$number, $result)) {
         $result[(string)$number] += 1;
      } else {
         $result[(string)$number] = 1;
      }
    }

    if (isPrime($index) === true) {
      if (array_key_exists((string)$index, $result)) {
        $result[(string)$index] += 1;
      } else {
        $result[(string)$index] = 1;
      }
    }
  }

  $answer = "";
  foreach($result as $key => $value) {
    if ($key === 1) {
      continue;
    }
    if($value === 1) {
      $answer .= $key . " * ";
      continue;
    }
    $answer .= $key . "^" . $value . " * ";
  }

  return substr($answer, 0, -3);
}

function isPrime($n) {
  $count = ceil(sqrt($n));
  for($index=2; $index<=$count; $index++) {
    if ($n % $index === 0) {
      return false;
    }
  }

  return true;
}

cloudyhug • Aug 30 '19

Haskell

import Data.List
import qualified Data.Map.Strict as Map

primes :: [Int]
primes = filterPrime [2..]
  where filterPrime (p : xs) = p : filterPrime [x | x <- xs, x `mod` p /= 0]

decomp :: Int -> Map.Map Int Int
decomp n =
  if n == 1 || n `elem` lowerPrimes then Map.singleton n 1
  else Map.filter (/= 0) $ divide Nothing 0 n lowerPrimes Map.empty
  where
    lowerPrimes = takeWhile (<= n) primes
    divide Nothing             _     1 _             factors = factors
    divide (Just current)      count 1 _             factors = Map.insert current count factors
    divide Nothing             _     n (p : ps)      factors = divide (Just p) 0 n ps factors
    divide curr@(Just current) count n prim@(p : ps) factors =
      case n `divMod` current of
        (q, 0) -> divide curr (count + 1) q prim factors
        _      -> divide (Just p) 0 n ps (Map.insert current count factors)

decompFactorial :: Int -> String
decompFactorial n = toString $ foldl1 (Map.unionWith (+)) $ map decomp [2..n]
 where toString = intercalate " + " . Map.foldlWithKey (\acc k v -> (show k ++ "^" ++ show v) : acc) []

The decomp function creates a (factor, power) map describing the decomposition of an integer. The decompFactorial function creates this decomposition for all integers from 2 to n, then merges the maps summing the values for each key. The result is then pretty printed.

View full discussion (21 comments)

DEV Community

Daily Challenge #7 - Factorial Decomposition

Examples:

Explanation:

Top comments (21)

Read next

🚀 快速、智能、高效的现代端口扫描器 — RustScan

ModuleNotFoundError in FastAPI Project When Running Pytest

# 揭秘Proof of SQL：让数据验证变得高效又安全

In React, quickly collect form data into a complex JSON object