True So Far

[hv at crypt.org]

"Eric Angelini" <keynews.tv at skynet.be> wrote:
:Description :
:
:    "True so far"-sequence. Last digit of a(n) must be seen
:    as a glyph and preceding digits as a quantity. So "10"
:    reads [one "0"] and "12" [one "2"] -- which are both true
:    statements: there is only one "0" glyph so far in the
:    sequence when [10] is read, and there is only one "2"
:    glyph when [12] is read. The sequence is built with
:    [a(n+1)-a(n)] being minimal and a(n+1) always "true so
:    far". This explains why integers [11], [21], [22], [31],
:    etc. are not in: their statements are false.
:
:    The nice substring ...1112,1113,1114,1115,1116,1117 1118...
:    appears in the sequence -- which means that so far the
:    whole sequence has used 111 "2", 111 "3", 111 "4", 111 "5",
:    111 "6", 111 "7" and 111 "8"...
[...]

I think it would be fairer to call this "about to be true", and interesting
to consider also an "already true" sequence, in which we include, say, "1234"
if the *preceding* sequence includes 123 '4's.

The latter can also be generalised to base b, and also varies depending
on whether a(0) is chosen as '0' or '1'. Eg starting at 0:
base 2: 0 1 2 4 7 8 14 16 23 26 30 32 42 48 56 62 64 75 82 89 96 101 109 116
base 3: 0 1 2 3 5 6 9 11 14 17 18 24 25 27 31 38 41 42 45 50 51 54 63 68 69
baes 4: 0 1 2 3 4 6 7 8 11 12 16 18 19 22 23 26 27 31 32 39 40 43 44 48 55 56
base 10: 0 1 2 3 4 5 6 7 8 9 10 12 13 14 15 16 17 18 19 20 23 24 25 26 27 28

.. and starting at 1:

base 2: 1 3 7 13 19 25 31 41 47 57 65 69 75 83 91 101 109 119 131 137 143 153
base 3: 1 2 4 5 8 13 14 17 23 29 32 35 41 44 50 56 62 67 74 76 82 88 92 95 98
base 4: 1 2 3 5 6 7 10 11 15 21 22 23 26 27 31 38 39 43 47 55 62 66 70 71 74
base 10: 1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 22 23 24 25 26 27 28 29

I think these sequences are always infinite. I'm unsure how many of them
merit entries in the OEIS.

Starting at 1 also leads to the interesting question whether the '0' digits
ever get sufficiently represented to be included in the sequence (ie whether
there exists an a(n) divisible by b in the sequence for any base b);
empirical evidence from some brief playing suggests not.

In case anyone is interested, the perl code below can be used to investigate
all these sequences.

Hugo van der Sanden
---
#!/usr/bin/perl -w
use strict;
use integer;
my $start = 1;    # start at 0 or 1 (irrelevant unless $include is 0)
my $include = 0;  # include (1) or exclude (0) the about-to-be-chosen number
my $base = 10;    # the base to work in

$| = 1;
print "base $base (start=$start, include=$include): ";
my @digit = (0) x $base;

for (my $n = $start; 1; ++$n) {
  my $digit = $n % $base;
  my $count = $n / $base;
  if ($include) {
    next if $count <= $digit[$digit];
  } else {
    next if $count != $digit[$digit];
  }
  my @d2 = basedig($n);
  if ($include) {
    next if $count != $digit[$digit] + $d2[$digit];
  }
  print "$n ";
  $digit[$_] += $d2[$_] for 0 .. $base-1;
}

sub basedig {
  my $n = shift;
  my @d = (0) x $base;
  do {
    ++$d[$n % $base];
    $n /= $base;
  } while $n;
  @d;
}