¿Cómo podemos calcular la multiplicación de las funciones de partición

Question

Por favor, ¿cómo podemos calcular la multiplicación de las funciones de partición. Por ejemplo,$24$, tiene, precisamente, $6$ válido factorizations: $2\cdot2\cdot2\cdot3$, $2\cdot2\cdot6$, $2\cdot3\cdot4$, $2\cdot12$, $3\cdot8$, y $4\cdot6$.

Answer 1

Hay una fórmula que sólo depende de la forma de la descomposición en factores primos de a $n$, es decir, los exponentes de los números primos en la factorización. Esta fórmula se obtiene con el Polya Enumeración Teorema (PET) que se aplica a un determinado repertorio. Incluye la factorización de un producto de un término, es decir,$n$.

Deje $$n= p_1^{v_1} p_2^{v_2} \times \cdots \times p_q^{v_q}$$ ser la factorización prima de $n$ y recuperar la función $\Omega(n)$, que está dada por $$\Omega(n) = \sum_{k=1}^q v_k,$$ es decir, cuenta los factores primos de acuerdo con sus multiplicidades.

El repertorio que va en la MASCOTA está dada por $$Q = -1 + \prod_{k=1}^q \sum_{v=0}^{v_k} u_{p_k}^v = -1 + \prod_{k=1}^q \frac{u_{p_k}^{v_k+1}-1}{u_{p_k}-1}$$ que es una corriente de generación de función en el conjunto de las variables de $\{u_{p_k}\}.$

Con estos valores el valor de $q(n)$ de la multiplicación de las funciones de partición está dada por $$q(n) = [u_{p_1}^{v_1} u_{p_2}^{v_2}\cdots u_{p_q}^{v_q}] \sum_{m=1}^{\Omega(n)} Z(S_m)(P),$$ donde $Z(S_m)$ es el ciclo del índice del grupo simétrico actuando en $m$ elementos, que se calcula a partir de $$Z(S_0) = 1 \quad \text{and}\quad Z(S_m) = \frac{1}{m} \sum_{l=1}^m a_l Z(S_{m-l}).$$

Esto produce la siguiente secuencia de partida en $n=2$ y que se extiende a $n=64$ $$1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 5, 1, 4, 1, 4,\\ 2, 2, 1, 7, 2, 2, 3, 4, 1, 5, 1, 7, 2, 2, 2, 9, 1, 2, 2, 7,\\ 1, 5, 1, 4, 4, 2, 1, 12, 2, 4, 2, 4, 1, 7, 2, 7, 2, 2, 1, 11, 1, 2, 4, 11,\ldots$$ que apunta a OEIS A001055.

La complejidad del repertorio que va en el ciclo de índice es $\tau(n).$ Comentario de Tue Jan 7 00:40:27 CET 2014. Este algoritmo es definitivamente no es tan bueno como lo fue publicado en la Matemática de Desbordamiento de enlace. Por favor, consulte mi segunda respuesta para un algoritmo rápido.

Aquí está el Arce de código que se usó para calcular los valores anteriores:

con(numtheory);
con(grupo):
con(planta):

pet_cycleind_symm :=
proc(n)
 local p, s;
 opción de recordar;

 si n=0 entonces devolver 1; fi;

 ampliar(1/n*añadir(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;

pet_varinto_cind :=
proc(poli, ind)
 local subs1, subs2, polyvars, indvars, v, bote, res;

 res := ind;

 polyvars := indets(poli);
 indvars := indets(ind);

 para v en indvars ¿
 bote := op(1, v);

 subs1 :=
[seq(polyvars[k]=polyvars[k]^olla,
k=1..nops(polyvars))];

 subs2 := [v=subs(subs1, poli)];

 res := subs(subs2, res);
od;

res;
end;

v :=
proc(n)
 opción de recordar;
 local de hecho, rep, gf, fcount, p, res;

 hecho := op(2, ifactors(n));

 rep := mul(añadir(u[hecho[k][1]]^p, p=0..hecho[k][2]),
k=1..nops(hecho de));
 rep := rep-1;

 res := 0;
 para fcount a bigomega(n) hacer
 gf := pet_varinto_cind(rep, pet_cycleind_symm(fcount));
 gf := expand(gf);

 para p a nops(hecho) hacer
 gf := coef(gf, u[hecho[p][1]], hecho[p][2]);
od;

 res := res+gf;
od;

res;
end;

Answer 2

Para el propósito de completar esta discusión y proporcionar una solución eficaz estoy enviando un dinámicos de programación de la aplicación en madera de Arce y en Perl. Este es el Arce de código. Anexo Tue Jan 7, a las 08:05:14 CET 2014. La optimización es posible ya que esta estadística sólo depende de la forma de la factorización y no la de los números primos, por lo que la forma puede ser nuestra clave para su uso en memoization. El lector es invitado a probar esta. Por supuesto, en esta configuración sólo se benefician de memoization si se invoca la función en la interfaz principal varias veces, así que no es un algoritmo DP en el sentido clásico.

mp :=
proc(n)
 opción de recordar;
 local rec, onef, res, f, asg, targ, t;

 si n=1 entonces return {}; fi;

 onef := op(2, ifactors(n))[1];

 rec : a= mp(n/onef[1]);
 si nops(rec) = 0 then return {[n=1]} fi;

 res := {};
 para f en rec ¿
 t := tabla(f);

 targ := onef[1];
 si el tipo(t[targ], entero), a continuación,
 t[targ] := t[targ] + 1
otra cosa
 t[targ] := 1;
fi;

 res := res de la unión {sort(op(op(t)))};

 para asg en f ¿
 t := tabla(f);

 targ := onef[1]*op(1, asg);
 si el tipo(t[targ], entero), a continuación,
 t[targ] := t[targ]+1;
otra cosa
 t[targ] := 1;
fi;

 si t[op(1,asg)]>1, entonces
 t[op(1,asg)] := t[op(1,asg)]-1;
otra cosa
 t[op(1,asg)] := evaln(t[op(1,asg)]); 
fi;

 res := res de la unión {sort(op(op(t)))};
od;
od;

res;
end;

Puede ser usada para calcular el número de factorizations aproximadamente hasta alrededor de $9!$, después de lo cual disminuye drásticamente, por alguna razón.

Para evitar este problema también estoy enviando un Perl programa que implementa el algoritmo DP. Esto tiene el inconveniente de que el método de factorización es ingenuo y lento para detectar grandes números primos pero ilustra el concepto especialmente para valores con muchos factores que tienen numerosos factorizations por ejemplo, para $10^{10}$ da $59521$ factorizations.

#! /usr/bin/perl -w
#

sub onefact {
 my ($n) = @_;

 devuelve 2 si $n % 2 == 0;

 mi $f = 3;

 while($n % $f > 0){
 $f += 2;
}

 return $f;
}

mi %memo = ( 1 => {} );

sub mp {
 my ($n) = @_;
 return $memo{$n} si existe $memo{$n};

 mi $res = {};

 mi $onef = onefact($n);
 if($n/$onef == 1){
 $res->{"$n=1"} = 1;
}
else{
 sub tbl2str {
 my ($tref) = @_;
 mi @keyl = map {
 $_ . "=" . $tref->{$_}
 } ordenar(teclas(%$tref));

 volver join('-', @keyl);
}

 foreach my $f (teclas de %{mp($n/$onef)}){
 mi @asigs = map {
split(/=/);
 } split(/-/, $f);

 mi (%tblsrc) = @asigs;

 mi (%tbl) = @asigs;
si(existe($tbl{$onef})){
 $tbl{$onef} = $tbl{$onef} + 1;
}
else{
 $tbl{$onef} = 1;
}

 $res->{tbl2str(\%tbl)} = 1;

 para mi $a (llaves %tblsrc){
 %tbl = %tblsrc;

 mi $targ = $onef*$a;
si(existe($tbl{$targ})){
$tbl{$targ}++;
}
else{
 $tbl{$targ} = 1;
}

if($tbl{$a}>1){
$tbl{$a}--;
}
else{
 eliminar $tbl{$a};
}

 $res->{tbl2str(\%tbl)} = 1;
}
}
}

 $memo{$n} = $res;
 return $resultado;
}


PRINCIPAL: {
 while(my $n = shift){
 mi $res = escalar(teclas de %{mp($n)});
 mi $msize = escalar(llaves %de la nota);
 print "$n $resultado [$msize]\n";
}
}

Este programa es muy rápido y puede ser usada para calcular el número de factorizations incluso de grandes factoriales, por ejemplo, para $8!, 9!, 10!$ $11!$ calcula en cuestión de segundos los valores $$2116,11830, 70520, 425240,2787810\ldots$$ que nos señala OEIS A076716. Perl tomó cerca de ocho minutos para calcular el valor de $12!.$ a pesar de la ingenuidad de la factorización de Perl el programa puede ser utilizado en grandes números primos o productos de ellos, por ejemplo, intente $104729$ o $62773913 = 7919\times 7927.$

Answer 3

Me siento obligado a agregar otra pregunta como el código de mi esfuerzo inicial es realmente muy pobre y no sólo me refiero a la escuela de grado de la factorización de la rutina. Le pregunté al tipo de gente en MaplePrimes para el asesoramiento y resulta que la multiplicación de las funciones de partición fue objeto de una amplia discusión y no un esfuerzo de colaboración llevado a un algoritmo sencillo y efectivo que está siendo desarrollado. La observación clave de este algoritmo es que podemos generar todas las particiones, comenzando con el único factor de partición y el cálculo de los dos factores, de tres factores etc. particiones repetidamente dividir el elemento más grande en dos factores y admitir la partición resultante en la nueva colección si ambos factores son al menos tan grande como el factor en el final de la partición cuyo último elemento fue dividida. Que es de todos y de esta simple observación hace posible calcular muy grandes conjuntos de multiplicativo de las particiones de forma rápida y eficaz. El crédito va a la MaplePrimes Hilo de curso y a las personas que participaron en él. Lo que es bueno acerca de este algoritmo es que mantiene las particiones y sus elementos ordenados automágicamente.

Estoy enviando un programa Perl que implementa este algoritmo simple (hay un Arce de implementación incluyendo un extenso comentario en el enlace que he dado). Se necesitan tres tipos de argumentos: un factorial produce el recuento de los multiplicativo de la partición de los valores en un rango de factoriales hasta algunos máximo, una gama con una central dash proceso de toda una gama de valores y un solo argumento numérico salidas de las particiones para ese argumento.

Aquí están algunos ejemplos.

$ ./mp-final.pl 40-60
7, 1, 5, 1, 4, 4, 2, 1, 12, 2, 4, 2, 4, 1, 7, 2, 7, 2, 2, 1, 11
$ ./mp-final.pl 10!
0, 1, 2, 7, 21, 98, 392, 2116, 11830, 70520
$ ./mp-final.pl 100
> 100
> 5 20
> 2 50
> 10 10
> 4 25
> 2 5 10
> 2 2 25
> 4 5 5
> 2 2 5 5
9

El principal inconveniente de este Perl skript es que la factorización es ingenuo y no hay builtin para calcular el número teórico de la función de $\Omega(n)$ dar el primer recuento incluyendo multiplicidades.

Este es el código, y mejora con respecto a la primera versión, espero que a pesar de que no es decir mucho.

#! /usr/bin/perl -w
#

sub onefact {
 my ($n) = @_;

 devuelve 2 si $n % 2 == 0;

 mi $f = 3;
 mi $z = int sqrt $n;

 while($n % $f > 0 && $f <= $z){
 $f += 2;
}
 return $n si $f>$z;

 return $f;
}


mi %div_memo;
sub div {
 my ($n) = @_;
 return $div_memo{$n} si existe $div_memo{$n};

 mi $de = onefact($n);
 if($a == $n){
 $div_memo{$n} = [1, $n];
}
else{
 mi $div = [];
 push @$divs, @{div($n/$de)};

 mi %ve = map { $_, 1 } @$divs;

 mi $mx = escalar(@$divs);
 para(mi $pos=0; $pos<$mx; $pos++){
 mi $targ = $divs->[$pos]*$de;
 push @$divs, $targ si no existe $visto{$targ};
}

 $div_memo{$n} = $divs;
}

 return $div_memo{$n};
}

mi %memo = ("1" => []);

sub mp {
 my ($n) = @_;
 return $memo{"$n"} si existe $memo{"$n"};

 mi @resultado = ([$n]); my $m = 2; 
 my ($min, $max) = (0, 0);

while(1){
 para(mi $ind = $min, $ind<=$max; $ind++){
 mi $mpart = $resultado[$ind];

 mi $spl = $#$mpart;
 mi $spval = $mpart->[$spl];
 mi @divs = @{ div($spval) };

 foreach my $d (@divs){
 mi $q = $spval/$d;

 si($d > 1 && $d <= $q && 
 ($spl == 0 || $d >= $mpart->[-2])){
 mi $npart = [@$mpart];

 pop @$npart;
 push @$npart, $d, $q;

 empuje @result, $npart;
}
}
}

 mi $lastfact = $resultado[-1]; $cont = undef;
 foreach my $plazo (@$lastfact){
 si(escalares(@{ div($plazo) }) != 2){
 $cont = 1;
último;
}
}

 de última si no se define($cont);
 $min = $max+1; $max = $#resultado;
$m++;
}

 $memo{"$n"} = \@resultado;
 volver \@resultado;
}


PRINCIPAL: {
 while(my $nstr cambio=) {
 si(mi @int = ($nstr =~ /^(\d+)-(\d+)$/)){
 para(mi $n = $int a[0]; $n <= $int a[1]; $n++){
 imprimir ", " si $n>$int a[0];
 imprimir escalar(@{mp($n)});
}
}
 elsif (mi @mx = ($nstr =~ /^(\d+)!$/)){
 para(mi ($n, $p) = (1, 1); $n <= $mx[0]; $n++){
 $p *= $n;

 imprimir ", " si $p>1;
 imprimir escalar(@{mp($p)});
}
}
 elsif (mi @nvals = ($nstr =~ /^(\d+)$/)){
 foreach my $ent (@{mp($nvals[0])}){
 print "> @$ent\n";
}

 imprimir escalar(@{mp($nvals[0])});
}
else{
 advertir en "saltar argumento $nstr";
}
}

 print "\n";
}

Answer 4

Seguimiento de algunos de Marko respuestas, Perl tiene al menos dos maneras de calcular la Ω(n), suponiendo que usted está dispuesto a utilizar los módulos de: escalar Matemáticas::Principal::Util::factor, y Matemáticas::Pari::bigomega. Aquí hay un ejemplo de uso de módulos para hacer más simple código. También he añadido la fcnt función de A001055 que sólo devuelve el recuento, que permite calcular el factorial ejemplos más rápido y con una cantidad razonable de la memoria.

use warnings;
use strict;
use Math::Prime::Util qw/divisors fordivisors is_prime/;
use Memoize;  memoize('mp');  memoize('fcnt');
$|++;

sub fcnt {
  my($n, $m) = @_;
  return 1 if $n == 1;
  my $s = 0;
  fordivisors {
    $s += fcnt($n/$_, $_) if $_ > 1 && $_ <= $m;
  } $n;
  return $s;
}

sub mp {
  my ($n) = @_;
  return [] if $n == 1;

  my @result = ([$n]);
  my ($min, $max) = (0, 0);

  while ( scalar grep { !is_prime($_) } @{$result[-1]} ) {

    for (my $ind = $min; $ind <= $max; $ind++) {
      my @mpart = @{$result[$ind]};

      my $spval = $mpart[-1];
      my $dmin = (scalar @mpart < 2) ? 2 : $mpart[-2];
      foreach my $d (divisors($spval)) {
        next unless $d >= $dmin;
        my $q = $spval/$d;
        last if $d > $q;  # Divisors are sorted
        push @result, [ @mpart[0 .. $#mpart-1], $d, $q ];
      }
    }
    ($min, $max) = ($max+1, $#result);
  }
 return \@result;
}

La sección PRINCIPAL es idéntica a otras que el uso de "imprimir fcnt($p,$p);" en el factorial caso.