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.
Challenge
Write a program/function that takes a positive integer n as input and prints the nth meandric number.
Specifications
- 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.
Test cases
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
ᖘ
so the meandric numbers would be bigger.) \$\endgroup\$ – Not a tree Jul 21 '17 at 0:56