[seqfan] Re: Sum of a(n) first digits of S is a(n+1)

[hv at crypt.org]

"Eric Angelini" <Eric.Angelini at kntv.be> wrote:
:
:Hello SeqFans,
:
:... I couldn't get to sleep yesterday, 'cause I was
:trying to find more terms with my poor new 2010 brain...
:
:a) the sum of the a(n) first digits of S is a(n+1)
:b) always use the smallest available integer not leading
:   to a contradiction
:
:S = 4, 10, 50, 59, 98, 99, ...
:
:Could it be that no such S is infinite?
:
:Explanation:
:
: '4' says: "The first  4 digits of S sum up to 10" (--true)
:'10' says: "The first 10 digits of S sum up to 50" (--true)
:'50' says: "The first 50 digits of S sum up to 58" (--possible)
:'59' says: "The first 59 digits of S sum up to 98" (--possible)
:'98' says: "The first 98 digits of S sum up to 99" (--?)
:etc. (?)
:
:--> This start doesn't work:
:
:    S = 4, 10, 50, 58, 99, 900, ...

Assuming there is an additional rule that a(n+1) > a(n), I knocked up some
(very hacky) code to search for longer sequences, attached below.

Running it for half an hour, it gets as far as:
  4 10 50 68 89 91 100 110 120 210 1000 2000 10000 20000 100000 100010 100080 100313 102000
(and the initial seven terms were fixed after the first 10 seconds).

The code already takes account of the fact that a(n+1) <= 10 a(n) - 9 a(n-1),
but it would be much improved if it could see also the huge constraint here
that the 21 digits from #69 to #89 must sum to 2 (and therefore must be at
least 10-11 digit numbers), which implies that earlier numbers must increase
at around the maximum rate (ie 100, 200, 1000, 2000 etc).

You might also want to try this in some smaller bases - I suspect they would
make life rather easier.

Hugo
---
#!/usr/bin/perl -w
use strict;
$| = 1;
my @seq;		# the sequence so far
my @digits;		# cumulative number of digits
my @sod;		# cumulative sum of digits
for (my $start = 4; 1; ++$start) {
	$seq[0] = $start;
	$digits[0] = length($start);
	$sod[0] = sod($start);
	print "$start ";
	for (my $next = $start + 1; $next < $start * 9; ++$next) {
		$seq[1] = $next;
		$digits[1] = $digits[0] + length($next);
		$sod[1] = $sod[0] + sod($next);
		print "$next ";
		try(0, 2);
		clear($next);
	}
	print clear($start);
}

sub try {
	my($test, $index) = @_;
	my $known = $digits[$index - 1];
	my $known_sum = $sod[$index - 1];
	my $prev;
	for ($test .. $index - 2) {
		next if $seq[$_] <= $known;
		my $required = $seq[$_ + 1] - $known_sum;
		return if $required <= 0;
		my $space = $seq[$_] - $known;
		return if $space * 9 < $required;
		if ($prev) {
			$required -= $prev->[0];
			$space -= $prev->[1];
			return if $required < 0;
			return if $space * 9 < $required;
		}
		$prev = [ $required, $space ];
	}
	my $limit = 10 * $seq[$index - 1] - 9 * $seq[$index - 2] + 1;
	NEXT: for (my $next = $seq[$index - 1] + 1; $next < $limit; ++$next) {
		$seq[$index] = $next;
		$digits[$index] = $digits[$index - 1] + length($next);
		$sod[$index] = $sod[$index - 1] + sod($next);
		my $nexttest = $test;
		for ($test .. $index - 2) {
			if ($digits[$index] < $seq[$_]) {
				last if $sod[$index] < $seq[$_ + 1];
				my $length = length($next);
				my $max = $seq[$_ + 1] - $sod[$index - 1];
				++$next;
				++$next while $next < $limit && length($next) == $length
						&& sod($next) > $max;
				last NEXT if $next >= $limit;
				redo NEXT;
			}
			my $required = $seq[$_ + 1] - $sod[$index - 1];
			my $space = $seq[$_] - $digits[$index - 1];
			if (sod(substr($next, 0, $space)) != $required) {
				++$next;
				++$next while $next < $limit
						&& sod(substr($next, 0, $space)) != $required;
				last NEXT if $next >= $limit;
				redo NEXT;
			}
			++$nexttest;
		}
		print "$next ";
		try($nexttest, $index + 1);
		clear($next);
	}
}

sub sod {
	my $s = 0;
	$s += $_ for split //, $_[0];
	$s;
}

sub clear {
	print "\x08 \x08" x (length($_[0]) + 1);
}