It absolutely is an increasing sequence. The kata defined 0 as coming after 9 for increasing sequences. The 1 in the end can be safely ignored because a number was defined to have at least three characters

nah you'r right @VecZz that would throw a DividedByZeroException.

The kata explicitely says the idea is not to sort it... Why is this considered best solution?

nice solution, I just dislike how you've written the IsPrime function. The if that everything is wrapped in could easily be replaced with another guard clause. You did use guards so you seem to know that guards are prefered when using ifs.
how about if input is 2 return true, if input is 1 return false? so that catches the only edge cases I have in mind right now with a nice guard clause and then you can keep your approach without nesting everything into an if check.

I wonder why choosing why choosing a List of tuples over a regular Dictionary?

"this" keyword is not needed here. Only if you have same spelling on param and property but you have one starting with capital letter and one starting with non-capital letter