Write a script to generate sequence starting at

`1`

. Consider the increasing sequence of integers which contain only`1`

s,`2`

s, and`3`

s, and do not have any doublets of`1`

s > like below. Please accept a positive integer`$N`

and print the`$N`

th term in the generated sequence.1, 2, 3, 12, 13, 21, 22, 23, 31, 32, 33, 121, 122, 123, 131, ...

I could not think of a way to directly generate the \(N\)th number of the sequence.

But there is a straight forward way to, given a number in the sequence, generate the next number in the sequence.

Let the sequence be \(a_0, a_1, a_2, \ldots\). Let \(a_n\) be a number in the sequence, such that \(a_n = d_1 d_2 d_3 \ldots d_m c \overbrace{3 \ldots 3}^{k \text{ times}}, c \neq 3 \). That is, \(a_n\) consists of a possibly empty, sequence of digits \(d_i\) then a digit, \(c\), not equal to \(3\), followed by a, possibly empty, sequence of \(k\) \(3\)s. So, \(c\) is the last digit in \(a_n\) which is not a \(3\). If \(a_n\) consists of only \(3\)s, we can always prepend \(a_n\) with a \(0\), so, in that case, \(c = 0\).

We now first construct an intermediate number \(t = d_1 d_2 d_3 \ldots d_m (c + 1) \overbrace{1 \ldots 1}^{k \text{ times}}\).

Then we construct \(a_{n + 1}\) from \(t\) by replacing each non-overlapping \(11\) in \(t\) by \(12\). Note that the sequence \(d_i\) cannot contain the pattern \(11\); otherwise, \(a_n\) is not part of the sequence. Also, the only way for \(c + 1\) to be \(1\) is if the sequence \(d_i\) is empty (in that case, \(a_n\) consists of only \(3\)s).

With this in mind, it's easy to generate the generate the \(N\)th number: starting with \(0\), we apply the construction above \(N\) times.

In each of our implementations below, we start of with prepending a \(0\) to number. That way, we will always find a \(c\) as above. And we'll strip off a leading \(0\) when we're done.

First, the method which takes a number in the sequence, and return
the next number. It makes extensive use of the `/r`

modifier on
substitutions: this tells perl not to modify the string it's acting on,
but to return the modified string instead.

```
sub next_num ($prev_num) {
"0$prev_num" =~ s!([012])(3*)$!($1 + 1) . ($2 =~ s/3/1/rg)!re
=~ s!11!12!rg
=~ s!^0!!r
}
```

The pattern in the first substitution captures the last digit which
is not a `3`

, and any `3`

s following that. This is replaced with the
non-`3`

digit incremented by `1`

, and a string of `1`

s of the same
length as the string of `3`

. We do this by using the `/e`

modifier,
which tells Perl to execute the replacement part, and use the return
value as the replacement. Note that we use another substitution here —
with a modern enough Perl, the regexp engine is reentrant.

The second substitution simply replaces any `11`

with a `12`

— this
is the part which prevents a `1-1`

sequence.

The final substitution removes any leading `0`

which still may be there.

We can now calculate the `$N`

th element of the sequence, where
`$_`

contains `$N`

:

```
my $n = 0;
$n = next_num $n for 1 .. $_;
say $n;
```

Find the full program on GitHub.

AWK doesn't have capture groups (GNU AWK does though), so we have to
work a little bit harder. It does have `RSTART`

, which indicates the
position in the string where the match started , and `RLENGTH`

, which
indicates the length of the matched substring. Our `next_num`

function
then becomes:

```
function next_num (prev_num, tail) {
match (prev_num, /3*$/)
tail = substr (prev_num, RSTART)
```

Now `tail`

contains the trailing `3`

s of `prev_num`

(`tail`

may be the
empty string). We first replace the `3`

s with `1`

s:

```
gsub (/3/, 1, tail)
```

We now put `tail`

back into `prev_num`

, after incrementing the number
before the trailing `3`

s. If no such number exists (that is, `prev_number`

consists of just `3`

s) we just put a `1`

before `tail`

:

```
if (RLENGTH == length (prev_num)) {
prev_num = 1 tail
}
else {
prev_num = substr (prev_num, 1, RSTART - 2) \
(substr (prev_num, RSTART - 1, 1) + 1) \
tail
}
```

Now we just replace any `11`

with `12`

, and return the result.

```
gsub (/11/, "12", prev_num)
return prev_num
}
```

Find the full program on GitHub.

The Bash function to calculate the next number is surprisingly compact:

```
function next_number () {
[[ 0$1 =~ ^(.*)([012])(3*)$ ]]
next_num=${BASH_REMATCH[1]}$((BASH_REMATCH[2] + 1))${BASH_REMATCH[3]//3/1}
next_num=${next_num//11/12}
next_num=${next_num/0/}
}
```

The first line capturings any leading digits, then the last digit
which is not a `3`

, and the any trailing `3`

s. Capture groups are
availabe in the array `BASH_REMATCH`

.

A new number is constructed by concatenating the first part with
the second (incremented by one), and then the third, where each `3`

is replaced by a `1`

. The increment is done using the `$((EXPR))`

construct,
which evaluates `EXPR`

and substitutes its value. The replacement
is done by the `${word//pat/replacement}`

construct, which expands
`word`

, then replaces each occurance of `pat`

with `replacement`

.

Then, in the new number, we replace any `11`

with `12`

, and strip off
any remaining leading `0`

.

Find the full program on GitHub.

C doesn't have build in pattern matching, nor much of support for strings. We therefore have to do a lot of manual work. We will be assuming any answer will not require more than 32 digits.

With the input number (`$N`

) in the variable `num`

, we get:

```
# define BUF_SIZE 32
char number [BUF_SIZE + 1];
for (int i = 0; i < BUF_SIZE; i ++) {
number [i] = '0';
}
number [BUF_SIZE] = `\0`;
```

This initializes a NUL-terminated string `number`

of 32 `0`

s.

```
while (num --) {
for (i = BUF_SIZE - 1; i > 0 && number [i] == '3'; i --) {
number [i] = '1';
}
number [i] ++;
```

Set all trailing `3`

s to `1`

s, and increment the last digit which is
not a `3`

.

```
for (i = 0; i < BUF_SIZE - 1; i ++) {
if (number [i] == '1' && number [i + 1] == '1') {
number [i + 1] = '2';
}
}
```

This replaces any `11`

with `12`

.

Now we get to print the number, without any leading 0:

```
int i;
for (i = 0; i < BUF_SIZE && number [i] == '0'; i ++);
printf ("%s\n", number + i);
}
```

Find the full program on GitHub.

```
function next_number (prev_num)
local _, _, prefix, num, tail =
("0" .. prev_num) : find ("(.*)([012])(3*)$")
return (prefix .. tostring (tonumber (num) + 1)
.. tail : gsub ("3", "1")) : gsub ("11", "12")
: gsub ("^0", "")
end
```

We first split the given number (with a `0`

prepended) into
three groups: the numbers before the last digit which is not
a `3`

(`prefix`

), the last digit which is not a `3`

(`num`

),
and any trailing `3`

s (`tail`

).

We then concatenate `prefix`

with `num`

incrementated by `1`

(`tostring (tonumber (num) + 1)`

), and `tail`

with all
`3`

s replaced by `1`

(`tail : gsub ("3", "1")`

).

In the concatenated number, we replace each `11`

with `12`

(`gsub ("11", "12")`

), and remove any leading `0`

(`gsub ("^0", "")`

).

Find the full program on GitHub.

The Node.js solution is very similar to the Lua solution:

```
function next_number (prev_number) {
let [match, prefix, num, tail] =
("0" + prev_number) . match (/^(.*)([012])(3*)$/)
return (prefix + (+ num + 1) + (tail . replace (/3/g, "1"))) .
replace (/11/g, "12") .
replace (/^0/, "")
}
```

Find the full program on GitHub.

In Python, a regular expression match returns a match object. Which we can query for its capture groups.

```
def next_num (prev_num):
match = re . match ('^(.*)([012])(3*)$', "0" + prev_num)
return (re . sub ('^0', '', \
re . sub ('11', '12', match . group (1) + \
str (int (match . group (2)) + 1) + \
re . sub ('3', '1', match . group (3)))))
```

Find the full program on GitHub.

Captures in Ruby are also available in match object — but we can index this as an array to get the capture groups. But it's still the same algorithm:

```
def next_num (prev_num)
("0" + prev_num) . match (/^(.*)([012])(3*)$/) do
|match|
return (match [1] + (1 + match [2] . to_i) . to_s +
match [3] . gsub(/3/, "1")) . gsub(/11/, "12") . gsub(/^0/, "")
end
end
```

Find the full program on GitHub.