How many squares, cubes, fourth powers, etc. do I need to sum to n?

Mathematica 61 50 bytes

With 11 bytes saved by LegionMammal978.

When restricted to powers of counting numbers, this problem is straightforward (in Mathematica). When extended to include powers of integers, it's a nightmare.

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

---

Test Cases

(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] finds all the cases in which n can be expressed as a sum of k positive integers raised to the p-th power.

---

For example,

PowersRepresentations[1729, 2, 3]

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

Checking,

1^3 + 12^3

1729

---

9^3 + 10^3

1729

Pyth, 20 19 bytes

Saved 1 byte thanks to FryAmTheEggman.

L&bhSmhy-b^dQS@bQyE

Takes input on two lines, p first and then n.

Try it online. Test suite.

Explanation

The code defines a recursive function y(b) that returns the result for 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

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

---

Result

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