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

 

=={{header|C++}}==

#include <iostream>

#include <string>

return 0;

}

{{out}}

<pre>

 

</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}}

 

string[] selfReferentialSeq(string n, string[] seen=[]) nothrow {

foreach (const idx, const val; max_vals[0].text.selfReferentialSeq)

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

{{out}}

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

===More Efficient Version===

{{trans|Python}}

 

struct Permutations(bool doCopy=true, T) {

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.

 

struct MemoryPool(T, int MAX_BLOCK_BYTES = 1 << 17) {

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

//recPool.freeAll;

Faster than the C entry, run-time is about 1.16 seconds using the dmd compiler (about 1.5 without memory pool). Same output as the C entry.

 

Extra credit: searching up to 1e+10 does not find a longer sequence.

 

(lib 'hash)

(lib 'list) ;; permutations

(writeln (expt 10 n) '--> 'max-sequence= (1+ seqmax) 'nodes= (length (hash-values H))))

{{out}}

(task 6)

1 (9009 9090 9900)

10000000000 --> max-sequence= 21 nodes= 188493

 

 

=={{header|Eiffel}}==

Only checks numbers where digits are in ascending order. Digits with trailing zeros have to be treated as ascending numbers (special case). Calculates all the permutations in the end.

class

SELF_REFERENTIAL_SEQUENCE

 

end

{{out}}

<pre>

19281716151413427110

19182716152413228110

</pre>

 

=={{header|Go}}==

Brute force

 

import (

}

return r

Output:

<pre>

=={{header|Groovy}}==

Solution:

def number = delegate as String; def sequence = []

 

}

}

Test:

 

println "\nLargest sequence size among seeds < 1,000,000\n"

println "Size: ${max.seqSize}\n"

println "Sample sequence:"

Output:

<pre>Largest sequence size among seeds < 1,000,000

=={{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

=={{header|Java}}==

{{works with|Java|8}}

import java.util.concurrent.ConcurrentHashMap;

import java.util.stream.IntStream;

}

}

 

<pre>Seeds:

19281716151413427110

19182716152413228110</pre>

 

=={{header|jq}}==

def runs:

reduce .[] as $item

;

 

{{out}}

<div style="overflow:scroll; height:400px;">

The maximal length to convergence for seeds up to 1000000 is 21.

The corresponding seeds are the allowed permutations

19281716151413430000,

19182716152413230000

 

=={{header|Kotlin}}==

 

const val LIMIT = 1_000_000

sieve[n] = size

if (n > 9) {

for (perm in perms) {

if (perm[0] == '0') continue

println()

}

 

{{out}}

=={{header|Lua}}==

Runs in about nine seconds under LuaJIT. Uses memoisation via the global table 'nextTerm'.

function findNext (nStr)

local nTab, outStr, pos, count = {}, "", 1, 1

print("\n\nIterations: " .. highest)

print("\nSample sequence:")

{{out}}

<pre>Seed values: 9009 9090 9900

19182716152413228110</pre>

 

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}

19182716152413228110

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

 

=={{header|Phix}}==

Optimisation idea taken from CoffeeScript, completes in under a second.

<pre>

{"9900","9009","9090"}

=={{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>

 

The REXX language supports &nbsp; '''sparse''' &nbsp; (stemmed) arrays, so this program utilizes REXX's hashing of

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

parse arg LO HI . /*obtain optional arguments from the CL*/

if LO=='' | LO=="," then LO= 1 /*Not specified? Then use the default.*/

do k=1 for words(q); say word(q, k)

end /*k*/

{{out|output|text=&nbsp; when using the default inputs:}}

<br>(Shown at five-sixths size.)

=={{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|TXR}}==

This is a close, almost expression-by-expression transliteration of the Clojure version.

 

(defmacro reduce-with ((acc init item sequence) . body)

^(reduce-left (lambda (,acc ,item) ,*body) ,sequence ,init))

(put-line `Iterations: @(length result)`)

(put-line)

 

{{out}}

Like in Common Lisp, TXR's <code>sort</code> is destructive, so we take care to use <code>copy-str</code>.

 

(let* ((s [sort (copy-str str) <])

(out `@[s 0]0`))

(when (> l len) (set len l) (set nums nil))

(when (= l len) (push x nums))))

 

{{out}}

==={{trans|Racket}}===

 

(defmacro for-accum (accum-var-inits each-vars . body)

(let ((accum-vars [mapcar first accum-var-inits])

*seq))))

(put-line `Numbers: @{nums ", "}\nLength: @len`)

 

{{out}}

19182716152413228110</pre>

 

}

}

}

}

<pre>

9009

9090

9900

</pre>

 

=={{header|zkl}}==

 

fcn lookAndJustSaying(seed){ // numeric String --> numeric String

.filter(fcn(s){ s[0]!="0" }) : Utils.Helpers.listUnique(_);

println(max," iterations for ",zs.concat(", "));

Ignoring permutations cut run time from 4 min to 9 sec.

{{out}}