Reverse Greedy Issue

[Juggler_IN]

I need help with the following logic ---
Let N/QR be a fraction in lowest terms with Q > 1 and GCD(Q,R) = 1, and let x,y be the smallest positive solution of Nx - Qy = R. Then 1/Qx is a term in the expansion, with remainder y/Rx. Expand this remainder and iterate until reaching a unit fraction remainder.

Take the fraction 31/311. Here we have N = 31, Q = 311, R = 1. (Notice that the denominator QR = 311, and we require Q > 1 and also that Q,R must have no common factor. Therefore, we set Q = 311 and R = 1.) So for this first round, we need the smallest integer solution of 31x - 311y = 1. It’s easy to see by trial and error that the smallest solution is x = 301, y = 30. Therefore, the first term in our expansion is 1/Qx = 1/[(311)(301)] = 1/93611, with the remainder y/Rx = 30/[(1)(301)]. That is: 31/311 = 1/93611 + 30/301.

If we apply the same procedure to 30/301, we should get: 30/301 = 1/688 + 11/112.

With n=31, d=311, my code gives ReverseGreedy(31,311) = 1/93611 + 30/301 (Correct). But with n=30, d=301, my code gives ReverseGreedy(30,301) = 1/87591 + 29/291 (Incorrect); it should be 1/688 + 11/112.

How?

Function ReverseGreedy(n As Double, d As Double) As String
    
    Dim sUnit As String
    Dim x As Double, y As Double, q As Double
    Dim bFlag As Boolean

    sUnit = ""

    ' Smallest positive solution of Nx - Qy = 1.
    For x = 1 To d
        For y = 1 To n
            If (n * x - d * y) = 1 Then
                bFlag = True
                Exit For
            End If
        Next y
        If bFlag Then Exit For
    Next x

    q = d * x

    sUnit = "1/" & q & " + " & y & "/" & x

    ReverseGreedy = sUnit

End Function

 

[StephenCrump]

Your code only allows for R=1. The first case works because 311 is prime, i.e. R = 1.

In the 30/301 case, Q=43 and R=7 (not 1). Lowest integer solution for x is 16, so first term of expansion is 1/Qx = 1/(43 x 16) = 1/688.

 

[Juggler_IN]

@StephenCrump; How do I adjust the code ... attaching a function for Prime factors.

Function PrimeF(n As Long) As Variant

    Dim r As String
    Dim f As Long, i As Long
    Dim a As Variant

    i = 0
    ReDim a(0&)
    f = 2

    r = ""

    Do While n > 1
        If n Mod f = 0 Then
            r = r & f & ", "
            n = n / f
            a(i) = f
            i = i + 1
            ReDim Preserve a(0 To i)
        Else
            f = f + 1
        End If
    Loop

    If Len(r) > 0 Then r = Left(r, Len(r) - 2)

    ReDim Preserve a(0 To i - 1)

    PrimeF = a

End Function