# Collapsing numbers

Let's define the a function on natural numbers $$\n\$$, written as base 10 digits $$\d_k\; d_{k-1}\; \dotsc\; d_1\; d_0\$$, as follows:

As long as there are equal adjacent digits $$\d_i\;d_{i-1}\$$, replace them by their sum $$\d_i+d_{i-1}\$$ from left to right. If there were any such digits, repeat the same procedure.

In other words, in each iteration we greedily take all pairs of equal adjacent digits and replace them by their sum at the same time (using the left-most pair if they overlap).

## Example

Let's take $$\\texttt{9988}\$$ for example:

1. The first adjacent digits which are equal are the two $$\\texttt{9}\$$
2. So we replace them by $$\\texttt{9 + 9} = \texttt{18}\$$ which gives us $$\\texttt{1888}\$$
3. Since we're still in the first left-right traversal and there were still two $$\\texttt{8}\$$s we need to first replace these
4. So we get $$\\texttt{1816}\$$
5. Something changed, so we need to do another iteration
6. But there are no such digits, so we stop

Therefore the $$\9988^\text{th}\$$ number in that sequence is $$\1816\$$.

## Challenge

The first 200 terms are:

0,1,2,3,4,5,6,7,8,9,10,2,12,13,14,15,16,17,18,19,20,21,4,23,24,25,26,27,28,29,30,31,32,6,34,35,36,37,38,39,40,41,42,43,8,45,46,47,48,49,50,51,52,53,54,10,56,57,58,59,60,61,62,63,64,65,12,67,68,69,70,71,72,73,74,75,76,14,78,79,80,81,82,83,84,85,86,87,16,89,90,91,92,93,94,95,96,97,98,18,10,101,102,103,104,105,106,107,108,109,20,21,4,23,24,25,26,27,28,29,120,121,14,123,124,125,126,127,128,129,130,131,132,16,134,135,136,137,138,139,140,141,142,143,18,145,146,147,148,149,150,151,152,153,154,20,156,157,158,159,160,161,162,163,164,165,4,167,168,169,170,171,172,173,174,175,176,24,178,179,180,181,182,183,184,185,186,187,26,189,190,191,192,193,194,195,196,197,198,28


Your task is to generate that sequence, either

• given $$\n\$$, return the $$\n^\text{th}\$$ number in that sequence,
• given $$\n\$$, return the first $$\n\$$ numbers in that sequence
• or generate the sequence indefinitely.

You may choose your submission to use either $$\0\$$- or $$\1\$$-indexing, but please specify which.

## Test cases

You may use the above given terms, however here are some larger ones:

222 -> 42
1633 -> 4
4488 -> 816
15519 -> 2019
19988 -> 2816
99999 -> 18189
119988 -> 21816
100001 -> 101
999999 -> 181818


# Python 3, 128 bytes

def t(z):j=z and(z[0]==z[1:2])+1;return[str(int(z[0])*j),*t(z[j:])]if j else''
def c(n):r="".join(t(n));return r!=n and c(r)or r


Try it online!

• Welcome to PPCG! Nice first post! Commented Jan 2, 2019 at 18:33
• 108 bytes
– Jo King
Commented Jan 3, 2019 at 2:09

# Python 2, 9796 93 bytes

def f(n):r=re.sub(r'(.)\1',lambda m:int(m.group(1))*2,n);return r!=n and f(r)or r
import re


Try it online!

Non regex version:

# Python 2, 133130122112 98 bytes

def f(n):
r='';s=n
while s:a=1+(s[0]==s[1:2]);r+=int(s[0])*a;s=s[a:]
return r!=n and f(r)or r


Try it online!

# Jelly, 11 bytes

DŒg+2/€FVµ¡


This is an unnecessarily slow, full program.

Try it online!

### Alternate version, 12 bytes

DŒg+2/€FVµƬṪ


One byte longer, but much faster. Works as a program or a function.

Try it online!

### How it works

DŒg+2/€FVµƬṪ  Main link. Argument: n (integer)

µ    Combine the previous links into a chain. Begin a new one.
D               Decimal; yield n's digit array in base 10.
Œg             Group adjacent, identical digits into subarrays.
+2/€         Map non-overlapping, pairwise sum over the subarrays.
If there is an odd number of digits in a subarray, the
last digit will remain untouched.
F        Flatten; dump all sums and digits into a single array.
V       Eval; turn the result into an integer.
Ƭ   Execute the chain 'til the results are no longer unique.
Return all unique results.
Ṫ  Tail; extract the last result.


The 11-byte version does the same, except it calls the link n times for input n, instead of calling it until a fixed point is reached.

• It's not unnecessary if it saves 1 byte :-) Commented Jan 3, 2019 at 1:29

## Haskell, 70 bytes

until((==)=<<f)f
f a=a


Input is taken as a string.

Try it online!

• It doesn't save you anything so far, but with the same length you can replace the second clause with |x<-b:c=a:f x or even f(a:c)=a:f c, in case one or the other could actually lead to an improvement:) Commented Jan 2, 2019 at 20:57

# Retina, 16 bytes

+(.)\1
$.(2*$1*


Try it online! Link includes test cases. Explanation:

+


Repeat until the input stops changing.

(.)\1


Replace pairs of adjacent digits...

$.(2*$1*


... with twice the digit. ($1* generates a string of $1 _s, 2* duplicates that, and $.( takes the length. Actually, the Retina engine is cleverer than that and just doubles $1.)

# JavaScript, 4847 46 bytes

Input and output as strings. Returns the nth term of the sequence.

f=s=>s-(s=s.replace(/(.)\1/g,x=>x/5.5))?f(s):s


Try it online

• 1 byte saved thanks to Arnauld
• 1 byte saved thanks to tsh
• x[0]*2 -> x/5.5
– tsh
Commented Jan 3, 2019 at 7:22
• Thanks, @tsh. Wouldn't have thought of that. Commented Jan 3, 2019 at 23:01

# Perl 6, 37 bytes

{($_,{S:g[(\d)$0]=2*$0}...*==*)[*-1]}  Try it online! This is a function which generates the nth term of the sequence, given n as its argument. ($_, { ... } ... * == *) is the sequence of successive changes to the input number, generated by the bracketed expression (a simple regex substitution) and stopping when * == *, that is, when the last two numbers in the sequence are equal. Then the [*-1] takes just the final element of that sequence as the return value.

• You can save bytes by removing the ==* and replacing the *-1 with $_, since there are always less than n replacements for a number n. 33 bytes – Jo King Commented Jan 3, 2019 at 1:51 # C# (.NET Core), 231, 203, 200, 196, 192 bytes EDIT: Function is now at 185 bytes plus 18 for using System.Linq; Thanks to BMO (for 1>0 being equal to true plus newline removal) and Mr. XCoder (for f=!f statements)! EDIT2: Down to 182 bytes plus 18 for using System.Linq thanks to dana for sharing a few golf tips! EDIT3: Thanks to Embodiment of Ignorance for the int[] -> var, removal of short circuit && -> &, and changing up ToArray -> ToList! (178 bytes + 18 using) EDIT4: Embodiment of Ignorance dropped 4 bytes by changing an assignment. Dummy me shoulda counted! Thanks again :D p=>{var f=1>0;while(f){var t=p.Select(n=>n-48).ToList();p="";f=!f;for(var j=0;j<t.Count;j++){if(j<t.Count-1&t[j]==t[1+j]){p+=t[j]+t[++j];f=!f;continue;}p+=t[j];}};return p;};  Try it online! • 174 before using Commented Jan 4, 2019 at 0:09 # Perl 5-p, 21 bytes s/(.)\1/$1*2/ge&&redo


Try it online!

# Japt v2.0a0 -h, 15 14 bytes

Returns the nth term of the sequence.

Æ=s_r/(.)\1/ÏÑ


Try it

This should work for 10 bytes but there seems to be a bug in Japt's recursive replacement method.

e/(.)\1/ÏÑ


# Groovy, 63 bytes

{s->r=/(\d)\1/
while(s=~r)s=s.replaceAll(r){(it[1]as int)*2}
s}


Try it online!

# 05AB1E, 11 bytes

Δγε2ôSO}˜J


Explanation:

Δ             # Continue until the (implicit) input no longer changes:
γ            #  Split the integer in chunks of the same adjacent digits
#   i.e. 199999889 → [1,99999,88,9]
ε     }     #  Map each to:
2ô         #   Split it into parts of size 2
#    i.e. 99999 → [99,99,9]
€S       #   Split each part into digits
#    i.e. [99,99,9] → [[9,9],[9,9],[9]]
O      #   And take the sum of each part
#    i.e. [[9,9],[9,9],[9]] → [18,18,9]
˜    #  Flatten the list
#   i.e. [[1],[18,18,9],[16],[9]] → [1,18,18,9,16,9]
J   #  Join everything together
#   i.e. [1,18,18,9,16,9] → 118189169
# (And output the result implicitly at the end)
#  i.e. output = 28189169


# Wolfram Language 108 bytes

ToExpression[""<>ToString/@Total/@Flatten[Partition[#,UpTo@2]&/@Split@IntegerDigits@#,1]]&~FixedPoint~#&


## Explanation

IntegerDigits transforms the input number into a list of its digits.

Split groups consecutive repeated digits.

Partition[#, UpTo@2]&/@ breaks runs of like digits into lists of, at most, lengths of 2.

Flatten[...,1] eliminates occasional overly-nested braces--e.g., {{2,2}} becomes {2,2}

Total/@ sums totals of paired digits. Isolated digits need not be summed.

ToString converts the totals (and isolated digits) to strings.

""<> joins all the strings in the list.

ToExpression converts the outcome to an integer.

...~FixedPoint~#& applies the function until the result ceases to change.

# C# (Visual C# Interactive Compiler) with flag /u:System.Text.RegularExpressions.Regex, 70 bytes

s=>{for(;s[0]!=(s[0]=Replace(s[0],@"(.)\1",m=>m.Value[0]*2-96+"")););}


Outputs by modifying the input. Takes in a list containing one string for input.

Thanks to @dana for golfing an entire 23 bytes!

Try it online!

• 95+34 - 33 + 1 for the extra space you need in the commandline args, iirc Commented Jan 3, 2019 at 6:23
• Recursive anonymous functions have to be defined first, and the definition is in included in the byte count. Commented Jan 3, 2019 at 6:42
• Oh, it's recursive Commented Jan 3, 2019 at 7:18
• Nice! I think I can get it down a bit more Commented Jan 27, 2019 at 16:30
• That's a pretty good score considering it's C# :)
– dana
Commented Jan 28, 2019 at 5:44

# Clean, 118 bytes

import StdEnv,Data.List
$[a,b:t]|a==b=[1,(a*2)rem 10]%(1-a/5,1)++$t=[a: $[b:t]]$l=l

limit o iterate$o map digitToInt  Try it online! Takes the first repeated value (limit) from the infinite list of applications (iterate) of a lambda performing a single step of the collapsing process. Input taken as a [Char]. # Red, 8483 80 bytes func[n][if parse s: form n[to some change[copy d skip d](2 * do d)to end][f s]s]  Try it online! Returns the nth term of the sequence. ## Explanation: Red[] f: func [ n ] [ if parse s: form n [ ; parse the input converted to a string to some change [ ; find and change one or more copy d skip ; digit (in fact any character, no predefined character classes) d ; followed by itself ] (2 * do d) ; with its doubled numeric value to end ; go to the end of the string ] [ f s ] ; call the function with the altered string if parse returned true s ; finally return the string ]  # Scala, 84 bytes s=>{var t=s while(t!=(t="(\\d)\\1".r.replaceAllIn(t,m=>s"$m"(0)*2-96+""),t)._2){}
t}


Try it online!

# C# (Visual C# Interactive Compiler), 111 bytes

s=>{var t=s;do{s=t;t="";for(int i=0;i<s.Length;)t+=s[i]%48*(s[i++]!=(s+0)[i]?1:2*++i/i);}while(t!=s);return t;}


Try it online!

HUGE credit to @ASCIIOnly for golfing ~30 ;) At first we were both posting updates simultaneously, but at some point he clearly went to town!

-2 thanks to @EmbodimentOfIgnorance!

Less golfed code...

// s is the input as a string
s=>{
// t is another string used
// to hold intermediate results
var t=s;
// the algorithm repeatedly
// processes s and saves the
// result to t
do{
// copy the last result to s
// and blank out t
s=t;
t="";
// iterate over s
for(int i=0;i<s.Length;)
// append either 1 or 2 times
// the current digit to t
t+=s[i]%48*
// compare the current digit
// to the next digit. to prevent
// an out-of-bounds exception,
// append a 0 to s which either
// gets ignored or collapses
// to 0
(s[i++]!=(s+0)[i]
// if they are different, then
// the multiplier is 1
?1
// if they are the same, then
// the multiplier is 2, and we
// have to increment i
:2*++i/i);
}
// continue this until the input
// and output are the same
while(t!=s);
return t;
}

• 139 Commented Jan 3, 2019 at 6:47
• 134 Commented Jan 3, 2019 at 6:52
• @ASCIIOnly - Good move :) (s[i++]-48)*2 => s[i++]*2-96
– dana
Commented Jan 3, 2019 at 6:54
• 131 Commented Jan 3, 2019 at 6:59
• 114 Commented Jan 3, 2019 at 7:22

# Husk, 15 bytes

→U¡ödṁoṁodΣC2gd


Try it online!

# Ruby-p, 39 34 bytes

-5 bytes thanks to Steffan

$_.gsub!(/(.)\1/){$1.to_i*2}&&redo


Attempt This Online!

• You have to count the F= in the bytecount since you're recursing. However, you can just replace F[s] with redo and then you don't need to. Commented Nov 28, 2022 at 0:26
• @Steffan I always forget about redo. Thanks. Commented Nov 28, 2022 at 0:28
• You can get 34 bytes with a full program and -p flag: $_.gsub!(/(.)\1/){$1.to_i*2}&&redo ATO Commented Nov 28, 2022 at 0:31
• @Steffan Of course. Good catch. Commented Nov 28, 2022 at 0:34