title: Pascal's Triangle (Sort of)

text:
# Question
Title: Pascal's Triangle (Sort of)
Most everyone here is familiar with Pascal's Triangle. It's formed by successive rows, where each element is the sum of its two upper-left and upper-right neighbors. Here are the first `5` rows (borrowed from Generate Pascal's triangle):

```
    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1
  . . .

```

Collapse these rows to the left

```
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
. . .

```

Sort them in ascending order

```
1
1 1
1 1 2
1 1 3 3
1 1 4 4 6
. . .

```

Read this triangle by rows

```
[1, 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 4, 6 ...]

```

Given an input `n`, output the `n`th number in this series. This is OEIS 107430.

### Rules

* You can choose either 0- or 1-based indexing. Please state which in your submission.
* The input and output can be assumed to fit in your language's native integer type.
* The input and output can be given by any convenient method.
* Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
* Standard loopholes are forbidden.
* This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

# Answer
# JavaScript (ES6), 79 bytes

0-indexed.

```
f=(n,a=[L=1])=>a[n]||f(n-L,[...a.map((v,i)=>k=(x=v)+~~a[i-1-i%2]),L++&1?k:2*x])

```

### Demo

```
f=(n,a=[L=1])=>a[n]||f(n-L,[...a.map((v,i)=>k=(x=v)+~~a[i-1-i%2]),L++&1?k:2*x])

console.log([...Array(79).keys()].map(n => f(n)).join(', '))
```

### How?

```
f = (                       // f = recursive function taking:
  n,                        //   n = target index
  a = [L = 1]               //   a[] = current row, L = length of current row
) =>                        //
  a[n] ||                   // if a[n] exists, stop recursion and return it
  f(                        // otherwise, do a recursive call to f() with:
    n - L,                  //   n minus the length of the current row
    [                       //   an array consisting of:
      ...a.map((v, i) =>    //     replace each entry v at position i in a[] with:
        k =                 //       a new entry k defined as:
        (x = v) +           //       v +
        ~~a[i - 1 - i % 2]  //       either the last or penultimate entry
      ),                    //     end of map()
      L++ & 1 ?             //     increment L; if L was odd:
        k                   //       append the last updated entry
      :                     //     else:
        2 * x               //       append twice the last original entry
    ]                       //   end of array update
  )                         // end of recursive call

```

This algorithm directly generates the sorted rows of Pascal's Triangle. It updates **n** according to the length of the previous row until **a\[n\]** exists. For instance, 6 iterations are required for **n = 19**:

```
 L | n  | a[]
---+----+------------------------
 1 | 19 | [ 1 ]
 2 | 18 | [ 1, 1 ]
 3 | 16 | [ 1, 1, 2 ]
 4 | 13 | [ 1, 1, 3, 3 ]
 5 |  9 | [ 1, 1, 4, 4, 6 ]
 6 |  4 | [ 1, 1, 5, 5, 10, 10 ]
                        ^^

```
> 9 votes

# Answer
# Octave, 46 bytes

```
@(n)(M=sort(spdiags(flip(pascal(n)))))(~~M)(n)

```

1-based.

**Try it online!**

### Explanation

Consider `n=4` as an example.

`pascal(n)` gives a Pascal matrix:

```
 1     1     1     1
 1     2     3     4
 1     3     6    10
 1     4    10    20

```

The rows of the Pascal triangle are the antidiagonals of this matrix. So it is flipped vertically using `flip(···)`

```
 1     4    10    20
 1     3     6    10
 1     2     3     4
 1     1     1     1

```

which transforms antidiagonals into diagonals.

`spdiags(···)` extracts the (nonzero) diagonals, starting from lower left, and arranges them as zero-padded columns:

```
 1     1     1     1     0     0     0
 0     1     2     3     4     0     0
 0     0     1     3     6    10     0
 0     0     0     1     4    10    20

```

`M=sort(···)` sorts each column of this matrix, and assigns the result to variable `M`:

```
 0     0     0     1     0     0     0
 0     0     1     1     4     0     0
 0     1     1     3     4    10     0
 1     1     2     3     6    10    20

```

Logical indexing `(···)(~~M)` is now used to extract the nonzeros of this matrix in column-major order (down, then across). The result is a column vector:

```
 1
 1
 1
 1
···
10
10
20

```

Finally, the `n`-th entry of this vector is extracted using `(···)(n)`, which in this case gives `1`.
> 6 votes

# Answer
# Python 2, ~~86~~ ~~78~~ 72 bytes

-8 bytes thanks to Rod

```
g=lambda n,r=[1]:r[n:]and r[n/2]or g(n-len(r),map(sum,zip([0]+r,r+[0])))

```

Try it online!

## Ungolfed

```
def g(n, row=[1]):
  if n < len(row):
    return row[n/2]
  else:
    next_row = map(sum, zip([0] + row, row + [0]))
    return g(n - len(row), next_row)

```

Try it online!

The function recursively calculates the row of Pascal's Triangle. Given the current row as `row`, `map(sum, zip([0] + row, row + [0]))`.
At each call `n` is reduced by the length of the current row. If the function arrives at the right row the `nth` lowest number of the row should be returned.
As the first half of a row is in ascending order and each row is symmetrical, the number is at index `n/2` (0-indexed, integer division).
> 5 votes

# Answer
# Wolfram Language (Mathematica), 55 bytes

The indexing is 1-based.

```
(##&@@@Sort/@Table[n~Binomial~k,{n,0,#},{k,0,n}])[[#]]&

```

Try it online!

## Explanation

This is likely golfable, I am not a very experienced Mathematica user.

```
Table[n~Binomial~k,{n,0,#},{k,0,n}]

```

For each **n ∈ \[0, Input\] ∩ ℤ**, generate the table of binomials with each **k ∈ \[0, n\] ∩ ℤ**.

```
Sort/@

```

Sort each. Uses a shorthand to `Map[function,object]``function/@object`.

```
(##&@@@...)[[#]]

```

Flatten the resulting list and retrieve the element whose index in the list is the input.
> 4 votes

# Answer
# APL (Dyalog), ~~26~~ 25 bytes

*1 byte saved thanks to @ngn*

```
{⍵⊃0~⍨∊(⍋⊃¨⊂)¨↓⍉∘.!⍨⍳1+⍵}

```

Try it online!
> 3 votes

# Answer
# , 58 bytes

```
function(n)(m=apply(outer(0:n,0:n,choose),1,sort))[m>0][n]

```

Try it online!

Computes `n choose k` for each `n,k` in `[0,1,...,n]` as a matrix, sorts the rows ascending(\*), and removes the zeros, then selects the `n`th element.

(\*) This also transforms them into *columns* but that's better since R stores a matrix as a vector columnwise, which allows us to index directly into it while preserving order.
> 3 votes

# Answer
# Haskell, ~~143~~ ~~132~~ ~~125~~ 123 bytes

```
((p>>=s.h)!!)
p=[1]:map(\r->zipWith(+)(0:r)(r++[0]))p
h r=splitAt(div(length r)2)r
s(a,b)=reverse b!a
(h:t)!b=h:(b!t)
x!_=x

```

The first line is a point-free function that takes an index (0-based) and returns the appropriate number in the sequence. Try it online!

This is my first ever Haskell program! I'm sure it can get much shorter. Tips are appreciated.

*Saved 2 bytes thanks to nimi*

### Ungolfed

```
pascalRows = [1] : map (\row -> zipWith (+) (0:row) (row++[0])) pascalRows
halves row = splitAt (div (length row) 2) row
joinSorted (first, second) = interleave (reverse second) first
interleave [] _ = []
interleave longer shorter = (head longer) : (interleave shorter (tail longer))
f n = (concatMap (joinSorted.halves) pascalRows) !! n

```
> 3 votes

# Answer
# JavaScript, 57 bytes

```
f=(i,r=1)=>i<r?i>1?f(i-2,--r)+f(i<r?i:r-1,r):1:f(i-r,r+1)

```

0-indexed.

How does this come:

Step 0:

```
c=(i,r)=>i?r&&c(i-1,r-1)+c(i,r-1):1
f=(i,r=1)=>i<r?c(i>>1,r-1):f(i-r,r+1)

```

This code is easy to understand:

* function `c` calculate the Combination use formula: C(n,k) = C(n-1,k) + C(n-1,k-1); or 1 if k == 0 or k == n
* function `f` try to find out the row number and index in the row, and then call function c for getting the result.

Step 1:

```
c=(i,r)=>i>1?--r&&c(i-2,r)+c(i,r):1
f=(i,r=1)=>i<r?c(i,r):f(i-r,r+1)

```

In this step, we try to modify the call of function `c` to `c(i,r)` which makes it as same as parameter of `f`.

Step 2:

```
c=(i,r)=>i>1?--r&&c(i-2,r)+c(i<r?i:r-1,r):1
f=(i,r=1)=>i<r?c(i,r):f(i-r,r+1)

```

We test `i<r` for whether using function `f` or function `c`. That's why we musk keep `i<r` holds during recursion of function `c`.

Step 3:

```
f=(i,r=1)=>i<r?i>1?--r&&f(i-2,r)+f(i<r?i:r-1,r):1:f(i-r,r+1)

```

At this step, we merge these two function into one.

After some more golf, we finally got the answer described above.

```
f=(i,r=1)=>i<r?i>1?f(i-2,--r)+f(i<r?i:r-1,r):1:f(i-r,r+1)

for(i=0,x=1;x<10;x++) {
document.write('<p>')
for(j=0;j<x;j++,i++) document.write(`<b>${f(i)}</b>`)
}
```

```
p { text-align: center; }
b { display: inline-block; width: 4ch; font-weight: normal; }
```
> 3 votes

# Answer
# Jelly, 13 bytes

```
0rcþ`ZṢ€Ẏḟ0⁸ị

```

Try it online!

Using Uriel's Dyalog algorithm.

1-indexed.

Explanation:

```
0rcþ`ZṢ€Ẏḟ0⁸ị
0r            Return inclusive range from 0 to n
    `         Call this dyad with this argument on both sides
   þ           Outer product with this dyad
  c             Binomial coefficient
     Z        Zip
       €      Call this link on each element
      Ṣ        Sort
        Ẏ     Concatenate elements
         ḟ0   Remove 0s
           ⁸ị Take the nth element

```
> 2 votes

# Answer
# APL (Dyalog Classic), 17 bytes

```
⎕⊃∊i!⍨,\⌊.5×i←⍳99

```

Try it online!

0-based indexing

note that `(49!98) > 2*53`, i.e. the binomial coefficient 98 over 49 is greater than 253, so at that point Dyalog has already started losing precision because of IEEE floating point
> 2 votes

# Answer
# JavaScript (Node.js), 65 bytes

Not even an array is used. 0-indexed.

```
f=(n,i=0,g=x=>x?x*g(x-1):1)=>n>i?f(n-++i,i):g(i)/g(c=n>>1)/g(i-c)

```

Try it online!

Explanation:

```
f=(n,i=0,                 )=>                                     // Main Function
         g=x=>x?x*g(x-1):1                                        // Helper (Factorial)
                             n>i?                                 // Is n > i?
                                 f(n-++i,i):                      // If so, call function
                                                                  // f(n-i-1, i+1) to skip
                                                                  // . i+1 terms
                                            g(i)/g(c=n>>1)/g(i-c) // If not, since sorting
                                                                  // . the binomial coeffs
                                                                  // . equals to writing
                                                                  // . the first floor(i/2)
                                                                  // . coefficients twice
                                                                  // . each, so a shortcut

```
> 2 votes

# Answer
# Pascal, 373 bytes

```
function t(n,k,r:integer):integer;begin if(n<k)then t:=r-1 else t:=t(n,k+r,r+1)end;
function s(n,k:integer):integer;begin if(k=0)then s:=n else s:=s(n+k,k-1)end;
function f(n,k:integer):integer;begin if((k<1)or(k>n))then f:=0 else if n=1 then f:=1 else f:=f(n-1,k-1)+f(n-1,k)end;
function g(n:integer):integer;var k:integer;begin k:=t(n,0,1);g:=f(k,(n-s(0,k-1)+2)div 2)end;

```

`g` is the function.

Try it online!
> 1 votes

# Answer
# MATL, 11 bytes

```
:qt!XnSXzG)

```

1-based.

Try it online! Or verify all test cases.

### Explanation

Consider input `4` as an example. `;` is the row separator for matrices or column vectors.

```
:     % Implicit input: n. Push the row vector [1 2 ... n]
      S STACK: [1 2 3 4]
q     % Subtract 1, emlement-wise: gives [0 1 ... n-1]
      % STACK: [0 1 2 3]
t!    % Duplicate and transpose into a column vector
      % STACK: [0 1 2 3], [0; 1; 2; 3]
Xn    % Binomial coefficient, element-wise with broadcast. Gives an
      % n×n matrix where entry (i,j) is binomial(i,j), or 0 for i<j
      % STACK: [1 1 1 1;
                0 1 2 3;
                0 0 1 3;
                0 0 0 1]
S     % Sort each column
      % STACK: [0 0 0 1;
      %         0 0 1 1;
      %         0 1 1 3;
      %         1 1 2 3]
Xz    % Keep only nonzeros. Gives a column vector
      % STACK: [1; 1; 1; 1; 1; 2; 1; 1; 3; 3]
G)    % Get the n-th element. Implicitly display
      % STACK: 1

```
> 1 votes

# Answer
# Java 8, 187 bytes

```
n->{int r=~-(int)Math.sqrt(8*n+1)/2+1,a[]=new int[r],k=r,x=0;for(;k-->0;a[k]=p(r,k))x+=k;java.util.Arrays.sort(a);return a[n-x];}int p(int r,int k){return--r<1|k<2|k>r?1:p(r,k-1)+p(r,k);}

```

**Explanation:**

Try it online.

```
n->{                   // Method with integer as both parameter and return-type
  int r=~-(int)Math.sqrt(8*n+1)/2+1,
                       //  Calculate the 1-indexed row based on the input
      a[]=new int[r],  //  Create an array with items equal to the current row
      k=r,             //  Index integer
      x=0;             //  Correction integer
  for(;k-->0;          //  Loop down to 0
    a[k]=p(r,k))       //   Fill the array with the Pascal's Triangle numbers of the row
    x+=k;              //   Create the correction integer
  java.util.Arrays.sort(a);
                       //  Sort the array
  return a[n-x];}      //  Return the `n-x`'th (0-indexed) item in this sorted array

// Separated recursive method to get the k'th value of the r'th row in the Pascal Triangle
int p(int r,int k){return--r<1|k<2|k>r?1:p(r,k-1)+p(r,k);}

```
> 1 votes

# Answer
## Batch, 128 bytes

```
@set/as=2,t=r=m=i=1
:l
@if %1 geq %t% set/as+=r,t+=r+=1&goto l
@for /l %%i in (%s%,2,%1)do @set/ar-=1,m=m*r/i,i+=1
@echo %m%

```

0-indexed.
> 1 votes

# Answer
# 05AB1E, 10 bytes

0-indexed

```
ÝεDÝc{}˜sè

```

Try it online!

**Explanation**

```
Ý             # push range [0 ... input]
 ε    }       # apply to each element
  DÝc         # N choose [0 ... N]
     {        # sort
       ˜      # flatten result to a list
        sè    # get the element at index <input>

```
> 1 votes

# Answer
# Jelly, 11 bytes

```
Ḷc€`Ṣ€Fḟ0ị@

```

**Try it online!**

A monadic link taking the index and returning an integer - uses 1-based indexing.

### How?

Performs the challenge pretty much just as it is written, just with more of the right of Pascal's triangle (zeros) which is then thrown away...

```
Ḷc€`Ṣ€Fḟ0ị@ - Link: integer, i    e.g. 1   or    9
Ḷ           - lowered range            [0]       [0,1,2,3,4,5,6,7,8]
   `        - repeat left as right arg [0]       [0,1,2,3,4,5,6,7,8]
 c€         - binomial choice for €ach [[1]]     [[1,0,0,0,0,0,0,0,0],[1,1,0,0,0,0,0,0,0],[1,2,1,0,0,0,0,0,0],[1,3,3,1,0,0,0,0,0],[1,4,6,4,1,0,0,0,0],[1,5,10,10,5,1,0,0,0],[1,6,15,20,15,6,1,0,0],[1,7,21,35,35,21,7,1,0],[1,8,28,56,70,56,28,8,1]]
    Ṣ€      - sort €ach                [[1]]     [[0,0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,1,1],[0,0,0,0,0,0,1,1,2],[0,0,0,0,0,1,1,3,3],[0,0,0,0,1,1,4,4,6],[0,0,0,1,1,5,5,10,10],[0,0,1,1,6,6,15,15,20],[0,1,1,7,7,21,21,35,35],[1,1,8,8,28,28,56,56,70]]
      F     - flatten                  [1]       [0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,1,2,0,0,0,0,0,1,1,3,3,0,0,0,0,1,1,4,4,6,0,0,0,1,1,5,5,10,10,0,0,1,1,6,6,15,15,20,0,1,1,7,7,21,21,35,35,1,1,8,8,28,28,56,56,70]
       ḟ0   - filter discard zeros     [1]       [1,1,1,1,1,2,1,1,3,3,1,1,4,4,6,1,1,5,5,111,1,6,6,15,15,21,1,7,7,21,21,35,35,1,1,8,8,28,28,56,56,70]
         ị@ - index into (sw@p args)    1         3 --------------^

```
> 1 votes

# Answer
# Red, 206 bytes

```
f: func[n][t: copy[[1]]l: 0
while[l < n][a: copy last t insert append a 0 0 b: copy[]repeat i k:(length? a)- 1[append b a/(i) + a/(i + 1)]append t reduce[b]l: l + k]foreach p t[sort p]pick split form t{ }n]

```

1-based

Try it online!

## Explanation:

```
f: func [n] [
    t: copy [[1]]                       ; start with a list with one sublist [1]
    l: 0                                ; there are 1 items overall
    while [l < n] [                     ; while the number of items is less than the argument
        a: copy last t                  ; take the last sublist
        insert append a 0 0             ; prepend and append 0 to it
        b: copy []                      ; prepare a list for the sums
        repeat i k: (length? a) - 1 [   ; loop throught the elements of the list
            append b a/(i) + a/(i + 1)] ; and find the sum of the adjacent items
        append t reduce [b]             ; append the resulting list to the total list
        l: l + k                        ; update the number of the items
    ]
    foreach p t [sort p]                ; sort each sublist
    v: pick split form t { } n          ; flatten the list and take the n-th element
]

```
> 1 votes

# Answer
# Perl, 48 bytes

Includes `+1` for `p`

```
perl -pe '$_-=$%until$_<++$%;$./=$_/--$%for 1..$_/2;$_=$.' <<< 19

```

Uses base 0 indexing.
> 1 votes

# Answer
# , ~~43~~ 38 bytes

```
](([-2!]){/:~@(i.!<:)@])[:<.2&!@,:^:_1

```

Try it online!

0-indexed

Notes:

* `<.2&!@,:^:_1` gives the relevant row number of Pascal's triangle by rounding down the inverse of `y choose 2`.
* `/:~@(i.!<:)@]` calculates the row and sorts it.
* `[-2!]` gives the index into the row.
> 1 votes

# Answer
# Julia, 70 bytes

```
f(x)=map(n->binomial(n-1,ceil(Int,x/2-(n^2-n)/4-1)),round(Int,√(x*2)))

```

1-based

Explanation:

it first find the row number, then the column number, then compute the binomial
> 1 votes

# Answer
# Vyxal, 9 bytes

```
ʀƛʀƈs;f$i

```

Try it Online!

No efficiency at all. 0-indexed.

```
ʀ         # 0...n
 ƛ   ;    # Mapped to...
  ʀ       # 0...n
   ƈ      # Binomial coefficient with n, vectorised
    s     # Sort these
      f   # Flatten
       $i # Index input into this.

```
> 1 votes

# Answer
# Thunno 2, 8 bytes

```
ĖDȷc€ṠḞi

```

Try it online!
or see the interpreter complaining (explained below)

#### Explanation

```
ĖDȷc€ṠḞi  # Implicit input
Ė         # Push [0..input]
 Dȷc      # Outer product over ncr with itself
          # NOTE: the interpreter actually tries to calculate all the
          #       values: [0C0, 0C1, 0C2, ..., (input)C(input)], but
          #       fails for the ones where r > n. It silently carries
          #       on, ignoring those values, so we end up with input+1
          #       rows of Pascal's triangle :D. However, if you add
          #       the w (warnings) flag, you'll see all the errors
          #       which were caught by the interpreter (link above)
    €Ṡ    # Sort each row of the triangle
      Ḟ   # Flatten the list of lists
       i  # Index in using the input
          # Implicit output

```
> 1 votes

# Answer
# Vyxal `M`, 7 bytes

```
ƛʀƈs;fi

```

Try it Online!

#### Explanation

```
ƛʀƈs;fi  # Implicit input
ƛ   ;    # Map over [0..input]
 ʀƈ      #  nCr with each of [0..that]
   s     #  Sort the resulting list
     f   # Flatten the list of lists
      i  # Index in using the input
         # Implicit output

```
> 1 votes

# Answer
# Jelly, 17 bytes

```
1+2\1,1j$$Ð¡Ṣ€Ẏ⁸ị

```

Try it online!
> 0 votes

# Answer
# Pyth, 15 bytes

```
@u+GSm.cHdhHhQY

```

0-indexed

Try it

### Explanation

```
@u+GSm.cHdhHhQY
 u          hQY   Reduce on [0, ..., input], starting with the empty list...
  +G              ... append to the accumulator...
    Sm.cHdhH      ... the sorted binomial coefficients.
@              Q  Take the 0-indexed element.

```
> 0 votes

# Answer
# Clean, 80 bytes

```
import StdEnv

```

#

```
\n=flatten[sort[prod[j+1..i]/prod[1..i-j]\\j<-[0..i]]\\i<-[0..]]!!n

```

Try it online!

As a lambda function.
> 0 votes

# Answer
# C (gcc), ~~140~~ 123 bytes

```
F(n){n=n?n*F(~-n):1;}f(n,j,k,c){for(c=j=0;j<n;j++)for(k=0;k<=j/2;k++)if(++c==n||j&1|k-j/2&&++c==n)return F(j)/F(k)/F(j-k);}

```

Try it online!
> 0 votes

# Answer
# Actually, 8 bytes

Largely based on Jonathan Allan's Jelly answer. Uses 0-indexing.

```
;r♂╣♂SΣE

```

Try it online!

**Ungolfing**

```
          Implicit input n.
;         Duplicate n.
 r        Lowered range. [0..n-1].
  ♂╣      Pascal's triangle row of every number.
    ♂S    Sort every row.
      Σ   Sum each row into one array.
       E  Get the n-th element of the array (0-indexed).
          Implicit return.

```
> 0 votes

# Answer
# Ruby, 56 bytes

```
->n{a=0;n-=a until n<a+=1;[*2..a].combination(n/2).size}

```

0-based

First get the row and column in the triangle, then calculate the binomial coefficient corresponding to that position.

Try it online!
> 0 votes

# Answer
# Coconut, 69 bytes

```
def g(n,r=[1])=r[n:]and r[n//2]or g(n-len(r),[*map((+),[0]+r,r+[0])])

```

Try it online!
> 0 votes

# Answer
# Pari/GP, 47 bytes

```
n->concat([vecsort(Vec((1+x)^i))|i<-[0..n]])[n]

```

Try it online!
> 0 votes

# Answer
# Pyth, 12 bytes

```
@smS.cMm,dkh

```

Try it online!
> 0 votes

# Answer
# Julia 1.0, 45 bytes

```
!n=[(0:n.|>i->sort(binomial.(i,0:i)))...;][n]

```

Try it online!

1-indexed

computes the complete Pascal triangle up to line n, sorts all the lines, flattens everything and returns the n-th element. It's highly inefficient, and computing `√(2n)` lines would be enough but that would add so many bytes (8)
> 0 votes

---
Tags: code-golf, sequence, number-theory
---


# Question
Title: AGM Series Hole 1: Calculate the Arithmetic–Geometric Mean
*This question was inspired by this HNQ.*

## About the series

This question is now part of a series about the AGM method. This first post in the series will be about actually calculating the `AGM`. You may treat this like any other code golf challenge, and answer it without worrying about the series at all. However, there is a leaderboard across all challenges.

## What is the Arithmetic–Geometric Mean

The Arithmetic–Geometric Mean of two numbers is defined as the number that repeatedly taking the arithmetic and geometric means converges to. Your task is to find this number after some `n` iterations.

## Clarifications

* You take three numbers, `a, b, n` in any reasonable format.
* For `n` iterations, take the arithmetic and geometric mean of `a` and `b` and set those to `a` and `b`.
* For two numbers `a` and `b`, the arithmetic mean is defined as `(a + b) / 2`.
* The geometric mean is defined as `√(a * b)`.
* `a` and `b` should be approaching each other.
* Then, output both `a` and `b`.
* You don't have to worry about float imprecision and such.
* This is so shortest code in **bytes** wins!

## Test Cases

```
[0, [24, 6]] -> [24, 6]
[1, [24, 6]] -> [15.0, 12.0]
[2, [24, 6]] -> [13.5, 13.416407864998739]
[5, [24, 6]] -> [13.458171481725616, 13.458171481725616]
[10, [100, 50]] -> [72.83955155234534, 72.83955155234534]

The next one is 1/Gauss's Constant:
[10, [1, 1.41421356237]] -> [1.198140234734168, 1.1981402347341683]

```

## Leaderboard

*Stolen from Martin's series.*

The following snippet will generate a leaderboard across all challenges of the series.

To make sure that your answers show up, please start every answer with a headline, using the following Markdown template:

```
# Language Name, N bytes

```

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

```
# Ruby, <s>104</s> <s>101</s> 96 bytes

```

```
/* Configuration */

var QUESTION_IDs = [66068]; // Obtain this from the url
// It will be like http://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!.FjwQBrX2KXuFkv6p2lChi_RjzM19";

/* App */

var answers = [], page = 1, currentQ = -1;

function answersUrl(index) {
  return "http://api.stackexchange.com/2.2/questions/" +  QUESTION_IDs.join(";") + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function getAnswers() {
  $.ajax({
    url: answersUrl(page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      if (data.has_more) getAnswers();
      else process();
    }
  });
}

getAnswers();

var SIZE_REG = /\d+(?=[^\d&]*(?:<(?:s>((?!>).)*<\/s>|((?!>).)+>)[^\d&]*)*$)/;
var NUMBER_REG = /\d+/;
var LANGUAGE_REG = /^#*\s*([^\n,]+)(?=,)/;//

function shouldHaveHeading(a) {
  var pass = false;
  var lines = a.body_markdown.split("\n");
  try {
    pass |= /^#/.test(a.body_markdown);
    pass |= ["-", "="]
              .indexOf(lines[1][0]) > -1;
    pass &= LANGUAGE_REG.test(a.body_markdown);
  } catch (ex) {}
  return pass;
}

function shouldHaveScore(a) {
  var pass = false;
  try {
    pass |= SIZE_REG.test(a.body_markdown.split("\n")[0]);
  } catch (ex) {}
  if (!pass) console.log(a);
  return pass;
}

function getAuthorName(a) {
  return a.owner.display_name;
}

function getAuthorId(a) {
  return a.owner.user_id;
}

function process() {
  answers = answers.filter(shouldHaveScore)
                   .filter(shouldHaveHeading);
  answers.sort(function (a, b) {
    var aB = +(a.body_markdown.split("\n")[0].match(SIZE_REG) || [Infinity])[0],
        bB = +(b.body_markdown.split("\n")[0].match(SIZE_REG) || [Infinity])[0];
    return aB - bB
  });

  var users = {};
  answers.forEach(function (a) {
    var headline = a.body_markdown.split("\n")[0];
    var question = QUESTION_IDs.indexOf(a.question_id);
    var size = parseInt((headline.match(SIZE_REG)||[0])[0]);
    var language = headline.match(LANGUAGE_REG)[1];
    var user = getAuthorName(a);
    var userId = getAuthorId(a);
    if (!users[userId]) users[userId] = {name: user, nAnswer: 0, answers: []};
    if (!users[userId].answers[question]) {
      users[userId].answers[question] = {size: Infinity};
      users[userId].nAnswer++;
    }
    if (users[userId].answers[question].size > size) {
      users[userId].answers[question] = {size: size, link: a.share_link}
    }
  });

  var sortedUsers = [];
  for (var userId in users)
    if (users.hasOwnProperty(userId)) {
      var user = users[userId];
      user.score = 0;
      user.completedAll = true;
      for (var i = 0; i < QUESTION_IDs.length; ++i) {
        if (user.answers[i])
          user.score += user.answers[i].size;
        else
          user.completedAll = false;
      }
      sortedUsers.push(user);
    }

  sortedUsers.sort(function (a, b) {
    if (a.nAnswer > b.nAnswer) return -1;
    if (b.nAnswer > a.nAnswer) return 1;
    return a.score - b.score;
  });

  var place = 1;
  for (var i = 0; i < sortedUsers.length; ++i) {
    var user = sortedUsers[i];
    var row = '<tr><td>'+ place++ +'.</td><td>'+user.name+'</td>';
    for (var j = 0; j < QUESTION_IDs.length; ++j) {
      var answer = user.answers[j];
      if (answer)
        row += '<td><a href="'+answer.link+'">'+answer.size+'</a></td>';
      else
        row += '<td class="missing"></td>';
    }
    row += '<td></td>';
    if (user.completedAll)
      row += '<td class="total">'+user.score+'</td>';
    else
      row += '<td class="total missing">'+user.score+'</td>';
    row += '</tr>';
    $("#users").append(row);
  }
}
```

```
body { text-align: left !important}

#leaderboard {
  width: 500px;
}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}

td.total {
  font-weight: bold;
  text-align: right;
}

td.missing {
  background: #bbbbbb;
}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="leaderboard">
  <h2>Leaderboard</h2>
  <p>
    Missing scores are shown as grey cells. A grey total indicates that the user has not participated in all challenges and is not eligible for the overall victory yet.
  </p>
  <table class="_user-list">
    <thead>
      <tr><td></td><td>User</td>
        <td><a href="http://codegolf.stackexchange.com/q/66068">#1</a></td>
        <td></td><td>Total</td>
      </tr>
    </thead>
    <tbody id="users">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
```

# Answer
> 10 votes
## CJam, 16 bytes

```
{{_2$+2/@@*mq}*}

```

Takes input on the stack as `a b n` where `a` and `b` are doubles. Online demo

# Answer
> 9 votes
# Dyalog APL, ~~22~~ ~~21~~ 15 bytes

```
.5∘(+.×,×.*⍨)⍣⎕

```

Takes (*a*,*b*) as right argument, and prompts for *n*:

`(`

`+.×` dot product of 0.5 and the right argument

`,` followed by

`×.*⍨` "dot power" of the right argument and 0.5*

`)⍣⎕` applied numeric-prompt times.

* "dot power" is like dot product, but using multiplication and power instead of plus and multiplication, as follows:

*n*
`A ×.*⍨ B` is  *BiA* =  *B*1*AB*2*A*
*i*=1

-3 bytes thanks to ngn.

---

Old version:

```
{((+/÷≢),.5*⍨×/)⍣⍺⊢⍵}

```

Takes `n` as left argument and `a b` as right argument.

`⊢⍵` On the RightArg
`(`...`)⍣⍺` recalculate LeftArg times
`(+/÷≢)` sum divided by tally
`,` followed by
`.5*⍨×/` the square root of the product.

All the test cases:

```
      f←{((.5×+/),.5*⍨×/)⍣⍺⊢⍵}
      0 1 2 5 10 10 f¨ (24 6)(24 6)(24 6)(24 6)(100 50)(1,2*.5)
┌────┬─────┬────────────────┬───────────────────────┬───────────────────────┬───────────────────────┐
│24 6│15 12│13.5 13.41640786│13.45817148 13.45817148│72.83955155 72.83955155│1.198140235 1.198140235│
└────┴─────┴────────────────┴───────────────────────┴───────────────────────┴───────────────────────┘

```

# Answer
> 7 votes
## TI-BASIC, 22 bytes

```
Input N
For(I,1,N
{mean(Ans),√(prod(Ans
End
Ans

```

Does exactly what the algorithm says. Takes N from the prompt, and A and B through `Ans` as a two-element list.

If N is 0, the `For(` loop is skipped entirely.

# Answer
> 6 votes
# JavaScript ES7, ~~48~~ 43 bytes

-5 thanks to Downgoat!

```
f=(n,a,b)=>n?f(n-1,(a+b)/2,(a*b)**.5):[a,b]

```

Very simple recursive function.

# Answer
> 6 votes
# MATLAB/Octave, ~~69~~ 65 bytes

```
function [a,b]=r(a,b,n)
for i=1:n;j=(a+b)/2;b=(a*b)^.5;a=j;end

```

# Answer
> 6 votes
# Jelly, 9 bytes

```
SH;P½¥ðṛ¡

```

Try it online!

### How it works

```
SH;P½¥ðṛ¡    Input: x (vector) -- y (repetitions)

SH           Take the sum (S) of x and halve (H) the result.
   P½        Take the product (P) of x and the square root (½) of the result.
     ¥       Combine the last two instructions in a dyadic chain.
  ;          Concatenate the results to the left and to the right.
      ð      Push the preceding, variadic chain; begin a new, dyadic chain.
       ṛ     Return the right argument (y).
        ¡    Repeat the pushed chain y times.

```

# Answer
> 5 votes
## C++, ~~108~~ ~~102~~ 100 bytes

Thank you to @RetoKoradi and @AlexA for saving me 6 bytes.

This is non-competitive, because C++ is not a good golfing language. Did this for fun :)

```
#include<cmath>
std::string f(float a,float b,int n){return n==0?a+" "+b:f((a+b)/2,sqrt(a*b),n-1);}

```

This is a simple recursion function, very similar to the JS answer.

# Answer
> 4 votes
# K5, 15 bytes

Very literal:

```
{(+/x%2;%*/x)}/

```

In action:

```
 {(+/x%2;%*/x)}/[0; 24 6]
24 6
 {(+/x%2;%*/x)}/[5; 24 6]
1.345817e1 1.345817e1

```

Unfortunately, this does not work in oK because that interpreter does not currently support projection (currying) of adverbs. Works in the real k5.

In oK, it would currently be necessary to wrap the definition in a lambda:

```
  {x{(+/x%2;%*/x)}/y}[5; 24 6]
13.4582 13.4582

```

# Answer
> 4 votes
# J,  ~~18~~ 13 bytes

```
-:@+/,%:@*/^:

```

Usage:

```
   agm =: -:@+/,%:@*/^:
   5 agm 24 6
13.4582 13.4582

```

# Answer
> 4 votes
## Seriously, 11 bytes

```
,p`;π√@æk`n

```

Hex Dump:

```
2c70603be3fb40916b606e

```

Try it online

Explanation:

```
,                    Read in the list as [n,a,b]
 p                   pop list to yield: n [a,b]
  `      `n          Push a quoted function and run it n times.
   ;                 Duplicate [a,b] pair
    π√               Compute its product and square root it (GM)
      @              Swap the other copy of the pair to the top
       æ             Compute its mean.
        k            Compile the stack back into a list.

```

# Answer
> 3 votes
# Japt, 24 bytes ~~25 33~~

*Saved 9 ~~7~~ bytes thank to @ETHproductions*

```
Uo r@[VW]=[V+W /2(V*W q]

```

Takes advantage of ES6 destructuring.

Try it online

### Ungolfed && Explanation

```
Uo r@[VW]=[V+W /2(V*W q]

       // Implicit: U: 1st input, V: 2nd input, W: 3rd input
Uo     // Range from 0 to 1st input
r@     // Loop over range
  [V,W]=    // Set 2nd and 3rd input to...
   [V+W /2,   // Add 2nd and 3rd inputs, divide by 2
   (V*W q]    // Multiple 2nd and 3rd inputs, find square root
            // Set's to the above respectively
       // Implicit: return [V,W]

```

# Answer
> 3 votes
# Pyth, 12

```
u,.OG@*FG2EQ

```

Test Suite

### Explanation

```
u,.OG@*FG2EQ    ##  implicit: Q = eval(input())
u         EQ    ##  reduce eval(input()) times, starting with Q
                ##  the reduce lambda has G as the previous value and H as the next
  .OG           ##  arithmetic mean of last pair
     @*FG2      ##  geometric mean of last pair, uses *F to get the product of the list
                ##  and @...2 to get the square root of that
 ,              ##  join the two means into a two element list

```

# Answer
> 3 votes
# Matlab, 54 bytes

```
function x=f(x,n)
for k=1:n
x=[mean(x) prod(x)^.5];end

```

Example:

```
>> f([24 6], 2)
ans =
  13.500000000000000  13.416407864998739

```

# Answer
> 2 votes
# Minkolang v0.14, 23 bytes

Try it here!

```
$n[$d+2$:r*1Mi2%?!r]$N.
$n                      C get all input C
  [                ]    C pop N; repeat inner N times C
   $d                   C duplicate stack [1,2] => [1,2,1,2] C
     +                  C add top two elements C
      2$:               C divide by two C
         r              C reverse stack (get the other two) C
          *             C multiply them together C
           1M           C take square root C
             i2%?!r     C reverse the stack if an odd step number C
                    $N  C output stack
           1M           C take square root C
             i          C get step in for loop C

```

# Answer
> 2 votes
# Python 3, ~~65~~ 55 bytes

Thanks to mathmandan for pointing out a shorter version using the `lambda` operator.

```
f=lambda a,b,n:f((a+b)/2,(a*b)**.5,n-1)if n else(a,b)

```

## My original version:

```
def f(a,b,n):
 if n:f((a+b)/2,(a*b)**.5,n-1)
 else:print(a,b)

```

To my chagrin, a recursive function (a la the JavaScript and C++ answers) was shorter than a simple for loop.

# Answer
> 2 votes
# Pyth, 15 bytes

```
u,^*FG.5csG2vzQ

```

# Answer
> 2 votes
# Mathematica, ~~31~~ 30 bytes

Saved one byte thanks to Martin Büttner.

```
{+##/2,(1##)^.5}&@@#&~Nest~##&

```

Usage:

```
In[1]:= {+##/2,(1##)^.5}&@@#&~Nest~##&[{24, 6}, 5]

Out[1]= {13.4582, 13.4582}

```

# Answer
> 2 votes
# R, 66 bytes

```
f=function(a,b,n){while(n){x=(a+b)/2;b=(a*b)^.5;n=n-1;a=x};c(a,b)}

```

Usage:

```
> f(24,6,0)
[1] 24  6
> f(24,6,1)
[1] 15 12
> f(24,6,2)
[1] 13.50000 13.41641
> f(24,6,3)
[1] 13.45820 13.45814
> f(24,6,4)
[1] 13.45817 13.45817
> f(100,50,10)
[1] 72.83955 72.83955
> f(1,1.41421356237,10)
[1] 1.19814 1.19814

```

# Answer
> 1 votes
# Lua, 62 bytes

```
n,a,b=...for i=1,n do a,b=(a+b)/2,math.sqrt(a*b)end print(a,b)

```

Uses command line arguments from `...` to assign to `n`, `a` and `b`, a nifty trick I learned about Lua recently.

# Answer
> 1 votes
# Python 2, 62 61 62 bytes

```
def f(a,b,n):
 while n:a,b=(a+b)/2.,(a*b)**.5;n-=1
 print a,b

```

# Answer
> 1 votes
# Haskell, 47 Bytes

```
f a b 0=(a,b)
f a b n=f((a+b)/2)(sqrt$a*b)(n-1)

```

# Answer
> 1 votes
## Haskell, 40 bytes

```
(!!).iterate(\(a,b)->((a+b)/2,sqrt$a*b))

```

An anonymous function. Example usage:

```
>> let f=(!!).iterate(\(a,b)->((a+b)/2,sqrt$a*b)) in f (1.0,1.41421356237) 10
(1.198140234734168,1.1981402347341683)

```

The lambda function `(\(a,b)->((a+b)/2,sqrt$a*b))` takes the arithmetic and geometric mean on a tuple. This is iterated starting with the first input (a tuple), and then `(!!)` indexes the second input to specify the number of iterations.

# Answer
> 1 votes
# Perl, 60 bytes

```
perl -ape'F=($F[0]/2+$F[1]/2,sqrt$F[0]*$F[1])for 1..shift@F;$_="@F"'

```

**N.B.:** Per this meta post, I *believe* I've got the scoring correct. The actual code (between single quotes) is 58 characters, then I added +2 for `a` and `p` flags as that's the difference from the shortest invocation, `perl -e'...'`

### Vague complaints

I have this nagging feeling I'm missing an obvious improvement. I know, "welcome to code golf", but I mean *more than usual* I believe there's an easy opportunity to shorten this.

Early on, I had messed around with using `$\` as the second term with some success, but the above approach ended up being 2 bytes shorter, even with the extra `ap` flags required. Similarly, avoiding the explicit `$_` assignment would be nice, but the loop makes that difficult.

The `shift@F` bugs me, too; if I don't do it that way, though (or use `@F=(0,...,...)` instead, which doesn't save any bytes), there's an off-by-one error with the `@F` assignment.

### Example

```
echo 5 24 6 | perl -ape'F=($F[0]/2+$F[1]/2,sqrt$F[0]*$F[1])for 1..shift@F;$_="@F"'

```

### Outputs

```
13.4581714817256 13.4581714817256

```

# Answer
> 1 votes
# Julia, 49 bytes

```
(a,b,n)->(for i=1:n;a,b=(a+b)/2,√(a*b)end;(a,b))

```

Pretty direct iterative algorithm. Using the symbol and the multiple return saves a few bytes, but the for loop syntax costs a few.

# Answer
> 1 votes
# Julia, 42 bytes

```
f(a,b,n)=n>0?f((a+b)/2,(a*b)^.5,n-1):(a,b)

```

This is a recursive function `f` that accepts three numbers and returns a tuple.

Ungolfed:

```
function f(a::Real, b::Real, n::Integer)
    if n > 0
        # Recurse on the arithmetic and geometric means, decrementing n
        return f((a + b) / 2, sqrt(a * b), n - 1)
    else
        # Return the pair
        return (a, b)
    end
end

```

# Answer
> 1 votes
# LabVIEW, 21 LabVIEW Primitives

Primitives counted as per this meta post.

pretty staightforward not much to explain.

# Answer
> 1 votes
# CJam, 16 bytes

```
{{_:+2/\:*mq]}*}

```

This is an anonymous function. The input is a list with the two values (as doubles), followed by the iteration count. Try it online with I/O code for testing.

I wouldn't normally have posted this because @PeterTaylor posted an equally long CJam answer before I saw the question. But since this is advertised as the start of a series, I wanted to keep my options open in case the series is interesting.

While the length is the same as Peter's answer, the code is not. I chose a different input format by taking the two values in a list, where Peter used separate values. So while there's not much to it with either input format, the code looks quite different.

```
{     Start loop over number of iterations.
  _     Copy the current pair of values.
  :+    Reduce pair with + operator.
  2/    Divide by 2.
  \     Swap second copy of pair to top.
  :*    Reduce pair with * operator.
  mq    Calculate square root.
  ]     Wrap the two new values in a list for next iteration.
}*    End iteration loop.

```

# Answer
> 1 votes
# \>\<\> (Fish), 66 bytes

Uses newtons method to approximate the square root in 15 steps

```
iii>:?v~naon;
*&f:?v\1-@:&$:@$:@+2,@
$@:$@//,2+,@:
4{~$~/\@@1-21.0

```

Try it

# Answer
> 1 votes
# Scala, 58 bytes

Golfed version. Try it online!

```
(n,a,b)=>if(n>0)f(n-1,(a+b)/2,Math.sqrt(a*b))else s"$a,$b"

```

# Answer
> 1 votes
# Thunno 2, 6 bytes

```
{[m;pƭ

```

Try it online!

Takes input on the stack. This default was +11/-5 at the time of posting (Wayback Machine).

#### Explanation

```
{[m;pƭ  # Implicit input
{       # First input no. times:
 [ ;    #  Parallelly apply:
  m     #   Arithmetic mean
    pƭ  #   Square root of product
        # Implicit output

```

# Answer
> 1 votes
# Go, ~~95~~ 92 bytes

```
import(."math";."fmt")
func f(n,a,b float64){for;n>0.;n--{a,b=(a+b)/2,Sqrt(a*b)}
Print(a,b)}

```

Attempt This Online!

Prints to STDOUT, with a space separating the means.

The explicitly looped solution is the same length as the recursive solution, funnily enough (all byte savings from making it recursive is lost by needing an extra `else{}` block to prevent output when `n>0`).

* -3 by @The Thonnu

# Answer
> 0 votes
# Perl 6,  ~~53~~  47 bytes

```
{(($^a,$^b),->(\a,\b){((a+b)/2,sqrt(a*b))}...*)[$^n]} # 53 bytes

```

usage:

```
# give it a name
my &code = {(($^a,$^b),->(\a,\b){((a+b)/2,sqrt(a*b))}...*)[$^n]}

say code 100,50,10;          # (72.8395515523453 72.8395515523453)
say code 1,1.41421356237,10; # (1.19814023473417 1.19814023473417)

```

---

If I change the input from `a,b,n` to `(a,b),n` I can save a few bytes.

```
{($^l,->(\a,\b){((a+b)/2,sqrt(a*b))}...*)[$^n]} # 47 bytes

```

usage:

```
my &code = {($^l,->(\a,\b){((a+b)/2,sqrt(a*b))}...*)[$^n]}

say code (100,50),10;          # (72.8395515523453 72.8395515523453)
say code (1,1.41421356237),10; # (1.19814023473417 1.19814023473417)

say code (24,6),$_ for 0,1,2,5;
# (24 6)
# (15 12)
# (13.5 13.4164078649987)
# (13.4581714817256 13.4581714817256)

```

```
{
  (
    $^l,          # first 2 element tuple
    ->            # pointy block (lambda)
      (\a,\b)     # take a single tuple, and give its 2 elements each a name
    {
      (           # create a 2 element tuple
        (a+b)/2,  # arithmetic mean
        sqrt(a*b) # geometric mean
      )
    } ... *       # create a lazy infinite sequence of tuples
  )[ $^n ]        # take the nth "tuple" from the outer sequence
}

```

---

Really I would swap out the `... *` with `... -> (\a,\b) { a =~= b }`, then there would be no need for the `$^n` parameter.
( do not use `==` instead of `=~=`, or it may not stop )

```
my &code = {($^l,->(\a,\b){((a+b)/2,sqrt(a*b))}...->(\a,\b){a=~=b})[*-1]}

say code (24,6);           # (13.4581714817256 13.4581714817256)
say code (100,50);         # (72.8395515523453 72.8395515523453)
say code (1,1.41421356237) # (1.19814023473417 1.19814023473417)

```

# Answer
> 0 votes
# Prolog, 80 bytes

**Code:**

```
p(A,B,0):-write([A,B]).
p(A,B,N):-X is(A+B)/2,Y is sqrt(A*B),M is N-1,p(X,Y,M).

```

**Example:**

```
p(100,50,10).
[72.83955155234534, 72.83955155234534]

```

Try it online here

# Answer
> 0 votes
# Java, ~~103~~ ~~96~~ 84 bytes

```
String f(int n,double a,double b){return n>0?f(n-1,(a+b)/2,Math.sqrt(a*b)):a+","+b;}

```

Verify all testcases.

Old version (96 bytes):

```
String f(int n,double a,double b){for(;n>0;a=(a+b)/2,b=Math.sqrt((b-2*a)*b))n--;return a+","+b;}

```

Old version (103 bytes):

```
String f(int n,double a,double b){double t;for(;n>0;t=(a+b)/2,b=Math.sqrt(a*b),a=t)n--;return a+","+b;}

```

# Answer
> 0 votes
# Vyxal, 6 bytes

```
(₌ṁΠ√W

```

Try it Online!

The obvious 6 byte solution

## Explained

```
(₌ṁΠ√W
(       # n times:
 ₌ṁ     #   Push the mean of the top of the stack
 ₌ Π    #   And the product of the top of the stack
    √   #   Square root that product
     W  #   And wrap into a list

```

Created with the help of Luminespire.

---
Tags: code-golf, math, number-theory
---


title: Tut-tut-tut-tut-tut

text:
# Question
Title: Tut-tut-tut-tut-tut
The string `tut-tutut-tut-tuttut-tut` can be constructed with overlapping or concatenated instances of the word `tut-tut`:

```
tut-tutut-tut-tuttut-tut
tut-tut
      tut-tut
          tut-tut
                 tut-tut

```

The string `tut-tututut-tutut-tut` cannot:

```
tut-tututut-tutut-tut
tut-tut^
       |tut-tut
       |      tut-tut
       |
this u is unaccounted for

```

Given a string, determine whether it's constructed of overlapping or concatenated instances of the word `tut-tut`. Where two or more `tut-tut` strings overlap they must share the same letters in the same positions.

### Rules

* Standard I/O rules apply. You can use any two *distinct, consistent* values to distinguish the true and false cases.
* You may assume the input strings are nonempty and only contain lowercase ASCII letters and `-`.
* This is code golf, shortest code in bytes wins.

### Test Cases

True:

```
tut-tut
tut-tut-tut
tut-tutut-tut
tut-tuttut-tut
tut-tut-tut-tut-tut
tut-tutut-tut-tutut-tut
tut-tutut-tut-tuttut-tut
tut-tut-tutut-tuttut-tut
tut-tuttut-tutut-tut-tutut-tut

```

False:

```
x
tut
tut-
-tut
t-tut
tu-tut
tut-tutx
tut-tutt
xtut-tut
ttut-tut
tutut-tut
tut-tu-tut
tut-tuttut
tuttut-tut
tut-tut-tutt
tut-tutt-tut
tut-tuttut-tu
tut-tututut-tut
tut-tuttuttut-tut
tut-tututut-tutut-tut

```

# Answer
# Regex (POSIX ERE / RE2 or better), ~~23~~ ~~21~~ 20 bytes

```
^\b((t?\But)?-tut)+$

```

Based on regexes by thejonymyster and Bubbler.

Try it on regex101! \- RE2
Try it online! \- GNU ERE (Bash + egrep)
Try it online! \- ECMAScript
Try it online! \- Perl
Try it online! \- Raku`:P5`
Try it online! \- PCRE
Try it online! \- Java
Try it online! – Try It Online") - Boost
Try it online! \- Python
Try it online! \- Ruby
Try it online! \- .NET

```
^            # Anchor to start of string.
\b           # Assert there is a word boundary here. Given the context, this is
             # equivalent to asserting that the first character isn't "-".
(
    (
        t?   # Optionally match and consume "t".
        \B   # Assert that this is not a word boundary. Given the context, this
             # is equivalent to asserting that the string does not start here.
        ut   # Match and consume "ut".
    )?       # Optionally match the above.
    -tut     # Match and consume "-tut".
)+           # Iterate the above as many times as possible, minimum one.
$            # Assert we've reached the end of the string.

```

Alternative 20 bytes:

```
^(tut-(tu\Bt?)?)+\b$

```

Try it on regex101! \- RE2
Try it online! \- ECMAScript
Try it online! \- PCRE

This version doesn't work properly in GNU ERE; it matches `tut-tuttut-tu`. This appears to be a bug in GNU ERE, and is still present in the latest version. Note that `^(a\Bb?){2}$` incorrectly matches `aba`:

Try it online! \- GNU ERE (bug) / Attempt This Online! (bug)
Try it online! \- PCRE (no bug)

But `^a\Bb?a\Bb?$` correctly doesn't match `aba`:

Try it online! \- GNU ERE / Attempt This Online!

21 bytes without word-boundary assertions (GNU ERE or better):

```
^(tut-(tut?|))+tut$\2

```

21 bytes without word-boundary assertions or backreferences (ECMAScript or better):

```
^(?=t)((t?ut)?-tut)*$

```

## Regex (ECMAScript or better), 22 bytes

```
^((?=tut-tut).{1,7})*$

```

Try it online! \- ECMAScript
Try it online! \- Perl
Try it online! \- Raku`:P5`
Try it online! \- PCRE
Try it online! \- Java
Try it online! \- Boost
Try it online! \- Python
Try it online! \- Ruby
Try it online! \- .NET

```
^                 # Anchor to start of string
(
    (?=tut-tut)   # Assert that the following 7 characters match "tut-tut",
                  # without consuming them.
    .{1,7}        # Skip anywhere from 1 to 7 characters
)*                # Iterate the above as many times as possible
$                 # Assert we've reached end of string

```

Alternative 22 bytes:

```
^(t(?=ut-tut).{0,6})*$

```

## Regex (Python / Ruby), 21 bytes

```
^((?=tut-tut).{,7})*$

```

Try it online! \- Python
Try it online! \- Ruby

Python and Ruby support the quantifier shorthand of `{,N}` to mean `{0,N}`.

Alternative 21 bytes:

```
^(t(?=ut-tut).{,6})*$

```

Try it online! \- Python
Try it online! \- Ruby

# Regex (Raku), ~~25~~ 21 bytesSBCS

```
^tut»((t?ut)?\-tut)+$

```

Ported from a previous (21 byte) version of the "POSIX ERE / RE2 or better" regex.

Try it online!

Porting the 21 byte lookahead-using version comes to **28 bytes**:

```
^<?before t>((t?ut)?\-tut)*$

```

Try it online!

## \\$\large\textit{Anonymous functions}\\$

# Raku, ~~29~~ 25 bytesSBCS

```
{/^tut»((t?ut)?\-tut)+$/}

```

Try it online!

# Ruby, ~~29~~ ~~28~~ 30 bytes

```
->s{s=~/^\b((t?\But)?-tut)+$/}

```

Try it online!

# JavaScript, ~~35~~ ~~34~~ 33 bytes

```
s=>/^\b((t?\But)?-tut)+$/.test(s)

```

Try it online!

# PowerShell, ~~35~~ 34 bytes

```
$args-match'^\b((t?\But)?-tut)+$'

```

Try it online!

# Java, 36 bytes

```
s->s.matches("((?=tut-tut).{1,7})*")

```

Try it online!

```
s->s.matches("tut\\b((t?ut)?-tut)+")

```

Try it online!

```
s->s.matches("\\b((t?\\But)?-tut)+")

```

Try it online!

# Julia v1.2+, ~~39~~ ~~38~~ 37 bytes

```
s->endswith(s,r"^\b((t?\But)?-tut)+")

```

Attempt This Online!

# , 40 bytes

```
\(L)grepl('^((?=tut-tut).{1,7})*$',L,,1)

```

Attempt This Online!

```
\(L)grepl('^tut\\b((t?ut)?-tut)+$',L,,1)

```

Attempt This Online!

```
\(L)grepl('^\\b((t?\\But)?-tut)+$',L,,1)

```

Attempt This Online!

# PHP, 47 bytes

```
fn($s)=>preg_match('/^\b((t?\But)?-tut)+$/',$s)

```

Try it online!

# Python, ~~54~~ 53 bytes

```
lambda s:re.match(r'\b((t?\But)?-tut)+$',s);import re

```

Try it online!

## \\$\large\textit{Full programs}\\$

# Retina, ~~21~~ 20 bytes

```
^\b((t?\But)?-tut)+$

```

Try it online!

# Pip, ~~25~~ ~~24~~ 21 bytes

```
+`(t?\But|\b)-tut`~=a

```

Try it online!

Thanks to DLosc for demonstrating this syntax. This is apparently shorthand for `^((t?\But|\b)-tut)+$`. This regex is slightly less inefficient speed-wise, but by moving all distinctive operations inside the loop, it allows this shortcut to be used.

# Ruby `-n`, ~~25~~ 24 bytes

```
p~/^\b((t?\But)?-tut)+$/

```

Try it online!

Prints `nil` for false and `0` for true, which are respectively falsey and truthy in Ruby. If printing `0` or `1` is desired, replace `p~` with `p !!` (+2 bytes).

# Perl `-p`, ~~27~~ ~~26~~ 25 bytes

```
$_=/^\b((t?\But)?-tut)+$/

```

Try it online!

# MATL, 25 bytes

```
'^\<((t?\But)?-tut)+$'XXn

```

Try it online!

MATL appears to have `\<` and `\>` as its word boundary assertions, and apparently doesn't support `\b`, yet somehow still supports `\B`. I can't currently explain this; I thought it used PCRE.

# Zsh, ~~35~~ 34 bytes

```
[[ $1 =~ '^\<((t?\But)?-tut)+$' ]]

```

Try it online!

Zsh uses GNU ERE as its regex engine, so while `\b` would work, `\<` should be slightly more efficient due to only checking for the type of word boundary that can occur at that location.

# PHP `-F`, ~~48~~ ~~47~~ 46 bytes

```
<?=preg_match('/^\b((t?\But)?-tut)+$/',$argn);

```

Try it online! \- bare-bones test harness
Try it online! \- fancier test harness
> 22 votes

# Answer
# Zsh, ~~66~~ 54 bytes

***-6 bytes** thanks to Neil, **-6 bytes** by switching to `-e` thanks to pxeger.*

```
s=xxxxxx$1
repeat $#1 [[ ${s:$[i++]:13} = *tut-tut* ]]

```

Try it online!  ~~Try it online!~~

The problem stated is equivalent to: Every sliding 13-character window of `xxxxxx[string]xxxxxx` contains `tut-tut`. In Bash and Zsh, the `${var:${idx}:13}` is valid even if the string isn't long enough, so the trailing `xxxxxx` are unneeded.

We loop over each window, and `exit` out if any single test fails thanks to `errexit`.
> 14 votes

# Answer
# APL (Dyalog Classic), 21 bytes

```
∧/7∨/'tut-tut'⍷6∘↓⍣¯1

```

Try it online!

```
               6∘↓⍣¯1   pad with leading spaces
     'tut-tut'⍷         find occurrences of tut-tut
∧/7∨/                   present in every group of 7 consecutive positions

```
> 10 votes

# Answer
# Python3, 61 bytes:

```
f=lambda x:x==''or'tut-tut'==x[:6|f(x[4:])|f(x[6:])|f(x[7:])]

```

Try it online!
> 8 votes

# Answer
# Prolog (SWI), 70 bytes

```
b-->"tut-tut".
n-->(b;"ut-tut";"-tut"),(n;"").
t-->b;b,n.
+X:-t(X,[]).

```

Try it online!

-4 from jo king.
> 8 votes

# Answer
# Python, 50 bytes

```
def f(s):s[:7]=="tut-tut"and f(s[~ord(s[7])%5|4:])

```

Signals by exit code: errors out if the input is "tut-tut"-decomposible.

## How?

Recursively checks that input starts with "tut-tut". Based on the next character directly computes where the next "tut-tut" has to start.

```
0 1 2 3 4 5 6   7   8 9 ...
               ---
t u t - t u t | - |
              |   |
 ==>    t u t | - | t u t
               ---

               ---
t u t - t u t | u |
              |   |
 ==>        t | u | t - t u t
               ---

               ---
t u t - t u t | t |
              |   |
 ==>          | t | u t - t u t
               ---

```

The figure shows offsets inferred from char at position 7:

* `"-"` --\> 4
* `"u"` --\> 6
* `"t"` --\> 7

The magic formula `~x%5|4` implements this map. `x` is the code point of input character.

Importantly, any input is mapped to 4,5,6,7, so the algorithm can neither get stuck nor skip any characters.

Now, if we can cover the input with `"tut-tut"`s we will eventually reach the end and error out as soon as we try to access out-of-bounds characters. Otherwise the algorithm will simply stop at the first place that cannot be covered.

Attempt This Online!

### Thanks to eagle-eyed @Jonathan Allan for spotting a problem with my first attempt.

### Wrong Python, 54 bytes

```
def f(s):s[:7]=="tut-tut"and f(s[~ord(s[7])%31%12%8:])

```

Attempt This Online!
> 8 votes

# Answer
# Vyxal, ~~16~~ ~~14~~ 13 bytes

```
mp13l‛≠₈‹∞vcg

```

Try it Online! | 12 bytes with `g` flag

Returns `1` for true, or falsy for false (`0` or an empty list).

```
mp13l‛≠₈‹∞vcg
m              # Mirror the input - append its reverse
 p             # Append the input to that
  13l          # Get all overlapping strings of length 13
     ‛≠₈‹∞vc   # For each, does it contain "tut-tut"?
            g  # Minimum. Returns an empty list for an empty list (no idea why)

```

-3 from porting Jonathan Allan's Jelly answer!

-1 thanks to emanresu A.

Previously:

## Vyxal, 16 bytes

```
6Iø.13l`≠₈-`∞vcA

```

Try it Online!

Uses the same idea as @GammaFunction's Zsh answer.

```
6Iø.13l`≠₈-`∞vcA
6Iø.              # Surround the input with 6 spaces on both sides
    13l           # Get all overlapping strings of length 13
       `≠₈-`∞vcA  # Do all of them contain "tut-tut"?

```
> 7 votes

# Answer
# Curry (PAKCS), 42 bytes

```
f""=1
f(a@(_:_++b)++c)|a=="tut-tut"=f$b++c

```

Try it online!

Returns `1` for truth, and nothing otherwise.
> 5 votes

# Answer
# Raku, 42 bytes

```
{^.comb⊆m:ex/tut\-tut/>>.&{.from..^.to}}

```

Try it online!

An anonymous function that takes a string and returns a true/false value for if it is composed of overlapping 'tut-tut's.

### Explanation

```
{                                      } # Anonymous function block
 ^.comb    # The range 0 to length of input
       ⊆   # is a subset or equal to
        m:ex/tut\-tut/                  # Match all instances of 'tut-tut'
                      >>.&{           } # And map them to

                           .from..^.to  # The range of covered indexes

```

This basically finds the indexes covered by each 'tut-tut' and makes sure that they cover the entire string. Note that you could easily generalise this function to any string.
> 5 votes

# Answer
# sed, 39 bytes

```
:a
s/tut-tut/TUTTUT/i
ta
s/[^TU]//
T
cN

```

Truthy test cases -- outputs nothing

Falsy test cases -- outputs one N for each line

The idea here is quite simple:

* Continuously replace `tut-tut` with `TUTTUT`, using case-insensitive matching, until the input stops changing.
* Check if there are any lowercase characters or `-` left.
* If so, output an `N` for failure. Otherwise, output nothing for success.

# sed, 29 bytes, straight regex, thanks to Deadcode

```
s/^((t?\But)?\b-tut)+$//
t
cN

```

Attempt This Online!

Thanks to Deadcode for this alternate approach which forgoes looping and solves it with a single application of a true regex.
> 5 votes

# Answer
# Brachylog, 20 bytes

```
Ẹ|a₀"tut-tut"sl;?b₍↰

```

Try it online!

### Explanation

This is a pretty straight-at-the-problem approach; possibly something more subtle would be shorter.

```
Ẹ|a₀"tut-tut"sl;?b₍↰
Ẹ                     Either the input is the empty string
 |                    Or
  a₀                  A prefix of the input
    "tut-tut"         is "tut-tut"
             s        Take a nonempty substring of "tut-tut"
              l       Get its length
               ;?b₍   Remove that many characters from the start of the input string
                   ↰  Recurse

```
> 5 votes

# Answer
# Husk, ~~24~~ 23 bytes

*Edit: saved 1 byte based on Dominic van Essen's comment.*

```
±Λ≤7Ẋ-J¥¨μζ-μζ¨X7¹e_6→L

```

Try it online!

## Explanation

```
±Λ≤7Ẋ-J¥¨μζ-μζ¨X7¹e_6→L

±Λ≤7                          check if all differences are ≤7
    Ẋ-                        take the difference of all adjacent elements in list
      J                       put indices list the into the middle of [-6,1+len(input)]
       ¥                      create indices list of all occurrences of "tut-tut" in substring list
        ¨μζ-μζ¨               "tut-tut"
                X7¹           create list of substrings of input with length 7
                   e_6→L      list [-6,1+len(input)]

```
> 5 votes

# Answer
# 05AB1E, 17 bytes

```
žO.øü13"tut-"ûδåP

```

Port of *@GammaFunction*'s Zsh answer, so make sure to upvote him/her as well!

Try it online or verify all test cases.

**Explanation:**

```
žO                # Push constant string "aeiouy"
  .ø              # Prepend and append this string to the (implicit) input
    ü13           # Pop and create overlapping parts of size 13
       "tut-"û    # Push string "tut-" and palindromize it to "tut-tut"
              δ   # Map over each overlapping part using "tut-tut" as argument:
               å  #  Check if the part contains "tut-tut" as substring
                P # Product to check if all are truthy
                  # (after which the result is output implicitly)

```
> 4 votes

# Answer
# JavaScript (ES6), 58 bytes

A non-regex solution.

```
f=([c,...a],i)=>i>6?!c:c=="tut-"[i&3]&&f(a,-~i)|3%~-i&f(a)

```

Try it online!

### How?

We use a pointer \\$i\\$ into the string \\$s=\\$ `"tut-tut"`. At each iteration, we make sure that the current character from the input string matches \\$s\[i\]\\$, then we either increment \\$i\\$ or restart with \\$i=0\\$ if we are allowed to do so. The parsing is successful if we end up with \\$i=7\\$ exactly when the end of the input string is reached.

The table below summarizes after which positions it's possible to restart with \\$i=0\\$ and how this can be computed with the expression `3 % ~-i & 1`.

| i = position | character | restart after? | 3 % ~-i | 3 % ~-i & 1 |
| --- | --- | --- | --- | --- |
| 0 | t | No | 0 | 0 |
| 1 | u | No | NaN | 0 |
| 2 | t | No | 0 | 0 |
| 3 | - | Yes | 1 | 1 |
| 4 | t | No | 0 | 0 |
| 5 | u | Yes | 3 | 1 |
| 6 | t | Yes | 3 | 1 |
> 4 votes

# Answer
# Jelly, 16 bytes

```
m0;w13Ƥ“"ṁĿ4ṘṘ»Ṃ

```

A monadic Link that accepts a list of characters and yields `1` if constructible or `0` if not.

**Try it online!**

### How?

The input must (a) start with `tut-tut`, (b) end with `tut-tut`, and (c) have `tut-tut` as a contiguous substring of all of its length \\$13\\$ slices. We can, however, just test that (c) holds for the input concatenated with its reverse concatenated with the input (e.g. `abc` -\> `abccbaabc`). This works since `tut-tut` is palindromic and any bad starts or bad ends in the input will now nest between any `tut-tut`s.

```
m0;w13Ƥ“"ṁĿ4ṘṘ»Ṃ - Link: list of characters, S e.g. "abc"
m0               - reflect -> "abccba"
  ;              - concatenate -> "abccbaabc"
      Ƥ          - for infixes...
    13           - ...of length 13:
   w   “"ṁĿ4ṘṘ»  -   first 1-indexed index of "tut-tut" or 0 if not found
               Ṃ - minimum (an empty list yields 0)

```

---

Bit of a shame it takes half the code to make "tut-tut"!
> 4 votes

# Answer
# Husk, ~~22~~ ~~18~~ 17 bytes

*Edit: saved ~~4~~ 5 bytes based on Jonathan Allan's idea*

```
▼M€X13‼S+↔⁰¨μζ-μζ

```

Try it online!

```
      ‼   ⁰             # apply twice to the input:
       S+↔              #   join to itself reversed
   X13                  # and split this into strings of 13 characters;
 M                      # now map over these
  €                     #   do they contain
           ¨μζ-μζ¨      #   the compressed string "tut-tut"?
▼                       # and return the minimum result

```
> 4 votes

# Answer
# JavaScript (V8), 39 bytes

```
x=>x.replace(/(?=tu)((t?ut)?-tut)*/,"")

```

Try it online!

Returns a falsy string if the string is correctly composed of `tut-tut`s, and a truthy string otherwise.

Mostly the same logic as my (slightly broken) regex solution, except instead of having the "this regex matches the entire string or else it fails" logic be in the regex, its in the fact that we only delete one occurrence of the pattern. If the entire string is not composed of the pattern, there will be string remaining after the replacement, and in js, any nonempty string is truthy, with the empty string being the only falsy string :-)

(in case you wonder why this doesn't fail for cases where two valid strings are concatenated: regex is greedy, and will grab the largest match it can grab)

Breakdown:

```
x=>x.replace(/(?=tu)((t?ut)?-tut)*/,"") // full function

x=>x.replace(/                    /,"") // return the string with exactly one
                                        // match of the following regex removed
              (?=tu)                    //   string starting with "tu"
                    (           )*      //   which contains at least 0 of
                                        //   the following pattern
                                        //   (actually at least 1, since otherwise,
                                        //   the pattern would be empty and
                                        //   thus would fail the "tu" check)
                     (t?ut)?-tut        //     any of "-tut"
                                        //     (will never be at the start due to the
                                        //     "tu" check, but can appear in cases
                                        //     where the entire "tut" overlaps),
                                        //     "ut-tut"
                                        //     (in cases where just the "t" is overlapping,
                                        //     also can never be at the start)
                                        //     or "tut-tut"
                                        //     (this one always comes first
                                        //     due to the "tu" check)

```

BTW this regex saves a byte over the straightforward regex `/tut-tut((t?ut)?-tut)*/` because we don't actually have to use the entire "tut-tut"; the first group `((t?ut)?-tut)` is forced to complete to `tut-tut` once it's forced to start with `tu`, if that makes sense... :-)
> 3 votes

# Answer
# Factor, 36 bytes

```
[ R/ tut\b((t?ut)?-tut)+/ matches? ]

```

Try it online!

Port of Deadcode's (Bubbler's/thejonymyster's) regex answer.

# Factor \+ `math.unicode`, 63 bytes

```
[ "xxxxxx"dup surround 13 clump [ "tut-tut"swap subseq? ] ∀ ]

```

Try it online!

Port of GammaFunction's Zsh answer.
> 3 votes

# Answer
# Charcoal, 21 bytes

```
⬤θ№✂⁺×⁶ψθκ⁺¹³κ¹…tut-⁷

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-` for a valid string, nothing if not. Explanation: A port of my golf to @GammaFunction's zsh answer.

```
 θ                      Input string
⬤                       All indices satisfy
      ⁶                 Literal integer `6`
     ×                  Repetitions of
       ψ                Null byte
    ⁺                   Plus
        θ               Input string
   ✂          ¹         Sliced from
         κ              Current index to
           ¹³           Literal integer `13`
          ⁺             Plus
             κ          Current index
  №                     Contains
                tut-    Literal string `tut-`
               …        Extended to length
                    ⁷   Literal integer `7`

```
> 2 votes

# Answer
# MathGolf, 24 bytes

```
☼▌☼▐l£{_C<ÿtut-ñ╧\╞};]ε*

```

Port of *@GammaFunction*'s Zsh answer, so make sure to upvote him/her as well!

Try it online.

**Explanation:**

```
☼▌               # Prepend a leading "100000" in front of the (implicit) input-string
  ☼▐             # Append "100000" as well
l£               # Push the input-string, pop and push its length
  {            } # Loop that many times:
   _             #  Duplicate the current string
    C<           #  Pop the copy, and keep its first 13 characters
      ÿtut-ñ     #  Push string "tut-", and palindromize it to "tut-tut"
            ╧    #  Check if the string contains this "tut-tut" as substring
             \   #  Swap so the string we've duplicated is at the top of the stack again
              ╞  #  Remove its leading character
;                # After the loop, discard the remaining string from the stack
 ]               # Wrap everything else on the stack into a list
  ε*             # Product (reduce by multiplication) to verify whether all checks were
                 # truthy
                 # (after which the entire stack is output implicitly as result)

```
> 2 votes

# Answer
# Rust, 101 bytes

```
|s:&str|(0..s.len()).scan(0,|r,i|{if s[i..].starts_with("tut-tut"){*r=7}*r-=1;Some(*r)}).all(|i|i>=0)

```

Playground

Returns a boolean with the obvious meaning.
> 2 votes

# Answer
# jq, ~~78~~ 68 bytes

```
[range(length) as $i|"xxxxxx\(.)"[$i:13+$i]|contains("tut-tut")]|all

```

Try it online!  ~~Try it online!~~

Port of my Zsh answer. ~~The `<> as $<>` feels optimizable, but I couldn't figure it out.~~ *EDIT: Turns out, it was optimizable!*
> 2 votes

# Answer
# C (gcc), ~~94~~ 86 bytes

```
d;b;f(char*s){for(b=~0;b&&s[3]|b+4;s-=b=d&b|d==1?0:~3)s+=d=strstr(s,"tut-tut")-s;b=b;}

```

Try it online!

*Saved 8 bytes thanks to c--*

Inputs a pointer to a string.
Returns `~3` if the input is constructed of overlapping or concatenated instances of the string `"tut-tut"` or `0` otherwise.
> 1 votes

# Answer
# Japt, 16 bytes

```
pÔiU ãD eø`t©-t©

```

Try it

```
pÔiU ãD eø`t©-t©     :Implicit input of string U
p                    :Append
 Ô                   :  Reverse
  iU                 :Prepend input
     ã               :Substrings of length
      D              :  13
        e            :All
         ø           :  Contain
          `t©-t©     :    Compressed string "tut-tut"

```
> 1 votes

# Answer
# C (gcc), 58 bytes

Assumes non-empty input

```
f(char*s){s=bcmp(s,"tut-tut",7)?!*s:f(s+4)|f(s+6)|f(s+7);}

```

Try it online!

# C (gcc), 62 bytes

```
f(char*s){s=bcmp(s,"tut-tut",7)?0:!s[7]|f(s+4)|f(s+6)|f(s+7);}

```

Try it online!

-7 bytes from xnor's comment to another answer and 2 from ceilingcat
> 1 votes

# Answer
# JavaScript (Node.js), 57 bytes

```
x=>x.split`-tut`.every(i=>+{ut:1,tut:1,'':x[3]+1}[j=i])>j

```

Try it online!

Regless

See another regless solution here
> 1 votes

# Answer
# Nekomata \+ `-e`, 19 bytes

```
ʷ{;"tut-tut"=ip,}ᵗN

```

Attempt This Online!

A port of my Curry answer. See also @DLosc's Brachylog answer.

```
ʷ{;"tut-tut"=ip,}ᵗN
ʷ{              }       Loop until failure
  ;                         Split the input into two parts
   "tut-tut"=               Check if the second part is "tut-tut"
             ip             Take a proper prefix of the second part
               ,            Append it to the first part
                 ᵗN     Check if the result is empty

```
> 1 votes

# Answer
# Retina 0.8.2, 26 bytes

I know it's not as short as some other answers, but here's my solution.

```
^(tut(-tut))(\1|(ut)?\2)*$

```

Try it online!
> 1 votes

---
Tags: code-golf, string, decision-problem
---


title: Undo a Range of Numbers

text:
# Question
Title: Undo a Range of Numbers
It is fairly simple to, given a number `n`, create a range from `0` to `n-1`. In fact, many languages provide this operation as a builtin.

The following CJam program reads an integer, and then prints out such a range (Try it online!):

```
ri,

```

Notice that it prints out numbers *without* a separator.

## The Challenge

Your task is to reverse this process. You should write a program that, given a string representing a range, returns the number used to produce that range.

## Specifications

* The numbers are given without any separator.
* You may assume the string forms a valid range.
* You may use 0- or 1-based indexing for your range.
* You may assume that a correct output will never exceed 32,767 (so a valid input will never have a length greater than 152,725).
* You may assume that a correct output will always be positive (so you do not have to handle 0 or negative).

This is , so the shortest competing answer (measured in bytes) wins.

## Test Cases

0-indexed:

```
0123 -> 4
0 -> 1
0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100 -> 101

```

1-indexed:

```
1234 -> 4
1 -> 1
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100 -> 100

```

# Answer
# Prolog (SWI), ~~91~~ 80 bytes

0-indexed.

```
X*L:-atom_length(X,L),
     between(0,L,Y),
     numlist(0,Y,B),
     atomic_list_concat(B,X)
     ;L=0.

```

Newlines added for readability.

Try it online!
> 13 votes

# Answer
# Husk, 5 bytes

```
LCmLN

```

Try it online!

Only letters!

Takes input as a string, result is 1-indexed.

### Explanation

```
LCmLN
  mLN    get the list of lengths of all positive naturals
 C       cut the input into slices of those lengths
L        get the length of the resulting list

```
> 12 votes

# Answer
# 05AB1E, ~~7~~ 6 bytes

1-indexed.

```
āηJsk>

```

Try it online! or as a Test Suite

**Explanation**

```
ā        # push range [1 ... len(input)]
 η       # compute prefixes of the range
  J      # join each prefix to a string
   sk    # get index of the input in the list of prefixes
     >   # increment

```
> 8 votes

# Answer
# Brachylog, ~~9~~ 7 bytes

```
⟦kṫᵐc,Ẹ

```

Try it online!

0-indexed.

### Explanation

Here we pass the input through the Output variable, and access the result through the Input variable.

```
⟦          The result is the input to a range…
 k         …with the last element removed…
  ṫᵐ       …which when all elements are casted to string…
    c      …and are then concatenated results in the input string
     ,Ẹ    (Append the empty string, this is necessary for it to work in the case where the
             input is the empty string)

```
> 7 votes

# Answer
# Java 8, ~~66~~ 59 bytes

```
s->{int r=0;for(String c="";!c.equals(s);c+=r++);return r;}

```

0-indexed

-7 bytes thanks to *@PunPun1000*.

~~I have the feeling this can be shortened by only checking the length of the input somehow, since we can assume the input is always valid. Still figuring this out.~~ Unable to figure this out, and it will probably cost too many bytes in Java to be useful anyway (same applies to returning a substring of the end of a 1-indexed input).

**Explanation:**

Try it here.

```
s->{                 // Method with String parameter and integer return-type
  int r=0;           //  Result-integer
  for(String c="";   //  Check-String
      !c.equals(s);  //  Loop as long as the sum-String doesn't equal the input-String
    c+=r++           //   Append the number to the the Check-String,
                     //   and increase the Result-integer by 1
  );                 //  End of loop
  return r;          //  Return the result-integer
}                    // End of method

```
> 7 votes

# Answer
# Japt, 8 bytes

Starting to get to grips with function methods in Japt.

0-indexed. Can take input as a string, an integer or an array containing 0 or 1 elements.

```
_o ¬¥U}a

```

Test it

---

## Explanation

Implicit input of string `U`.

```
_     }a

```

Get the first integer `>=0` that returns true when passed through a function that ...

```
o

```

Generates an array of integers from `0` to 1 less than the current integer ...

```
¬

```

Joins it to a string ...

```
¥U

```

Checks that string for equality with `U`.

Implicit output of resulting integer.

---

## Alternative, 8 bytes

```
ÊÇo ¬ÃbU

```

Test it
> 5 votes

# Answer
# Ly, 29 bytes

```
iys&p>0<11[ppl>s1+<lfspSylL]>

```

Try it online!

Can't believe this worked as well as it did...
> 5 votes

# Answer
# Haskell, ~~40~~ 37 bytes

```
f s=[n|n<-[0..],(show=<<[0..n])>s]!!0

```

Function that reverses zero-based ranges.

Thanks to Laikoni for saving 3 bytes!

Try it online.
> 4 votes

# Answer
# Charcoal, 13 bytes

```
Ｉ⌕Ｅ⁺ψθ⪫ＥκＩλωθ

```

Try it online! Link is to verbose version of code. Explanation:

```
          λ     Inner map variable (μ inner map index also works)
         Ｉ      Cast to string
        κ       Outer map index
       Ｅ        Map over implicit range
      ⪫    ω    Join result
     θ          Input string
   ⁺ψ           Plus an extra character
  Ｅ             Map over each character
 ⌕          θ   Find the index of the original string
Ｉ               Cast from integer to string
                Implicit print

```
> 4 votes

# Answer
# Retina, 30 bytes

```
+1`(\d+?)(?!\D)(?<!\1.+)
$0;
;

```

Recursively adds a semicolon after each number then counts the number of semicolons

Try it online!
> 4 votes

# Answer
# JavaScript (ES6), ~~32~~ 31 bytes

*Saved 1 byte thanks to Challenger5*

```
f=(s,r=n='')=>r<s?f(s,r+n++):+n

```

### Test cases

```
f=(s,r=n='')=>r<s?f(s,r+n++):+n

console.log(f('0123'))
console.log(f('0'))
console.log(f(''))
console.log(f('0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100'))
```
> 3 votes

# Answer
## Perl 5, 19 bytes

**18 bytes code + 1 for `-p`.**

```
$i++while s/$i\B//

```

Uses 1-based indexing. -7 bytes thanks to @nwellnhof's *much* better approach!

Try it online!

### Explanation

`$\` is a special variable that is `print`ed automatically after each statement, so by using that to store our number we don't need to update `$_` (which is automatically printed as part of the functionality of the `-p` flag) to contain the desired output. Then, whilst the input starts with `$\`, remove it and `redo` the program, which again increments `$\` and replaces it. When it no longer finds the number at the beginning of the string, we're done! Finally, decrement `$\` so we have the last number in the range.
> 3 votes

# Answer
# Mathematica, 46 bytes

```
Array[""<>ToString/@Range@#&,2^15]~Position~#&

```

1-indexed

**input**

> \["12345678910"\]
> 2 votes

# Answer
# , 47 bytes

```
n=nchar(scan(,""));which(cumsum(nchar(1:n))==n)

```

Try it online!

1-indexed
> 2 votes

# Answer
# Ruby, ~~51~~ ~~50~~ 46 bytes

```
->n{(0..4e4).map{|x|(1..x).to_a.join}.index n}

```

(This is my first Ruby program ever so it must be easy to golf it further)

-4 bytes thanks to @Nnnes
> 2 votes

# Answer
# Python 2, 43 bytes

```
f=lambda s,i=1,r='':r<s and-~f(s,i+1,r+`i`)

```

Try it online!

---

# Python 2, 43 bytes

```
f=lambda s,i=1:s>''and-~f(s[len(`i`):],i+1)

```

Try it online!

---

# Python, 46 bytes

```
lambda s:s[-sum(i*'0'in s for i in range(5)):]

```

Try it online!

A different strategy. Takes a number of characters from the end equal to the length of the largest run of `0`'s in s.

---

# Python, 46 bytes

```
f=lambda s,c=0:c*'0'in s and f(s,c+1)or s[-c:]

```

Try it online!

Recursive version of the above.
> 2 votes

# Answer
# APL (Dyalog), ~~17~~ 11 bytes

-6 bytes thanks to ngn.

```
{,\⍕¨⍳≢⍵}⍳⊂

```

Try it online!

`⍳⊂` find the **ɩ**ndex of the entire argument in

`{``}` the result of this anonymous function:

length of the argument

**ɩ**ntegers until that

`⍕¨` format (stringify) each

`,\` cumulative concatenation of those
> 2 votes

# Answer
# Python 2, 46 bytes

0-indexed

```
l=lambda x,z="",y=0:z<x and l(x,z+`y`,y+1)or y

```

Try it online!
> 1 votes

# Answer
# Pyth, ~~11~~ 10 bytes

1-indexed.

```
fqQ|jkSTk0

```

**Try it here**

If the empty string could be ignored, this can be shortened to **6 bytes**:

```
fqQjkS

```

*-1 byte thanks to @Mnemonic*
> 1 votes

# Answer
# Aceto, ~~27~~ 25 bytes

1-based index.

```
;L[¥
`=]z
MLdI<
r!`;   p

```

We `r`ead the input and `M`emorize it (and directly `L`oad it again), then we negate it (`!`; leading to a truthy value only for an empty string). If this value is truthy (```), we jump to the end (`;`), where we `p`rint the implicit zero.

Otherwise, we increment the current stack value (initially a zero), duplicate it, and put one copy on the stack to the right, while also moving there (`Id]`). We then construct a decreasing range (`z`), join the stack as a string (`¥`), and move the value (and us) on the original stack again (`[`). We `L`oad the value we memorized earlier (the input) and compare it with this string. If equal, we jump to the end again, where we print the current "counter" value (`=`;`).

Otherwise, lots of empty space is traversed until the Hilbert curve eventually hits the `<` which puts the IP on top of `I` again, incrementing the counter and testing again.
> 1 votes

# Answer
# CJam, 13 bytes

```
q:Q,),{,sQ=}#

```

So many commas...

Try it online!

### Explanation

```
q:Q            Read the input and store it in Q
   ,           Get its length
    ),         Get the range 0..n
      {,sQ=}#  Find the index of the first number in the range to satisfy this block:
       ,        Get the range 0..(number)-1
        s       Stringify it
         Q=     Check if it equals the input

```
> 1 votes

# Answer
# CJam, 16 bytes

```
r0({)_,s2$=!}g\;

```

Try it online!

## Alternative 16 bytes

```
r:V;0({)_,sV=!}g

```

Try it online!
> 1 votes

# Answer
# Perl 6,  ~~30 28~~  27 bytes

```
{first :k,*eq$_,[\~] '',0...*}

```

Test it

```
{[\~]('',0...*).first($_):k}

```

Test it

```
{first :k,$_,[\~] '',0...*}

```

Test it

## Expanded:

```
{  # bare block lambda with implicit parameter ｢$_｣

  first       # find the first one
  :k,         # return the index into the Seq instead of what matched
  $_          # that matches the input

  # from the following

  [\~]        # triangle reduce using &infix:«~» (string concatenation)

              # a Seq
    '',       #   that starts with an empty Str
    0         #   then a 0
    ...       #   generate values
    *         #   indefinitely
}

```

---

`'',0...*` produces an infinite sequence of values `''`,`0`,`1`,`2`,`3`

`[\~] '',0...*` produces an infinite sequence of all of the possible inputs

```
""
"0"
"01"
"012"
"0123"
...

```

Note that this code will never stop if you give it an invalid input.
> 1 votes

# Answer
# CJam, ~~14~~ ~~12~~ 11 bytes

```
q,_){,s,}%#

```

Try it Online

```
q,   e# Get length of input string
_)   e# Duplicate length, increment by 1
{    e# Generate array by mapping [0,1,2,...,length] using the following function:
,    e# Generate range [0,x] (x is the int we're mapping)
s    e# Convert range to string (e.g [0,1,2,3] => "0123"
,    e# Get the length of that string
}%   e# Map the int to the length of it's range string
#    e# Return the index of the length of the input string in the generated array

```
> 1 votes

# Answer
# Dyvil, 42 38 bytes

```
s=>"".{var r=0;while($0!=s)$0++=r++;r}

```

Same algorithm as this Java answer, except it (ab)uses some of Dyvil's syntactic specialties.

Explanation:

```
s=>          // starts a lambda expression with one parameter
"".{         // begins a brace access expression, the value before the '.'
             // is available within the braces as a variable named '$0'
var r=0;     // variable with inferred type int
while($0!=s) // while the accumulator $0 does not (structurally) equal s
$0++=r++     // concatenate $0 and the String representation of r,
             // then store the result in $0 and increment r by 1
;            // end of while
r}           // return r as the result of the lambda

```

---

* **Saved `4` bytes by using a brace access expression instead of a variable for the accumulator**
> 1 votes

# Answer
# Thunno 2, 4 bytes

```
ƘRJ=

```

Try it online!

## Thunno 2, 6 bytes

```
żƒ€JȮ⁺

```

Try it online!

#### Explanation

```
ƘRJ=  # Implicit input
Ƙ     # First integer where:
 RJ   #  Join the range
   =  #  Equals the input?
      # Implicit output

```

```
żƒ€JȮ⁺  # Implicit input
ż       # Push [1..length]
 ƒ      # Prefixes of this list
  €J    # Join each into a string
    Ȯ⁺  # 1-based index of input
        # Implicit output

```
> 1 votes

# Answer
# PowerShell, 47 bytes

```
do{$b=1..$a-join"";$a+=1}while($b-ne$args);$a-1

```

Try it online!
> 1 votes

# Answer
# Arturo, 31 bytes

```
$->s[0while[s<>join@1..<=]->1+]

```

Try it!
> 1 votes

# Answer
# Python 2, ~~49~~ ~~48~~ 46 bytes

-1 thanks to Challenger5
-2 thanks to Mr. Xcoder

```
f=lambda s,i=0,t='':t<s and f(s,i+1,t+`i`)or i

```

Try it online!
> 0 votes

# Answer
# MATL, 14 bytes

```
`@q:VXzGX=~}@q

```

1-indexed.

Try it online!

### Explanation

```
`       % Do...while
  @     %   Push iteration index (1-based), k
  q     %   Subtract 1: gives k-1
  :     %   Range: [1 2 ... k-1]. Will be empty for k=1
  V     %   Convert to string
  Xz    %   Remove spaces
  G     %   Push input
  X=    %   Are the two strings equal?
  ~     %   Negate. This is the loop condition. If true: next iteration
}       % Finally (execute at the end of the loop)
  @     %   Push k
  q     %   Subtract 1: gives k-1. This is the solution
        % End (implicit). Display (implicit)

```
> 0 votes

# Answer
# SOGL V0.12, ~~11~~ ~~10~~ 9 bytes

1-indexed.

```
I∫HΔ∑=?f←

```

Try it Here!

Explanation:

```
I∫         repeat input+1 times
  HΔ         create a range from 1 to the 0-indexed iteration, inclusive
    ∑        join it
     =?      if it's equal to the input
       f←      exit, pushing the 0-indexed counter

```

..or 7 bytes without the empty case

```
∫Δ∑=?F←

```

Try it Here!
> 0 votes

# Answer
## C#, 72 bytes

---

### Data

* **Input** `String` `i` The int array to be deciphered
* **Output** `Int32` The number used to make the array

---

### Golfed

```
(string i)=>{int c,p=c=0;for(;p<i.Length;c++)p+=(c+"").Length;return c;}

```

---

### Ungolfed

```
( string i ) => {
    int
        c,
        p = c = 0;

    for( ; p < i.Length; c++ )
        p += ( c + "" ).Length;

    return c;
}

```

---

### Ungolfed readable

```
// Takes the string with the int array
( string i ) => {
    int
        c,         // Counter, it will count how many ints the array has.
        p = c = 0; // Padding, it will help jumping from int to int on the string.

    // Start counting. If 'i' is empty, the 'c' will be 0.
    for( ; p < i.Length; c++ )

        // Increase the number of digits with the length of 'c'.
        p += ( c + "" ).Length;

    // Return the counter.
    return c;
}

```

---

### Full code

```
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TestBench {
    public static class Program {
        private static Func<String, Int32> f = ( string i ) => {
            int
                c,
                p = c = 0;

            for( ; p < i.Length; c++ )
                p += ( c + "" ).Length;

            return c;
        };

        static void Main( string[] args ) {
            List<String>
                testCases = new List<String>() {
                    "0123",
                    "0",
                    "",
                    "0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100",
                };

            foreach(String testCase in testCases) {
                Console.WriteLine($" Input: {testCase}\nOutput: {f(testCase)}\n");
            }

            Console.ReadLine();
        }
    }
}

```

---

### Releases

* **v1.0** \- `72 bytes` \- Initial solution.

---

### Notes

* None
> 0 votes

# Answer
# Stacked, 23 bytes

```
{!0$#+[::>''#`n=]until}

```

Try it online!

Basically, increments `0` until the range from `0` to the number looks like the input, checking for equality first.
> 0 votes

# Answer
# Jelly, 8 bytes

```
JVṾẎ$$Ƥi

```

Try it online!
> 0 votes

# Answer
# APL, 28 bytes

```
{⍺←0⋄(' '~⍨⍕⍳⍺)≡∊⍵:⍺⋄⍵∇⍨⍺+1}

```

Try it online!

The index origin must be `1`, thus this is `1`-based.

This will not work on some of the test cases due to memory limitations.

It works by going through each number and checking if the range as a string with spaces removed matches the argument, if not, it calls itself with its left argument (default of `0`) incremented by 1.
> 0 votes

# Answer
# PHP, 35 bytes

```
for(;$s!=$argv[1];$s.=++$i);echo$i;

```

Try it online!

1-indexed.

Continually increment `i` and add to a string until it matches the input, then return `i`.
> 0 votes

# Answer
# Proton, 50 bytes

```
n=input(s="")
i=0
for(;s!=n;s+=str(i++))1
print(i)

```

Sadly Proton doesn't do default parameters very well, so no recursion...

Try it online!
> 0 votes

# Answer
# Common Lisp, 84 bytes

```
(lambda(x)(do((i 0(1+ i))(s""(concatenate'string s(format()"~a"i))))((equal x s)i)))

```

Try it online!
> 0 votes

# Answer
# Jelly, 7 bytes

```
1RV⁼ɗ1#

```

Try it online!

1-indexed, and expects input as one big int (or equivalently, requires no additional quotes or such as a full program).

```
1    1#    Find the first positive integer n for which
 R         [1 .. n]
  V        smashed together into a flat string then evaluated as an integer
   ⁼ɗ      equals the input.

```

This one... runs into some issues pretty fast...

# Jelly, 4 bytes

```
RV)i

```

Try it online!

Jelly lists are Python lists, and Python lists aren't lazy. So even for relatively small outputs, this ends up attempting to construct lists that CPython literally cannot construct regardless of any actual memory issues, and it slows down very dramatically before that.
> 0 votes

# Answer
# PowerShell Core, 34 bytes

```
for(;"$args"-ne-join(1..++$a)){}$a

```

Try it online!

1-indexed, takes the input as a string
> 0 votes

# Answer
# Curry (KiCS2) \+ `:set +first`, 26 bytes

```
f(g n)=n
g n=[1..n]>>=show

```

Attempt This Online!

1-indexed.
> 0 votes

# Answer
# Vyxal, 31 bits<sup>v2</sup>, 3.875 bytes

```
ʀɾṅḟ

```

Try it Online!

1 indexed. Takes input as a number

## Explained

```
ʀɾṅḟ
ʀɾ    # The range [1, n] for each number in the range [0, input]
  ṅ   # Join each range into a single string
   ḟ  # And find the index of the input in that.

```

Created with the help of Luminespire.
> 0 votes

---
Tags: code-golf, string, number, integer
---