Summarize and say sequence: Difference between revisions

{{task}}

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:

The terms generated grow in length geometrically and never converge.

 

 

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.

Sort the digits largest to smallest. Do not include counts of digits that do not appear in the previous term.

 

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.)

 

 

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.

 

19182716152413228110

</pre>

 

=={{header|Ada}}==

with Ada.Containers.Vectors;

procedure SelfRef is

IO.Put (mseed, Width => 1); New_Line;

len := Iterate (mseed, True);

{{out}}

<pre>21 Iterations:

=={{header|Aime}}==

{{trans|C}}

{

data d;

 

while (l) {

}

 

}

 

}

 

 

d = 0;

if (d <= 0) {

i += 1;

if (d <= 0) {

}

}

}

 

text s;

 

e = d - 1;

s = itoa(i);

while (e) {

e -= 1;

}

 

return 0;

{{out}}

<pre>longest length is 21

=={{header|AutoHotkey}}==

Not optimized in the slightest.

; The following directives and commands speed up execution:

#NoEnv

return errorlevel

}

Output:

<pre>Seeds: 9009 9090 9900

19281716151413427110

19182716152413228110</pre>

=={{header|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

DIM list$(30)

maxiter% = 0

IF d%(I%) o$ += STR$d%(I%) + STR$I%

NEXT

'''Output:'''

<pre>

 

=={{header|Bracmat}}==

= seq N next

. ( next

)

& out$("Iterations:" !max !seqs)

Output:

<pre> Iterations:

 

=={{header|C}}==

#include <stdlib.h>

#include <string.h>

 

return 0;

{{out}}

<pre>longest length: 21

</pre>

 

 

 

 

 

 

 

=={{header|Clojure}}==

"simplifies form of reduce calls"

[bindings & body]

(zero? cmp) (conj max-seqs new-seq)))))

 

 

The above code saves a lot of time by only calculating summary step sequences for one

but the one here will serve.

 

"produce all the permutations of a finite sequence"

[ds]

(println "Sequence:")

(doseq [ds result]

 

=={{header|Common Lisp}}==

Doesn't do cache, and takes forever.

(let* ((s (sort (map 'list #'identity str) #'char>))

(out (list (first s) 0)))

(let ((r (find-longest 1000000)))

(format t "Longest: ~a~%" r)

9900

2920

19281716151423228110

19281716151413427110

 

=={{header|D}}==

===Slow High-level Version===

{{trans|Ruby}}

 

 

int[10] digit_count;

digit_count[d - '0']++;

string term;

if (digit_count[d] > 0)

term ~= text(digit_count[d], d);

int[] max_vals;

 

const seq = n.text().selfReferentialSeq();

if (seq.length > max_len) {

writeln("iterations: ", max_len);

writeln("sequence:");

writefln("%2d %s", idx + 1, val);

<pre>values: [9009, 9090, 9900]

iterations: 21

===More Efficient Version===

{{trans|Python}}

 

struct Permutations(bool doCopy=true, T) {

T[] result;

 

this.items = items;

immutable int n = items.length;

} else {

this.stopped = false;

}

 

}

 

return this.stopped;

}

 

static if (doCopy) {

assert(!this.stopped);

auto result = new T[r];

}

} else {

assert(!this.stopped);

foreach (immutable i, ref re; this.result)

}

 

assert(!this.stopped);

int i = r - 1;

if (j > 0) {

cycles[i] = j;

return;

}

immutable int num = indices[i];

 

indices[i + 1 .. n1 + 1].copy(indices[i .. n1]);

indices[n1] = num;

Permutations!(doCopy, T) permutations(bool doCopy=true, T)

(T[] items, int r=-1)

return Permutations!(doCopy, T)(items, r);

}

enum maxIters = 1_000_000;

 

}

 

writefln(" %2d %s", iterations, numberString);

 

 

if (lastThree[].canFind(numberString))

 

foreach (n; startRange) {

 

if (sns !in alreadyDone) {

A036058_length!true(n.text);

}

The output is similar to the Python entry.

 

{{trans|C}}

From the C version, with a memory pool for a faster tree allocation.

 

static assert(!is(T == class),

"MemoryPool is designed for native data.");

static assert(MAX_BLOCK_BYTES >= 1,

"MemoryPool: MAX_BLOCK_BYTES must be >= 1 bytes.");

 

 

static T* newItem() nothrow {

if (blocks[$ - 1] == null)

exit(1);

}

 

}

 

}

 

if (!next) {

nNodes++;

root.p[c] = next;

}

}

 

int[10] cnt;

for (int i = 0; s[i]; i++)

rec_root = recPool.newItem();

 

sprintf(buf.ptr, "%d", i);

int l = getLen(buf.ptr, 0);

 

printf("seq leng: %d\n\n", ml);

sprintf(buf.ptr, "%d", longest[i]);

// print len+1 so we know repeating starts from when

printf("%2d: %s\n", getLen(buf.ptr, 0), buf.ptr);

nextNum(buf.ptr);

 

printf("Allocated %d Rec tree nodes.\n", nNodes);

 

=={{header|Go}}==

Brute force

 

import (

}

return r

Output:

<pre>

19182716152413228110

</pre>

=={{header|Haskell}}==

Brute force and quite slow:

import Data.List (group, sort)

 

map show -- turn the numbers into digits

[1..1000000] -- The input seeds

 

=={{header|Icon}} and {{header|Unicon}}==

 

procedure main()

every (n := "") ||:= (0 < Counts[i := 9 to 0 by -1]) || i # assemble counts

return integer(n)

 

{{libheader|Icon Programming Library}}

exists at the maximum sequence length. As with the first example, it works

in both Icon and Unicon.

 

procedure main(A)

every s := !seqTab do (write() & every write(!(!s\1)[2]))

end

Output with <tt>limit = 1000000</tt>:

<pre>

=={{header|J}}==

Given:

digits=: 10&#.inv"0 :. ([: ".@; (<'x'),~":&.>)

summar=: (#/.~ ,@,. ~.)@\:~&.digits

sequen=: ~.@(, summar@{:)^:_

values=: ~. \:~&.digits i.1e6

 

The values with the longest sequence are:

 

9900 9090 9009

# sequen 9900

19281716151423228110

19281716151413427110

 

Notes:

<code>digits</code> is an invertible function that maps from a number to a sequence of digits and back where the inverse transform converts numbers to strings, concatenates them, and then back to a number.

 

3 2 1

digits inv 34 5

 

<code>summar</code> computes the summary successor.

 

 

<code>sequen</code> computes the complete non-repeating sequence of summary successors

Finally, <code>allvar</code> finds all variations of a number which would have the same summary sequence based on the permutations of that number's digits.

 

DisplaySequence[ x_ ] := NestWhileList[selfRefSequence,x,UnsameQ[##]&,4]

data= {#, Length@DisplaySequence[#]}&/@Range[1000000];

Print["Values: ", Select[data ,#[[2]] == Max@data[[;;,2]]&][[1,;;]]]

Print["Iterations: ", Length@DisplaySequence[#]&/@Select[data ,#[[2]] == Max@data[[;;,2]]&][[1,;;]]]

 

<pre>Values: {9009, 9090, 9900}

19281716151413427110</pre>

 

 

 

=={{header|Perl}}==

my @a;

$a[$_]++ for split '', shift;

my $l = seq($_);

next if $l < $mlen;

if ($l > $mlen) { $mlen = $l; @mlist = (); }

push @mlist, $_;

 

print "longest ($mlen): @mlist\n";

9009

2920

19281716151423228110

19281716151413427110

</pre>

 

=={{header|PicoLisp}}==

Using 'las' from [[Look-and-say sequence#PicoLisp]]:

(let L (mapcar format (chop Seed))

(make

(println 'Values: (cdr Res))

(println 'Iterations: (car Res))

Output:

<pre>Values: (9009 9090 9900)

The number generation function follows that of Look-and-say with a sort. only the first of any set of numbers with the same digits has the length of its sequence calculated in function max_A036058_length, although no timings were taken to check if the optimisation was of value.

 

 

def A036058(number):

for n in starts:

print()

 

;Output:

20 19281716151413427110

21 19182716152413228110</pre>

 

=={{header|Racket}}==

#lang racket

 

(printf "Numbers: ~a\nLength: ~a\n" (string-join nums ", ") len)

(for ([n seq]) (printf " ~a\n" n))

{{out}}

<pre>

19281716151413427110

19182716152413228110

</pre>

 

=={{header|REXX}}==

<br>array elements to speed up the checking to see if a sequence has been generated before.

 

 

end

 

 

────────────────────────────── iteration sequence for: 9009 (21 iterations)

=={{header|Ruby}}==

Cached for performance

def selfReferentialSequence_cached(n, seen = [])

return $cache[n] if $cache.include? n

selfReferentialSequence_cached(max_vals[0]).each_with_index do |val, idx|

puts "%2d %d" % [idx + 1, val]

output

<pre>values: [9009, 9090, 9900]

20 19281716151413427110

21 19182716152413228110</pre>

 

=={{header|Tcl}}==

<!-- The first version of this code had a neat trick with sorting the strings characters and using a counting regexp, but it was very slow -->

foreach c [split $n ""] {incr t($c)}

foreach c {9 8 7 6 5 4 3 2 1 0} {

puts "\t$seed"

}

Output:

<pre>

19281716151413427110

19182716152413228110

</pre>