use bigint;

$| = 1;

sub forward {
	my $base = shift;
	my $prev = shift;
	my $sum = shift;

	my $carry = 1;

	my $next = 0;
	my $rank = 0;
	while ($prev or $sum or $carry) {
		my $dprev = $prev % $base;
		my $dsum  = $sum  % $base;

		if ($dprev + $dsum + $carry < $base) {
			$next += ($dprev + $carry) * $base**$rank;
			$carry = 0;
		} else {
			$next = 0;
			$carry = 1;
		}

		$prev = ($prev - $dprev) / $base;
		$sum  = ($sum  - $dsum ) / $base;

		$rank++;
	}

	return $next;
}

sub tobase {
	my $base = shift;
	my $n = shift;
	my @d = ();

	do {
		my $d = $n % $base;
		@d = ($d => @d);
		$n = ($n - $d)/$base;
	} while ($n);

	return @d;
}

sub simplify {
	my $base = shift;
	my $a = shift;
	my $sum = shift;

	while (($a % $base)==0 && (($sum % $base)==($base-1))) {
		$a = $a / $base;
		$sum = ($sum-$base+1) / $base;
	}

	return "$a-$sum";
}

sub search {
	my $base = shift;

	my @values = ();

	my $a = 0;
	my $sum = 0;

	my %seen = ();
	for (my $n=1;; $n++) {
		$a = forward($base, $a, $sum);
		$sum += $a;

		push @values => [$a, $sum];

		my $key = simplify($base, $a, $sum);

		if (exists $seen{$key}) {
			return ($n - $seen{$key} => @values);
		} else {
			$seen{$key} = $n;
		}
	}
}

print "<pre>\n";
print "<h1>A278743</h1>\n";

print "<table border=1 cellspacing=0 cellpadding=4>\n";

print "<tr bgcolor=lightgrey><th>n</th><th bgcolor=PaleTurquoise>a(n)</th><th bgcolor=PeachPuff>k<sub>0</sub></th><th>b</th><th>c<sub>n</sub></th></tr>\n";

foreach my $base (2..42) {
	print STDERR "At base $base...\n";

	my ($a, @values) = search($base);

	print "<tr>\n";
	
	print "<td align=right valign=top>$base</td>\n";
	print "<td align=right valign=top>$a</td>\n";

	my $k0 = $#values-$a;
	print "<td align=right valign=top>$k0</td>\n";

	my $b = scalar(tobase($base, $values[$#values][0]/$values[$#values-$a][0]))-1;

	print "<td align=right valign=top>$b</td>\n";

	print "<td>";

	print "<table border=1 cellspacing=0 cellpadding=2>\n";

	print "<tr bgcolor=lightgrey>\n";
	print "<th rowspan=2>k</th><th rowspan=2>c<sub>$base</sub>(k)</th><th colspan=2>In base $base</th>";
	print "</tr>\n";
	print "<tr bgcolor=lightgrey>\n";
	print "<th>c<sub>$base</sub>(k)</th></th><th>Partial sum</th>";
	print "</tr>\n";

	foreach my $k (0..$#values) {
		my $c = $values[$k][0];
		my $sum = $values[$k][1];

		my $bgcolor;
		if ($k==$#values) {
			$bgcolor = "white";
		} elsif ($k < $#values-$a) {
			$bgcolor = "peachpuff";
		} else {
			$bgcolor = "PaleTurquoise";
		}

		print "<tr bgcolor=$bgcolor>";
		print "<td align=right>", $k+1, "</td>\n";
		print "<td align=right>$c</td>\n";

		my @c = tobase($base, $c);
		my @sum = tobase($base, $sum);

		my $skipped = 0;
		while (@c && @sum && ($c[$#c]%$base)==0 && ($sum[$#sum]%$base)==($base-1)) {
			$c = $c / $base;
			$sum = ($sum - $base + 1)/$base;

			pop @c;
			pop @sum;

			$skipped++;
		}

		print "<td align=right>";
		print join($base <=10 ? "" : "<sub>,</sub>" => (map {"<b>$_</b>" } @c), ("<span style='color: gray'>0</span>") x $skipped);
		print "</td>\n";

		print "<td align=right>";
		print join($base <=10 ? "" : "<sub>,</sub>" => (map {"<b>$_</b>" } @sum), ( ("<span style='color: gray'>" . ($base-1) . "</span>") ) x $skipped);
		print "</td>\n";

		print "</tr>";
	}

	print "</table>\n";

	print "</td>";

	print "</tr>\n";
}

print "</table>\n";

print "</pre>\n";