Representación de un número como suma de k pth poderes

Question

Existe un algoritmo para encontrar una representación de un determinado número de no negativo $n$ como una suma de $k$, $p$ th poderes donde $k, p > 1$ ? Que es una representación de como,

$n = n_{1}^p + n_{2}^p + . . . + n_{k}^p$

Mathematica, PowersRepresentations[n, k, p] resuelve este problema y quiero implementar un algoritmo de mí mismo para resolver el problema.

He encontrado que Waring del problema está estrechamente relacionado con éste, pero que no es exactamente lo que estoy buscando.

Answer 1

Estoy enviando un dinámicos de programación de la aplicación que soluciona este problema. Este algoritmo es pseudo-polinomial es decir, el polinomio en el valor de ${n}$ veces $k$. Este es exponencial en el número de bits. Con este tipo de tiempo complejidad generalmente uno podría decidir no molestes, me decidí a probarlo de todas maneras como el Mathematica aplicación también parece ser que en esta clase o que no han añadido la advertencia a la documentación que se señaló anteriormente. Mi Perl aplicación es más rápido de lo que Mathematica ofrece.

Aquí una muestra de la salida:

$ ./powrep.pl 14000 3 2
12^2 + 20^2 + 116^2 = 14000
20^2 + 44^2 + 108^2 = 14000
20^2 + 60^2 + 100^2 = 14000
36^2 + 52^2 + 100^2 = 14000
44^2 + 60^2 + 92^2 = 14000
60^2 + 68^2 + 76^2 = 14000

$ ./powrep.pl 1729 2 3
1^3 + 12^3 = 1729
9^3 + 10^3 = 1729

$ ./powrep.pl 126 4 2
0^2 + 1^2 + 2^2 + 11^2 = 126
0^2 + 1^2 + 5^2 + 10^2 = 126
0^2 + 3^2 + 6^2 + 9^2 = 126
1^2 + 3^2 + 4^2 + 10^2 = 126
1^2 + 5^2 + 6^2 + 8^2 = 126
2^2 + 3^2 + 7^2 + 8^2 = 126
2^2 + 4^2 + 5^2 + 9^2 = 126
4^2 + 5^2 + 6^2 + 7^2 = 126

$ ./powrep.pl 28732 4 5
4^5 + 5^5 + 6^5 + 7^5 = 28732

Y este es el código, escrito con la brevedad y la simplicidad en mente.

#! /usr/bin/perl -w

mi %memo;
mi @basepows;

sub powrep {
 my ($n, $k, $p) = @_;

 mi $clave = "$n-$k";
 return $memo{$key} si existe $memo{$key};

 volver [] si $k == 1;

 mi @res;
 foreach my $bpair (@basepows){
 mi $bp = $bpair->[1];
 última si $bp >= $n;

 foreach my $r (@{powrep($n-$ta, $k-1, $p)}){
 push @res, [$bpair->[0], @$r]
 si $bpair->[0] <= $r->[0];
}
}

 $memo{$key} = \@res;
 return $memo{$key};
}


PRINCIPAL: {
 mi $n = shift || 1729;
 mi $k = shift || 2;
 mi $p = shift || 3;

 mueren "todos los parámetros (n, k, p) positiva por favor"
 si $n<1 || $k<1 || $p<1;

 my ($p, $val) = (1);
 do {
 $val = $p ** $p;

if($val<=$n){
 $memo{"$val-1"} = [[$p]];
 push @basepows, [$p, $val];
}

$p++;
 } while($val<$n);

 mi @allsols;

 para(mi $zterms = $k-1; $zterms >= 0; $zterms--){
 foreach my $sol (@{powrep($n, $k$zterms, $p)}){
 push @allsols, 
 [(0) x $zterms, @$sol];
}
}

 foreach my $sol (@allsols){
 mi $check = 0;
 foreach my $t (@$sol){
 $cheque += $t ** $p;
}

 mi @términos = map { "$_^$p" } @$sol;
 imprimir join(' + ', @términos);
 print "= $compruebe\n";
}

 exit 0;
}

Answer 2

Como había un poco de preocupación de que el programa iba a usar demasiado la memoria, lo que fue justificado, estoy enviando una versión modificada que sólo las tiendas y encuentra una única solución por n-k combinación. Esto debería hacer posible el ataque de los casos hasta el límite impuesto por el tamaño de un Perl entero.

#! /usr/bin/perl -w

mi %memo;
mi @basepows;

sub powrep {
 my ($n, $k, $p) = @_;

 mi $clave = "$n-$k";
 return $memo{$key} si existe $memo{$key};

 volver [] si $k == 1;

 mi @res = ();
 foreach my $bpair (@basepows){
 mi $bp = $bpair->[1];
 última si $bp >= $n;

 mi $resref = powrep($n-$ta, $k-1, $p);
si(escalares(@$resref)){
 push @res, [$bpair->[0], @{$resref->[0]}];
último;
}
}

 $memo{$key} = \@res;
 return $memo{$key};
}


PRINCIPAL: {
 mi $n = shift || 1729;
 mi $k = shift || 2;
 mi $p = shift || 3;

 mueren "todos los parámetros (n, k, p) positiva por favor"
 si $n<1 || $k<1 || $p<1;

 my ($p, $val) = (1);
 do {
 $val = $p ** $p;

if($val<=$n){
 $memo{"$val-1"} = [[$p]];
 push @basepows, [$p, $val];
}

$p++;
 } while($val<$n);

 mi @allsols;

 para(mi $zterms = $k-1; $zterms >= 0; $zterms--){
 mi $resref = powrep($n, $k$zterms, $p);
si(escalares(@$resref)){
 push @allsols, [(0) x $zterms, @{$resref->[0]}];
}
}

 foreach my $sol (@allsols){
 mi $check = 0;
 foreach my $t (@$sol){
 $cheque += $t ** $p;
}

 mi @términos = map { "$_^$p" } @$sol;
 imprimir join(' + ', @términos);
 print "= $compruebe\n";
}

 exit 0;
}

Este programa modificado fue capaz de calcular la siguiente tabla con la mitad de una hora de tiempo de cálculo y una muy modesta cantidad de memoria.

0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 10000^2 = 100000000
0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 2800^2 + 9600^2 = 100000000
0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 192^2 + 1680^2 + 9856^2 = 100000000
0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 8^2 + 40^2 + 1544^2 + 9880^2 = 100000000
0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 1^2 + 1^2 + 1^2 + 1346^2 + 9909^2 = 100000000
0^2 + 0^2 + 0^2 + 0^2 + 1^2 + 1^2 + 1^2 + 5^2 + 3504^2 + 9366^2 = 100000000
0^2 + 0^2 + 0^2 + 1^2 + 1^2 + 1^2 + 2^2 + 2^2 + 5335^2 + 8458^2 = 100000000
0^2 + 0^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 4113^2 + 9115^2 = 100000000
0^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 9^2 + 3512^2 + 9363^2 = 100000000
1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 2^2 + 5335^2 + 8458^2 = 100000000

Answer 3

Una vez que dejamos de exigir que el algoritmo de producir todas las soluciones, y la demanda de cambio que se producen de una solución, se puede utilizar un codicioso técnica para acelerar el algoritmo aún más. Asignar a los términos que empiezan con la más grande posible. Esto le da un muy rápido algoritmo que, sin embargo, no falte a ninguna de las soluciones, en el sentido de que si hay al menos uno, una solución.

Aquí es un ejemplo.

0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 10000^2 = 100000000
0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 9600^2 + 2800^2 = 100000000
0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 9984^2 + 512^2 + 240^2 = 100000000
0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 9992^2 + 392^2 + 56^2 + 56^2 = 100000000
0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 9999^2 + 141^2 + 10^2 + 3^2 + 3^2 = 100000000
0^2 + 0^2 + 0^2 + 0^2 + 9999^2 + 141^2 + 10^2 + 4^2 + 1^2 + 1^2 = 100000000
0^2 + 0^2 + 0^2 + 9999^2 + 141^2 + 10^2 + 3^2 + 2^2 + 2^2 + 1^2 = 100000000
0^2 + 0^2 + 9999^2 + 141^2 + 9^2 + 5^2 + 3^2 + 1^2 + 1^2 + 1^2 = 100000000
0^2 + 9999^2 + 141^2 + 10^2 + 2^2 + 2^2 + 2^2 + 2^2 + 1^2 + 1^2 = 100000000
9999^2 + 141^2 + 10^2 + 3^2 + 2^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 = 100000000

Y aquí es otra.

0^3 + 0^3 + 0^3 + 0^3 + 396^3 + 312^3 + 196^3 = 100000000
0^3 + 0^3 + 0^3 + 463^3 + 79^3 + 57^3 + 41^3 = 100000000
0^3 + 0^3 + 464^3 + 46^3 + 17^3 + 7^3 + 4^3 = 100000000
0^3 + 464^3 + 46^3 + 16^3 + 10^3 + 6^3 + 2^3 = 100000000
464^3 + 46^3 + 16^3 + 9^3 + 7^3 + 5^3 + 3^3 = 100000000

Un último ejemplo.

0^5 + 39^5 + 22^5 + 21^5 + 14^5 + 3^5 + 1^5 = 100000000
37^5 + 27^5 + 27^5 + 18^5 + 8^5 + 8^5 + 5^5 = 100000000

Este es el código.

#! /usr/bin/perl -w

mi %memo;
mi @basepows;

sub powrep {
 my ($n, $k, $p) = @_;

 mi $clave = "$n-$k";
 return $memo{$key} si existe $memo{$key};

 volver [] si $k == 1;

 mi @res = ();
 foreach my $bpair (@basepows){
 mi $bp = $bpair->[1];
 siguiente si $bp >= $n;

 mi $resref = powrep($n-$ta, $k-1, $p);
si(escalares(@$resref)){
 push @res, [$bpair->[0], @{$resref->[0]}];
último;
}
}

 $memo{$key} = \@res;
 return $memo{$key};
}


PRINCIPAL: {
 mi $n = shift || 1729;
 mi $k = shift || 2;
 mi $p = shift || 3;

 mueren "todos los parámetros (n, k, p) positiva por favor"
 si $n<1 || $k<1 || $p<1;

 my ($p, $val) = (1);
 do {
 $val = $p ** $p;

if($val<=$n){
 $memo{"$val-1"} = [[$p]];
 push @basepows, [$p, $val];
}

$p++;
 } while($val<$n);
 @basepows = reverse(@basepows);

 mi @allsols;

 para(mi $zterms = $k-1; $zterms >= 0; $zterms--){
 mi $resref = powrep($n, $k$zterms, $p);
si(escalares(@$resref)){
 push @allsols, [(0) x $zterms, @{$resref->[0]}];
}
}

 foreach my $sol (@allsols){
 mi $check = 0;
 foreach my $t (@$sol){
 $cheque += $t ** $p;
}

 mi @términos = map { "$_^$p" } @$sol;
 imprimir join(' + ', @términos);
 print "= $compruebe\n";
}

 exit 0;
}