15
\$\begingroup\$

You are given a nonnegative integer n and an integer p >= 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

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

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

\$\endgroup\$
3
  • \$\begingroup\$ Well, it looks like brute force will win. I hope not though. \$\endgroup\$
    – lirtosiast
    Dec 1, 2015 at 18:29
  • 3
    \$\begingroup\$ This problem is incredibly hard, and I doubt that any answer will either ever finish while giving correct results. \$\endgroup\$
    – orlp
    Dec 1, 2015 at 19:41
  • \$\begingroup\$ At least have upper bounds \$\endgroup\$
    – qwr
    Dec 2, 2015 at 3:07

5 Answers 5

8
\$\begingroup\$

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

\$\endgroup\$
4
  • \$\begingroup\$ Competitively languages like Mathematica defeat the purpose of these things... it doesn't take any creativity to know a function name. But still, well written. \$\endgroup\$
    – csga5000
    Dec 2, 2015 at 3:41
  • 1
    \$\begingroup\$ @csga5000 Hey, golfing languages win 99% of the challenges on this site... \$\endgroup\$ Dec 2, 2015 at 11:40
  • \$\begingroup\$ @LegionMammal978 While I don't agree with csga's point, golfing things down in golfing languages requires a huge amount of creativity. \$\endgroup\$
    – Doorknob
    Dec 2, 2015 at 12:16
  • 2
    \$\begingroup\$ Agreed, no awards for creativity on this submission. Nor for compactness: the Pyth submission is less than half the length. Problems become challenging for languages like Mathematica when they can be recast as instances of more general phenomena and when unusual combinations of high-level functions can play a role. They also become more interesting. \$\endgroup\$
    – DavidC
    Dec 2, 2015 at 13:30
5
\$\begingroup\$

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
\$\endgroup\$
0
3
\$\begingroup\$

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
\$\endgroup\$
8
  • \$\begingroup\$ This answer is invalid. p(32,2) returns 5 when it should return 2 (4^2 + 4^2 = 32). \$\endgroup\$ Dec 1, 2015 at 22:44
  • \$\begingroup\$ @Pietu1998 Ok I'll modify it. \$\endgroup\$ Dec 1, 2015 at 22:47
  • \$\begingroup\$ @Pietu1998 How would you do it? \$\endgroup\$ Dec 1, 2015 at 22:54
  • \$\begingroup\$ I did it recursively, checking each possible power for every number. \$\endgroup\$ Dec 1, 2015 at 22:57
  • 1
    \$\begingroup\$ @YassinHajaj +1 for java and doing it yourself \$\endgroup\$
    – csga5000
    Dec 2, 2015 at 3:39
1
\$\begingroup\$

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)

Recursively tries subtracting each p-th power which leaves the remainder non-negative, computing its value on each remainder, and taking the minimum plus 1. On 0, outputs 0.

The ugly check if n/k**p (equivalent to if k**p<=n) is to stop the function from going into the negatives and trying to take the min of the empty list. If Python has min([])=infinity, this wouldn't be needed.

\$\endgroup\$
1
  • \$\begingroup\$ Wow. This is a lot shorter than my test code on Python. +1! \$\endgroup\$
    – Sherlock9
    Dec 3, 2015 at 15:14
0
\$\begingroup\$

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

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.