Is there a way to generate a sequence that includes squares which sum up to an integer square?

user_13540217 0
Viewed 190

decompose(11) must return [1,2,4,10]. Note that there are actually two ways to decompose 11², 11² = 121 = 1 + 4 + 16 + 100 = 1² + 2² + 4² + 10².

For decompose(50) don't return [1, 1, 4, 9, 49] but [1, 3, 5, 8, 49] since [1, 1, 4, 9, 49] doesn't form a strictly increasing sequence.

I created a function but in only some cases provides a strictly increasing sequence all of my solutions add up to the correct number, what changes do i have to make to enable the return of a strictly increasing sequence?

vector<ll> Decomp::decompose(ll n){
    ll square = n * n, j = 1, nextterm = n - 1, remainder, sum = 0;
    float root;
    vector<ll> sequence;
    do
    {
        sequence.push_back(nextterm);
        sum = sum + (nextterm * nextterm);
        remainder = square - sum;
        root = sqrt(remainder - 1);
        if (root - (int)root > 0)
        {
            root = (int)root;
        }
        j = 1;
        nextterm = (int)root;
        if (remainder == 1)
        {
            sequence.push_back(1);
        }
    } while (root > 0);
    reverse(sequence.begin(),sequence.end());
    for (int i=0; i < sequence.size(); i++)
    {
        cout << sequence[i] << endl;
    }
}
algorithm c++
2 Answers

Here is a simple recursive approach, basically exploring all the possibilities.
It stops once a solution is found.

Output:

11 : 1 2 4 10
50 : 1 3 5 8 49

And the code:

#include    <iostream>
#include    <vector>
#include    <algorithm>
#include    <cmath>

bool decompose_dp (long long int sum, long long int k, std::vector<long long int> &seq) {
    
    while (k > 0) {
        long long int sump = sum - k*k;
        if (sump == 0) {
            seq.push_back(k);
            return true;
        }
        if (sump < 0) {
            k--;
            continue;
        }
        long long int kp = k-1;
        
        while (kp > 0) {
            if (decompose_dp(sump, kp, seq)) {
                seq.push_back(k);
                return true;
            }
            kp --;
        }
        k--;
    }
    return false;
}


std::vector<long long int> decompose(long long int n){
    long long int square = n * n, j = 1, nextterm = n - 1, remainder, sum = 0;
    float root;
    std::vector<long long int> sequence;
    
    auto check = decompose_dp (n*n, n-1, sequence);
    return sequence;
}

void pr (long long int n, const std::vector<long long int> &vec) {
    std::cout << n << " : ";
    for (auto k: vec) {
        std::cout << k << " ";
    }
    std::cout << "\n";
}

int main() {
    long long int n = 11;
    auto sequence = decompose (n);
    pr (n, sequence);
    n = 50;
    sequence = decompose (n);
    pr (n, sequence);
}
user_105533410

Here's BFS, DFS and brute force in Python. BFS seems slow for input 50. Brute force yielded 91020 different combinations for input 50.

from collections import deque

def bfs(n):
  target = n * n
  queue = deque([(target, [], 1)])
  while queue:
    t, seq, i = queue.popleft()
    if t == 0:
      return seq
    if (t == target and i*i < t) or (t != target and i*i <= t):
      queue.append((t - i*i, seq[:] + [i], i + 1))
      queue.append((t, seq, i + 1))

def dfs(n):
  target = n * n
  stack = [(target, [], 1)]
  while stack:
    t, seq, i = stack.pop()
    if t == 0:
      return seq
    if (t == target and i*i < t) or (t != target and i*i <= t):
      stack.append((t - i*i, seq[:] + [i], i + 1))
      stack.append((t, seq, i + 1))

def brute(n):
  target = n * n
  stack = [(target, [], 1)]
  result = []
  while stack:
    t, seq, i = stack.pop()
    if t == 0:
      result.append(seq)
    if (t == target and i*i < t) or (t != target and i*i <= t):
      stack.append((t - i*i, seq[:] + [i], i + 1))
      stack.append((t, seq, i + 1))
  return result

print bfs(50) # [1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20]
print dfs(50) # [30, 40]
#print brute(50)
user_20347870
Related