# Output nth term in Catalan type sequence

Given a number, starting with 1, create new numbers (children) by taking the last digit, n, and concatenating 1 through n+1.

This seems to be a much better explanation of the sequence A071159.

Integers whose decimal expansion start with 1, do not contain zeros and each successive digit to the right is at most one greater than the previous.

1, 11, 12, 111, 112, 121, 122, 123, 1111, 1112, 1121, 1122, 1123, 1211, 1212, 1221, 1222, 1223, 1231, 1232, 1233, 1234, 11111, 11112, ...

Personally I find the description for the sequence rather unhelpful, and find it is easier to understand with a graph.

                              1
11-------------------------------------12
111----112                     121---------122----------123
1111-1112    1121-1122-1123    1211-1212    1221-1222-1223    1231-1232-1233-1234


I find the graph rather interesting as it is very self-repeating. For instance, the left-most node on a branch is always identical to the root node. Might be easier to see on this graph.

# Challenge

Submit a solution that can output the nth item of sequence A071159.

# Rules

Your submission should be able to calculate any item before number 23713. A071159(23713) is the first time a 10 would appear as a single digit (12345678910; comma-separated 1,2,3,4,5,6,7,8,9,10).

• What about 1213? Jul 16 '14 at 16:29
• @Ypnypn Doesn't exist. Jul 16 '14 at 17:01
• @TheRare Which means the two sequences (normalizing sequence and A071159) are not equivalent and the task therefore does not match its description. Jul 16 '14 at 17:11
• @tolos Can you please clarify which of the two sequences you want to have? Until then I am voting to close as "unclear what you are asking". Jul 16 '14 at 17:20
• Btw. the variable normalizing sequence seems to be A193023. Jul 16 '14 at 17:21

## GolfScript (29 chars)

~([1]{.{.10*)\10%{.)}*}%|}9*=


This is a pretty naïve implementation, although reasonably fast.

~(         # Evaluate input, decrement to get a 0-based index
[1]        # Initial row of tree
{          # Loop: stack is the first n rows of the tree as an array
.        # Duplicate the array
{        # Map: extend each element of the array into its children
.10*)  # Get the first child; stack is   rows x 10x+1
\10%   # How many more children does x have?
{.)}*  # Those children are found by successive incrementation
}%       # End map
|        # Add the new unique elements (i.e. the new bottom row) to the rows
}9*        # Repeat 9 times, so that the array has 23713 correct values and one incorrect
=          # Array lookup


# Python 2 (83) (86)

r=[1]
exec"r=[1]+[i+w*10for w in r for i in range(1,w%10+2)];"*9
print r[input()-1]


Explanation to come.

A completely different approach of counting up an testing for membership in the sequence (87 chars). Take ridiculously long for larger numbers,

n=0
k=input()
while k:n+=1;k-=all(0<int(b)<2+int(a)for a,b in zip('0'+n,n))
print n


# JAVA (146)

I know I'm not winning this, but oh well:

public class a{public static void main(String[]a){float b=Float.parseFloat(a[0]);float c=1;for(int i=2;i<=b;i++)c*=(i+b)/i;System.out.print(c);}}


Just straightforward from Wikipedia, any tips for further golfing this will be appreciated.

• you ca save a char by turning for(int i=2;i<=b;i++)c*=(i+b)/i into for(int i=2;i<=b;)c*=(i+b)/i++ Jul 16 '14 at 18:17
• Oops, just noticed that I'm calculating the Nth catalan number which is not what was asked, I'll be updating this as soon as I have the answer. Jul 16 '14 at 20:52

## Powershell (136)

$n=Read-Host;$x=,'1';$a=1;While($x.length-lt$n){$b=[int]$x[$a-1].Substring($x[$a-1].length-1);1..($b+1)|%{$x+=$x[$a-1]+$_};$a++}$x[$n-1]


Probably some wasted characters here, but I'm still learning. $a traverses the list as it's being built (each level of the tree).$b takes the last digit of the current item, then the loop after that adds on 1 to $b+1 to the end of the current item and adds it to the array$x.

Loop is a bit inefficient, as the \$n-1 index is necessary because it doesn't always stop on the nth number of the sequence that you want.

But hey, it's my first draft. And it replicated the correct sequence output based on the input here.

Also an input of 23713 produces an output of 12345678910.

• It's funny how I tend to find Powershell to be the most obfuscated language. Jul 16 '14 at 19:24
• @TheRare Yeah, when it's done really well (aka not by me) Powershell can be really freaking confusing to look at from the outside. Still got nothin' on Brainfuck or Golfscript or stuff like that... Jul 17 '14 at 20:10
• Honestly, I find both of those cleaner. Jul 17 '14 at 20:17

c=1:((\n->[10*n+d|d<-[1..nmod10+1]])=<<)c;main=readLn>>=print.((0:c)!!)


And ungolfed:

step n = [ 10*n + d | d <- [1 .. lastDigit+1] ]
where lastDigit = n mod 10

soln = 1 : concatMap step soln

main = do
let nthTerm = soln !! (n - 1)
print nthTerm


soln is a list containing the entire A071159 sequence.

The step function is not very interesting, just a straightforward list comprehension that takes a number to the list of its children in the OP's tree.

The main function's only trick is to do 1-based indexing of [1,11,12,...] by using 0-based indexing on [0,1,11,12,...], saving a character.

The real fun is in the recursive definition of soln, which does the breadth-first traversal of the OP's tree. A couple characters are saved by replacing concatMap with its generalization =<<.

• save three characters: c=1: instead of c=[1]++ Jul 17 '14 at 6:56
• Thanks, @MtnViewMark! Don't know what happened there.. Jul 17 '14 at 12:25