How many squares, cubes, fourth powers, etc. do I need to sum to n? You are given a nonnegative integer n and an integer p &gt;= 2. You need to add some p-th powers (p=2 means squares, p=3 means cubes) together to get n. This is always for any nonnegative n, but you don't know many p-th powers (of any positive integer) you'll need.

This is your task: find the minimum number of p-th powers that can sum to n.

Examples

&gt;&gt;&gt; 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
&gt;&gt;&gt; min_powers(4, 2)
1                       # you need at least one square to add to 4
                        # Example: (2)^2 = 4
&gt;&gt;&gt; min_powers(7, 3)
7                       # you need at least seven cubes to add to 7
                        # Example: 7*(1)^3 = 7
&gt;&gt;&gt; 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


A related Wikipedia article on this problem, Waring's problem.

Rules


Your code must be a program or a function.
Input is two integers n and p in any order. You can assume all inputs are valid (n is any positive integer, p &gt;= 2
Output is an integer representing the number of powers needed to sum to n.
This is code golf, so the shortest program wins., not necessarily the most efficient.
Any and all built-ins are allowed.


As always, if the problem is unclear, please let me know. Good luck and good golfing!
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)&amp;


Test Cases
(k = 0; While[PowersRepresentations[#, ++k, #2] == {}]; k) &amp;[7, 2]
(k = 0; While[PowersRepresentations[#, ++k, #2] == {}]; k) &amp;[4, 2]
(k = 0; While[PowersRepresentations[#, ++k, #2] == {}]; k) &amp;[7, 3]
(k = 0; While[PowersRepresentations[#, ++k, #2] == {}]; k) &amp;[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