Imagine a straight river and a road that goes across the river n times through bridges. The road does not loop on itself and is infinitely long. This road would be considered an open meander. An open meander is an open curve, that does not intersect itself and extends infinitely at both ends, which intersects a line n times.
A valid meander may be described entirely by the order of the intersection points it visits.
The number of distinct patterns of intersection with n intersections a meander can be is the nth meandric number. For example, n = 4:
The first few numbers of this sequence are:
1, 1, 1, 2, 3, 8, 14, 42, 81, 262, 538, 1828, 3926, 13820, 30694, 110954...
This is OEIS sequence A005316.
Write a program/function that takes a positive integer n as input and prints the nth meandric number.
- Standard I/O rules apply.
- Standard loopholes are forbidden.
- Your solution can either be 0-indexed or 1-indexed but please specify which.
- This challenge is not about finding the shortest approach in all languages, rather, it is about finding the shortest approach in each language.
- Your code will be scored in bytes, usually in the encoding UTF-8, unless specified otherwise.
- Built-in functions that compute this sequence are allowed but including a solution that doesn't rely on a built-in is encouraged.
- Explanations, even for "practical" languages, are encouraged.
These are 0-indexed. Note that you need not handle numbers this big if your language cannot by default.
Input Output 1 1 2 1 11 1828 14 30694 21 73424650 24 1649008456 31 5969806669034
In a few better formats:
1 2 11 14 21 24 31 1, 2, 11, 14, 21, 24, 31