Solve Iterative Equation on Natural Numbers ?

[lvl107]

Hi, Everyone.
From the following:

How to Solve the Iterative Equation on Natural Numbers ?
Thanks in advance for your time and help.
Best Regards.
Loi.

[Werner_E]

Your definition seems not define series of numbers.

Its NOT defined what the NEXT pair (a1; b1) would be.

Is it (165; 238) or should it be (877; 1265) or would you rather like it to be (1589; 2292) ?

The general solution is a.1=165+k*712 and b.1=238+k*1027 with k being any integer.

If you settle for the smallest positive numbers, a first hack could be

Not much error checking or whatsoever and the 'math' method used is not Euklid or congruences but simple pure brute force 😉

[lvl107]

---

@Werner_E wrote:

Not much error checking or whatsoever and the 'math' method used is not Euklid or congruences but simple pure brute force 😉

  With big numbers then:

(Attach ***.xmcd please)

Best Regards.

Loi.

---

[Werner_E]

Interesting error message. No idea what it should mean and why it pops up.

Solution: Don't use too high numbers 🙂

[AlfredFlaßhaar]

Your result: a.1=165+k*712 and b.1=238+k*1027 does not solve the equation. There is -1 instead of 1. Where is my mistake?

[Werner_E]

---

@AlfredFlaßhaar wrote:

Your result: a.1=165+k*712 and b.1=238+k*1027 does not solve the equation.

---

It does ->  a0*b1 -b0*a1 = 712 * (238+k*1027) - 1027 * (165+k*712) = +1 

Why do you think that "there is -1" ??

[AlfredFlaßhaar]

Because:

(165 + k·712)·(238 + (k + 1)·1027) - (238 + k·1027)·(165 + (k + 1)·712) = -1

[Werner_E]

No wonder, if you use and mix up k an k+1.

I look to me that you did not understand the meaning of this general solution.

What you get by different values of k are just different solutions for (a1; b1).

Its just about (a0; b0) -> (a1;b1). Nothing more! And here a1 and b1 can be an infinite number of solutions, every value of k give another one. Thats the normal way to solve that kind of linear diophantic equation. The point was that ivl107 did not specify which of these infinite possible pairs of solutions he want to chose for (a1; b1) in his recursive defined series. I suggested to chose the smallest positive values and provided a (brute force) solution for his series for this choice.

Of course the formulas I mentioned will not give you the next pair (a2; b2) or any other pairs in this series. They are just the general solution for (a1; b1).

It sure is possible to give formulas for the whole series an and bn to avoid the brute force approach. This may also overcome the strange error ivl107 encountered  with my appraoch when he started the series with rather high numbers, who knows. It may be that you can arrive at the numbers in the series by using some kind of modified Euler algorithm. After all Eulers algorithm (similar to finding the  gcd of two numbers) can also be used to find the general solution of a linear diophantic equation.

I simply couldn't bring myself to put more effort into this number theory task and am happy to leave that to others. 😉

[AlfredFlaßhaar]

"The words have been exchanged enough". 😉
I must have misunderstood the task then. I assumed that the recursion is to apply to all n and that the sequences A_n and B_n are to be calculated using it, starting from the initial values A_0 and B_0. And that would be a higher difficulty because of non-linearity.

Many greetings!

[Werner_E]

I don't think that you had misunderstood the task given by ivl107 but you misunderstood that, what I called the general solution, was NOT the solution for the whole task but just for the first step of it. My goal was to show that the description of the task wasn't clear enough because the first step means solving a simple linear diophantic equation with an infinite number of solution. Before you go on to the second step you would have to decide which of these solution you want to use. The description of ivl107 did not provide a rule for this selection.

Once you settle for one of those solutions, the next step would again be solving another(!) linear diophantic equation, chosing one of its solutions, etc. etc. These steps sure could be automated and maybe even distilled into a simpler formula, but I didn't bother and solved the original task just by using brute force.

[Werner_E · Accepted solution]

While cleaning up I noticed that I forgot to post the solution using Euklids algorithm. So before the file is deleted, I post it here.

Here we have no problem with numbers too high, as it seems.