##### README
####
#####!/bin/sh
##### Main file created by:
#####./a171922.pl.txt 15137 >A171922
##### but can be lengthened by feeding the existing data back to itself:
#####./a171922.pl.txt 100 A171922 >A171922   # find 100 more elements
####
##### remove duplicates for [c_i]
####perl -nle 'print if !$seen{$_}++' A171922 >A171921
####
##### indices of a() at which a(k) = 2
####perl -nle 'print $. if $_ == 2' A171922 >A171925
####
##### indices of a() at which c_n first appears
####perl -nle 'print $. if !$seen{$_}++' A171922 >A171926
####
##### new records in a()
####perl -nle '$max=$_, print if $max < $_' A171922 >A171927
####
##### indices of a() at which new records occur
####perl -nle '$max=$_, print $. if $max < $_' A171922 >A171930
####
##### index of a() at which n first appears, or blank if not known:
#####   A171939(n) := min(k: A171922(k) = n)
####perl -nle '$a[$_]=$. if !$seen{$_}++; END { print $a[$_] for 1..200 }' A171922 >A171939
####
##### index of [c_i] at which n appears, or blank if not known
#####   A171940(n) := min(k: A171921(k) = n)
####perl -nle '$a[$_]=$. if !$seen{$_}++; END { print $a[$_] for 1..200 }' A171921 >A171940
####
####
##### END OF README


#!/opt/maths/bin/perl -w
use strict;
$| = 1;

#
# Given a(n-1) = k, assert min(m: a(n+m) = a(n)) = k. What is the lexically
# first sequence satisfying the definition *after* the simple a(i) = 1?
#

sub usage {
	print STDERR <<USAGE;
Usage: ./a171922.pl.txt <n> [ <file> ]
  find and print the next <n> values of A171922(); if <file> is specified,
read initial values from that file, else start from 1.
USAGE
	print STDERR "\n$_[0]" if @_;
}

my %fixed_val = (value => [], forward => [], backward => []);
my %fixed_vec = (value => '', forward => '', backward => '');
my %next_vec = %fixed_vec;

my $next_index = 1;
my @avail;
my $next_avail = 1;
init_trigger();

my $target = shift(@ARGV) || 1000;
init_from_file(shift @ARGV) if @ARGV;

VALUE: while (1) {
	# print any newly discovered values
	while (vec($fixed_vec{'value'}, $next_index, 1)) {
		print $fixed_val{'value'}[$next_index], "\n";
		exit(0) if --$target <= 0;
		++$next_index;
	}

	for (my $i = 0; 1; ++$i) {
		push @avail, $next_avail++ if $i >= $#avail;
		%next_vec = %fixed_vec;
		next_trigger();
		next unless try($next_index, $avail[$i]);
		fix_trigger();
		splice @avail, $i, 1;
		%fixed_vec = %next_vec;
		last;
	}
}
exit 0;

sub init_from_file {
	my $filename = shift;
	my %seen;
	my $max = 0;
	warn "importing from <$filename>\n";
	open my $fh, $filename or die "$filename: $!";
	while (my $line = <$fh>) {
		chomp $line;
		next unless $line;	# skip blank lines
		if (vec($fixed_vec{'value'}, $next_index, 1)) {
			my $expect = $fixed_val{'value'}[$next_index];
			die "mismatch in file: expected $expect got $line at $next_index\n"
					unless $expect == $line;
			++$next_index;
			next;
		}
		die "mismatch in file: repeated $line was not forced at $next_index\n"
				if $seen{$line}++;
		die "mismatch in file: a($next_index)=$line fails\n"
				unless try($next_index, $line);
		++$next_index;
		$max = $line if $max < $line;
	}
	@avail = grep !$seen{$_}, 1 .. $max;
	$next_avail = $max + 1;
	warn "importing ok\n";
}

{
	# not sure of an efficient way to do this
	my $fixed_trigger;
	my $next_trigger;
	sub init_trigger {
		$fixed_trigger = [];
	}
	sub next_trigger {
		$next_trigger = [ map [ @$_ ], @$fixed_trigger ];
	}
	sub fix_trigger {
		$fixed_trigger = $next_trigger;
		$next_trigger = undef;
	}
	sub test_trigger {
		my $t = shift;
		while (vec($next_vec{'value'}, $t->[0], 1)) {
			my $skip = $fixed_val{'value'}[$t->[0]];
			$t->[0] += $skip;
			$t->[1] -= $skip;
			last if $t->[1] <= 0;
		}
		return $t;
	}
	sub check_triggers {
		my $index = shift;
		for (my $i = $#$next_trigger; $i >= 0; --$i) {
			my $t = $next_trigger->[$i];
			next if $t->[0] != $index;
			test_trigger($t);
			next if $t->[1] > 0;
			return 0 if $t->[1] == 0;
			splice @$next_trigger, $i, 1;
		}
		return 1;
	}
	sub new_trigger {
		my $t = test_trigger([ @_ ]);
		return 0 if $t->[1] == 0;
		push @$next_trigger, $t if $t->[1] > 0;
		return 1;
	}
}

sub try {
	my($index, $value) = @_;
	my @pend;
	push @pend, [ 'value', $index, $value ];
	while (@pend) {
		my($type, $index, $value) = @{ shift @pend };
#warn "try with: <$type $index $value>\n";
#warn("... failed\n"),
		return 0 if vec($next_vec{$type}, $index, 1);
		vec($next_vec{$type}, $index, 1) = 1;
		$fixed_val{$type}[$index] = $value;
		if ($type eq 'value') {
#warn("... failed by existing trigger\n"),
			return 0 unless check_triggers($index);
			push @pend, [ 'forward', $index + 1, $index + 1 + $value ];
			push @pend, [ 'backward', $index + 1 + $value, $index + 1 ];
			if (vec($next_vec{'forward'}, $index, 1)) {
				push @pend, [ 'value', $fixed_val{'forward'}[$index], $value ];
			}
			if (!vec($next_vec{'value'}, $index - 1, 1)) {
#warn("... failed by new trigger\n"),
				return 0 unless new_trigger($index - 2, $value + 1);
			}
		} elsif ($type eq 'forward' && vec($next_vec{'value'}, $index, 1)) {
			push @pend, [ 'value', $fixed_val{'forward'}[$index],
					$fixed_val{'value'}[$index] ];
		}
	}
	# success: mark the stored values as valid
	%fixed_vec = %next_vec;
#warn("... success\n");
	return 1;
}

__END__