Otrzymujesz nieujemną liczbę całkowitą ni liczbę całkowitą p >= 2. Musisz dodać razem p-te moce ( p=2oznacza kwadraty, p=3oznacza sześciany), aby je zdobyć n. Dzieje się tak zawsze dla każdej nieujemnej n, ale nie znasz wielu ppotęg (jakiejkolwiek dodatniej liczby całkowitej), których potrzebujesz.

Oto twoje zadanie: znajdź minimalną liczbę p-tych mocy, które można sumować n.

Przykłady

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

Powiązany artykuł w Wikipedii na temat tego problemu, problemu Waringa .

Zasady

• Twój kod musi być programem lub funkcją.

• Wejście to dwie liczby całkowite ni pw dowolnej kolejności. Możesz założyć, że wszystkie dane wejściowe są prawidłowe ( ndowolna dodatnia liczba całkowita,p >= 2

• Dane wyjściowe to liczba całkowita reprezentująca liczbę potęg potrzebnych do sumowania n.

• To jest golf golfowy, więc wygrywa najkrótszy program , niekoniecznie najbardziej wydajny.

• Wszelkie wbudowane elementy są dozwolone.

Jak zawsze, jeśli problem jest niejasny, daj mi znać. Powodzenia i dobrej gry w golfa!

Pyth, 20 19 bajtów

Zaoszczędzono 1 bajt dzięki FryAmTheEggman.

L&bhSmhy-b^dQS@bQyE

Pobiera dane wejściowe w dwóch wierszach, pnajpierw, a następnie n.

Wypróbuj online. Zestaw testowy.

Wyjaśnienie

Kod definiuje funkcję rekurencyjną, y(b)która zwraca wynik 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

Mathematica 61 50 bajtów

Z 11 bajtami zapisanymi przez LegionMammal978.

Problem ograniczony do mocy liczenia liczb jest prosty (w matematyce). Po rozszerzeniu o moc liczb całkowitych jest to koszmar.

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

Przypadki testowe

(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]znajduje wszystkie przypadki, w których nmożna wyrazić jako sumę kliczb całkowitych dodatnich podniesionych do p-tej potęgi.

Na przykład,

PowersRepresentations[1729, 2, 3]

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

Kontrola,

1^3 + 12^3

1729

9^3 + 10^3

1729

Java - 183 177 bajtów

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 bajtów

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

Nie golfił

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

Wynik

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

Python 2, 66 bajtów

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

Rekurencyjnie próbuje odjąć każdą p-tą moc, która pozostawia resztę nieujemną, obliczając jej wartość na każdej pozostałej i przyjmując minimum plus 1. Przy 0, wyjścia 0.

Brzydka kontrola if n/k**p(odpowiednik if k**p<=n) polega na powstrzymaniu funkcji przed przejściem do przeczeń i próbą przejęcia minpustej listy. Jeśli Python tak min([])=infinity, nie byłoby to potrzebne.

C (gcc) , 122 bajty

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

Wypróbuj online!