Wie viele Quadrate, Würfel, vierte Potenzen usw. muss ich mit n summieren?

14

Sie erhalten eine nichtnegative Ganzzahl nund eine Ganzzahl p >= 2. Sie müssen einige pPotenzen ( p=2bedeutet Quadrate, p=3bedeutet Würfel) addieren , um zu erhalten n. Dies gilt immer für alle nichtnegativen Potenzen n, Sie kennen jedoch nicht viele pPotenzen ( positive ganze Zahlen), die Sie benötigen.

Dies ist Ihre Aufgabe: Finden Sie die minimale Anzahl von pPotenzen, die sich summieren können n.

Beispiele

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

Ein verwandter Wikipedia-Artikel zu diesem Problem, Warings Problem .

Regeln

  • Ihr Code muss ein Programm oder eine Funktion sein.

  • Die Eingabe erfolgt in zwei Ganzzahlen nund pin beliebiger Reihenfolge. Sie können davon ausgehen, dass alle Eingaben gültig sind ( nist eine positive ganze Zahl,p >= 2

  • Die Ausgabe ist eine Ganzzahl, die die Anzahl der Potenzen angibt, die summiert werden müssen n.

  • Dies ist Codegolf, also gewinnt das kürzeste Programm , nicht unbedingt das effizienteste.

  • Alle eingebauten sind erlaubt.

Wie immer, wenn das Problem unklar ist, lassen Sie es mich bitte wissen. Viel Glück und gutes Golfen!

Sherlock9
quelle
Nun, es sieht so aus, als würde Brute Force gewinnen. Ich hoffe aber nicht.
Lirtosiast
3
Dieses Problem ist unglaublich schwer, und ich bezweifle, dass eine Antwort jemals beendet wird, während korrekte Ergebnisse geliefert werden.
Orlp
Zumindest obere Schranken haben
qwr

Antworten:

5

Pyth, 20 bis 19 Bytes

Gespeichert 1 Byte dank FryAmTheEggman.

L&bhSmhy-b^dQS@bQyE

Nimmt die Eingabe pzuerst und dann in zwei Zeilen vor n.

Probieren Sie es online aus. Testsuite.

Erläuterung

Der Code definiert eine rekursive Funktion y(b), die das Ergebnis für zurückgibt 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
quelle
8

Mathematica 61 50 Bytes

Mit 11 Bytes von LegionMammal978 gespeichert.

Wenn dieses Problem auf Potenzen zum Zählen von Zahlen beschränkt ist, ist es unkompliziert (in Mathematica). Wenn es um Potenzen von ganzen Zahlen erweitert wird, ist es ein Albtraum.

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

Testfälle

(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]findet alle Fälle , in denen nals eine Summe von ausgedrückt werden kzu der erhöhten positiven ganzen Zahlen p-te Leistung.


Beispielsweise,

PowersRepresentations[1729, 2, 3]

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

Überprüfung,

1^3 + 12^3

1729


9^3 + 10^3

1729

DavidC
quelle
Wettbewerbsfähige Sprachen wie Mathematica schlagen den Zweck dieser Dinge nieder ... es erfordert keine Kreativität, einen Funktionsnamen zu kennen. Trotzdem gut geschrieben.
csga5000
1
@ csga5000 Hey, Golfsprachen gewinnen 99% der Herausforderungen auf dieser Seite ...
LegionMammal978
@ LegionMammal978 Während ich mit CsgA des Punkt, Golf Dinge nach unten in Golf Sprachen erfordert nicht einverstanden riesige Menge an Kreativität.
Türklinke
2
Einverstanden, keine Auszeichnungen für Kreativität für diesen Beitrag. Auch nicht aus Gründen der Kompaktheit: Der Pyth-Beitrag ist weniger als halb so lang. Für Sprachen wie Mathematica werden Probleme zu einer Herausforderung, wenn sie als Beispiele allgemeinerer Phänomene neu formuliert werden können und wenn ungewöhnliche Kombinationen von Funktionen auf hoher Ebene eine Rolle spielen können. Sie werden auch interessanter.
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;
}

Ergebnis

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
quelle
Diese Antwort ist ungültig. p(32,2)Gibt zurück, 5wann es zurückkehren soll 2( 4^2 + 4^2 = 32).
PurkkaKoodari
@ Pietu1998 Ok, ich werde es ändern.
Yassin Hajaj
@ Pietu1998 Wie würdest du das machen?
Yassin Hajaj
Ich tat es rekursiv und überprüfte jede mögliche Energie für jede Zahl.
PurkkaKoodari
1
@ YassinHajaj +1 für Java und es selbst machen
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)

Versucht rekursiv, jeweils zu subtrahieren p Potenz zu , wodurch der Rest nicht negativ wird, berechnet seinen Wert für jeden Rest und nimmt das Minimum plus 1. Bei 0 wird 0 ausgegeben.

Die hässliche Prüfung if n/k**p(entspricht if k**p<=n) soll verhindern, dass die Funktion ins Negative geht und versucht, mindie leere Liste zu übernehmen. Wenn es Python gibt min([])=infinity, wird dies nicht benötigt.

xnor
quelle
Beeindruckend. Dies ist viel kürzer als mein Testcode auf 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;}

Probieren Sie es online!

Jonathan Frech
quelle