Hash-counting string

You are given a positive integer $N.

Write a script to produce the hash-counting string of that length. The definition of a hash-counting string is as follows:

• the string consists only of digits 0-9 and hashes, ‘#’
• there are no two consecutive hashes: ‘##’ does not appear in your string
• the last character is a hash
• the number immediately preceding each hash (if it exists) is the position of that hash in the string, with the position being counted up from 1

It can be shown that for every positive integer N there is exactly one such length-N string.

Examples

Examples
'#' is the counting string of length 1
'2#' is the counting string of length 2
'#3#' is the string of length 3
'#3#5#7#10#' is the string of length 10
'2#4#6#8#11#14#' is the string of length 14

Analysis

This is an interesting challenge, and I thought it could be quite tricky until I realised that the sensible way to create the string is backwards from the end.

The string always ends with $N#, for example 25#. That is preceded with $M# where

$M = $N - length($N) - 1

So for the example of 25, it will be preceded by 22#, and this process repeats until the series ends with 2# or #3 (or just # if $N == 1).

The final string is always $N characters long, because - in the example - the # following 25 has to be the 25th character in the string.

The script copes with $N = 10000 in under a second on my machine.

Note that this is the only possible way to end with - in the example 25# - thus confirming the assertion made in the challenge definition that the representation is unique.

The following diagram illustrates how the strings are made up, with the final '#' always in the same column as row.

Try it 

#!/usr/bin/perl

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

use v5.26;    # The Weekly Challenge - 2021-03-01
use utf8;     # Week 102 - task 2 - Hash-counting string
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

for my $n (1, 2, 3, 4, 10, 50, 100, 1000) {
    hash_counting_string($n);
}

sub hash_counting_string {
    
    my ($n, $m, $string);
    
    # initialise
    $n = $m = $_[0];
    $string = '';
    
    # create string from end to start
    while ($m > 0) {
        $string = '#' . $string;
        $string = $m . $string if $m > 1;
        $m = $n - length($string);
    }

    say qq[\nInput:  $n];
    say qq[Output: $string];
}

10 lines of code
Completed after the closing date and not submitted to GitHub

Output

Input:  1
Output: #

Input:  2
Output: 2#

Input:  3
Output: #3#

Input:  4
Output: 2#4#

Input:  10
Output: #3#5#7#10#

Input:  50
Output: 2#4#6#8#11#14#17#20#23#26#29#32#35#38#41#44#47#50#

Input:  100
Output:
   #3#5#7#9#12#15#18#21#24#27#30#33#36#39#42#45#48#51#54#57#60#63#66#6
   9#72#75#78#81#84#87#90#93#96#100#

Input:  1000
Output:
   #3#5#7#9#12#15#18#21#24#27#30#33#36#39#42#45#48#51#54#57#60#63#66#6
   9#72#75#78#81#84#87#90#93#96#99#103#107#111#115#119#123#127#131#135
   #139#143#147#151#155#159#163#167#171#175#179#183#187#191#195#199#20
   3#207#211#215#219#223#227#231#235#239#243#247#251#255#259#263#267#2
   71#275#279#283#287#291#295#299#303#307#311#315#319#323#327#331#335#
   339#343#347#351#355#359#363#367#371#375#379#383#387#391#395#399#403
   #407#411#415#419#423#427#431#435#439#443#447#451#455#459#463#467#47
   1#475#479#483#487#491#495#499#503#507#511#515#519#523#527#531#535#5
   39#543#547#551#555#559#563#567#571#575#579#583#587#591#595#599#603#
   607#611#615#619#623#627#631#635#639#643#647#651#655#659#663#667#671
   #675#679#683#687#691#695#699#703#707#711#715#719#723#727#731#735#73
   9#743#747#751#755#759#763#767#771#775#779#783#787#791#795#799#803#8
   07#811#815#819#823#827#831#835#839#843#847#851#855#859#863#867#871#
   875#879#883#887#891#895#899#903#907#911#915#919#923#927#931#935#939
   #943#947#951#955#959#963#967#971#975#979#983#987#991#995#1000#