3
$\begingroup$

Consider the diophantine equation of the form $$a_1x_1+a_2x_2+\cdots +a_kx_k=n$$ where $n,k\geq 1$ and $a_i$ are non-negative integers. Then we are concerned $v(n)$ denote the number of solutions for a fixed tuple $(a_1,a_2,\cdots ,a_k).$ Can $v(n)$ be expressed recursively, that is, in terms of $v(n-1),v(n-2),$ etc?

I considered the following example to see if I could generalize $$x_1+2x_2 = n.$$ I noticed that if $(x_1,x_2)$ is a solution of $x_1+2x_2 = n-k$ then $(x_1+k,x_2)$ is a solution of $x_1+2x_2=n.$ Furthermore for $k=2p$ then if $x_1+2x_2 = n-k=n - 2p$ then $(x_1,x_2+p)$ is a solution of $x_1+2x_2=n.$ Therefore, $$v(n) = \sum_{k=1}^{n}v(n-k)+v(n-2)+v(n-4)+\cdots $$

Is this correct? How do I get a general formula for $v(n)?$ Any ideas will be much appreciated?

$\endgroup$
5
  • $\begingroup$ Are the $x_k$ to be any integers? (then infinitely many solutions can happen), or are the $x_k$ to be non-negative? $\endgroup$
    – coffeemath
    Commented Dec 29, 2018 at 22:27
  • 3
    $\begingroup$ $x_k$ are non-negative. $\endgroup$
    – Student
    Commented Dec 29, 2018 at 22:48
  • $\begingroup$ In your formula, in the sum part are many terms which coincide with the extra terms after the sum. Have you tried your formula in some cases of reasonably small $n$? It would be good to include them. [I assume the extra terms are restricted so no terms $v( \rm{negative})$ occur.] $\endgroup$
    – coffeemath
    Commented Dec 30, 2018 at 0:37
  • 1
    $\begingroup$ Yeah, I will try that. In the meantime I found this: nipne.ro/rjp/2013_58_9-10/1408_1417.pdf Refer to page 2. I think it is interesting. $\endgroup$
    – Student
    Commented Dec 30, 2018 at 0:48
  • $\begingroup$ Yes, that link of your comment seems to be to a proven recurrence. $\endgroup$
    – coffeemath
    Commented Dec 30, 2018 at 1:07

1 Answer 1

1
$\begingroup$

Let's denote with $v(k,n)$ the number of solutions of the following equation:

$$a_1x_1+a_2x_2+\cdots +a_kx_k=n$$

Take a look at the last item $x_k$. It can take any value from 0 to $\lfloor{\frac{n}{a_k}}\rfloor$. So we have the following recurrence relation:

$$v(k,n)=\sum_{i=0}^{\lfloor{\frac{n}{a_k}}\rfloor} v(k-1,n-i\cdot a_k)\tag{1}$$

...with the following exit criteria:

$$v(1,n)=\begin{cases} 1, & \text{if}\ a_1\mid n \\ 0, & \text{if}\ a_1\nmid n \end{cases}$$

Here is an example: let's count the number of solutions for the following equation:

$$x_1+2x_2+3x_3+2x_4+6x_5+2x_6=100$$

You can do this in Java:

public class SolutionCounter {
    public static int count(int[] a, int k, int n) {
        if(k == 1) {
            return (n % a[0] == 0)? 1: 0;
        }
        int cnt = 0;
        for(int i = 0; i <= n / a[k - 1]; i++) {
            cnt += count(a, k - 1, n - i * a[k - 1]);
        }
        return cnt;
    }

    public static void main(String[] args) {
        int[] a = {1,2,3,2,6,2};
        int sum = 100;
        int cnt = count(a, a.length, sum);
        System.out.println(cnt);
    }

}

or with this ridiculously short Python script:

def cnt(a, k, n):
    if k == 1:
        return 1 if n % a[0] == 0 else 0
    return sum(cnt(a, k - 1, n - i * a[k - 1]) for i in range(0, int(n / a[k - 1]) + 1))

print(cnt([1,2,3,2,6,2], 6, 100))

...and the result is: 847875.

$\endgroup$
4
  • $\begingroup$ Could you give a recurrence in terms of $n$? $\endgroup$
    – Student
    Commented Jan 2, 2019 at 9:31
  • $\begingroup$ (1) already gives recurrence formula for $v(n)$ in terms of $v(n-1)$, $v(n-2)$,... but you must also take values of $a_i$ into account. I doubt that simpler recurrence formula exists. $\endgroup$
    – Saša
    Commented Jan 2, 2019 at 10:54
  • $\begingroup$ Say you have $x_1+2x_2=n$ and the number of solutions to this is $v(n).$ Is there a way to express $v(n)$ in terms of $v(1),v(2),\cdots,v(n-1)?$ In your recurrence, it like you are conditioning on one variable and therefore getting rid of a term. Whereas I want to condition on $n$. I hope this makes sense? $\endgroup$
    – Student
    Commented Jan 2, 2019 at 11:00
  • $\begingroup$ @Hello_World Can you explain your request on the simplest possible example: $4x_1=n$. What is the recurrence formula for $v(n)$ in this simplest case? If we don't find a cute formula for one variable, chances are we won't find it for many more. $\endgroup$
    – Saša
    Commented Jan 2, 2019 at 11:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .