Prime factorization of a factorial

Question

I need to write a program to input a number and output its factorial's prime factorization in the form:

4!=(2^3)*(3^1)

5!=(2^3)*(3^1)*(5^1)

The problem is I still can't figure out how to get that result.

Apparently each first number in brackets is for the ascending prime numbers up until the actual factorial. The second number in brackets is the amount of times the number occurs in the factorial.

What I can't figure out is for example in 5!=(2^3)*(3^1)*(5^1), how does 2 only occur 3 times, 3 only 1 time and 5 only one time in 120 (5!=120).

I have now solved this thanks to the helpful people who commented but I'm now having trouble trying to figure out how could I take a number and get the factorial in this format without actually calculating the factorial.

Valentijn

You're aware that 2*2*2 * 3 * 5 is equal to 120, right? What confuses you about that? – Aristocracy

I was just confuse where those numbers come from. I have figured it out now. – Valentijn

Look at my answer towards the bottom. It explains how you can get the prime factorization of the factorial without actually calculating the factorial. Basically, you factor all of the numbers that make up the factorial and add the exponents of like bases. – Perkins

Answer 1

Every number can be represented by a unique (up to re-ordering) multiplication of prime numbers, called the prime factorization of the number, as you are finding the prime factors that can uniquely create that number.

2^3=8

3^1=3

5^1=5

and 8*3*5=120

But this also means that: (2^3)*(3^1)*(5^1) = 120

It's not saying that 2 occurs 3 times as a digit in the number 120, which it obviously does not, but rather to multiply 2 by 2 by 2, for a total of 3 twos. Likewise for the 3 and 5, which occur once in the prime factorization of 120. The expression which you mention is showing you this unique prime factorization of the number 120. This is one way of getting the prime factorization of a number in Python:

def pf(number):
    factors=[]
    d=2
    while(number>1):
        while(number%d==0):
            factors.append(d)
            number=number/d
        d+=1
    return factors

Running it you get:

>>> pf(120)
[2, 2, 2, 3, 5]

Which multiplied together give you 120, as explained above. Here's a little diagram to illustrate this more clearly:

Wrenn

Thanks the prime factor bit clued me in. – Valentijn

I understand, although im not familiar with python. My next question is how could I take a number and get the factorial in this format without actually calculating the factorial. – Valentijn

@Valentijn you can use the definition of factorial. It is a product of a bunch of factors (components). Each of those factors (components) can be decomposed into prime factors. Therefore the product of factors can be rewritten in terms of the product of the found prime factors of the components -- yielding the answer to your problem without having to compute the factorial at all. – Soaring

Answer 2

Consider e.g. 33!. It's a product of:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

the factors are:

2   2   2   2    2     2     2     2     2     2     2     2     2     2     2     2
    2       2          2           2           2           2           2           2
            2                      2                       2                       2
                                   2                                               2
                                                                                   2
  3     3     3        3        3        3        3        3        3        3        3
              3                          3                          3
                                                                    3
      5          5              5              5              5              5
                                                              5
          7                  7                    7                    7
                   11                               11                               11
                         13                                     13
                                     17
                                           19
                                                       23
                                                                         29    31

Do you see the pattern?

33! = 2^( 33 div 2 + 33 div 4 + 33 div 8 + 33 div 16 + 33 div 32) *
      3^( 33 div 3 + 33 div 9 + 33 div 27) *
      5^( 33 div 5 + 33 div 25) *
      ----
      7^( 33 div 7) * 11^( 33 div 11) * 13^( 33 div 13) *
      ----
      17 * 19 * 23 * 29 * 31

Thus, to find prime factorization of n! without doing any multiplications or factorizations, we just need to have the ordered list of primes not greater than n, which we process (with a repeated integer division and a possible summation) in three stages - primes that are smaller or equal to the square root of n; such that are smaller or equal to n/2; and the rest.

Actually with lazy evaluation it's even simpler than that. Assuming primes is already implemented returning a stream of prime numbers in order, in Haskell, factorial factorization is found as

ff n = [(p, sum . takeWhile (> 0) . tail . iterate (`div` p) $ n) 
         | p <- takeWhile (<= n) primes]

-- Prelude> ff 33
-- [(2,31),(3,15),(5,7),(7,4),(11,3),(13,2),(17,1),(19,1),(23,1),(29,1),(31,1)]

because 33 div 4 is (33 div 2) div 2, etc..

Lowrie

Answer 3

2^3 is another way of writing 2³, or two to the third power. (2^3)(3^1)(5^1) = 2³ × 3 × 5 = 120.

(2^3)(3^1)(5^1) is just the prime factorization of 120 expressed in plain ASCII text rather than with pretty mathematical formatting. Your assignment requires output in this form simply because it's easier for you to output than it would be for you to figure out how to output formatted equations (and probably because it's easier to process for grading).

The conventions used here for expressing equations in plain text are standard enough that you can directly type this text into google.com or wolframalpha.com and it will calculate the result as 120 for you: (2^3)(3^1)(5^1) on wolframalpha.com / (2^3)(3^1)(5^1) on google.com

---

WolframAlpha can also compute prime factorizations, which you can use to get test results to compare your program with. For example: prime factorization of 1000!

A naïve solution that actually calculates the factorial will only handle numbers up to 12 (if using 32 bit ints). This is because 13! is ~6.2 billion, larger than the largest number that can be represented in a 32 bit int.

However it's possible to handle much larger inputs if you avoid calculating the factorial first. I'm not going to tell you exactly how to do that because either figuring it out is part of your assignment or you can ask your prof/TAs. But below are some hints.

a^b × a^c = a^b+c

equation (a)      10 = 2¹ × 5¹
equation (b)      15 = 3¹ × 5¹
10 × 15 = ?      Answer using the right hand sides of equations (a) and (b), not with the number 150.

10 × 15 = (2¹ × 5¹) × (3¹ × 5¹) = 2¹ × 3¹ × (5¹ × 5¹) = 2¹ × 3¹ × 5²

As you can see, computing the prime factorization of 10 × 15 can be done without multiplying 10 by 15; You can instead compute the prime factorization of the individual terms and then combine those factorizations.

Tailrace

Thanks you would be right in assuming that. I will attempt on my own before looking. Can't get a job if I rely on others to do the hard stuff. – Valentijn

Answer 4

If you write out the factorial 5!:
1 * 2 * 3 * 4 * 5,
you will notice that there is one non-prime number: 4. 4 can be written as 2 * 2 or 2^2, which is where the extra 2s come from. Add up all of the occurrences (exponential forms are in parentheses; add exponents for like bases):
2 (2^1) * 3 (3^1) * 4 (2^2) * 5 (5^1), you get the proper answer.

Perkins

Readers should note that here "2 (2^1) * 3 (3^1) * 4 (2^2) * 5 (5^1)" doesn't mean "2 × 2¹ × 3 × 3¹ × 4 × 2² × 5 × 5¹", (which evaluates to 120² rather than 120). In this context the parenthesized text simply expands the corresponding term of the factorial rather than acting as terms themselves. – Tailrace

Answer 5

You can use O(n/2 log log n) algorithm using only sums (no need precalc primes).

This is a sieve using relation

f = a * b  ~>  f^k = a^k * b^k

then, we reduce all initial factors 1 * 2 * 3 * ... * n moving k from big numbers to small numbers.

Using Sieve of Atkin the Will Ness algorithm could be better for very big n if not, I think it could be better

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
  int n = atoi(argv[1]);
  int *p = (int *) malloc(sizeof(int) * (n + 1));
  int i, j, d;
  for(i = 0; i <= n; i++)
    p[i] = 1;
  for(i = n >> 1; i > 1; i--)
    if(p[i]) {
      for(j = i + i, d = 2; j <= n; j += i, d++) {
        if(p[j]) {
          p[i] += p[j];
          p[d] += p[j];
          p[j] = 0;
        }
      }
    }
  printf("1");
  for(i = 2; i <= n; i++)
    if(p[i])
      printf(" * %i^%i", i, p[i]);
  printf("\n");
  return 0;
}

Locomobile

sieve of Atkin is reportedly very hard to implement efficiently. – Lowrie

Good point @WillNess, for that reason I think your aproach is better for very (very) big numbers :) On the other hand, I wonder if Atkin could be used as my sieve to get a better alg. Nice problem! – Locomobile

I think for very big numbers N the output will consist of way too many entries - about N / (log N - 1) of them (as many as there are primes below N). For 10^9 it's 50,701,542 entries (actually, 50,847,534). We won't really need to do that, I guess. :) So any normal impl of SoE will do, I think, whether pre-calc'd or as part of the algo. :) – Lowrie

You've convinced me :) XD XD – Locomobile

Answer 6

Another way of looking at the same problem is how to group their exponents to absolutely minimize duplicate computations :

    31*29*23*19*17*11*5*3*2*
               (13*11*5*3*2*
                   (7*5*3*2*
                       (3*2*(2)^2)^2)^2)^2

---

8683317618811886495518194401280000000: 

  2^31 3^15 5^7 7^4 11^3 13^2 17 19 23 29 31

Notice still there are many copies of ((11)*5)*3*2, but once you set them to temp variables along the way ….

             31 * 29 * 23 * 19 * 17

      * (x = 11 * (y = (z = 3 * 2) * 5))

* (13 *  x * (7 *  y * (z * (2)^2)^2)^2)^2

… instead of 32 multiplication ops at the worst case linear scenario, now we have just

• 4 mults (*) on the primes above half way (so always a single copy),

• 4 mults in 2nd row to define the 3 temp variables,

• 6 more mults at 3rd row, and finally,

• 4 nested squarings

Leading to a total of just 18 mult-or-square ops in total. Once in a blue moon, when the exponents are so well lined up, like 10!, one can even write it as

     7 * (5 * (3 * (2) ^ 2) ^ 2) ^ 2

     7 * 720^2 (the most succinct form I'm aware of)

Rule of thumb for prime factorization prior to factorials is realizing for most of the primes you need you don't even need to do any division at all - since the higher half cannot even have 2 copies of itself, and like 75% of the prime range would have a max of 3 copies.

So it's mostly just the tiny primes with lots of copies that you actually need to calculate precisely. e.g.

For factorials <= 120, only 4 primes have reached at least its own square and require extra processing - 2, 3, 5, and 7. Factorials <= 360, add in 11, 13, and 17

    120 ! is already kinda big - 199 digits in decimal 
    360 ! larger still,          766 digits 
262,143 ! is something like 1.306 mn digits 

And most of the time, it's not worth the hassle to pre-take-out trailing zeros.

ps : to someone else's point, the factorials from 3! to 6! all have a very common approach

 3 ! =   6 = 2^3 - 2 = 1 + 2 + 3
 4 ! =  24 = 3^3 - 3 =   5^2 - 1
 5 ! = 120 = 5^3 - 5 =  11^2 - 1
 6 ! = 720 = 9^3 - 9 =  27^2 - 9 = 3^6 - 9

No factorization even needed, since all 4 use the same value for the cubing and the subtraction.

 4! + 5! = 144 = 12^2
 5! + 6! = 840 = 29^2 - 1

Heptangular