2
$\begingroup$

I'm doing a challenge and it has posed a problem I am unfamiliar with. It goes like this, You start with two numbers, 1 and 1. You can combine the numbers in either direction, in this case makes 2,1 and 1,2 or in the case of 3,2 it would produce 5,2 or 3,5. Always starting from 1,1 my challenge is to try to find a pair of numbers in as few "moves" as possible.

My first pass was to build a greedy-first SSS* like algorithm. Works well for a small space but in the end takes too long on large inputs. So I think I have to massively narrow the search. Or I'm sure someone has seen this before and has come up with a clever workaround.

Any help is appreciated

$\endgroup$
1
$\begingroup$

You have discovered the Calkin–Wilf tree, which is the game tree of your game. There is a unique way to reach any pair of coprime positive integers. Given a pair of coprime positive integers, repeatedly subtract the smaller one from the larger one, and you will eventually reach $(1,1)$. Reversing your moves, you obtain the unique way to generate the given (ordered) pair.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.