javaalgorithmmathpolynomial-math# Solving a Linear Diophantine Equation(see description for examples)

Let me start off by clarifying that(before you guys dismiss me), this is not a homework problem and I'm not a university student. :)

**EDIT**
Thanks to @Klas and others, my question now boils down to a mathematical equation which needs to be solved programmatically.

I'm looking for an algorithm/code which solves `Linear Diophantine Equation`

.
For lesser mortals like me, here's how such an equation looks like:

Example 1: `3x + 4y + 5z = 25`

(find all possible values of x,y,z)

Example 2: `10p + 5q + 6r + 11s = 224`

(find all possible values of p,q,r,s)

Example 3: `8p + 9q + 10r + 11s + 12t = 1012`

(find all possible values of p,q,r,s,t)

I tried googling to no avail. I would have thought that some code would already be written to solve this. Do let me know if you guys have come across some kind of library which has already implemented this. And if the solution is in Java, nothing can be cooler!. Algorithm/pseudo code will also do. Thanks much.

Solution

Brute-force recursion is an option, depending on how large you will allow the value or number of values to become.

Assumptions: The user inputs (the multiplicands) are always distinct positive integers. The coefficients to be found must be non-negative integers.

Algorithm:

```
Of the multiplicands, let M be the largest.
Calculate C=floor(F/M).
If F=M*C, output solution of the form (0,0,...,C) and decrement C
If M is the only multiplicand, terminate processing
Loop from C down to 0 (call that value i)
Let F' = F - i*M
Recursively invoke this algorithm:
The multiplicands will be the current set minus M
The goal value will be F'
For each solution output by the recursive call:
append i to the coefficient list and output the solution
```

- Maven (commandline): No compiler is provided in this environment
- Java Swing: display Text selectable
- How to make a query for mongodb using spring to return objects ordered alphabetically'
- cant update array contents java
- In Gradle, how can I generate a POM file with dynamic dependencies resolved to the actual version used?
- Why do we use @Embeddable In Hibernate
- IS there a way to configure ehcache 2 for spring boot 3?
- org.hibernate.mapping.Table.getColumn returns null
- Java Swing bars floating instead of starting from the same baseline
- How to find files that match a wildcard string in Java?
- java.lang.ClassCastException: oracle.sql.CLOB cannot be cast to oracle.sql.CLOB
- Update a Vertex after Retrieving it
- Read nested list with other attributes in Java streams
- Do you not need a password to access a truststore (made with the java keytool)?
- Creating new Instance of @Component each time FXMLLoader calls applicationContext.getBean(class)
- Add ' to particular place in String in Java
- ExecutionCompletionService hangs when used with Project loom
- How do you handle "impossible" exceptions in Java?
- Android navigation drawer, change text/hover color
- Fastest way to determine if an integer's square root is an integer
- Play WAV file backward
- EclipseLink and Derby with Java 19
- SpringBoot + AWS cognito, can't resolve issuerUri
- Is there a way to use a custom, arbitrary SQL query for loading an entity in Jmix?
- Fill an array with matches from a HashMap in Java
- Print retry count with @Retryable
- Actuator endpoints returning 500 error after upgrade to spring boot 3
- Bufferedimage resize
- What is the difference between ExecutorService.submit and ExecutorService.execute in this code in Java?
- Spring Boot - Process finished with exit code 0