Fatorial revisitado III

Minhas tentativas anteriores de otimizar o cálculo dos fatoriais a partir de potências de números primos tinha evoluído até eu conseguir calcular o total dos expoentes de cada primo p entre potências consecutivas. Agora, consegui encontrar uma maneira de calcular todos os expoentes até uma potência qualquer.

Para um primo p, a soma dos expoentes de sua participação em cada múltiplo anterior ou igual a pⁿ é

n+[(pⁿ-p*n+n-1)/(p-1)]
= pⁿ-1/p-1

Por exemplo, entre 2 e 8, temos os seguintes múltiplos de 2: 2, 4, 6, e 8. Anteriormente, teríamos que calcular os expoentes entre 2 e 4 e somá-los aos expoentes entre 4 e 8 e ainda somar os expoentes das potências (2, 4, e 8).

Agora, chegamos rapidamente ao resultado:

3+[(2³-2*3+3-1)/(2-1)] = 3+[(8-6+3-1)/1] = 3+4 = 7
= 8-1/2-1
= 7

Conferindo os múltiplos de 2, confirmamos que

• 2 = 2¹
• 4 = 2²
• 6 = 2¹*3
• 8 = 2³

E assim, percebemos que a soma dos expoentes é, de fato, 7.

Alterei um pouco o código para exibir as respectivas fatorações.

import java.math.BigInteger;

public class Factorial {

  private static int in(int p, int i) {
    int n=0;
    while(i%p==0) {
      n++;
      i=i/p;
    }
    return n;
  }

  public static BigInteger f(int n) {
    int m=n+1;
    int[] p=new int[m];
    double logn=Math.log(n);
    for(int i=2; i<=m/2; i++) {
      if(p[i]!=-1) {
        //Marcar todos os múltiplos
        for(int j=i+i; j<m; j+=i) {
          p[j]=-1;
        }
        //Calcular soma de expoentes até a maior potência anterior a n
        int power=(int)(logn/Math.log(i));
        int k=(int)Math.pow(i, power);
        p[i]=(k-1)/(i-1);
        //Calcular os expoentes para os múltiplos que seguem a última potência
        for(int l=k+i; l<m; l+=i) {
          p[i]+=in(i, l);
        }
      }
    }
    BigInteger f=BigInteger.ONE;
    for(int k=2; k<m; k++) {
      int pk=p[k];
      if(pk>=0) {
        if(k>2) {
          System.out.print("*");
        }
        if(pk<2) {
          System.out.print(k);
          f=f.multiply(BigInteger.valueOf(k));
        } else {
          System.out.print(k+"^"+pk);
          f=f.multiply(BigInteger.valueOf(k).pow(pk));
        }
      }
    }
    return f;
  }
    
  public static void main(String... args) {
    for(int i=2; i<20; i++) {
      System.out.printf("%d! = ", i);
      BigInteger f1=f(i);
      System.out.printf(" = %d\n", f1);
    }
  }
 }

E isso produz o seguinte:

2! = 2 = 2
3! = 2*3 = 6
4! = 2^3*3 = 24
5! = 2^3*3*5 = 120
6! = 2^4*3^2*5 = 720
7! = 2^4*3^2*5*7 = 5040
8! = 2^7*3^2*5*7 = 40320
9! = 2^7*3^4*5*7 = 362880
10! = 2^8*3^4*5^2*7 = 3628800
11! = 2^8*3^4*5^2*7*11 = 39916800
12! = 2^10*3^5*5^2*7*11 = 479001600
13! = 2^10*3^5*5^2*7*11*13 = 6227020800
14! = 2^11*3^5*5^2*7^2*11*13 = 87178291200
15! = 2^11*3^6*5^3*7^2*11*13 = 1307674368000
16! = 2^15*3^6*5^3*7^2*11*13 = 20922789888000
17! = 2^15*3^6*5^3*7^2*11*13*17 = 355687428096000
18! = 2^16*3^8*5^3*7^2*11*13*17 = 6402373705728000
19! = 2^16*3^8*5^3*7^2*11*13*17*19 = 121645100408832000

É muito mais interessante que um fatorial recursivo simples, com if ou sem.