Abstract
You need to represent a number as a non-negative linear combination of two positive integers?
You can achieve this with the (external link!) extended Euklidean Algorithm:
Note: If your desired result is a multiple of the greatest common divisor of the inputs then there will always be an integer solution, but not necessarily a non-negative one. Example: You can represent 1 with the inputs 5 and 3 because 1 is the GCD of 3 and 5: 1 = 2 * 5 + (-3) * 3. But you cannot achieve this with non-negative integers only.
Another note: There might be more than one non-negative integer solution, with bAllNonNegative = True the algorithm below will return a minimal sum of the output values. When there is an integer solution then there is a countable number of solutions.
Appendix – sbEuklid Code
Please read my Disclaimer.
Possible error returns of the program are:
- #NV! - There is no solution
- #VALUE! - bAllNonNegative = True but not all inputs are non-negative
- #NUM! - bAllNonNegative = True but there is no non-negative integer solution
Option Explicit
Function sbEuklid(lInput1 As Long, _
lInput2 As Long, _
Optional lDesiredResult As Long, _
Optional bAllNonNegative As Boolean = False) As Variant
'Extended Euklidean Algorithm which calculates two factors f1 and f2
'so that lDesiredResult = f1 * lInput1 + f2 * lInput2. If lDesiredResult
'is not given, the greatest common divisor (GCD) of lInput1 and lInput2
'will be calculated. If bAllNonNegative is True then we try to achieve a
'non-negative result of all inputs and outputs with minimal Sum(f1+f2).
'Error return values can be:
'xlErrNA - There is no solution
'xlErrValue - bAllNonNegative = True but not all inputs are non-negative
'xlErrNum - bAllNonNegative = True but there is no non-negative solution
'Source (EN): http://www.sulprobil.de/sbeuklid_en/
'Source (DE): http://www.berndplumhoff.de/sbeuklid_de/
'(C) (P) by Bernd Plumhoff 20-May-2024 PB V0.4
Dim lDiv As Long
Dim lGCD As Long
Dim lRest As Long
Dim lT1 As Long
Dim lT2 As Long
Dim vR As Variant
Dim vT As Variant
With Application '.WorksheetFunction 'Test with, release without
lGCD = .Gcd(lInput1, lInput2)
If IsMissing(lDesiredResult) Then lDesiredResult = lGCD
lRest = lDesiredResult Mod lGCD
If lRest <> 0 Then
sbEuklid = CVErr(xlErrNA) 'There is no solution
Else
If bAllNonNegative And (lInput1 < 0 Or lInput2 < 0 Or lDesiredResult < 0) Then
sbEuklid = CVErr(xlErrValue) 'bAllNonNegative but not all inputs are non-negative
Else
'See https://www.arndt-bruenner.de/mathe/scripts/erweitertereuklid.htm
vR = [{1, 0; 0, 1}]
vT = [{0, 1; 1, 0}]
lT1 = lInput1
lT2 = lInput2
Do
lDiv = lT1 \ lT2
lRest = lT1 Mod lT2
lT1 = lT2
lT2 = lRest
vT(2, 2) = -lDiv
vR = .MMult(vR, vT)
Loop While lRest <> 0
vR = .MMult(Array(lDesiredResult \ lGCD, 0), .Transpose(vR))
Debug.Assert lDesiredResult = vR(1) * lInput1 + vR(2) * lInput2 'Just assuring
sbEuklid = vR
If bAllNonNegative Then
If lInput1 > lInput2 Then
lT1 = lDesiredResult \ lInput1 + 1
Do While lT1 > 0
lT1 = lT1 - 1
If (lDesiredResult - lInput1 * lT1) Mod lInput2 = 0 Then GoTo Success1
Loop
GoTo ErrorExit
Success1: vR(1) = lT1
vR(2) = (lDesiredResult - lInput1 * lT1) \ lInput2
Else
lT2 = lDesiredResult \ lInput2 + 1
Do While lT2 > 0
lT2 = lT2 - 1
If (lDesiredResult - lInput2 * lT2) Mod lInput1 = 0 Then GoTo Success2
Loop
GoTo ErrorExit
Success2: vR(2) = lT2
vR(1) = (lDesiredResult - lInput2 * lT2) \ lInput1
End If
sbEuklid = vR
End If
End If
End If
'Debug.Assert lDesiredResult = vR(1) * lInput1 + vR(2) * lInput2 'Just testing
Exit Function
ErrorExit:
sbEuklid = CVErr(xlErrNum)
End With
End Function
Download
Please read my Disclaimer.
sbEuklid.xlsm [25 KB Excel file, open and use at your own risk]