Quantos quadrados, cubos, quarta potência etc. preciso somar n?

14

Você recebe um número inteiro não negativo ne um número inteiro p >= 2. Você precisa adicionar alguns p-ésimos poderes ( p=2quadrados, p=3cubos) para obter n. Isso é sempre para qualquer não-negativo n, mas você não conhece muitos ppoderes (de qualquer número inteiro positivo ) que precisará.

Esta é sua tarefa: encontre o número mínimo de p-ésimos poderes aos quais pode somar n.

Exemplos

>>> 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

Um artigo relacionado da Wikipedia sobre esse problema, o problema de Waring .

Regras

  • Seu código deve ser um programa ou uma função.

  • A entrada é dois inteiros ne pem qualquer ordem. Você pode assumir que todas as entradas são válidas ( nqualquer número inteiro positivo,p >= 2

  • A saída é um número inteiro que representa o número de potências necessárias para somar n.

  • Isso é código de golfe, portanto o programa mais curto vence., Não necessariamente o mais eficiente.

  • Todo e qualquer embutido é permitido.

Como sempre, se o problema não estiver claro, entre em contato. Boa sorte e bom golfe!

Sherlock9
fonte
Bem, parece que a força bruta vencerá. Espero que não.
precisa saber é o seguinte
3
Esse problema é incrivelmente difícil, e eu duvido que qualquer resposta seja concluída com os resultados corretos.
orlp
Pelo menos ter limites superiores
qwr

Respostas:

5

Pitão, 20 19 bytes

Salvo 1 byte graças a FryAmTheEggman.

L&bhSmhy-b^dQS@bQyE

Recebe entrada em duas linhas, pprimeiro e depois n.

Experimente online. Suíte de teste.

Explicação

O código define uma função recursiva y(b)que retorna o resultado para 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
fonte
8

Mathematica 61 50 bytes

Com 11 bytes salvos por LegionMammal978.

Quando restrito ao poder de contar números, esse problema é direto (no Mathematica). Quando estendido para incluir potências de números inteiros, é um pesadelo.

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

Casos de teste

(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

1

7

9


PowersRepresentationsp[n,k,p]encontra todos os casos em que npode ser expresso como uma soma de knúmeros inteiros positivos elevados à pdécima-potência.


Por exemplo,

PowersRepresentations[1729, 2, 3]

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

Verificando,

1^3 + 12^3

1729


9^3 + 10^3

1729

DavidC
fonte
Competitivamente, linguagens como o Mathematica derrotam o objetivo dessas coisas ... não é preciso criatividade para saber o nome de uma função. Mas ainda assim, bem escrito.
precisa saber é o seguinte
1
@ csga5000 Hey, línguas de golfe ganhar 99% dos desafios neste site ...
LegionMammal978
@ LegionMammal978 Embora eu não concorde com o ponto de vista da CSGA, jogar golfe em idiomas de golfe exige uma enorme quantidade de criatividade.
Maçaneta
2
Concordou, não há prêmios por criatividade neste envio. Nem para compacidade: a submissão Pyth tem menos da metade do comprimento. Os problemas tornam-se desafiadores para idiomas como o Mathematica, quando podem ser reformulados como instâncias de fenômenos mais gerais e quando combinações incomuns de funções de alto nível podem desempenhar um papel. Eles também se tornam mais interessantes.
DavidC
3

Java - 183 177 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;}

Ungolfed

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
fonte
Esta resposta é inválida. p(32,2)retorna 5quando deveria retornar 2( 4^2 + 4^2 = 32).
PurkkaKoodari
@ Pietu1998 Ok, eu vou modificá-lo.
Yassin Hajaj
@ Pietu1998 Como você faria isso?
Yassin Hajaj
Fiz isso recursivamente, verificando cada potência possível para cada número.
PurkkaKoodari
1
@YassinHajaj +1 para java e fazê-lo sozinho
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)

Recursivamente tenta subtrair cada penésima potência que deixa o restante não negativo, calculando seu valor em cada restante e assumindo o mínimo mais 1. No 0, sai 0.

A verificação feia if n/k**p(equivalente a if k**p<=n) é impedir que a função entre nos negativos e tente tirar a minlista vazia. Se o Python tiver min([])=infinity, isso não seria necessário.

xnor
fonte
Uau. Isso é muito mais curto que o meu código de teste no 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;}

Experimente online!

Jonathan Frech
fonte