Help with finding numbers to the alpha power that sum to n.

[idknuttin]

I am trying to solve this homework question and I think I solved it because it looks like my program works, so I am asking for help to see if there is a way to make my code run faster or if I should take a different approach to solving this problem.

Problem: For given n and alpha, determine the smallest number k for which n can be expressed as a sum of k numbers each of which is a perfect alpha-th power.

Just to make sure I understand the problem, if the user enters 34 for n and 2 for alpha, then k would be 2 because the smallest way we can represent 34 as a sum of numbers that are perfect squares is 25+9.

My idea was to create a sequence of numbers that consists of n integers and using recursion fill every sequence with perfect alpha powers and then checking to see if any of them sum to n, if they do replace k with the total of numbers in the sequence if the total is less then k, this should give me the smallest number k, but I am trying to think of a smarter way of doing this because this is using up way too much memory for no reason if n is even a double digit number. It also takes the program a long time to create the sequences if n is large.

My code:

#include<iostream>
#include<cmath>

int k = 99999;

void check(const int &N, const int &A, int *pSeq, int position){
  int sum=0;
  int total=0;
  for(int i=0; i<N; ++i){
    sum+=pSeq[i];
    if(pSeq[i]>0){
      ++total;
    }
  }
  if(sum==N){
    if(total < k){
      k=total;
    }
  }
  if(sum<N){
    if(position < N){
      for(int i=0; pow(i, A)<N+1; ++i){
        pSeq[position]=pow(i, A);
        check(N, A, pSeq, position+1);
      }
    }
  }
}

int main(){
  int n, a;
  std::cout<<"Enter n and a: ";
  std::cin>>n >>a;
  int *sequence=new int[n];
  for(int i=0; i<n; ++i){
    sequence[i]=0;
  }

  check(n, a, sequence, 0);
  
  std::cout<<"k=" <<k <<std::endl;

  return 0;
}

There's something wrong with the function that creates the sequences, i don't know why it doesn't create all possible sequences, for example I enter 5 for n and 2 for alpha then the program tells me k=2 which is correct because 4+1, if I enter 6 for n and 3 for alpha the program tells can't find the sequence, but 4+1+1 would work. It should always be able to find a sequence because the worst case scenario is for example n=5 and alpha=4, then k=5 because 1+1+1+1+1=5, that's the best you can do.

[Dj42]

Okay, so I'm not sure about the program itself, but 4+1+1 wouldn't work for n = 6. The answer for 6 would be 6, since 2^3 = 8>6, so it would need to be 1^3 + 1^3... 6 times

[Dj42]

Also, I noticed that when I enter a sequence that should make k = n, it never changes k, so k stays as 99999. I think the following code fixes that bug.

#include<iostream>
#include<cmath>


void check(const int &N, const int &A, int *pSeq, int position, int &k){
int sum=0;
int total=0;
for(int i=0; i<N; ++i){
sum+=pSeq[i];
if(pSeq[i]>0){
++total;
}
}

if(sum==N){
if(total < k){
k=total;
}
}
if(sum<N){
if(position < N){
for(int i=0; pow(i, A)<N+1; ++i){
pSeq[position]=pow(i, A);
check(N, A, pSeq, position+1, k);
}
}
}
}

int main(){
int n, a;
std::cout<<"Enter n and a: ";
std::cin>>n >>a;
int k = n;
int *sequence=new int[n];
for(int i=0; i<n; ++i){
sequence[i]=0;
}

check(n, a, sequence, 0, k);

std::cout<<"k=" <<k <<std::endl;

return 0;
}