Task — Sequence without 1-on-1

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 $Nth term in the generated sequence. 1, 2, 3, 12, 13, 21, 22, 23, 31, 32, 33, 121, 122, 123, 131, …

Examples

Example 1
Input: $N = 5
Output: 13
Input: $N = 10
Output: 32
Input: $N = 60
Output: 2223

Analysis

The simple way to do this is to loop over 1 to some large number and discard the values which contain digits other than 1, 2 or 3, or contain 11.

That works, but such numbers are quite sparse and on my computer finding the 1000th takes a second or so and the 2000th takes about 12 seconds. So a better algorithm is needed.

WThe better algorithm still loops $j up from 1, but whenever a number including a '4' in encountered the count is skipped forward as follows:

• Suppose the nummber is $b4$a, where $b and $a are strings of digits - possibly empty - before and after the 4.
• Add 1 to $b
• Change $a to a substring of '12121212...' the same length as $a
• Set $j to $b1$a
• Repeat until the number no longer contains a 4

How does that work? Suppose $j is 140. That is not a valid result because of the 4. So $b is 1 and $a is 0. Applying the rules above:

• $b becomes 2
• $a becomes 1
• $j becomes 211, which is the first number greater than 140 which comprises only 1s, 2s and 3s.

After all that, it is still necessary to reject numbers containing 11.

This algorithm finds the millionth qualifying number in under 10 seconds.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2021-06-28
use utf8;     # Week 119 - task 2 - Sequence without 1-on-1
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

sequence_without_1on1(5);
sequence_without_1on1(10);
sequence_without_1on1(60);
sequence_without_1on1(1000000);

sub sequence_without_1on1 {
    
    my ($n, $count, $j, $before, $after);
    
    # initialise
    $n = $_[0];
    say qq[\nInput:  $n];
    
    # count up to required number
    $count = 0;
    $j = 1;
    while (1) {
        
        # check for '4' and jump to next valid number
        while (1) { 
            last unless $j =~ m|^(.*)4(.*)$|;
            $before = $1 ? $1 : 0;
            $after = $2 ? $2 : 0;
            $after = substr('12121212121212', 0, length($2));
            $before += 1;
            $j = $before . '1' . $after;
        }
        
        # check for '11', else good result
        if ($j !~ m|11|) {
            $count ++;
            
            # found it
            if ($count == $n) {
                say qq[Output: $j];
                return;
            }
        }
        $j ++;
    }
}       

last updated 2026-03-16 — 20 lines of code

Output

Input:  5
Output: 13

Input:  10
Output: 32

Input:  60
Output: 2223

Input:  1000000
Output: 13122223122312