p/q in lowest terms is sent to a/b such that a*p = 1 mod (p + q) and a + b = p + q.
In other words, find p's multiplicative inverse in the ring of integers mod p + q (which must exist uniquely since p and q (and thus p and p + q) are relatively prime with p/q in lowest terms). Set the numerator to that value, and set the denominator such that the sum of the numerator and denominator is preserved.
p/q in lowest terms is sent to a/b such that a*p = 1 mod (p + q) and a + b = p + q.
In other words, find p's multiplicative inverse in the ring of integers mod p + q (which must exist uniquely since p and q (and thus p and p + q) are relatively prime with p/q in lowest terms). Set the numerator to that value, and set the denominator such that the sum of the numerator and denominator is preserved.
Spoiler: Response
This answer has no actual resemblance to how I'm actually implementing the function. I think it's possible that the the two methods are equivalent. Proving that they are seems to be quite the task. I'll get to working on it. PM me if you want my implementation.
implosion's answer was basically correct, though my implementation was dissimilar enough that only now can I prove the equivalence.
Spoiler: Explanation of my procedure and proof
What I did with a given input essentially was to find it on the Stern-Brocot tree, making note of the sequence of turns. I then reversed this sequence, and used that to traverse the tree to get the output.
To traverse the Stern-Brocot tree easily, you need to have a left and right 'ancestor' and their 'descendant', which is their mediant. It is possible to calculate the ancestors from the descendant, but it's much easier to just keep track of the ancestors. To go 'left' on the tree, the mediant of the left ancestor and the descendant becomes the new descendant, and the old descendant becomes the right ancestor. To go to the right the process is analogous.
By convention, the left ancestor is taken as smaller than the right. It is more convenient, however, for this proof to reverse this convention.
Since all iterated descendants of two given ancestors are between them, to capture all positive rationals we need to start with 1/0 as the left ancestor and 0/1 as the right ancestor. Also, it will be helpful to keep track of the numerators and denominators of the ancestors in matrix form(numerator on top). Thus the starting point of the tree is:
Note all the previous matrices have determinant 1, therefore so does the matrix of any path down the tree. Also, the elements of each path matrix are all integers.
The crux of the proof comes down to two lemmas.
Lemma 1:
From path matrix M get M' by path reversal. Then M' is the 'anti-transpose' on M where m'ij = m(n-j+1)(n-i+1), assuming 1-indexing.
This can be proven by induction.
Lemma 2:
Given a 2x2 matrix A, let s be the sum of all elements and ri, kj represent row and column sums respectively. The following equation holds:
rikj = aijs - det(A)*(-1^(ij))
This can be proven directly.
These two lemmas along with some facts we observed earlier, immediately imply that implosion's method is equivalent to to the path reversal method.
Posted: Fri Mar 04, 2022 10:30 am
by Jake The Wolfie
The hell is going on here
Posted: Fri Mar 04, 2022 4:13 pm
by StrangerCoug
I should probably come up with a good logic puzzle, come to think of it. Hmm...
Posted: Fri Mar 04, 2022 4:56 pm
by Jake The Wolfie
What lives in the woods, is brown, and is made of concrete?
Posted: Fri Mar 04, 2022 5:07 pm
by StrangerCoug
Here's an easy sudoku puzzle I created:
6
7
3
9
3
6
2
9
5
1
6
4
7
3
1
4
8
1
2
7
2
3
1
5
3
4
Edit:
Sudoku corrected; three of the numbers were one cell too far to the right.
If you prefer a little more of a challenge, I've got this sudoku, too:
1
8
5
9
5
8
3
8
1
9
2
9
6
6
5
3
7
1
6
4
1
9
1
8
4
Posted: Sun Mar 06, 2022 3:48 am
by StrangerCoug
Any takers for the Sudoku puzzles? I had a solution to the first one DM'd to me on Discord a couple nights ago, but I can't officially accept it unless and until it's posted here.
Or, if you want a harder puzzle than the one in #213, here is a Sudoku X puzzle. On top of the normal rules, each corner-to-corner diagonal must also contain each number from 1 to 9 exactly once.
Posted: Mon Mar 14, 2022 9:53 am
by Charles510
In post 213, StrangerCoug wrote:If you prefer a little more of a challenge, I've got this sudoku, too:
In post 217, StrangerCoug wrote:Or, if you want a harder puzzle than the one in #213, here is a Sudoku X puzzle. On top of the normal rules, each corner-to-corner diagonal must also contain each number from 1 to 9 exactly once.
This puzzle turns not to have a unique solution (not sure why SudokuWiki didn't catch this and gave it a grade anyway), so I'll give you two more clues from the intended solution:
Should still be plenty hard, though
