title: Count Euler's Tours

text:
# Question
Title: Count Euler's Tours
Leonhard Euler wants to visit a few friends who live in houses *2, 3, ..., N* (he lives in house 1). However, because of how his city is laid out, none of the paths between any houses form a loop (so, the houses exist on a graph which is a tree).

He gets bored easily but if he visits his friends in a different order, he won't be bored. So, he wants you to help him find how many unique ways there are for him to visit every friend and return home by the end of the day.

He doesn't have a map of his city, but he does remember the order of houses he visited last time he went on a walk.

## Problem Statement

Given the Euler Tour Representation of a tree, determine the number of unique ETRs of the same tree, with the root at 1.

## Input

The ETR of a tree. The Euler Tour Representation essentially starts at the root and traverses the tree depth-first writing out the label of each node as it goes along. A 3-node tree with one root and two children would be represented as `1 -> 2 -> 1 -> 3 -> 1`. A 3-node tree with one root, one child, and one grandchild would be represented as `1 -> 2 -> 3 -> 2 -> 1`.

In other words, it represents the Eulerian circuit of a directed graph derived from creating two edges from each edge in the tree, one in each direction.

Here is a visual example of an ETR:

I will allow a few alterations to the input:

1. You can choose if you want leaf nodes to be written once or twice consecutively.
2. You can choose if you want to return to the root at the end.

For example, here is a tree:

```
    1
   / \
  2   3
 / \   \
4   5   6

```

The following are acceptable:

* `1 2 4 2 5 2 1 3 6 3 1`
* `1 2 4 2 5 2 1 3 6 3`
* `1 2 4 4 2 5 5 2 1 3 6 6 3 1`
* `1 2 4 4 2 5 5 2 1 3 6 6 3` (this is shown on the Wikipedia article)

You can take the input in any reasonable format for a list of integers. You may also request to input `N` (the number of nodes) first, and to index at any arbitrary value (I use 1-indexing here). However, your node labels starting from `x` must be `x, x+1, x+2, ..., x+N-1`.

## Output

An integer, representing the number of unique ETRs of this tree, starting from the same root node.

## Challenge Specifications and Rules

* note that inputs are NOT always binary trees; see the second test case
* this is a problem, so scoring is by code length with a lower score being better
* no answer will be accepted
* Standard Loopholes apply

## Test Cases

```
[1, 2, 3, 2, 4, 5, 4, 6, 4, 2, 1, 7, 8, 9, 8, 7, 1]                      ->  8
[1, 2, 3, 2, 4, 2, 1, 5, 6, 5, 7, 5, 1, 8, 9, 8, 10, 8, 1]               -> 48
[1, 2, 3, 4, 5, 6, 7, 6, 8, 6, 5, 9, 5, 4, 10, 4, 3, 11, 3, 2, 12, 2, 1] -> 32
[1]                                                                      ->  1
[1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 4, 3, 2, 1]                      ->  1

```

If you want to test with more data, my reference implementation is here. It's pretty bad but it's correct so you can use it; just modify the list in line 3.

# Answer
> 8 votes
# Python 2, 45 bytes

```
f=lambda l:l==[]or(l.count(l.pop())or 1)*f(l)

```

Try it online!

It seems that one way to get the answer is take the counts of each node, that is the number of times each node is listed, subtract 1 from each, and multiply their factorials. That is,

$$\prod\_i (c\_i-1)!$$

where node \\$i\\$ is listed \\$c\_i\\$ times. Note that it doesn't matter what order the nodes appear in the Euler Tour Representation, only how many times they do. Listing leaf nodes once or twice doesn't make a difference, since \\$0!=1!=1\\$.

Since Python doesn't have a built-in factorial, we make do like this. For each entry of the list, we will count how many times that same values appears before it, that is label its `k`'th appearance 0-indexed as `k`. For example,

```
1 2 4 2 5 2 1 3 6 3 1
0 0 0 1 0 2 1 0 0 1 2

```

If we then remove all zeroes (or convert them to 1's) and multiply, we get the desired result.

To do this recursively, we repeatedly remove the last element and consider its its count in the remainder of the list, converting any count of 0 to 1. Then, we multiply by the recursive result on the list with its last element now removed, with a base case of 1 for the empty list.

We can save a couple of bytes using splatted input and `True` for 1 if this is allowed.

**43 bytes**

```
f=lambda a,*l:l==()or(l.count(a)or 1)*f(*l)

```

Try it online!

# Answer
> 5 votes
# APL (Dyalog Unicode), ~~17~~ 11 bytes

Based on xnor's answer. The  operator requires version 18, which is not yet on TIO.

```
(×/!÷⊢)≢⍤⊢⌸

```

Here is a longer variant that works in lower versions:

```
(×/!÷⊢)∘(+/∪∘.=⊢)

```

Try it online!

`+/∪∘.=⊢`/`≢⍤⊢⌸` counts the occurrences of the unique items in the input, `×/!÷⊢` calculates $$\prod\_i{c\_i!\over c\_i}$$

# APL (Dyalog Unicode), 27 bytes

I think this works with all suggested input formats.

```
{2>≢⍵:1⋄(×/∇¨,∘!≢)⍵⊆⍨⍵≠⌊/⍵}

```

Try it online!

I don't think the base case `2>≢⍵:1` is really necessary, since at some point there are no subtrees left to recurse on, but I can't get this to work without it.

**Commented:**

```
{2>≢⍵:1⋄(×/∇¨,∘!≢)⍵⊆⍨⍵≠⌊/⍵}  ⍝ A recursive dfns
 2>≢⍵                        ⍝ If the input has less than 2 elements
     :1                      ⍝   return 1
                  ⍵⊆⍨        ⍝ Partition the input ...
                     ⍵≠      ⍝ ... taking the elements that are not equal
                       ⌊/⍵   ⍝ to the minimum (the root of the current tree)
                             ⍝ These are the new subtrees
               !≢            ⍝ Take the factorial of the number of subtrees
             ,               ⍝ And append it to the results of ...
           ∇¨                ⍝ the recursive calls on each subtree
         ×/                  ⍝ take the product of the vector
                             ⍝ this is the result

```

# Answer
> 5 votes
# Jelly, 5 bytes

```
ĠẈ’!P

```

Try it online!

Count Euler's Tours 5 Byte Jelly Solution, as mentioned by HyperNeutrino.

The idea is the same as an earlier python solution, but I'd still like to explain how I came about it.

Note that we can solve this recursively. If our current node is N, with C children, our answer is C! times the product of the sub-answers from all the children. The reason is we can descend (in our euler tour) into the children in any order we so choose.

The second observation is that for every node except the root, where count(x) is the number of occurences of x in the euler tour:

$$count(i) = deg(i)$$

For the root,

$$count(r) = deg(r) + 1$$

Now, if we look at our formula above, we note that our answer is

$$deg(r)! * \[deg(n) - 1\]!$$

for every other node `n`. This actually works out hilariously well. We note that, as mentioned before, the answer is:

$$\prod\_{i = 1}^v \[count(v) - 1\]!$$

This solution lends itself very well to jelly.

```
ĠẈ’!P

```

First, we get the count array that we need, by `Ġ`rouping indices by their elements and taking vectorized length. Then we decrement and factorial, and finally product:

```
ĠẈ      Count array
  ’     Decrement
   !    Factorial
    P   Product

```

P.S.: Thanks to HyperNeutrino for helping me with the jelly solution, seeing as my jelly is a bit rusty...

# Answer
> 2 votes
# JavaScript (ES6), 42 bytes

This is based on @xnor's conjecture.

```
a=>a.map(x=>t*=(a[~x]=-~a[~x])-1||1,t=1)|t

```

Try it online!

# Answer
> 2 votes
# Charcoal, 11 bytes

```
ＩΠＥθ∨№…θκι¹

```

Try it online! Link is to verbose version of code. Uses @xnor's algorithm. Explanation:

```
   θ        Input array
  Ｅ         Map over elements
       θ    Input array
      …     Truncated to length
        κ   Current index
     №      Count occurrences of
         ι  Current element
    ∨       Logical Or
          ¹ Literal `1`
 Π          Take the product
Ｉ           Cast to string
            Implicitly print

```

Using the form of representation whereby leaf nodes are visited once and the root node is considered to have an extra edge so that it gets visited both at the start and the end, then the number of edges for a given node is equal to the number of times it was visited. On the first visit to a node with `n` edges you only have a choice of `n-1` edges since you have to completely traverse all of its subtrees before returning to the parent, and similarly on subsequent visits you have fewer choices until finally the last two visits both give you no choice at all. This could be reduced to the products of the relevant factorials for each node, although as @xnor points out it's actually golfier for some languages to replace each visit with the count of remaining choices and take the overall product (the Charcoal algorithm actually takes the product in reverse order but of course this makes no difference to the total).

# Answer
> 2 votes
# Japt, 8 bytes

```
ü ®ÅÊÊÃ×

```

Try it

```
ü ®ÅÊÊÃ×     :Implicit input of array
ü            :Group and sort by value
  ®          :Map
   Å         :  Slice off the first element
    Ê        :  Length
     Ê       :  Factorial
      Ã      :End map
       ×     :Reduce by multiplication

```

# Answer
> 1 votes
# 05AB1E, 5 bytes

```
Ù¢<!P

```

A bit lame, but this is simply a port of *@xnor*'s Python 2 answer and *@Riolku*'s Jelly answer, so make sure to upvote them!

Try it online or verify all test cases.

**Explanation:**

```
Ù      # Uniquify the (implicit) input-list
 ¢     # Count how many times each occurs in the (implicit) input-list
  <    # Decrease each count by 1
   !   # Take the factorial on each value
    P  # And take the product of that
       # (after which it is output implicitly as result)

```

# Answer
> 1 votes
# Perl 5 `-ap`, 27 bytes

```
$\=1;$\*=$h{$_}++||1for@F}{

```

Try it online!

---
Tags: code-golf, graph-theory
---


title: Palindromic Residue

text:
# Question
Title: Palindromic Residue
Today, as I'm writing this, is March 31st. In the US, this is `3/31`. I was playing around with `331` as a number to come up with a challenge, and found that its residues (modulo small numbers) is palindromic. `331%2=1, 331%3=1, 331%4=3, 331%5=1, 331%6=1` (`11311`).

Your challenge here is, when given an integer `n > 2`, output the first `n` positive numbers that have palindromic residue when taken modulo `[2,n]`.

For example, for input `7`, the output should be `1, 42, 43, 140, 182, 420, 421`. Here's the chart explaining why that's the case:

```
        mod
num | 2 3 4 5 6 7
-----------------
  1 | 1 1 1 1 1 1
 42 | 0 0 2 2 0 0
 43 | 1 1 3 3 1 1
140 | 0 2 0 0 2 0
182 | 0 2 2 2 2 0
420 | 0 0 0 0 0 0
421 | 1 1 1 1 1 1

```

## Input

A single positive integer `n` with `n > 2` in any convenient format.

## Output

The resulting array/list of the first `n` palindromic residues, as outlined above. Again, in any suitable format.

## Rules

* For `n > 10`, assume the residue list to be flattened before checking whether it's a palindrome. That is, `[1, 10, 11]` is palindromic, but `[1, 10, 1]` is not.
* Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
* If possible, please include a link to an online testing environment so other people can try out your code!
* Standard loopholes are forbidden.
* This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

### Examples

```
[input]
[output]

3
[1, 6, 7]

4
[1, 4, 5, 8]

5
[1, 50, 60, 61, 110]

6
[1, 30, 31, 60, 61, 90]

7
[1, 42, 43, 140, 182, 420, 421]

8
[1, 168, 169, 336, 337, 504, 505, 672]

9
[1, 2520, 2521, 5040, 5041, 7560, 7561, 10080, 10081]

10
[1, 280, 281, 560, 1611, 1890, 1891, 2170, 2171, 2241]

11
[1, 22682, 27720, 27721, 50402, 55440, 55441, 78122, 83160, 83161, 105842]

```

# Answer
## Haskell, 57 bytes

```
f n=take n[x|x<-[1..],(==)=<<reverse$show.mod x=<<[2..n]]

```

Usage example: `f 4` -\> `[1,4,5,8]`. Try it online!

The first `=<<` is in function context and translates to the lambda `\x -> reverse x == x` and the second `=<<` is in list context and equivalent to `concatMap`, i.e. map-and-flatten-one-list-level.
> 9 votes

# Answer
# 05AB1E, 12 bytes

```
µN2¹Ÿ%JÂQD½–

```

Try it online!

**Explanation**

```
µ              # until counter equals input do:
 N             # push current iterations number
     %         # modulus each in
  2¹Ÿ          # range [2 ... input]
      J        # joined to string
       ÂQ      # equals it's reverse
         D     # duplicate
          ½    # if true, increase counter
           –   # if true print iteration number

```
> 5 votes

# Answer
## Mathematica, 79 bytes

```
NestList[#+1//.x_/;!PalindromeQ[ToString/@Mod[x,Range@n+1]<>""]:>x+1&,1,n=#-1]&

```
> 4 votes

# Answer
# Python 2, ~~98~~ 97 bytes

```
n=input();i=j=0
while i<n:
 j+=1;l=''
 for k in range(2,n+1):l+=`j%k`
 if l==l[::-1]:i+=1;print j

```

Try it Online!
> 4 votes

# Answer
## JavaScript (ES6), 104 bytes

```
f=(n,x=(k=--n,2))=>k?([...Array(n)].map(_=>(r=x%++i+r,x%i),i=1,r='').join``==r?k--&&x+' ':'')+f(n,x+1):1

```

### Demo

**NB**: Because of the numerous recursive calls, this will crash for *n \> 8* on Firefox or *n \> 10* on Chrome.

```
f=(n,x=(k=--n,2))=>k?([...Array(n)].map(_=>(r=x%++i+r,x%i),i=1,r='').join``==r?k--&&x+' ':'')+f(n,x+1):1

for(n = 2; n < 9; n++) {
  console.log(n, '=>', f(n));
}
```
> 4 votes

# Answer
# MATL, 19 bytes

*Thanks to @AdmBorkBork for pointing out a mistake in an earlier version of the code, now corrected*

```
`@Gq:Q\VXztP=?@]NG<

```

Try it online!

### Explanation

```
`        % Do...while
  @      %   Push iteration index, starting at 1
  Gq:Q   %   Push [2 3 ... n], where n is the input
  \      %   Modulo, element-wise
  V      %   Convert to string. Numbers are separated by spaces
  Xz     %   Remove spaces
  tP     %   Duplicate, flip
  =      %   Equal? (element-wise)
  ?      %   If all results were true
    @    %     Push current iteration index. It is one of the sought numbers
  ]      %   End
  N      %   Push number of elements in stack
  G      %   Push input n
  <      %   Less than? This is the loop condition
         % End (implicit). Display (implicit)

```
> 3 votes

# Answer
# Scala, 90 86 82 bytes

```
(n:Int)=>Stream.from(1)filter{i=>val d=(2 to n)map(i%)mkString;d.reverse==d}take(n)

```

## Explanation

```
Stream.from(1)                              // From an infinite Stream starting from 1,
    filter ( i => {                         // keep only elements matching the next condition :
        val d=(2 to n)map(i%)mkString;      // Generate residues and convert to String,
        d.reverse==d                        // return true if palindrom, false otherwise
    })take(n)                               // Finally, take the n first elements matching the condition

```

## Test cases

```
val f = (n:Int)=>...    // assign function
(3 to 11).foreach { i =>
    println(i + "\n" + f(i).mkString(", ") + "\n")
}

```

## Results

```
3
1, 6, 7

4
1, 4, 5, 8

5
1, 50, 60, 61, 110

6
1, 30, 31, 60, 61, 90

7
1, 42, 43, 140, 182, 420, 421

8
1, 168, 169, 336, 337, 504, 505, 672

9
1, 2520, 2521, 5040, 5041, 7560, 7561, 10080, 10081

10
1, 280, 281, 560, 1611, 1890, 1891, 2170, 2171, 2241

11
1, 22682, 27720, 27721, 50402, 55440, 55441, 78122, 83160, 83161, 105842

```

## Edits

### #1 (90 =\> 86)

* anonymous function

### #2 (86 =\> 82)

* remove useless dot characters after parenthesis or bracket (ex. : `(2 to n).map(%i)` =\> `(2 to n)map(%i)`
> 3 votes

# Answer
# Jelly, 12 bytes

```
%Ð€ḊDFŒḂ
1ç#

```

### How?

```
1ç# - Main link: n
1   - initialise "i" at 1
  # - increment i and yield a list of the first n truthful results of:
 ç  -     last link (1) as a dyad

%Ð€ḊDFŒḂ - Link 1, test a value "i" for mod [2,n] being palindromic: i, n
 Ð€      - for each, mapped over the right argument, i.e. for j = 1 to n:
%        -     i modulo j
   Ḋ     - dequeue, i.e. discard the modulo 1 result
    D    - convert to decimal list (vectorises)
     F   - flatten into one list
      ŒḂ - is palindromic?

```

**Try it online!**
> 2 votes

# Answer
# PHP, 93 Bytes

```
for(;$x<$a=$argn;$s="")for($i=1,++$n;$i++<$a;)if($i==$a&strrev($s.=$n%$i)==$s)echo$n._.!++$x;

```

Online Version 2 Loops Output as string

Expanded

```
for(;$x<$a=$argn;$s="")
for($i=1,++$n;$i++<$a;)
    if($i==$a&strrev($s.=$n%$i)==$s)echo$n._.!++$x;

```

## PHP 130 Bytes

```
for(;count($r)<$a=$argn;$s=[])for($i=1,++$n;$i++<$a;){$s[]=$n%$i;if(count($s)==$a-1&strrev($j=join($s))==$j)$r[]=$n; }print_r($r);

```

Online Version 2 Loops

Expanded

```
for(;count($r)<$a=$argn;$s=[])
for($i=1,++$n;$i++<$a;){
    $s[]=$n%$i;
    if(count($s)==$a-1&strrev($j=join($s))==$j)$r[]=$n;
}
print_r($r);

```

## PHP, 139 Bytes with 1 loop

```
for($i=$n=1;count($r)<($a=$argn)&$i++<$a;){$s[]=$n%$i;if(count($s)==$a-1){if(strrev($j=join($s))==$j)$r[]=$n;$n++;$s=[];$i=1;}}print_r($r);

```

Online Version 1 Loop

Run with

```
echo '<string>' | php -nR '<code>'

```

Expanded

```
for($i=$n=1;count($r)<($a=$argn)&$i++<$a;){
    $s[]=$n%$i;
    if(count($s)==$a-1){
        if(strrev($j=join($s))==$j)$r[]=$n;
        $n++;
        $s=[];
        $i=1;
    }
}
print_r($r);

```
> 1 votes

# Answer
## CJam, 28 bytes

```
0ri:N{{)_N),2>f%s_W%#}g_p}*;

```

Try it online!

### Explanation

```
0          e# Push 0, the value we'll repeatedly increment to search for valid outputs.
ri:N       e# Read input, convert to integer, store in N.
{          e# Run this block N times...
  {        e#   Run this block until the condition is true, which will find the next
           e#   number with palindromic residues...
    )_     e#     Increment and duplicate.
    N),2>  e#     Push [2 3 ... N].
    f%     e#     Take the current value modulo each of these.
    s      e#     Flatten them into a single string.
    _W%    e#     Duplicate and reverse.
    #      e#     Try to find the reverse in the original. A common way to compute
           e#     "not equal" for strings of the same length.
  }g
  _p       e#   Print a copy of the result.
}*
;          e# Discard the final result to prevent printing it twice.

```
> 1 votes

# Answer
## QBIC, 48 bytes

```
:{A=G[2,a|A=A+!q%b$]~A=_fA||h=h+1?q]q=q+1~h=a|_X

```

Beats Mathematica! Sample run:

```
Command line: 10
 1
 280
 281
 560
 1611
 1890
 1891
 2170
 2171
 2241

```

Explanation:

```
:{          Get 'a' from the command line, start an inf. loop
A=G         Clear out whatever's in A$
[2,a|       For each of the numbers we want to modulo
A=A+        Add to A$
     q%b       our current number MODULO te loop iterator
    !   $      cast to string
]           NEXT
~A=_fA|     If the string of remainders is a palindrome (_f ... | is Reverse())
|h=h+1      THEN h=h+1 (h starts at 0) - this counts how many hits we've had
 ?q            also, print the number with the palindromic remainder
]           END IF
q=q+1       Test the next number
~h=a|_X     If we've had 'a' hits, quit.
            The last IF and the infinite loop are closed implicitly.

```
> 1 votes

# Answer
# Japt, 26 bytes

```
L³o fR{C=Uò2@R%XÃ¬ ¥CwÃj1U

```

Try it online! Takes a few seconds on *all* inputs, so be patient please.

This would be considerably shorter (and faster) if there were a built-in to get the first N numbers satisfying some condition:

```
R{C=Uò2@R%XÃ¬ ¥Cw}aU

```
> 1 votes

# Answer
# Jelly, 8 bytes

```
1%ⱮḊŒḂɗ#

```

Try it online!

## How it works

```
1%ⱮḊŒḂɗ# - Main link. Takes n on the left
1        - Set the return value to 1
       # - Count up i = 1, 2, ..., and return the first n which return true:
      ɗ  -   Combine the previous three links into a dyad
             with i on the left and n on the right:
  Ɱ      -     For each integer m in 1, 2, ..., n:
 %       -       i % m
   Ḋ     -     Remove i % 1
    ŒḂ   -     Is palindromic?

```
> 0 votes

# Answer
# Japt, 13 bytes

```
@õ!uX ÅêS}jU1

```

Try it or run all test cases

```
@õ!uX ÅêS}jU1     :Implicit input of integer U
@                 :Function taking an integer X as argument
 õ                :  Range [1,U]
  !uX             :  Mod X by each
      Å           :  Slice off the first
       êS         :  Is palindrome?
         }        :End function
          jU1     :Starting with 1, return the first U integers that return true

```
> 0 votes

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


title: Print the Super Collatz numbers

text:
# Question
Title: Print the Super Collatz numbers
The Collatz Sequence (also called the 3x + 1 problem) is where you start with any positive integer, for this example we will use 10, and apply this set of steps to it:

```
if n is even:
    Divide it by 2
if n is odd:
    Multiply it by 3 and add 1
repeat until n = 1

```

10 is even, so we divide by 2 to get 5. 5 is odd, so we multiply by 3 and add 1 to get 16. 16 is even, so cut it in half to get 8. Half of 8 is 4, half of 4 is 2, and half of 2 is 1. Since this took us 6 steps, we say that 10 has a **stopping distance** of 6.

A Super Collatz number is a number whose stopping distance is greater then the stopping distance of every number smaller than it. For example, 6 is a Super Collatz number since 6 has a stopping distance of 8, 5 has a stopping distance of 5, 4 has 2, 3 has 7, 2 has 1 and 1 has 0. (A006877 in the OEIS) You must take a number **n** as input, and output out all the Super Collatz numbers up to **n**.

# Rules

* Full Program or function is acceptable.
* You can not precompute or hard-code the Super Collatz sequence.
* You can take input in any reasonable format.
* Output can be returned as a list from the function, or printed to STDOUT or a file. Whichever is most convenient.
* Invalid inputs (non-numbers, decimals, negative numbers, etc.) result in undefined behavior.

# Sample ungolfed python

```
def collatzDist(n):
    if n == 1:
        return 0
    if n % 2 == 0:
        return 1 + collatzDist(n / 2)
    return 1 + collatzDist((n * 3) + 1)

n = input()

max = -1
superCollatz = []
for i in range(1, n + 1):
    dist = collatzDist(i)
    if dist > max:
        superCollatz.append(i)
        max = dist

print superCollatz

```

# Sample IO:

```
#in       #out
 4     --> 1, 2, 3
 50    --> 1, 2, 3, 6, 7, 9, 18, 25, 27
 0     --> invalid
 10000 --> 1, 2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711, 6171

```

Also here are the first 44 Super Collatz numbers:

```
1, 2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711, 6171, 10971, 13255, 17647, 23529, 26623, 34239, 35655, 52527, 77031, 106239, 142587, 156159, 216367, 230631, 410011, 511935, 626331, 837799

```

# Answer
> 0 votes
# Pyth, 23 bytes

```
q#eol.u@,/N2h*N3NN)STSQ

```

Demonstration

This works by taking the max of the range up to each number by their Collatz stopping distance, and checking whether that max is the number in question.

# Answer
> 2 votes
## Python 2, 104 bytes

```
c=lambda x:x>1and 1+c([x/2,x*3+1][x%2])
lambda n:[1]+[x for x in range(2,n)if c(x)>max(map(c,range(x)))]

```

`c` is a helper function that calculates the Collatz distance for a given integer. The unnamed lambda is the main function, which computes the super Collatz numbers up to (but not including) the input.

# Answer
> 2 votes
# Dyalog APL, 41 bytes

```
(∪⊢⍳⌈\)≢∘{1=⍵:⍬⋄2|⊃⌽⍵:⍵,∇1+3×⍵⋄⍵,∇⍵÷2}¨∘⍳

```

An unnamed function. Name or parenthesize to apply.

Test cases:

```
       ((∪⊢⍳⌈\)≢∘{1=⍵:⍬ ⋄ 2|⊃⌽⍵:⍵,∇ 1+3×⍵ ⋄ ⍵,∇ ⍵÷2}¨∘⍳)¨4 50 10000
┌─────┬────────────────────┬───────────────────────────────────────────────────────────────────────────────────────────┐
│1 2 3│1 2 3 6 7 9 18 25 27│1 2 3 6 7 9 18 25 27 54 73 97 129 171 231 313 327 649 703 871 1161 2223 2463 2919 3711 6171│
└─────┴────────────────────┴───────────────────────────────────────────────────────────────────────────────────────────┘

```

0 results in undefined behaviour.

# Answer
> 1 votes
# Haskell, 84 bytes

```
c 1=0;c x|odd x=1+c(3*x+1)|0<1=1+c(div x 2)
f x=[n|n<-[1..x],all(c n>)$c<$>[1..n-1]]

```

This is massively slow, of course, but it works!

# Answer
> 1 votes
## ES6, ~~86~~ 83 bytes

```
n=>(i=m=0,c=n=>n<3?n:c(n&1?n*3+1:n/2)+1,[for(x of Array(n))if(c(++i)>m&&(m=c(i)))i])

```

Edit: Saved 3 bytes by switching from `filter` to an array comprehension.

# Answer
> 1 votes
# Oracle SQL 11.2, 329 bytes

```
WITH q(s,i)AS(SELECT LEVEL s,LEVEL i FROM DUAL CONNECT BY LEVEL<=:1 UNION ALL SELECT s,DECODE(MOD(i,2),0,i/2,i*3+1)i FROM q WHERE i<>1),v AS(SELECT s,COUNT(*)-1 d FROM q GROUP BY s),m AS(SELECT s,d,MAX(d)OVER(ORDER BY s ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING)m FROM v)SELECT s FROM m WHERE(d>m OR s=1)AND:1>0ORDER BY 1;

```

Un-golfed version

```
WITH q(s,i) AS
  (
    SELECT LEVEL s, LEVEL i
    FROM DUAL CONNECT BY LEVEL <= :1
    UNION ALL
    SELECT q.s, DECODE(MOD(i,2),0,i/2,i*3+1)i FROM q WHERE q.i <> 1
  )
, v AS (SELECT s, COUNT(*)-1 d FROM q GROUP BY s)
, m AS (SELECT s, d, MAX(d)OVER(ORDER BY s ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING) m FROM v)
SELECT * FROM m WHERE (d>m OR s=1) AND :1>0
ORDER BY 1;

```

The q view is a true recursive view (not a hierarchical query with CONNECT BY) that compute all steps toward 1 for every integer between 1 and :1.

The v view compute the stopping distances.

The m view use the analytical version of MAX to apply it to every rows preceding, excluding the current row. That way for each integer we know it's stopping distance and the current greatest stopping distance.

The final query check if the stopping distance is greater than the greatest stopping distance. And adds a few tricks to handle 1 and the special case of :1 having a value of 0.

# Answer
> 0 votes
# , 30 chars / 38 bytes

```
⩥ïⓜМȬ⧺$,a=[])⋎⟮aꝈ-1⟯>ɐ⅋(ɐ=Ⅰ,ᵖ$

```

`Try it here (Firefox only).`

The only reason I didn't post this earlier was because I wasn't clear on the specs. Uses a custom encoding that encodes 10-bit chars.

# Explanation

`⩥ïⓜ` creates a range `[0,input)` to map over. `МȬ⧺$,a=[])` generates Collatz numbers in an empty array, and `⋎⟮aꝈ-1⟯>ɐ` uses the array of Collatz numbers to get the stopping distance and check if that's greater than the previous maximum stopping distance. If so, `⅋(ɐ=Ⅰ,ᵖ$` makes the current stopping distance the maximum stopping distance and pushes the current item in the range to the stack. After, the stack's items are implicitly printed.

# Answer
> 0 votes
# Jelly, 17 bytes

```
×3‘$HḂ?ƬL$€<Ṫ$PµƇ

```

Try it online!

I reckon there's still a couple of bytes that can be removed.

## How it works

```
×3‘$HḂ?ƬL$€<Ṫ$PµƇ - Main link. Takes n on the left
               µƇ - Generate the list [1, 2, ..., n] and filter each i based on the following:
         $€       -   Over each j [1, 2, ..., i]:
       Ƭ          -     Do the following until reaching a fixed point:
      ?           -       If statement:
     Ḃ            -         Condition: i is odd
   $              -         If so:
×3                -           Multiply by 3
  ‘               -           Increment
    H             -         Else: Halve
        L         -      Take the length
                      Call this list of lengths l
             $    -   Group the previous two links and run over l
            Ṫ     -     Remove the last value of l
           <      -     Is this greater than each value in l?
              P   -   Is this true for all values?

```

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


# Question
Title: How many ways to write numbers as sums of squares?
# Task

Given two integers \\$d\\$ and \\$n\\$, find the number of ways to express \\$n\\$ as a sum of \\$d\\$ squares. That is, \\$n = r\_1^2 + r\_2^2 + ... + r\_d^2\\$, such that \\$r\_m\\$ is an integer for all integers \\$1 ≤ m ≤ d\\$. Note that swapping two **different** values (e.g. \\$r\_1\\$ and \\$r\_2\\$) is considered different from the original solution.

For instance, the number 45 can be written as a sum of 2 squares 8 different ways:

$$\begin{align} & 45 \\ & = (-6)^2 + (-3)^2 \\ & = (-6)^2 + 3^2 \\ & = (-3)^2 + (-6)^2 \\ & = (-3)^2 + 6^2 \\ & = 3^2 + (-6)^2 \\ & = 3^2 + 6^2 \\ & = 6^2 + (-3)^2 \\ & = 6^2 + 3^2 \end{align}$$

# Rules

* Built-in solutions are allowed but non-competing (ahem, *Mathematica*)
* Standard loopholes are also forbidden.
* The inputs may be reversed.

# Example I/O

```
In:   d, n

In:   1, 0
Out:  1

In:   1, 2
Out:  0

In:   2, 2
Out:  4

In:   2, 45
Out:  8

In:   3, 17
Out:  48

In:   4, 1000
Out:  3744

In:   5, 404
Out:  71440

In:   11, 20
Out:  7217144

In:   22, 333
Out:  1357996551483704981475000

```

This is , so submissions using the fewest bytes win!

# Answer
> 7 votes
# Python 3, 125 bytes

```
n,d=eval(input())
W=[1]+[0]*n
exec("W=[sum(-~(j>0)*W[i-j*j]for j in range(int(i**.5)+1))for i in range(n+1)];"*d)
print(W[n])

```

Try it online!

Finishes the last testcase in 0.078 s. Naive complexity is O(*d* *n* 2).

# Answer
> 5 votes
# Mathematica, 8 bytes, non-competing

```
SquaresR

```

# Answer
> 5 votes
# Jelly, 9 bytes

```
Nr⁸²ṗS€ċ⁸

```

Try it online!

Takes `n` and `d` in this order.

# Answer
> 4 votes
# MATL, 13 bytes

```
y_t_&:Z^U!s=s

```

Inputs are `n`, then `d`. Some of the test cases run out of memory.

**Try it online!**

### Explanation

Consider inputs `17`, `3`.

```
y     % Implicit inputs. Duplicate from below
      % STACK: 17, 3, 17
_     % Negate
      % STACK: 17, 3, -17
t_    % Duplicate. Negate
      % STACK: 17, 3, -17, 17
&:    % Two-input range
      % STACK: 17, 3, [-17 -16 ... 17]
Z^    % Cartesian power. Gives a matrix where each Cartesian tuple is a row
      % STACK: 17, [-17 -17 -17; -17 -17 -16; ...; 17 17 17]
U     % Square, element-wise
      % STACK: 17, [289 289 289; 289 289 256; ...; 289 289 289]
!s    % Transpose. Sum of each column
      % STACK: 17, [867 834 ... 867]
=     % Equals?, element-wise
      % STACK: 17, [0 0 ... 0] (there are 48 entries equal to 1 in between)
s     % Sum. Implicit display
      % STACK: 48

```

# Answer
> 3 votes
## Haskell, 43 bytes

```
0#0=1
d#n=sum[(d-1)#(n-k*k)|d>0,k<-[-n..n]]

```

Just your basic recursion. Defines a binary infix function `#`. Try it online!

## Explanation

```
0#0=1            -- If n == d == 0, give 1.
d#n=             -- Otherwise,
 sum[            -- give the sum of
  (d-1)#(n-k*k)  -- these numbers
  |d>0,          -- where d is positive
   k<-[-n..n]]   -- and k is between -n and n.

```

If `d == 0` and `n /= 0`, we are in the second case, and the condition `d>0` causes the list to be empty. The sum of the empty list is 0, which is the correct output in this case.

# Answer
> 2 votes
# Pari/GP, 31 bytes

```
d->n->sum(i=-n,n,x^i^2)^d\x^n%x

```

Try it online!

# Answer
> 2 votes
# 05AB1E, 10 bytes

```
Ð(Ÿ²ã€nOQO

```

Takes the arguments as n, then d. Has problems solving the bigger test cases.

Try it online!

### Explanation

```
Ð(Ÿ²ã€nOQO   Arguments n, d
Ð            Triplicate n on stack
 (           Negate n
  Ÿ          Range: [-n ... n]
   ²ã        Caertesian product of length d
     €n      Square each number
       OQ    Sum of pair equals n
         O   Total sum (number of ones)

```

# Answer
> 2 votes
# Jelly, 23 bytes

```
‘ṬUµJ²fJ[0]ẋ;€ḤSḣL+µ⁹¡Ṫ

```

Try it online!

Port of my Python solution. Finishes the last testcase in 2.977 s.

# Answer
> 2 votes
# Mathematica, 38 bytes

```
Count[Tr/@Tuples[Range[-#,#]^2,#2],#]&

```

Pure function taking the inputs in the order `n`, `d`. `Range[-#,#]^2` gives the set of all possibly relevant squares, with positive squares listed twice to make the count correct; `Tuples[...,#2]` produces the `d`-tuples of such squares; `Tr/@` sums each `d`-tuple; and `Count[...,#]` counts how many of the results equal `n`.

The first few test cases terminate quickly, but I estimate this would take about half a year to run on the test case `1000,4`. Replacing `Range[-#,#]` by the (longer but) more sensible `Range[-Floor@Sqrt@#,Floor@Sqrt@#]` speeds up that computation to about 13 seconds.

# Answer
> 2 votes
# Jelly, 7 bytes

```
ŒRṗ²§ċ⁸

```

Try it online!

Very inefficient; fails to finish within a minute for the last 4 test cases.

## How it works

```
ŒRṗ²§ċ⁸ - Main link. Takes n on the left, d on the right
ŒR      - Yield [-n, -n+1, ..., 0, ..., n-1, n]
  ṗ     - Yield all sublists of this range of length d
   ²    - Square each number
    §   - Take the sum of each list
     ċ  - Count the occurrences of...
      ⁸ - ...n

```

# Answer
> 1 votes
## Python 2, 138

Very inefficient solution with my beloved eval. Why not?
Try it online

```
lambda n,d:d and 4*eval(eval("('len({('+'i%s,'*d+'0)'+'for i%s in range(n)'*d+'if '+'i%s**2+'*d+'0==n})')%"+`tuple(range(d)*3)`),locals())

```

It generated and evaluates code like this:

```
len({(i0,i1,0)for i0 in range(n)for i1 in range(n)if i0**2+i1**2+0==n})

```

So for some big **d** it will run very long and consume a lot of memory, having complexity of O(n^d)

# Answer
> 1 votes
# Mathematica, ~~53~~ 51 bytes

```
SeriesCoefficient[EllipticTheta[3,0,x]^#,{x,0,#2}]&

```

# Answer
> 1 votes
# , 23 bytes

```
{+/y=+/{x*x}y-!x#1+2*y}

```

Try it online! It's a simple brute forcer.

# Answer
> 1 votes
# Pyth - 16 bytes

```
lfqQsm*ddT^}_QQE

```

Try it

It's horribly inefficient

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


title: Square free Numbers

text:
# Question
Title: Square free Numbers
Given a number N, write the shortest complete program to find the number of square-free integers below N.

```
Sample Input
100000
Sample Output
60794

```

Constraints:

1. Should work for all positive N below 1,000,000
2. Should not take more than 10 secs.
3. Please do not use built in functions, please.

# Answer
## J, 21 chars

```
+/(]=&#~.)@:q:"0>:i.N

```

Checks for each integer from 1 to N if any prime factor appears more than once.

eg:

```
+/(]=&#~.)@:q:"0>:i.10000
 6083
+/(]=&#~.)@:q:"0>:i.100000
 60794

```

Takes ~3secs for N=1,000,000 (@2GHz,1core)
> 3 votes

# Answer
## Python 2: 71 chars

```
i=n=input()
A=[1]*n
while~-i:A[i*i::i*i]=~-n/i/i*[0];i-=1
print~-sum(A)

```

Basically an optimization of Keith Randall's solution of zeroing out numbers that are multiples of squares. The main improvement is directly zeroing out the sublist `A[i*i::i*i]`, which requires awkwardly calculating its length or else Python refuses to do the slice assignment.

Lots of `~-` are used for `-1`. The `~-sum(A)` corrects for `0` being falsely counted as a squarefree number.
> 7 votes

# Answer
## Python, 84 characters

```
n=input()
R=range(n)
A=[1]*n
for i in R[2:]:
 for x in R[::i*i]:A[x]=0
print sum(A)

```
> 2 votes

# Answer
**Java Solution**

```
import java.io.*;
    public class Main{
            public static void main(String[] args)throws Exception {
              int N=Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine());
              int list[]=new int[N];
    for (int i=0;i<N;i++){
    list[i]=(i+1);
    }
    for (int i=1;i<N;i++){
    if (Math.sqrt(list[i])-Math.floor(Math.sqrt(list[i]))==0){
    for(int j=i;j<N;j+=(i+1)){
    list[j]=-1;
    }}}
    int c=0;
    for (int i=0;i<N;i++){
    if (list[i]!=-1){
    c++;
    }}System.out.println(c);}}

```

IDEONE http://ideone.com/Yf467
> 1 votes

# Answer
# Python - 105 bytes

```
s=input()
C=set()
for q in [k*k for k in range(2,s+1)]:
 i=1
 while q*i<=s:C.add(q*i);i+=1
print s-len(C)

```
> 1 votes

# Answer
# APL (Dyalog Extended), 11 bytes

```
+/≡∘∪⍨⍤⍭¨⍤⍳

```

Try it online!

Bubbler's tacit form. (-4 bytes)

-1 byte from Adám.

# APL (Dyalog Extended), 16 bytes

```
{+/{(⊢≡∪)⍭⍵}¨⍳⍵}

```

Try it online!

Same approach as the J answer, `100000` runs under 10 secs on tio, so it should be all good.

## Explanation

```
{+/{(⊢≡∪)⍭⍵}¨⍳⍵}
   {(⊢≡∪)⍭⍵}     square-free checking function
   {     ⍭⍵}     prime factors of ⍵
    (⊢≡∪)        are the unique values equal to the originals?
                 function ends
            ¨⍳⍵  map function to range 1-n
 +/              sum the resulting boolean array

```
> 1 votes

# Answer
# Wolfram Language (Mathematica), 24 bytes

```
Count[√Range@#,_^_|1]&

```

Try it online!

`SquareFreeQ` is too long anyways.
> 1 votes

# Answer
# Ruby - ~~119~~ 114

```
I=gets.to_i
m=[]
(s=->i{(I>i*i)?s[i+1]+[i*i]:[]})[2].map{|s|(1..I).map{|x|s*x<I||break;m<<s*x}}
p ([*1...I]-m).size

```
> 0 votes

# Answer
## C

**144 Chars**
```
#define m 1000001
x[m];
main(s,o,f){
for(o=2;o*o<m;o++)
for(f=s=o*o;f<m;f+=s)x[f]=1;
scanf("%d",&f);
for(s=0,o=1;o<f;o++)if(!x[o])s++;
printf("%d",s);
}

```

Instantaneous Solution on my crummy PC! :)
> 0 votes

# Answer
# Java - 278 Characters

A golfed version of the Java answer already demonstrated here without changing the spirit of the answer, because the original poster's idea golfed could have saved 50%, which is huge compared to most other languages!

```
class T {public static void main(String[] a) {int n,i,j;double k;n=Integer.parseInt(a[0]);int l[]=new int[n];for(i=0;i<n;)l[i]=1+i++;for (i=1;i<n;i++) {k=Math.sqrt(l[i]);if(k==Math.floor(k))for (j=i;j<n;j+=i+1)l[j]=-1;}j=0;for(i=0;i<n;)if(l[i++]!=-1)j++;System.out.println(j);}}

```

Specifically, a few Java golfing tricks were used to optimize this:

* Removed long variable names
* Removed the use of a Reader in favor of using an argument (saves a huge amount of characters, including import, Exception handling, and casting the reader in general)
* Removed extra brackets and parentheses using single-line actions for ifs and fors where applicable
* Declare ints beforehand together to reduce calls to int
* Declare a double and optimize square calculation
* Extracted ++ where possible

This shows that the original ungolfed solution of 565 characters can be brought down to a very respectable \<300 character answer even with a more structured language like Java.

### Ungolfed

```
class T {
    public static void main(String[] a) {
        int n, i, j;
        double k;
        n = Integer.parseInt(a[0]);
        int l[] = new int[n];
        for (i = 0; i < n;)
            l[i] = 1 + i++;
        for (i = 1; i < n; i++) {
            k = Math.sqrt(l[i]);
            if (k == Math.floor(k))
                for (j = i; j < n; j += i + 1)
                    l[j] = -1;
        }
        j = 0;
        for (i = 0; i < n;)
            if (l[i++] != -1)
                j++;
        System.out.println(j);
    }
}

```
> 0 votes

# Answer
# GNU coreutils, 44 bytes

```
seq $1|factor|sed '$d;/\( .*\)\1\b/d'|wc -l

```

This factors every number up to N, removes the last line (as we're only counting results strictly less than N), and removes any line with a repeated word. Finally, we count the remaining lines.

The regular expression `\( .*\)\1\b` looks over-generous, but it takes advantage of what we know about the output of `factor` \- the factors will be in ascending order, with exactly one space between each.

With N=1,000,000, this completes on my machine in about ¼ second.
> 0 votes

# Answer
# Japt `-x`, 8 bytes

```
õ_=k)eZâ

```

Try it

```
õ_=k)eZâ     :Implicit input of integer U
õ            :Range [1,U]
 _           :Map each Z
  =          :  Reassign to Z
   k         :  Prime factors of Z
    )        :  End reassignment
     e       :  Test equality with
      Zâ     :  Z deduplicated
             :Implicit output of sum of resulting array

```
> 0 votes

---
Tags: code-golf, restricted-time
---


title: Triangles with rational side lengths

text:
# Question
Title: Triangles with rational side lengths
This challenge will have give you a positive integer \\$n\\$ and ask you to output \\$t(n)\\$, the number of triangles (up to congruence) satisfying the three conditions:

* The triangles have perimeter of 1,
* the triangles have side lengths \\$\displaystyle\frac{a\_1}{b\_1}, \frac{a\_2}{b\_2}\\$, and \\$\displaystyle\frac{a\_3}{b\_3}\\$, and
* when written in lowest terms, \\$\max \\{b\_1, b\_2, b\_3\\} = n\\$.

### Examples

For \\$n = 2\\$, there are no such triangles, so \\$t(2) = 0\\$.

For \\$n = 3\\$, there is one such triangle, so \\$t(3) = 1\\$: $$ \frac{a\_1}{b\_1} = \frac{a\_2}{b\_2} = \frac{a\_3}{b\_3} = \frac 1 3 $$ For \\$n = 4\\$, there are no such triangles, so \\$t(4) = 0\\$.

For \\$n = 5\\$, there is one such triangle, so \\$t(5) = 1\\$: $$ \left(\frac{a\_1}{b\_1}, \frac{a\_2}{b\_2}, \frac{a\_3}{b\_3}\right) = \left(\frac 1 5, \frac 2 5, \frac 2 5\right) $$

For \\$n = 6\\$, there are no such triangles, so \\$t(6) = 0\\$.

For \\$n = 7\\$, there are two such triangles, so \\$t(7) = 2\\$: $$ \left(\frac{a\_1}{b\_1}, \frac{a\_2}{b\_2}, \frac{a\_3}{b\_3}\right) = \left(\frac 2 7, \frac 2 7, \frac 3 7\right) \hspace{1em} \text{and} \hspace{1em} \left(\frac{a\_1}{b\_1}, \frac{a\_2}{b\_2}, \frac{a\_3}{b\_3}\right) = \left(\frac 1 7, \frac 3 7, \frac 3 7\right) $$

For \\$n = 8\\$, there is one such triangle, so \\$t(8) = 1\\$: $$ \left(\frac{a\_1}{b\_1}, \frac{a\_2}{b\_2}, \frac{a\_3}{b\_3}\right) = \left(\frac 1 4, \frac 3 8, \frac 3 8\right) $$

The first thirty pairs, \\$\left(n, t(n)\right)\\$ are:

```
(1,0),(2,0),(3,1),(4,0),(5,1),(6,0),(7,2),(8,1),(9,2),(10,1),(11,4),(12,2),(13,5),(14,2),(15,5),(16,4),(17,8),(18,4),(19,10),(20,8),(21,10),(22,6),(23,14),(24,8),(25,15),(26,9),(27,16),(28,14),(29,21),(30,13)

```

---

This is a challenge, so shortest code wins.

# Answer
# 05AB1E, 26 bytes

```
Lã3ãʒàQ}€€.«/DOÏ€{ʒR`+‹}Ùg

```

Brute-force approach, so extremely slow. Already times out for \\$t(10)\\$..

Try it online or verify the first 15 test cases (`ã` has been replaced with `2.Æʒ`¿}` to speed things up slightly).

**Explanation:**

```
L              # Push a list in the range [1,(implicit) input]
 ã             # Get all pairs with these integers
  3ã           # Create all possible triplets of these pairs
    ʒ          # Filter this list of triplets by:
     à         #  Get the flattened maximum
      Q        #  And check that it's equal to the (implicit) input
    }€         # After the filter: map over each triplet:
      €        #  Map over each pair in this triplet:
       .«      #   Right-reduce this pair by:
         /     #    Dividing
     D         # Then duplicate the list of triplets
      O        # Sum each inner triplet
     Ï         # And only keep the triplets at the truthy (==1) indices
      €        # Map over each triplet of decimal values:
       {       #  Sort them from lowest to highest
        ʒ      # Filter the list of triplets further by:
         R     #  Reverse the triplet from highest to lowest
          `    #  Pop and push all three separated to the stack
           +   #  Add the top two (the lowest two) together
            ‹  #  And check that they're larger than the highest one
        }Ù     # After this filter: uniquify the list of triplets
          g    # And pop and push its length
               # (after which this is output implicitly as result)

```

Here all the rules, and which piece of codes covers them:

* The triangles have a perimeter of 1: `DOÏ`
* The triangles have side lengths \\$\displaystyle\frac{a\_1}{b\_1}, \frac{a\_2}{b\_2}\\$, and \\$\displaystyle\frac{a\_3}{b\_3}\\$, and when written in lowest terms, \\$\max(b\_1, b\_2, b\_3) = n\\$: `ʒàO}`
* The triangles are not degenerate, thus \\$a+b\>c\land a+c\>b\land b+c\>a\\$: `€{ʒR`+‹}` (after sorting \\$\[a,b,c\]\\$ in descending order, we can check whether \\$a\<b+c\\$)

The other pieces of code are to generate all possible triplets of pairs: `Lã3ã`; actually getting their decimal values: `€€.«/`; and counting the final amount of triplets that are valid: `g`. The uniquify `Ù` is to filter out duplicated triplets which are in a different order from the .

Explanation of the snippet that slightly sped up the test suite:

```
 2.Æ         # Get all possible pairs in ascending order with unique values
    ʒ        # Filter this list of pairs by:
     `       #  Pop and push both values separated to the stack
      ¿      #  Get the greatest common divisor between the two: gcd(a,b)
             #  (Note: only 1 is truthy in 05AB1E, so this filter checks that the
             #   fraction cannot be lowered in terms any further)
    }        # Close the filter
             # (Now there are less pairs we create triplets with and have to check in
             #  the other filters)

```
> 6 votes

# Answer
# JavaScript (ES6),  ~~188 184~~  183 bytes

```
n=>{for(o=r=[],a=n;x=--a/n;)for(P=n;P;P--)for(p=P;y=--p/P;)for(Q=n;Q;)!(z=Q-x*Q-y*Q,g=(a,b)=>b?g(b,a%b):z%1||a>1)(a,n)&!o[k=[x,y,z/=Q--].sort()]&x+y>z&x+z>y&y+z>x?o[k]=++r:0;return+r}

```

Try it online!

### How?

Given \\$n\\$, we look for all pairs \\$(x,y)\\$ defined as:

$$x=\dfrac{a}{n},\\:1\le a \<n$$ $$y=\dfrac{p}{P},\\:1\le p \< P \le n$$

For each pair \\$(x,y)\\$, we compute \\$z=1-x-y\\$.

The triplet \\$(x,y,z)\\$ is valid if all the following conditions are met:

* \\$a\\$ and \\$n\\$ are coprime
* there is some \\$Q,\\:1\le Q \le n\\$ such that \\$Qz\\$ is an integer
* we have \\$x+y\>z\\$, \\$x+z\>y\\$ and \\$y+z\>x\\$

### Commented

*NB: this is the 184-byte version, which is slightly more readable*

```
n => {                       // n = input
  for(                       // 1st loop:
    o = r = [],              //   o = lookup object, r = output counter
    a = n; x = --a / n;      //   go from a = n - 1 to 1
  )                          //   and define x = a / n
  for(                       // 2nd loop:
    P = n; P; P--            //   go from P = n to 1
  )                          //
  for(                       // 3rd loop:
    p = P; y = --p / P;      //   go from p = P - 1 to 1
  )                          //   and define y = p / P
  for(                       // 4th loop:
    Q = n; Q;                //   go from Q = n to 1
  ) (                        //
      z = Q - x * Q - y * Q, //   define z = Q(1 - x - y)
      g = (a, b) =>          //   g is a helper function which
        b ?                  //     recursively computes the GCD
          g(b, a % b)        //     of 2 given integers
        :                    //
          a < 2              //     and returns true if it equals 1
    )(a, n) &                //   use it to figure out if a and n are coprime
    !(z % 1) &               //   make sure that z is an integer
    !o[                      //   make sure that the key k ...
      k = [x, y, z /= Q--]   //     ... made of [ x, y, z / Q ] ...
          .sort()            //     ... and sorted (lexicographically)
    ] &                      //   was not already found
    x + y > z &              //   make sure that all triangle inequalities
    x + z > y &              //   are fulfilled
    y + z > x ?              //   if all of the above is true:
      o[k] = ++r             //     increment r and save the key in o
    :                        //   else:
      0;                     //     do nothing
  return +r                  // return the final result
}                            //

```
> 8 votes

# Answer
# Python 3, 190 bytes

```
lambda x:sum(1for a,b,c in i.product(*[q(range(1,x+1))]*3)if{a,b,c}&q([x])and a<=b<=c<1==a+b+c>2*c)
q=lambda a:{x/y for y in a for x in range(y)if math.gcd(x,y)<2}
import math,itertools as i

```

Try it online!

The fraction part is just so it doesn't run into precision errors. It also makes it really slow though; this causes test case 20 (and supposedly later ones) to fail if disabled but uncomment it if you want to test larger numbers (though TIO won't be able to do it in time anyway; 20 takes about 10 minutes I believe).
> 5 votes

# Answer
# Perl 5, 241 bytes

```
sub{sub g{($a,$b)=@_;$b?g($b,$a%$b):$a}$r=0;for$a(@m=map{$N=$_;grep g(@$_)<2,map[$_,$N,$_/$N],1..$N-1}2..($n=pop)){for$b(@m){for(@m){($A,$B,$C)=map$$_[2],$a,$b,$_;$r++if$A<=$B&$B<=$C&1e-9>abs$A+$B+$C-1&$A+$B>$C&&grep$$_[1]==$n,$a,$b,$_}}}$r}

```

Try it online!

TIO times out at 60 seconds, it found 28 of the 30 test cases at that time. Very brute force.

```
sub t {
  $n=pop;                             #input number --> n
  sub g{($a,$b)=@_;$b?g($b,$a%$b):$a} #greatest common divisor,
                                      #about the worlds oldest algorithm
  $r=0;                               #result counter r
  @m=map {                            #m = list of 3-elem-arrays: nominator,
    $N=$_;                            #denominator and floating point fraction
    grep g(@$_)<2,                    #keep only irreducible fractions
   #grep g(@$_)<2&&g($$_[1],$n)>1,    #run faster with this grep but same result
    map [$_,$N,$_/$N], 1..$N-1        #all nominators 1 to N-1
  }
  2..$n;                              #with all denominators 2 to n
  for $a (@m){                        #loop through m on three levels a,b,c
    for $b (@m){
      for $c (@m){
        ($A,$B,$C)=map$$_[2],$a,$b,$c;#A,B,C is the fractions, side lengths
        $r++
          if $A<=$B                   #increase r result if length A < B
          && $B<=$C                   #and B < C lengths ABC sorted by length
          && 1e-9 > abs $A+$B+$C-1    #and A+B+C=1, taking care of f.p. errors
          && $A+$B > $C               #and A+B>C (not a trangle if not)
          && grep$$_[1]==$n,$a,$b,$_  #and at least one fraction must
                                      #have denominator = n
  }}}
  $r                                  #return result counter
}

```
> 3 votes

# Answer
# Charcoal, 135 bytes

```
ＮθＦΦθ∧ι¬﹪÷Ｘ²×ιθ⊖Ｘ²θ⊖Ｘ²ιＦ…·²θＦΦκ∧λ¬﹪÷Ｘ²×λκ⊖Ｘ²κ⊖Ｘ²λＦ…·²θＦΦμ∧ν¬﹪÷Ｘ²×νμ⊖Ｘ²μ⊖Ｘ²ν«≔××θκμη≔⟦×ι×κμ×λ×θμ×ν×θκ⟧ζ≔⟦η⌊ζ⌈ζ⟧ε¿∧∧⁼ηΣζ‹⊗⌈ζΣζ¬№υε⊞υε»ＩＬυ

```

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

```
Ｎθ

```

Input \\$ n \\$. We'll assume \\$ b\_1=n \\$ for now.

```
ＦΦθ∧ι¬﹪÷Ｘ²×ιθ⊖Ｘ²θ⊖Ｘ²ι

```

Loop for all values \\$ 0\<a\_1\<b\_1 \\$ such that \\$ a\_1 \\$ and \\$ b\_1 \\$ are coprime.

```
Ｆ…·²θ

```

Loop for all values \\$ 2 \le b\_2 \le n \\$.

```
ＦΦκ∧λ¬﹪÷Ｘ²×λκ⊖Ｘ²κ⊖Ｘ²λ

```

Loop for all values \\$ 0\<a\_2\<b\_2 \\$ such that \\$ a\_2 \\$ and \\$ b\_2 \\$ are coprime.

```
Ｆ…·²θ

```

Loop for all values \\$ 2 \le b\_3 \le n \\$.

```
ＦΦμ∧ν¬﹪÷Ｘ²×νμ⊖Ｘ²μ⊖Ｘ²ν«

```

Loop for all values \\$ 0\<a\_3\<b\_3 \\$ such that \\$ a\_3 \\$ and \\$ b\_3 \\$ are coprime.

```
≔××θκμη

```

Calculate a common denominator for the fraction \\$ \frac {a\_1} {b\_1} + \frac {a\_2} {b\_2} + \frac {a\_3} {b\_3} \\$.

```
≔⟦×ι×κμ×λ×θμ×ν×θκ⟧ζ

```

Calculate the numerators of the three fractions using the common denominator.

```
≔⟦η⌊ζ⌈ζ⟧ε

```

Get the denominator and minimum and maximum numerator. These don't depend on the order of the fractions, so will identify duplicates.

```
¿∧∧⁼ηΣζ‹⊗⌈ζΣζ¬№υε

```

Check that the numerators sum to the denominator (i.e. the perimeter is \\$ 1 \\$), that the largest numerator is less than half the sum (i.e. the triangle is not degenerate), and that the fractions haven't already been seen in a different order.

```
⊞υε

```

If all the tests pass then record this as a seen set of fractions.

```
»ＩＬυ

```

Print the number of fractions found.
> 3 votes

---
Tags: code-golf, sequence, geometry
---


title: To exponential digit growth and beyond!

text:
# Question
Title: To exponential digit growth and beyond!
## Challenge

Given a base \\$1 \< b \< 10\\$ and an index \\$t \ge 1\\$, output term \\$x\_t\\$, defined as follows:

* \\$x\_1 = 11\_{10}\\$
* \\$x\_{i+1}\\$ is obtained by converting \\$x\_i\\$ to base \\$b\\$ and then reinterpreting its digits in base \\$10\\$
* Output should be in base \\$10\\$

A walk through for base 5, term 5 would be:

* \\$x\_1 = 11\_{10}\\$.
* \\$11\_{10} = 21\_{5}\\$ so \\$x\_2 = 21\_{10}\\$.
* \\$21\_{10} = 41\_{5}\\$ so \\$x\_3 = 41\_{10}\\$.
* \\$41\_{10} = 131\_{5}\\$ so \\$x\_4 = 131\_{10}\\$.
* \\$131\_{10} = 1011\_{5}\\$ so \\$x\_5 = 1011\_{10}\\$.
* We output the string `"1011"` or the integer `1011`.

## Test Cases

Note: these are one indexed

```
base 2, term 5 --> 1100100111110011010011100010101000011000101001000100011011011010001111011100010000001000010011100011
base 9, term 70 --> 1202167480887
base 8, term 30 --> 4752456545
base 4, term 13 --> 2123103032103331200023103133211223233322200311320011300320320100312133201303003031113021311200322222332322220300332231220022313031200030333132302313012110123012123010113230200132021023101313232010013102221103203031121232122020233303303303211132313213012222331020133

```

## Notes

* Standard loopholes are not allowed
* Any default I/O method is allowed
* You may use different indexes (such as 0-indexed, 1-indexed, 2-indexed, etc) for \\$t\\$
* You may output the first \\$t\\$ terms.
* As this is , **shortest code wins for that language**

# Answer
> 6 votes
# JavaScript (Node.js), 40 bytes

*Thanks to @Neil for saving 5 bytes on this version and 2 bytes on the BigInt version*

Takes input as `(t)(base)`, where \\$t\\$ is 1-indexed.

```
n=>g=(b,x=11)=>--n?g(b,+x.toString(b)):x

```

Try it online!

---

# JavaScript (Node.js), 48 bytes (BigInt version)

Takes input as `(t)(base)`, where \\$t\\$ is 1-indexed. Returns a BigInt.

```
n=>g=(b,x=11n)=>--n?g(b,BigInt(x.toString(b))):x

```

Try it online!

# Answer
> 5 votes
# 05AB1E, 5 bytes

```
>IF¹B

```

Try it online!

**Explanation**

```
>       # increment <base>
 IF     # <term> times do:
   ¹B   # convert from base-10 to base-<base>

```

Note that there is no need to explicitly start the sequence at **11**.
Starting at `base+1` and doing an extra iteration will result in the first iteration giving **11**.

# Answer
> 3 votes
# Japt, 9 bytes

```
ÆB=sV n
B

```

Try it

```
(Two inputs, U and V)
Æ            Range [0..U)
 B=          For each, set B (B is preinitialized to 11) to
   sV          B's previous value converted to base-V
   n           and back to base-10
B            Print out B's final value

```

# Answer
> 3 votes
# Husk, 7 bytes

```
!¡odB¹→

```

Try it online! This version is 2-indexed; it takes the two inputs \\$b\\$ and \\$t\\$ as arguments.

### Explanation

```
!¡odB²→²⁰  (Written with explicit arguments; let B and T denote them.)
!       ⁰  Take element T of
 ¡          the function repeatedly applied to
      →²     B + 1:
  o B²       Convert to base B
  od         then convert to decimal.

```

# Answer
> 2 votes
# Wolfram Language (Mathematica), 46 bytes

```
bNest[FromDigits[#~IntegerDigits~b]&,11,#]&

```

Try it online!

Call with `f[base][t]`. 0-indexed.

# Answer
> 2 votes
# Python 2, 71 bytes

```
def f(b,n):h=lambda x:x and x%b+10*h(x/b);return n and h(f(b,n-1))or 11

```

Try it online!

0-indexed.

# Answer
> 2 votes
# Retina, 67 bytes

```
.+,(\d+)
11,$1*
"$+"{`^\d+
*
)+`(?=_.*,(_+))(\1)*(_*)
$#2*_$.3
,_+

```

Try it online! Takes comma-separated inputs \\$t\\$ (0-indexed) and \\$b\\$. Does all of its calculations in unary so times out for large numbers. Explanation:

```
.+,(\d+)
11,$1*

```

Initialise \\$x\_0=11\\$ and convert \\$b\\$ to unary.

```
"$+"{`

```

Repeat \\$t\\$ times.

```
^\d+
*

```

Convert \\$x\_i\\$ to unary.

```
)+`(?=_.*,(_+))(\1)*(_*)
$#2*_$.3

```

Convert to base \\$b\\$.

```
,_+

```

Delete \\$b\\$ from the output.

# Answer
> 2 votes
# Clojure, 109 bytes

*Credit to MilkyWay90 for removing 10 bytes by spotting unnecessary spaces* *Credit to Embodiment of Ignorance for another byte from another unnecessary space*

**Golfed**

```
(defn f([b t](f b t 11))([b t v](if(= t 1)v(f b(dec t)(read-string(.(new BigInteger(str v))(toString b)))))))

```

**Ungolfed**

```
(defn f
  ([base term] (f base term 11))
  ([base term value] (if (= term 1)
                      value
                      (f base (dec term) (read-string (. (new BigInteger (str value)) (toString base)))))))

```

I think the main place bytes could be saved is the expression for... *reradixing?* whatever that would be called. Specifically:

```
(read-string (. (new BigInteger (str value)) (toString base)))

```

# Answer
> 1 votes
# Jelly, ~~8~~ 7 bytes

```
‘b³Ḍ$⁴¡

```

Try it online!

A full program that takes \\$b\\$ as first argument and 1-indexed \\$t\\$ as its second argument. Returns the integer for the relevant term (and implicitly prints). Uses the observation by @Emigna regarding starting with \\$b + 1\\$.

### Explanation

```
‘b³Ḍ$⁴¡ | Main link: first argument b, second argument t
‘       | b + 1
    $⁴¡ | Repeat the following t times
 b³     | Convert to base b
   Ḍ    | Convert back from decimal to integer

```

# Answer
> 1 votes
# C# (Visual C# Interactive Compiler), 87 bytes

```
n=>m=>{int g=11;for(var s="";m-->0;g=int.Parse(s),s="")for(;g>0;g/=n)s=g%n+s;return g;}

```

Saved 5 bytes thanks to @KevinCruijssen

Try it online!

# Answer
> 1 votes
# Perl 6, 28 bytes

```
{(11,+*.base($^b)...*)[$^t]}

```

Try it online!

The index into the sequence is zero-based.

# Answer
> 1 votes
# K (ngn/k), 13 bytes

```
{y(10/x\)/11}

```

Try it online!

# Answer
> 1 votes
# Pyth, 8 bytes

```
uijGQTEh

```

Try it online!

# Answer
> 1 votes
# brainfuck, 270 bytes

```
++<<++<,+++<-[----->-<]<,,[<-----[->++++++++++<]++>[-<+>],]<[>>>>>>[<<<[->>+<<]>>>>>]<<[[>+<-]>>[-[<++++++++++>-]>+>]<[<<]>>[-<<+>>>+<]>>[-[<-[>>+>>]>>[+[-<<+>>]>[-<]<[>]>++>>>]<<<<<-]+>[-<+<+>>]<<[->>+<<]>>>]<[-]<[[-<+>]<<]<]<[->>+<<]<-]>>>>[>>]<<[>-[-----<+>]<----.<<]

```

Try it online!

0-indexed. The number of iterations is assumed to be at most 255.

## Explanation

The tape is laid out as follows:

```
num_iterations 0 0 base digit0 0 digit1 0 digit2 ...

```

Each digit is actually stored as that digit plus 1, with 0 reserved for "no more digits". During the base conversion, the digits currently being worked on are moved one cell to the right, and the base is moved to the left of the current working area.

```
++<<++              Initialize initial value 11
<,+++<-[----->-<]   Get single digit as base and subtract 48 to get actual number
<,,[<-----[->++++++++++<]++>[-<+>],]   Read multiple digits as number of iterations
<                   Go to cell containing number of iterations

[                   For each iteration:
  >>>>>>              Go to tens digit cell
  [<<<[->>+<<]>>>>>]  Move base to just before most significant digit
  <<                  Return to most significant digit

  [                   For each digit in number starting at the left (right on tape):
    [>+<-]            Move digit one cell to right (to tell where current digit is later)
    >>[-[<++++++++++>-]>+>]  Multiply each other digit by 10 and move left
    <[<<]>>           Return to base
    [-<<+>>>+<]       Copy base to just before digit (again) and just before next digit to right (left on tape)
    >>[               For each digit at least as significant as this digit:

      -[<-[>>+>>]>>[+[-<<+>>]  Compute "digit" divmod base
      >[-<]<[>]>++    While computing this: add quotient to next digit; initialize digit to "1" (0) first if "0" (null)
      >>>]<<<<<-]     End of divmod routine

      +>[-<+<+>>]     Leave modulo as current digit and restore base
      <<[->>+<<]      Move base to next position
      >>>
    ]

    <[-]<             Delete (now useless) copy of base
    [[-<+>]<<]<       Move digits back to original cells
  ]                   Repeat entire routine for each digit

  <[->>+<<]           Move base to original position
  <-                  Decrement iteration count
]

>>>>[>>]<<[>-[-----<+>]<----.<<]  Output by adding 47 to each cell containing a digit

```

# Answer
> 0 votes
# Charcoal, 14 bytes

```
≔11ζＦＮ≔⍘ＩζＩηζζ

```

Try it online! Link is to verbose version of code. Takes inputs as \\$t\\$ (0-indexed) and \\$b\\$. Explanation:

```
≔11ζ

```

\\$x\_0=11\\$.

```
ＦＮ

```

Loop \\$b\\$ times.

```
≔⍘ＩζＩηζ

```

Calculate \\$x\_i\\$.

```
ζ

```

Output \\$x\_t\\$.

# Answer
> 0 votes
# Pari/GP, 50 bytes

```
(b,n)->x=11;for(i=2,n,x=fromdigits(digits(x,b)));x

```

Try it online!

# Answer
> 0 votes
# C (gcc), 59 bytes

```
f(t,b){t=t?c(f(t-1,b),b):11;}c(n,b){n=n?c(n/b,b)*10+n%b:0;}

```

Try it online!

# Answer
> 0 votes
# Groovy, 45 bytes

```
a,b,c=11->a--?f(a,b,a.toString(c as int,b)):c

```

Try it online!

Port of @Arnauld's answer

# Answer
> 0 votes
# PHP, ~~83~~ 75 bytes

```
function c($b,$t,$v=11){return $t==1?$v:c($b,$t-1,base_convert($v,10,$b));}

```

Try it online!

This one will only work work with "small" numbers (e.g. not test cases 1 and 4)

# Answer
> 0 votes
# Japt, 10 bytes

0-indexed. Takes `t` as the first input, `b` as the second.

```
_ìV ì}gBìC

```

Try it

# Answer
> 0 votes
# Gaia, 8 bytes

```
Bd
11@↑ₓ

```

Try it online!

Takes 0-based `iterations` then `base`.

```
Bd		| helper function: convert to Base b (implicit) then convert to base 10
		| main function:
11		| push 11
  @		| push # of iterations
   ↑ₓ		| do the above function (helper function) that many times as a monad

```

# Answer
> 0 votes
# Ruby, 39 bytes

Zero-indexed.

```
->b,n,x=11{n.times{x=x.to_s(b).to_i};x}

```

Try it online!

# Answer
> 0 votes
# Perl 5 `-Mbigint -pa`, 65 bytes

```
$\=11;map{$p=$\;$\%=0+"@F";$\=($p%"@F").$\while$p/=0+"@F"}2..<>}{

```

Try it online!

# Answer
> 0 votes
# GolfScript, 16 bytes

```
11\~{base""*~}+*

```

Try it online!

The input is `t` (0-indexed) and then `b`.

```
11                 # x_1
  \~               # Parse the inputs to integers
    {base""*~}+    # Add b to the beginning of this block to get {b base""*~}
  {b base""*~}     # This block goes from x_n to x_(n+1)
   b base          # Convert to base b
         ""*       # Join the digits with "" between them
            ~      # Parse it to an integer
               *   # Execute this block t times

```

---
Tags: code-golf, number
---


title: Generate a "Poem"

text:
# Question
Title: Generate a "Poem"
Given a strictly positive integer, `N`, produce an output satisfying the following:

* Produce an array of length N.
* Every string (i.e. "word") in the array is of length N.
* Every letter in the word is unique.
* Every first letter of the words are unique between each other.
* The remaining items of each word are equal to each other.

## Example output

For an input of e.g. `3`:

```
cba
dba
eba

```

## Specification

* Trailing whitespace is totally allowed.
* The "letters" don't have to be from the lowercase alphabet, as long as they aren't whitespace.
* The maximum `N` you need to support is 13, since there are 26 letters in the lowercase alphabet.
* The separator of your array can be anything, as long as you will never involve that character for every possible input from 1 to 13. You can also just output a literal array.
* Letters have to be 1 character long.
* Letters are case-sensitive, e.g. `a` and `A` can appear on the same line.

# Answer
> 2 votes
# Japt, ~~9~~ 8 bytes

```
;ÆîEhCgX

```

Try it

```
;ÆîEhCgX     :Implicit input of integer U
 Æ           :Map each X in the range [0,U)
  î          :  Slice to length U
;  E         :    Printable ASCII
    h        :    Replace first character (space) with
;    C       :      Lowercase alphabet
      gX     :      Character at index X

```

# Answer
> 7 votes
# Pyth, 9 bytes

```
V>QG+N<Gt

```

Try it online!

* `V>QG` For each letter in the last `Q` (the input) elements of the lowercase alphabet:
* `+N>Gt` Append that letter to the first `Q-1` elements of the lowercase alphabet

For `Q=13`, the output looks like this:

```
nabcdefghijkl
oabcdefghijkl
pabcdefghijkl
qabcdefghijkl
rabcdefghijkl
sabcdefghijkl
tabcdefghijkl
uabcdefghijkl
vabcdefghijkl
wabcdefghijkl
xabcdefghijkl
yabcdefghijkl
zabcdefghijkl

```

# Answer
> 5 votes
# Charcoal, 11 bytes

```
ＮθＵＯθ⮌β↓…βθ

```

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

```
Ｎθ

```

Input `N`.

```
ＵＯθ⮌β

```

Print a square of size `N` filled with the reversed lowercase alphabet.

```
↓…βθ

```

Print the first `N` lowercase letters downwards.

# Answer
> 5 votes
# C (gcc), 58 bytes

```
i,j;f(n){for(i=n;i;)putchar(j++?j>n?j=!i--,10:j+63:i+77);}

```

Try it online!

# Answer
> 4 votes
# Python 2, 53 bytes

```
lambda n:['%xopqrstuvwxyz'[:n+1]%i for i in range(n)]

```

Try it online!

Chooses a hex digit (`0123456789abc`) for the first character, and the last half of the alphabet for the rest.

---

Another 53-byter that does the same thing, using `map`:

```
lambda n:map('%xopqrstuvwxyz'[:n+1].__mod__,range(n))

```

Try it online!

---

Another 53-byter, this time using Python 3 f-string:

```
lambda n:[f'{i:x}copqrstuvwxyz'[:n]for i in range(n)]

```

Try it online!

---

If numeric characters are not allowed:

### Python 2, ~~58~~ 57 bytes

*-1 byte thanks to @dingledooper !*

```
lambda n:['%copqrstuvwxyz'[:n+1]%(i+65)for i in range(n)]

```

Try it online!

Choose the first letter from the first half of the alphabet, and the last letters from the last half of the alphabet.

# Answer
> 4 votes
# 05AB1E, ~~10~~ 8 bytes

```
AÂSìδ£I£

```

Try it online!

Haha! With the expert help of Kevin, I beat Pyth once again!

## Explained (with Docs Descriptions)

```
A| 'abcdefghijklmnopqrstuvwxyz'
Â| Bifurcated a. Push a, reversed(a)
S| Cast a to a list of characters / digits.
ì| Merge b with a if both are lists, else prepend b to a. Push a.prepend(b)
δ| Outer Product. Get the next command and apply it double-vectorized.
£| Head. Push a[0:b]
I| Input
£| Head. Push a[0:b]

```

# Answer
> 3 votes
# JavaScript (Node.js), 74 bytes

```
n=>(q=`opqrstuvwxyz,`.slice(13-n)).replace(/./g,t=>i.toString(++i)+q,i=10)

```

Try it online!

# Answer
> 3 votes
# Retina, 38 26 bytes

```
.+
*.
Y`.`l
L$`.
$=
Y`a`Rl

```

*-12 bytes thanks to @Neil*

Try it online!

This works by generating the beginning of 'abc...' length N, then repeating it and substituting the first letter for something from 'zyx...'

```
.+         This converts the number into unary, using dots
*.         ^
Y`.`l      A cyclic transliteration: replace all dots with something from a-m
L$`.       Repeat per N with a line break at the end
$=         ^
Y`a`Rl     Finally, transliterate each 'a' with something from z-n

```

# Answer
> 3 votes
# Java (JDK), 83 bytes

```
n->{for(int i=n,j=0;i>0;)System.out.printf("%c",j++>0?j>n?10+(j=--i-i):j+63:i+77);}

```

Try it online!

I was able to make a one-liner, but it's 100 bytes long and works only on Java 13+ if that can inspire anyone to golf further...

```
n->(" %sNOPQRSTUVWXY".substring(0,n+2)).repeat(n).formatted((Object[])"ABCDEFGHIJKLM".split("",n+1))

```

Try it online!

# Answer
> 3 votes
# dc, 52 bytes

```
[nAP1-d0<M]sL?dsnCo[d96+POO^OO^Bd*/-ODln-^/d0<L]dsMx

```

Try it online!

Input is on stdin, and output is on stdout.

**Output for 13:**

```
mBA9876543210
lBA9876543210
kBA9876543210
jBA9876543210
iBA9876543210
hBA9876543210
gBA9876543210
fBA9876543210
eBA9876543210
dBA9876543210
cBA9876543210
bBA9876543210
aBA9876543210

```

**How it works:**

```
[                     Start a macro.
 n                       Pop a number and print it.
 AP                      Print a newline.
 1-                      Decrement top of stack by 1.
 d0<                     If top of stack > 0,
 M                         then continue by calling macro M.
]sL                   End macro and save it in register L.

?                     Input number and push it on stack.
dsn                   Store top of stack in n.
Co                    Change output radix to base 12.

[                     Start a macro.
 d96+P                   Print the character with
                           ASCII code 96 + (top of stack).
                           (This will be a lower-case letter,
                           since 97 = 'a'.)
 OO^OO^Bd*/-ODln-^/      Push (12^12 - (12^12)/(11*11)) / (12^(13-n)).
                           In base 12, this is the leftmost n-1 digits
                           of BA9876543210 (or 0 for n=1).
 d0<L                    If this number > 0, call macro L to print it,
                           decrement the value of n at the top of stack,
                           and go back to the top of the loop M.
]dsMx                   End macro, save it in register M, and execute it.

```

# Answer
> 2 votes
# B (asm2bf dialect), 136 bytes

```
p(c){asm("rclr1,r4");asm("outr1");}g(){asm("in r1");}n;c 65;d;i;main(){i=n=g();while(i--){p(c++);d=65+n;while(d-n-65<n-1)p(d++);p(10);}}

```

Output assembly:

```
#!/usr/bin/env bfmake
    stk 16
    org 0
db_ 0
db_ 65
db_ 0
db_ 0
#PAGE_SIZE = 16
#MM_BASE = 5
#call("alloc")
    mov r4, r6
#call("_main")
    end
@alloc
#alloc("r6", "r5")
    ret
@_p
    rclr1,r4
    outr1
    ret
@_g
    in r1
    ret
@_main
    psh 3
    psh 0
#call("_g")
    mov r2, r1
    pop r1
    sto r1, r2
    pop r1
    sto r1, r2
@L1
    mov r2, 3
    rcl r1, r2
    dec r1
    sto r2, r1
    inc r1
    jz_ r1, %L2
    psh r4
#call("alloc")
    mov r2, 1
    rcl r1, r2
    inc r1
    sto r2, r1
    dec r1
    sto r6, r1
    mov r4, r6
#call("_p")
#free("r4")
    pop r4
    psh 2
    psh 65
    rcl r1, 0
    mov r2, r1
    pop r1
    add r1, r2
    mov r2, r1
    pop r1
    sto r1, r2
@L3
    rcl r1, 2
    psh r1
    rcl r1, 0
    mov r2, r1
    pop r1
    sub r1, r2
    mov r2, 65
    sub r1, r2
    psh r1
    rcl r1, 0
    mov r2, 1
    sub r1, r2
    mov r2, r1
    pop r1
    lt_ r1, r2
    jz_ r1, %L4
    psh r4
#call("alloc")
    mov r2, 2
    rcl r1, r2
    inc r1
    sto r2, r1
    dec r1
    sto r6, r1
    mov r4, r6
#call("_p")
#free("r4")
    pop r4
    jmp %L3
@L4
    psh r4
#call("alloc")
    sto r6, 10
    mov r4, r6
#call("_p")
#free("r4")
    pop r4
    jmp %L1
@L2
    ret

```

# Answer
> 2 votes
# Ruby, 47 bytes

```
->n{a=*?`..?z;(1..n).map{|i|a[i]+a[14,n-1]*''}}

```

Try it online!

# Answer
> 2 votes
# Bash \+ Unix utilities, ~~62~~ 59 bytes

```
dc -e'[nAP1-d0<M]sL?dsnCo[d96+POO^OO^Bd*/-ODln-^/d0<L]dsMx'

```

Try it online!

Input is on stdin, and output is on stdout.

---

---

Here's the original, longer answer:

```
echo {a..m}`echo {o..z}|tr -d \ `|fold -14|cut -b 1-$1|sed $1q

```

Try it online (62 bytes)

Input is passed as an argument, and output is on stdout.

# Answer
> 2 votes
# Perl 5 `-na`, 42 bytes

```
say$_,(A..Z)[0..$F[0]-2]for(N..Z)[0..$_-1]

```

Try it online!

# Answer
> 2 votes
# Befunge-93, ~~53~~ 51 bytes

```
&:v
< <>::      v:::\,+*77:
|  ^-1,+*88<_$$\1-0.:
@

```

Try it online!

`0` is my two character delimiter. Outer loop outputs N'+(7\*7) in ascii, sets M to N (this requires a swap) then enters inner loop. Inner loop outputs M+(8\*8) in ascii and decrements M. On exiting inner loop outputs `0` and decrements N' (this requires a swap). `|` and `_` are the loop condition instructions respectively. `:` is often used to make copies since most operations - from arithmetic to conditional check, destroy the value they operate on by popping it out of the stack

Befunge is stack based with a single instruction pointer that points to a character in the code. It has a travelling direction that can be changed via arrows \<\>^v

Befunge-98 submission by ovs, 43 bytes

```
&:>:77*+,\:>:: v
.:|;-1,+*8;^;8<_$$\1-0
  @

```

Try it online!

# Answer
> 2 votes
# Husk, ~~14~~ ~~12~~ 11 bytes

```
←ẊM:M↑½…"az

```

Try it online! Splits the alphabet into two halves, truncates each half to the size of the input, and then recombines them in the proper way.

# Answer
> 1 votes
# C (gcc), ~~98~~ 88 bytes

-10 thanks to @ceilingcat

```
c,d,i,j;f(n){for(c=65,i=n,d=c+n;i--;puts(""))for(j=!putchar(c++);j<n-1;)putchar(d+j++);}

```

Try it online!

# Answer
> 1 votes
# Jelly, 9 bytes

```
Øa;€Ṛ$ḣḣ€

```

A monadic Link accepting an integer in \\$\[1,13\]\\$ which yields a list of lists of characters.

**Try it online!**

### How?

```
Øa;€Ṛ$ḣḣ€ - Link: integer, N
Øa        - lower-case alphabet
     $    - last two links as a monad:
    Ṛ     -   reverse (the alphabet)
  ;€      -   concatenate that to each of (the alphabet)
      ḣ   - head to index (N)
       ḣ€ - head each to index (N)

```

# Answer
> 1 votes
# JavaScript (Node.js),  ~~66~~  60 bytes

```
f=(n,k=n*n)=>k?Buffer(k--%n?[97+k%n]:[10,123-k/n])+f(n,k):''

```

Try it online!

# Answer
> 1 votes
# Google Sheets, 76 bytes

```
=ArrayFormula(Char(Row(Offset(78:78,,,A1)))&Join(,Char(Row(Offset(65:65,,,A1

```

When you exit the cell, Sheets will automatically add the 5 trailing parentheses. Input is in cell `A1`. Output is wherever you put the formula and the `N-1` cells below it.

`Row(Offset(78:78,,,A1))` gives us an array from `78` to `78+N-1`.
`Char(Row(~))` turns that array into their ASCII equivalent (capital letters).
`Char(Row(Offset(65:65,,,A1)))` does the same thing for the range `65` to `65+N-1`.
`Join(Char(~))` combines that second array into a single string.
`ArrayFormula(~)` makes these functions input and output arrays instead of a single value.

# Answer
> 1 votes
# \[MATLAB/Octave\], 35 bytes

```
char([N+[1:N]',ones(N,1)*[1:N]]+64)

```

First create a column vector ranging from N+1 to 2N with N+\[1:N\]. Make a column vector with all values equal to one and length N, and multiply by a row vector containing values 1 to N to make a matrix of N columns with all rows equal to 1:N. Concatenate the first vector with your matrix, add 64 to all digits and use char to turn every row into a string.

# Answer
> 1 votes
# Haskell, 34 bytes

```
(\t->t.(:['n'..])<$>t['a'..]).take

```

Try it online!

# Answer
> 0 votes
# CJam, 22 bytes

```
'[,65>_W%qi<_,(@<am*N*

```

Try it online!

This works by generating the Cartesian product of the each of the last `n` characters of the alphabet and a singular array containing a string with the first `n-1` characters of the alphabet. For example, the following is outputted for 13:

```
ZABCDEFGHIJKL
YABCDEFGHIJKL
XABCDEFGHIJKL
WABCDEFGHIJKL
VABCDEFGHIJKL
UABCDEFGHIJKL
TABCDEFGHIJKL
SABCDEFGHIJKL
RABCDEFGHIJKL
QABCDEFGHIJKL
PABCDEFGHIJKL
OABCDEFGHIJKL
NABCDEFGHIJKL

```

# Answer
> 0 votes
# Poetic, 360 bytes

```
absently,i jot out words,A-Z
moving a pen mindlessly about a page
i am making my art,i`m doing a poem
i ensure i can never do patterns at first
i`d alter a chr i am using
i`d say i am not consistent,cause i`m using a perfect copy i forged when i end a certain verse
o yes,i reckon i am doing A-Z lazily
o yes,i admit
o yes,i am silly
i compose tripe,o yes i do

```

Try it online!

This works by filling the entire memory with the negative of the inputted number (as that's the shortest way to copy it to multiple cells), then outputting the first character - which is decremented each iteration - and then the last few ASCII characters up to ASCII 255.

Warning: this takes a long time to run, even for small inputs. Such is the price to pay for a short length.

---
Tags: code-golf, string
---


title: Eating Persistence

text:
# Question
Title: Eating Persistence
# Intro

Find the result of number cannibalism.

Why was 6 scared of 7? Becase 7 `8` 9.

Your program will have to find the result of applying the `8` operation(defined below) on a number, repeatedly.

Related, Sandbox

# Challenge

Your input will be a single positive integer, n.

You need to find each `8` in the integer, and substitute it for `+` or `-` based on the following conditions.

* remove all `8`s at the beginning or end of the string.
* If there are multiple `8`s, then collapse them into a single `8`.
* \\$a\\$ and \\$b\\$ are the chunks to the left and right of the `8` respectively. Since `8` is an operator, the numbers are delimited by `8`.
* If \\$ a ≥ b,\\$ `8` becomes `+`.
* else, it becomes `-`.

Then evaluate the expression from left to right, and take the absolute value.

If the result has any `8`s in it, the repeat the above steps again till there are none.

For example, `12384568789` becomes:

```
123 456 7 9
123 < 456: 123 - 456 7 9
456 ≥ 7  : 123 - 456 + 7 9
7 < 9    : 123 - 456 + 7 - 9 = -335
= abs(-335)
= 335

```

Hence 335 is the final answer.

# Example Input and Output

```
789 → 2
180 → 1
42312348 → 4231234
2389687 → 66
12384568789 → 335
13749547874394873104972349 → 7309154
808 → 0
7800482 → 13
14458883442 → 1997
88888 → indeterminate
388182 → 2
08182 → 3

```

Here are the testcases as an array:

`[789,180,42312348,2389687,12384568789,13749547874394873104972349,808,7800482,14458883442,88888]`

## Scoring Criteria

This is . Shortest answer in each language wins.

# Answer
> 8 votes
# 05AB1E, ~~18~~ 14 bytes

```
Δ8¡þDü@1š·<*OÄ

```

Try it online or verify all test cases.

**Explanation:**

```
Δ               # Loop until it no longer changes:
 8¡             #  Split the integer on 8s
                #  (which will use the implicit input-integer in the first iteration)
   þ            #  Remove all empty strings by only leaving digits
    D           #  Duplicate this list
     ü          #  For each overlapping pair [a,b]:
      @         #   Check if a>=b (1 if truthy; 0 if falsey)
       1š       #  Prepend a 1 to this list
         ·      #  Double each value
          <     #  Decrease each by 1 (0 has become -1; 1 is still 1)
           *    #  Multiply the values at the same positions in the two lists
            O   #  Sum the list
             Ä  #  And take the absolute value of this sum
                # (after which the result is output implicitly)

```

# Answer
> 7 votes
# Jelly, ~~20~~ 18 bytes

```
IŻṠo-×
ṣ8LƇḌÇSAµÐL

```

Try it online!

Went through 5 or 6 other approaches before eval turned out to be the only one I could get to work... and then I tried a different spin on my second approach and it's 2 bytes shorter.

Old version: `ṣ8LƇḌ<Ɲị⁾_+ż@ƲFVAµÐL`

```
IŻṠo-×         Monadic helper link:
  Ṡ            signs of
I              deltas
 Ż             with prepended 0,
   o-          replace all 0s with -1s,
     ×         pairwise multiply with argument.

ṣ8LƇḌÇSAµÐL    Main link:
ṣ8             split (implicitly converted digit list) on 8s,
  LƇ           remove empty slices,
    Ḍ          convert digit lists from decimal,
     Ç         apply helper link,
      S        sum,
       A       abs.
        µÐL    Loop that whole thing until it doesn't change.

```

# Answer
> 7 votes
# JavaScript (ES6), 76 bytes

```
f=n=>n.replace(p=/[^8]+/g,x=>t-=p<(p=+x)?x:-x,t=0)&&n-(t=t<0?-t:t)?f(t+''):t

```

Try it online!

### Commented

```
f = n =>               // f is a recursive function taking n as a string
  n.replace(           // we look for ...
    p = /[^8]+/g,      // ... all groups of consecutive non-eight digits
    x =>               // for each group x:
      t -=             //   update t:
        p < (p = +x) ? //     if the previous value is less than x:
          x            //       subtract x from t
        :              //     else:
          -x,          //       add x to t
    t = 0              //   start with t = 0
  ) &&                 // end of replace()
  n - (                // if n is not equal to t,
    t = t < 0 ? -t : t // where t is first updated to its absolute value:
  ) ?                  //
    f(t + '')          //   do a recursive call with t (coerced back to a string)
  :                    // else:
    t                  //   success: return t

```

# Answer
> 5 votes
# Husk, ~~27~~ ~~26~~ 25 bytes

*Edit: -1 byte by using `S` combinator to recycle function argument, and moving helper function in-line, and then -1 more byte by a bit of rearrangement to be able to use `o` combinator instead of `()`*

```
ω(aΣSz*o:1Ẋȯ`^_1¬<mdfIx8d

```

Try it online!

A *slightly* different approach to Unrelated String's Husk answer, ~~also 27 bytes~~.

I'd held-off posting this for a bit, to give any new Husker a clean slate from which to try out this challenge... but now the Husketition is open...

**How?***

```
mdfIx8d                 # helper function: splits input on 8s
      d                 # get digits of input
    x8                  # split on 8
  f                     # remove elements that are falsy for
   I                    # the identity function (so, remove empty elements)
m                       # map over each element of the list
 d                      # combining digits as decimal number

ωλaΣz*₁¹m`^_1ΘẊo¬<₁     # main program
ω                       # repeatedly apply function until results are constant
 λ                      # lambda function taking one argument:
  a                     # get the absolute value of
   Σ                    # the sum of all elements of
    z*                  # element-wise multiplication of
      ₁¹                # (1) helper function applied to input
                        #     (so: the input split on 8s)
        m               # (2) map this function to all elements of
                  ₁     #     helper function applied to input
             Θ          #     (with 0 prepended at the start)
         `^_1           #     minus one to the power of
              Ẋ         #     the results for each pair of elements
               o        #     combine 2 functions
                ¬       #     NOT
                 <      #     second is greater than first

```

# Answer
> 4 votes
# Python 3, ~~158~~ ~~148~~ ~~145~~ 138 bytes

```
x=input()
while'8'in x:
 y=[int(f)for f in x.split('8')if f];x=str(sum([-1,1][y[i-1]<y[i]]*y[i]for i in range(len(y))))
print(abs(int(x)))

```

Try it online!

*-10 bytes thanks to @pavi2410 and to me not being an idiot and accidentally leaving an extra space from the golfing suggestion*

*and another -3 thanks to @pavi2410*

*and another -7 thanks to @pavi2410*

# Answer
> 4 votes
# , ~~89~~ 122 bytes

*Edit: +33 bytes to convert to recursive function when I realized that it should repeat the `8` operation on its own output until there are no more `8`s. Doh!*

```
f=function(s)`if`(grepl(8,a<-abs(sum(c(1,-sign(diff(n<-sapply((n=el(strsplit(s,8)))[n>-1],as.double))))*n))),f(c(a,'')),a)

```

Try it online!

Accepts argument `n` as a string. Errors for `n`s containing no non-8 digits/characters.

# Answer
> 4 votes
# C (gcc), <sup>~~149~~ \\$\cdots\\$ ~~139~~</sup> 137 bytes

Saved 2 bytes thanks to ceilingcat!!!
Saved 8 bytes thanks to AZTECCO!!!

```
R;t=10;m;s;p;c;f(n){R=n;for(s=p=0;n;){for(m=1,c=0;n&&n%t-8;n/=t,m*=t)c+=n%t*m;s+=c>p?p:-p;for(p=c;n%t==8;)n/=t;}p=abs(s+c);R=p-R?f(p):p;}

```

Try it online!

### Explanation (before some golfs)

```
t=10;                                 // golf by storing 10 in t
g(n){                                 // helper function takes int n
     for(     ;n;){                   // loops until n is zero
         s=p=0                        // init sum s and previous p to 0
       for(                           // inner loop calculates next rh value
           m=1,                       // init multiplier m to 1
               c=0;                   // and current c to 0
                   n&&                // loop until n is 0
                      n%t-8;          // or most rh digit is 8
                            n/=t,     // knock most rh digit off n
                               m*=t)  // and bump m by 10 each loop
         c+=n%t*m;                    // add next digit to current
                                      // building up number after
                                      // most right-hand 8
      s+=c>p?p:-p;                    // after that's done update sum s
      for(                            // loop to strip off all rh 8's
          p=c;                        // also make previous = current
              n%t==8;)                // loop until most rh digit isn't an 8
                      n/=t;           // knock most rh 8 off n
        }                             //
 p=abs(s+c);                          // return abs value of sum with
                                      // positive most lh value
}                                     //
f(n){                                 // recursive main function
     x=g(n);                          // calc first iteration
            x=x-g(x)?                 // is it different to next iteration?
                     f(x):            // if so iterate
                          x;          // else return value
}                                     //

```

# Answer
> 4 votes
# Perl 5 `-p`, 59 bytes

```
y/8/ /;s/\d+/$&<$'?"$&-":"$&+"/ge;$_=abs eval$_.0;/8/&&redo

```

Try it online!

# Answer
> 4 votes
# , 53 bytes

```
|@('8'+/@(*_1x^0,2</\])@(,(*@#;._1#".;._1)~[=,)":)^:_

```

Try it online!

### How it works

* `f^:_`: until the result does not change, do f.
* `'8'…(,g[=,)":`: convert the input to a string, prepend `,` the character `8`, and execute `g` with this as the left argument, and a bit mask of `8` characters as the right argument.
* `(…".;._1)~`: split the string into groups `u;._1`, which start with 1 in the bit mask and convert them back to numbers `".` (excluding the `8`).
* `*@#;._1#`: because we could have empty groups (`888`), take `#` only those, whose length's `#` signum `*` is 1. (There might be a nicer approach.)
* `2</\]`: compare `<` each group with its following, resulting a bit-mask.
* `*_1x^0,`: prepend a 0 to the bit mask, and calculate `x*(-1)^y` for each group `x` with `y` being the result of the comparing. So we get `3 1 2 -> 3 1 _2`.
* `|@…+/`: sum `+/` the result and take the absolute value `|`.

# Answer
> 3 votes
# Scala, ~~94~~ 90 bytes

```
i=>"[^8]+".r.findAllIn(""+i).map(_.toInt).scanRight(0){(a,b)=>if(a<b.abs)a else-a}.sum.abs

```

Try it online!

-4 bytes by not using Java's cursed `split` method.

```
i=>                           //The input
  "[^8]+".r                   //Regex for operands
  .findAllIn(""+i)            //Get all separate numbers in the input
  .map(_.toInt)               //Turn them into integers
  .scanRight(0){(a,b)=>       //Starting at the right,
    if(a<b.abs)a else-a}      //Replace a with -a if a >= b.abs (this is different from the challenge, but it works because we call abs again later)
  .sum                        //Sum them up
  .abs                        //Take the absolute value

```

# Answer
> 3 votes
# Husk, 27 bytes

```
ω(aΣSz*(Ẋȯ`^_1±>Ṡ:←)mdfIx8d

```

Try it online!

This isn't quite my first Husk answer, but it's a pretty clumsy direct translation of one of my attempted Jelly answers, so it could at least serve as a serviceable starting point for someone to swoop in and earn the bounty.

```
ω(                             Iterate until periodic:
  a                            absolute value of
   Σ                           sum of
     z*                        zipwith multiplication on:
                          d    decimal digits
                        x8     split on 8s
                      fI       with empty slices removed
                    md         and converted back from decimal,
    S                          and the result of that
       (        Ṡ:←)           with its first element duplicated
        Ẋ                      and with neighboring pairs mapped to
          `^_1                 -1 to the power of
         ȯ    ±>               if the first is less than the second.

```

# Answer
> 3 votes
# Bash, 177 bytes

```
A=($(sed s/8/\ /g<<<$1));B=;while [ ${#A[@]} -ge 2 ];do [ ${A[0]} -ge ${A[1]} ]&&C=+||C=-;B=$B${A[0]}$C;A=(${A[@]:1});done;R=$(bc<<<$B$A|tr -d -);grep -cq 8 <<<$R&&f $R||echo $R

```

It has to be stored as function `f` or in file `f` in the current working directory.

Try it online!

# Answer
> 3 votes
# PHP, 290 bytes

(Guess you shouldn't golf in php. :) )

```
<?php $n=$_SERVER["argv"][1];while(false!==strpos($n,'8')){$n=abs(array_reduce(str_split(preg_replace('|8+|','8',trim($n,'8')).'8'),function($c,$i){if($i!=8){$c[1]*=10;$c[1]+=$i;}else{$c[2]+=$c[1]*((!isset($c[0])||$c[0]>=$c[1])?1:-1);$c[0]=$c[1];$c[1]=0;}return$c;},[null,0,0])[2]);}echo$n;

```

Try it online

## Ungolfed:

```
<?php

$n = $_SERVER["argv"][1];

$f=function($c, $i){
    if($i!=8) {
        $c[1]*=10;
        $c[1]+=$i;
    } else {
        $c[2] += $c[1] * ( (!isset($c[0]) || $c[0]>=$c[1])?1:-1);
        $c[0]=$c[1];
        $c[1]=0;
    }
    return $c;
};

while(false!==strpos($n,'8')) {
    $n = trim($n, '8');
    $n = preg_replace('|8+|', '8', $n);
    $a = str_split($n.'8');
    $n = abs(array_reduce($a, $f, [null, 0, 0])[2]);
}

echo $n;

```

## Explanation:

I use array\_reduce to walk over every digit, and use an array as carry to have 3 datapoints carried on: the variables $a, $b and $sum, though they are unnamed as the elements of $c.

If the current digit is a non-8, I "add" it to my "$b", otherwise I first compare $b to $a, add/subtract $b from $sum, and move the content of $b to $a.

# Answer
> 2 votes
# Red, 142 bytes

```
func[n][while[find to""n"8"][b: to[]load form split to""n"8"forall b[if b/2[b/1:
reduce[b/1 pick[- +]b/1 < b/2]]]n: absolute do form b]to 1 n]

```

Try it online!

# Answer
> 2 votes
# GolfScript, 32 bytes

```
.,{8`%(~:x\{~.x\:x<2*(*-}/abs`}*

```

Try it online!

Every time the algorithm is executed, the number either stays the same or it gets at least 1 digit shorter. This means we can execute the algorithm once for every byte instead of testing if it has an 8.

```
.,                                 # Get the number of bytes in the input
  {                           }*   # Execute this block that many times
   8`%                             # Split the string around the 8s and remove the empty strings
                                   # This simultaneously executes the first 3 steps
      (~                           # Get the first number
        :x                         # Store it in the variable x
          \{~           }/         # For each number left in the array
             .x                    # Copy it and push x
               \:x                 # Store the current number in x
                  <                # Compare the two numbers
                   2*(             # 1 if previous<current and -1 if previous>=curret
                      *-           # Multiply and subtract
                          abs`     # Parse the absolute value to a string

```

# Answer
> 2 votes
# K (oK), ~~60~~ ~~43~~ 38 bytes

-22 bytes thanks to Traws

```
{a|-a:+/{x*1-2*>':x}.:'(~^.)#"8"\$:x}/

```

Try it online!

# Answer
> 2 votes
# Japt, 37 bytes

```
@=q8 f;=äÈn ¨Y?Y:-Y}Ug)x a s ,Uø8}f U

```

Try it

* takes input as a string, it can be easily modified to take input as a number but it won't work with big numbers

'''

```
@=q8 f;=äÈn ¨Y?Y:-Y}Ug)x a s ,Uø8}f U
@....}f    - return first number which return false when passed through @...
=q8 f;     - input splitted on 8 and empties removed
=äÈ...}Ug) - pass each consecutive values through È , but prepend first value before so that they are >=
n ¨Y?Y:-Y  - 1st to number compared to 2nd: return 2nd (negated eventually)
x a s      - reduce->abs->to string

The above is assigned to U while the funxtion returns..
Uø8        - contains 8? => repeat
Finally we return U

```

'''

# Answer
> 1 votes
# Retina 0.8.2, 68 bytes

```
{`8+
-
^-|-$

\d+
$*
(?=-(1*))(?<=\1)-
+
O`\D1*
\+

1>`-

(1+)-\1

1

```

Try it online! Link includes smaller test cases (Retina has to do subtraction in unary, which is too slow for the larger cases). Explanation:

```
{`

```

Repeat until there are no `8`s left.

```
8+
-

```

Convert each runs of `8`s to a `-`.

```
^-|-$

```

Delete leading and trailing `-`s.

```
\d+
$*

```

Convert the remaining numbers to unary.

```
(?=-(1*))(?<=\1)-
+

```

Replace each `-` with a `+` unless the following number is greater.

```
O`\D1*

```

Sort the numbers to be added to the beginning and the numbers to be subtracted to the end.

```
\+

```

Add all the numbers to be added together.

```
1>`-

```

Add all the numbers to be subtracted together.

```
(1+)-\1

```

Take the absolute value of the difference.

```
1

```

Convert it to decimal.

---
Tags: code-golf, number
---