¿Cuántos cuadrados, cubos, cuartos poderes, etc. necesito sumar a n?

14

Se le da un número entero no negativo ny un número entero p >= 2. Necesitas agregar algunas ppotencias ( p=2significa cuadrados, p=3significa cubos) juntas para obtener n. Esto es siempre para cualquier no negativo n, pero no sabes muchos ppoderes (de cualquier número entero positivo ) que necesitarás.

Esta es su tarea: encontrar el número mínimo de ppotencias que puede sumar n.

Ejemplos

>>> min_powers(7, 2)
4                       # you need at least four squares to add to 7
                        # Example: (2)^2 + (1)^2 + (1)^2 + (1)^2 = 4 + 1 + 1 + 1 = 7
>>> min_powers(4, 2)
1                       # you need at least one square to add to 4
                        # Example: (2)^2 = 4
>>> min_powers(7, 3)
7                       # you need at least seven cubes to add to 7
                        # Example: 7*(1)^3 = 7
>>> min_powers(23, 3)
9                       # you need at least nine cubes to add to 23
                        # Example: 2*(2)^3 + 7*(1)^2 = 2*8 + 7*1 = 23

Un artículo relacionado de Wikipedia sobre este problema, el problema de Waring .

Reglas

  • Su código debe ser un programa o una función.

  • La entrada es dos enteros ny pen cualquier orden. Puede suponer que todas las entradas son válidas ( nes cualquier número entero positivo,p >= 2

  • La salida es un número entero que representa el número de potencias necesarias para sumar n.

  • Este es el código de golf, por lo que gana el programa más corto , no necesariamente el más eficiente.

  • Todos y cada uno de los elementos integrados están permitidos.

Como siempre, si el problema no está claro, hágamelo saber. ¡Buena suerte y buen golf!

Sherlock9
fuente
Bueno, parece que la fuerza bruta ganará. Espero que no.
lirtosiast el
3
Este problema es increíblemente difícil, y dudo que alguna respuesta termine dando resultados correctos.
orlp
Al menos tenga límites superiores
qwr

Respuestas:

5

Pyth, 20 19 bytes

Guardado 1 byte gracias a FryAmTheEggman.

L&bhSmhy-b^dQS@bQyE

Toma entrada en dos líneas, pprimero y luego n.

Pruébalo en línea. Banco de pruebas.

Explicación

El código define una función recursiva y(b)que devuelve el resultado min_powers(b, p).

L                      define a function y(b):
 &b                      return b if it's 0
             S           get a list of positive integers less than or equal to
              @bQ        the p:th root of b
     m                   map the integers to:
        -b                 subtract from b
          ^dQ              the p:th power of the current integer
       y                   recurse on the above
      h                    increment the result
    hS                   find the smallest result number and return it
                 yE    calculate y(n) and print
PurkkaKoodari
fuente
8

Mathematica 61 50 bytes

Con 11 bytes guardados por LegionMammal978.

Cuando se limita a las potencias de contar números, este problema es sencillo (en Mathematica). Cuando se extiende para incluir poderes de enteros, es una pesadilla.

(k=0;While[PowersRepresentations[#,++k,#2]=={}];k)&

Casos de prueba

(k = 0; While[PowersRepresentations[#, ++k, #2] == {}]; k) &[7, 2]
(k = 0; While[PowersRepresentations[#, ++k, #2] == {}]; k) &[4, 2]
(k = 0; While[PowersRepresentations[#, ++k, #2] == {}]; k) &[7, 3]
(k = 0; While[PowersRepresentations[#, ++k, #2] == {}]; k) &[23, 3]

4 4

1

7 7

9 9


PowersRepresentationsp[n,k,p]encuentra todos los casos en los que nse puede expresar como una suma de kenteros positivos elevados a la penésima potencia.


Por ejemplo,

PowersRepresentations[1729, 2, 3]

{{1, 12}, {9, 10}}

Comprobación,

1^3 + 12^3

1729


9^3 + 10^3

1729

DavidC
fuente
Los lenguajes competitivos como Mathematica derrotan el propósito de estas cosas ... no se necesita creatividad para conocer el nombre de una función. Pero aún así, bien escrito.
csga5000
1
@ csga5000 Hola, los idiomas de golf ganan el 99% de los desafíos en este sitio ...
LegionMammal978
@ LegionMammal978 Si bien no estoy de acuerdo con el punto de csga, jugar golf en idiomas de golf requiere una gran cantidad de creatividad.
Pomo de la puerta
2
De acuerdo, no hay premios para la creatividad en esta presentación. Tampoco para la compacidad: la presentación de Pyth tiene menos de la mitad de la longitud. Los problemas se vuelven desafiantes para lenguajes como Mathematica cuando se pueden reformular como instancias de fenómenos más generales y cuando las combinaciones inusuales de funciones de alto nivel pueden desempeñar un papel. También se vuelven más interesantes.
DavidC
3

Java - 183177 bytes

int p(int a,int b){int P,c,t,l=P=t=a,f=0;double p;while(P>0){a=t=l;c=0;while(t>0){if(a-(p=Math.pow(t,b))>=0&&t<=P){while((a-=p)>=0)c++;a+=p;}t--;}f=c<f||f==0?c:f;P--;}return f;}

183 bytes

int p(int a,int b){int P,c,t,l,f=0;P=t=l=a;double p;while(P>0){a=t=l;c=0;while(t>0){if(a-(p=Math.pow(t,b))>=0&&t<=P){while((a-=p)>=0){c++;}a+=p;}t--;}f=c<f||f==0?c:f;P--;}return f;}

Sin golf

int p(int a, int b){
    int P,c,t,l=P=t=a,f=0;
    double p;
    while (P>0){
        a=t=l;
        c=0;
        while (t>0){
            if (a-(p=Math.pow(t, b))>=0 && t<=P){
                while((a-=p)>=0)c++;
                a+=p;
            }
            t--;
        }
        f=c<f||f==0?c:f;
        P--;
    }
    return f;
}

Resultado

System.out.println(p(7, 2));    // 4
System.out.println(p(4,2));     // 1
System.out.println(p(7,3));     // 7
System.out.println(p(23,3));    // 9
Yassin Hajaj
fuente
Esta respuesta no es válida p(32,2)devuelve 5cuando debería devolver 2( 4^2 + 4^2 = 32).
PurkkaKoodari
@ Pietu1998 Ok, lo modificaré.
Yassin Hajaj
@ Pietu1998 ¿Cómo lo harías?
Yassin Hajaj
Lo hice recursivamente, comprobando cada potencia posible para cada número.
PurkkaKoodari
1
@YassinHajaj +1 para java y hágalo usted mismo
csga5000
1

Python 2, 66 bytes

f=lambda n,p:n and-~min(f(n-k**p,p)for k in range(1,n+1)if n/k**p)

Intenta restando recursivamente cada una de las ppotencias que deja el resto no negativo, calculando su valor en cada resto y tomando el mínimo más 1. En 0, las salidas 0.

La comprobación fea if n/k**p(equivalente a if k**p<=n) es evitar que la función entre en los negativos e intente quitar la minlista vacía. Si Python tiene min([])=infinity, esto no sería necesario.

xnor
fuente
Guau. Esto es mucho más corto que mi código de prueba en Python. +1!
Sherlock9
0

C (gcc) , 122 bytes

r(n,p,k,s,j,b){if(!k)return n!=s;for(b=j=1;j<n;b*=r(n,p,~-k,s+(int)pow(j++,p)));n=b;}f(n,p,k){for(k=0;r(n,p,++k,0););n=k;}

Pruébalo en línea!

Jonathan Frech
fuente