Summarize and say sequence

Summarize and say sequence is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

There are several ways to generate a self-referential sequence. One very common one (the Look-and-say sequence) is to start with a positive integer, then generate the next term by concatenating enumerated groups of adjacent alike digits:

0, 10, 1110, 3110, 132110, 13122110, 111311222110 ...

The terms generated grow in length geometrically and never converge.

Another way to generate a self-referential sequence is to summarize the previous term.

Count how many of each alike digit there is, then concatenate the sum and digit for each of the sorted enumerated digits. Note that the first five terms are the same as for the previous sequence.

0, 10, 1110, 3110, 132110, 13123110, 23124110 ... see The On-Line Encyclopedia of Integer Sequences

Sort the digits largest to smallest. Do not include counts of digits that do not appear in the previous term. This means that if there is not a zero in the seed, it can never appear in the sequence since you don't include it if there is zero of any missing digits.

Depending on the seed value, series generated this way always either converge to a stable value or to a short cyclical pattern. (For our purposes, I'll use converge to mean an element matches a previously seen element.) The sequence shown, with a seed value of 0, converges to a stable value of 1433223110 after 11 iterations. The seed value that converges most quickly is 22. It goes stable after the first element. (The next element is 22, which has been seen before.)

Task:

Find all the positive integer seed values under 1000000, for the above convergent self-referential sequence, that takes the largest number of iterations before converging. Then print out the number of iterations and the sequence they return. Note that different permutations of the digits of the seed will yield the same sequence. For this task, assume leading zeros are not permitted.

Seed Value(s): 9009 9090 9900

Iterations: 21 

Sequence: (same for all three seeds except for first element)
9009
2920
192210
19222110
19323110
1923123110
1923224110
191413323110
191433125110
19151423125110
19251413226110
1916151413325110
1916251423127110
191716151413326110
191726151423128110
19181716151413327110
19182716151423129110
29181716151413328110
19281716151423228110
19281716151413427110
19182716152413228110

See also: Self-describing numbers and Look-and-say sequence

C

<lang c>#include <stdio.h>

1. include <stdlib.h>

1. define MAXN 1000000

typedef struct rec_t rec_t, *rec; struct rec_t { int depth; struct rec_t * p[10]; } *rec_root;

rec find_rec(char *s, rec root) { if (!*s) return root; int c = *s++ - '0';

if (!root->p[c]) root->p[c] = calloc(1, sizeof(rec_t)); return find_rec(s, root->p[c]); }

void free_rec(rec root) { if (!root) return;

int i; for (i = 0; i < 10; i++) free_rec(root->p[i]); free(root); }

void next_num(char *s) { int i = 0, cnt[10] = {0};

while (s[i]) cnt[s[i++] - '0']++; for (i = 9; i >= 0; i--) { if (!cnt[i]) continue; s += sprintf(s, "%d%c", cnt[i], i + '0'); } }

int get_len(char *s) { char *p, *q, c; for (p = s; *p; p++) for (q = p+1; *q; q++) if (*p > *q) c = *p, *p = *q, *q = c;

rec r = find_rec(s, rec_root); if (r->depth) return r->depth; r->depth = 1;

next_num(s); return r->depth = 1 + get_len(s); }

int main() { rec_root = calloc(1, sizeof(rec_t));

int longest[100], n_longest = 0; int i, l, ml = 0; char buf[32];

for (i = 0; i < MAXN; i++) { sprintf(buf, "%d", i); if ((l = get_len(buf)) < ml) continue; if (l > ml) { n_longest = 0; ml = l; } longest[n_longest++] = i; }

printf("seq leng: %d\n", ml); for (i = 0; i < n_longest; i++) { sprintf(buf, "%d", longest[i]); /* print len+1 so we know repeating starts from when */ for (l = 0; l <= ml || !puts(""); next_num(buf), l++) printf("%s\n", buf); }

// free_rec(rec_root); return 0; }</lang>

J

Given:

<lang j>digits=: 10&#.inv"0 :. ([: ".@; (<'x'),~":&.>) summar=: (#/.~ ,@,. ~.)&.digits sequen=: ~.@(, summar@{:)^:_ values=: ~. \:~&.digits i.1e6</lang>

The value with the longest value is:

<lang j> values #~ (= >./) #@sequen"0 values 9900

  # sequen 960

21

  sequen 9900

9900 2920 192210 19222110 19323110 1923123110 1923224110 191413323110 191433125110 19151423125110 19251413226110 1916151413325110 1916251423127110 191716151413326110 191726151423128110 19181716151413327110 19182716151423129110 29181716151413328110 19281716...</lang>

Note: Values tested are the cannonical forms, here's a quick attempt at finding the relevant non-cannonical forms:

<lang j> ~.({~ perm@#)&.(digits"1) 9900 9900 9090 9009 990 909 99</lang>

Only the four digit values count, but I am in a hurry and am not coding that up for now.

Note also that the computation for values could have been made much more efficient.

Perl 6

<lang perl6>my @list; my $longest = 0; my %seen;

for 1 .. 1000000 -> $m {

   next unless $m ~~ /0/;         # seed must have a zero
   my $j = join , $m.comb.sort;
   next if %seen.exists($j);      # already tested a permutation
   %seen{$j} = ;
   my @seq := converging($m);
   my %elems;
   my $count;
   for @seq[] -> $value { last if ++%elems{$value} == 2; $count++; };
   if $longest == $count {
       @list.push($m);
       say "\b" x 20, "$count, $m"; # monitor progress
   }
   elsif $longest < $count {
       $longest = $count;
       @list = $m;
       say "\b" x 20, "$count, $m"; # monitor progress
   }   

};

for @list -> $m {

   say "Seed Value(s): ", ~permutations($m).uniq.grep( { .substr(0,1) != 0 } );
   my @seq := converging($m);
   my %elems;
   my $count;
   for @seq[] -> $value { last if ++%elems{$value} == 2; $count++; };
   say "\nIterations: ", $count;
   say "\nSequence: (Only one shown per permutation group.)";
  .say for @seq[^$count], "\n";

}

sub converging ($seed) { return $seed, -> $l { join , map { $_.value.elems~$_.key }, $l.comb.classify({$^b}).sort: {-$^c.key} } ... * }

sub permutations ($string, $sofar? = ) {

   return $sofar unless $string.chars;
   my @perms;
   for ^$string.chars -> $idx {
       my $this = $string.substr(0,$idx)~$string.substr($idx+1);
       my $char = substr($string, $idx,1);
       @perms.push( permutations( $this, join , $sofar, $char ) ) ;
   }
   return @perms;

}</lang>

Output:

Seed Value(s): 9009 9090 9900

Iterations: 21

Sequence: (Only one shown per permutation group.)
9009
2920
192210
19222110
19323110
1923123110
1923224110
191413323110
191433125110
19151423125110
19251413226110
1916151413325110
1916251423127110
191716151413326110
191726151423128110
19181716151413327110
19182716151423129110
29181716151413328110
19281716151423228110
19281716151413427110
19182716152413228110