title: Satisfy as many people as possible

text:
# Question
Title: Satisfy as many people as possible
There are times when a large number of people need to choose something. They all want to get the stuff they choose, obviously, but it's impossible to please everyone that way, so a usual compromise is to give people three choices and try to make sure that everyone gets one of their choices.

For instance, consider three people who want to choose their parts in a play. The play has three parts. Imagine that the parts are called Word, PowerPoint and Excel, and imagine that the choices are like this:

```
Person 1 chooses: (from first choice to third choice)
Word
PowerPoint
Excel

Person 2 chooses: (from first choice to third choice)
PowerPoint
Excel
Word

Person 3 chooses: (from first choice to third choice)
Excel
Word
PowerPoint

```

Here, it is easy to assign Word to person 1, PowerPoint to person 2 and Excel to person 3 and thus give everyone their first choice. However, it is not so easy if...

```
Person 1 chooses: (from first choice to third choice)
Word
Excel
PowerPoint

Person 2 chooses: (from first choice to third choice)
Word
PowerPoint
Excel

Person 3 chooses: (from first choice to third choice)
Excel
Word
PowerPoint

```

Since person 3 is the only person who wants Excel, person 3 automatically gets Excel.

Person 1 and person 2 both want Word, but there is only one Word, so suppose we assign Word to person 1. Then person 2 cannot get Word but his second choice, PowerPoint, has not been taken, so we can assign PowerPoint to person 2.

It gets even more complicated here:

```
Person 1 chooses: (from first choice to third choice)
Word
PowerPoint
Excel

Person 2 chooses: (from first choice to third choice)
Word
Excel
PowerPoint

Person 3 chooses: (from first choice to third choice)
Excel
Word
PowerPoint

```

Again, person 3 is the only one who wants Excel, so he gets it.

If we assign Word to person 1, then person 2 cannot get Word. But person 2 cannot get Excel either because person 3 got it! This means that person 2 is stuck with his third choice, PowerPoint. Obviously he is not very happy.

If we assign Word to person 2, on the other hand, person 1 can get his second choice, PowerPoint, and overall everyone is happier.

And that is the aim of this challenge: to make everyone as "happy" as possible.

## Challenge

Write a program or function that takes in a list of lists. Each sublist contains three positive integers. If the length of the big list is \\$n\\$, then the positive integers from 1 to \\$n\\$ will be present in the list (and no other integers will be there). For instance, above we had three people, so there were three possible choices. If there are twenty people, then in total there will be the integers from 1 to 20 present in the list.

Input may be taken in any reasonable format similar to the one above.

Your output should be a list of \\$n\\$ distinct positive integers corresponding to the integer assigned to each person. This list is, due to the input format above, a permutation of `1..n`. The output should be such that the people represented in the input are as "happy" as possible.

Output may be in any reasonable format similar to the one above.

Your code may do anything if it receives an empty list.

## Quantifying happiness for the purposes of this challenge

The "happiest" arrangement is the one where the following expression is minimal:

$$\sum^{4}\_{i=1} ix\_i$$

Here, \\$x\_i\\$ is the number of people who got their \\$i\\$-th choice. \\$x\_4\\$ is the number of people who got *none* of their choices.

This measure means that if many people get none of their choices, then the population as a whole will be *very* unhappy. On the other hand, if everyone gets their first choice, then the population will be very happy.

If there are multiple arrangements that have the same "happiness value", then you may output any number of them.

## Test cases

```
[[1,2,3],[2,3,1],[3,1,2]] -> [1,2,3] // first worked example above with 1=Word, 2=PowerPoint, 3=Excel
[[1,3,2],[1,2,3],[3,1,2]] -> [1,2,3] // second worked example
[[1,2,3],[1,3,2],[3,1,2]] -> [2,1,3] // third worked example
[[1,2,3],[1,2,4],[2,3,4],[2,4,3]] -> [1,2,3,4] // happiness measure 7; multiple answers possible
[[1,4,2],[1,4,2],[1,4,2],[2,3,4]] -> [1,2,4,3]
[[1,2,3],[2,3,5],[4,5,1],[5,1,2],[5,4,3]] -> [1,2,4,5,3]
[[1,2,3],[1,3,4],[1,4,5],[1,5,6],[1,6,7],[1,7,8],[2,3,8],[2,6,5]] -> [1, 3, 4, 5, 6, 7, 8, 2]
[[1,2,3],[2,3,4],[3,4,5],[4,5,1],[1,2,3]] -> [1,2,3,4,5]
[[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[4,5,6],[5,6,7]] -> [1, 2, 3, 6, 7, 4, 5]

```

This is , so the shortest code, measured in bytes, wins.

# Answer
> 5 votes
# Wolfram Language (Mathematica), 75 bytes

-2 bytes thanks to @att.

```
MinimalBy[Permutations[i=0;++i&/@#],tTr[Tr@*Position[0]/@(#-t)/. 0->4]]&

```

Try it online!

# Answer
> 3 votes
# Python SciPy, 120 bytes

```
def f(x):a=x@x.T*0+4;a[[*zip(range(len(x)))],x-1]=1,2,3;return linear_sum_assignment(a)[1]+1
from scipy.optimize import*
```

Attempt This Online!

Not fully builtin but leaves the heavy lifting to scipy.optimize.linear\_sum\_assignment. We just need to feed it in the right format (essentially one-hotting --- or rather three-hotting --- the input).

# Answer
> 3 votes
# , ~~137~~ 133 bytes

*Edit: -4 bytes thanks to pajonk and the new-to-me function `anyDuplicated()`*

```
\(l,n=length(l),q=expand.grid(rep(list(1:n),n)),p=q[!apply(q,1,anyDuplicated),])p[order(apply(p,1,\(x)sum(mapply(match,x,l,4))))[1],]
```

Attempt This Online!

**Ungolfed**

```
assignments=
function(l){
    # get all combinations of n times 1..n, unfortunately with repeats that we don't want
    p=expand.grid(rep(list(seq(l)),length(l)))
    # now get rid of the combinations with duplicates
    p=p[apply(p,1,function(x)sum(unique(x)|1)==length(l)),]
    # calculate the happiness score of each person
    # as the position of the match of each assigned value in each input list
    # (or 4 if it isn't found)
    e=apply(p,1,function(x)mapply(match,x,l,4))
    # calculate total happiness score for each combination:
    h=colSums(e)
    # return the combination for which happiness score is minimal:
    p[which.min(h),]
}

```

# Answer
> 3 votes
# Husk, 12 bytes

```
◄oṁo%4←z€¹Pŀ

```

Try it online!

```
          P   # calculate all permutations of
           ŀ  # the length of the input;
◄             # now output the element that minimizes:
 o            # combination of
       z€¹    # zip 'get index' function over input (or 0 if not found)
  ṁo%4←       # then subtract 1 & modulo 4 (so not found becomes 3)

```

# Answer
> 2 votes
# APL(Dyalog Unicode), 34 bytes SBCS

```
{x⊃⍨⊃⍋(⍵+.⍳⊢)¨x←/⍨∘(≡∘∪⍨¨)⍨,⍳⍴⍨≢⍵}

```

Try it on APLgolf! (Last cases uses more memory than allowed on TryAPL.)

The cost function for a single arrangement can be computed in a very compact way with `+.⍳`, taking the preferences on the left and the arrangement on the right. Half of the code is just generating the permutations.

# Answer
> 2 votes
# Python 3, 123 bytes

```
lambda*a:p({*sum(a,[])},*a)[1:]
p=lambda r,b,*a:min([[*b,i].index(i)+k,i,*j]for i in r for k,*j in[a and p(r-{i},*a)or[0]])

```

Try it online!

Using builtins only.

As a one-liner:

# Python 3, 125 bytes

```
def f(b,*a,r=0):s=r or{*sum(a,b)};return min([[*b,i].index(i)+k,i,*j]for i in s for k,*j in[a and f(*a,r=s-{i})or[0]])[r==0:]

```

Try it online!

# Answer
> 1 votes
# Python 3.8+, ~~172~~ ~~171~~ 165 bytes

-6 bytes thanks to @jezza\_99

## Golfed code

```
from itertools import*
def f(m):
 L=len(m);H=s=5*L
 for p in permutations(range(1,L+1)):
  if(h:=sum((m[i]+[p[i]]).index(p[i])for i in range(L)))<H:H,s=h,p
 return s

```

Try it online!

# Answer
> 1 votes
# Javascript, 178 bytes

```
// 178 Bytes
f=a=>(h=(m,i=a.map(_=>0),n=a.length)=>(g=_=>new Set(b=i.map((k,j)=>a[j][k])).size-n?(c=j=>j===!!j||(j<n&&++i[j]&&c(i.reduce((a,b)=>a+b)>m&&j+!(i[j]=0))))(0)&&g():b)()||h(m+1))(0)

// Example
const arr = [
  [1, 2, 3],
  [1, 3, 4],
  [1, 4, 5],
  [1, 5, 6],
  [1, 6, 7],
  [1, 7, 8],
  [2, 3, 8],
  [2, 6, 5],
];
console.log(f(arr));
```

## Explanation

```
f = a => (
  h = ( // This function tries to find an assignment that happiness <= m
    m,             // Maximum allowed happiness
    i=a.map(_=>0), // Assignments (by rank), i.e. [0,1,2] means P1 gets first choice, P2 gets second, P3 gets third.
    n=a.length
  ) => (
    g = _ => // This function will iterate through the possibilities of i until it finds a solution (or not)
      new Set(b = i.map((k, j) => a[j][k])).size - n // Checks if assignments are unique
      ? (
          c = j=>  // This function finds the "next" i with maximum happiness m
            j===!!j || (                        // If j is a bool (i.e. not a number, then stop)
              j < n &&                          // If j >= n, then no more combinations
              ++i[j] &&                         // Increment i[j] (otherwise, nop)
              c(
                i.reduce((a, b)=> a + b) > m && // If happiness score exceeds m ...
                j + !(i[j] = 0)                 // Set i[j] to 0 and negate, so we call c(j + 1)
              )
            )
        )(0) &&
        g()
      : b
  )() ||
  h(m+1) // If no assignment was found, try again with a more relaxed contraint
)(0) // Start with m = 0

```

# Answer
> 1 votes
# 05AB1E, ~~13~~ 12 bytes

```
āœΣδkÅ\®₄:O}н

```

-1 byte and corrected my limitations mistake thanks to *@DominicVanEssen*

Try it online or verify all test cases.

**Explanation:**

```
ā           # Push a list in the range [1, (implicit) input-length]
 œ          # Pop and push a list of its permutations
  Σ         # Sort these permutation-lists by:
   δ        #  Apply double-vectorized with the (implicit) input-list of lists
    k       #   Get the first 0-based index of the value in the inner input-list
            #   (or -1 if it's not present)
     Å\     #  Pop the list of lists, and leave its main diagonal
       4%   #  Modulo-4 to replace all -1s with 3s
         O  #  Then sum the list together
  }н        # After the sort-by: pop and leave the first list (with lowest sum)
            # (which is output implicitly as result)

```

# Answer
> 1 votes
# Charcoal, ~~57~~ 46 bytes

```
≔Ｅθκη⊞υ⟦⟧Ｆη≔ΣＥυＥ⁻ηκ⁺κ⟦μ⟧υ≔ＥυΣＥι﹪⌕§θμλ⁴ηＩ§υ⌕η⌊η

```

Attempt This Online! Link is to verbose version of code. 0-indexed. Explanation:

```
≔Ｅθκη⊞υ⟦⟧Ｆη≔ΣＥυＥ⁻ηκ⁺κ⟦μ⟧υ

```

Generate all the permutations of `[0..n)`. This is based on my answer to 1 to N column and row sums but tweaked to use the length of the input as `n`.

```
≔ＥυΣＥι﹪⌕§θμλ⁴η

```

Calculate the unhappiness of each permutation.

```
Ｉ§υ⌕η⌊η

```

Output a permutation with the least unhappiness.

# Answer
> 1 votes
# Vyxal, 18 bytes

```
żṖµ£⁰ƛ¥$vḟ;Þ/4%∑;h

```

Try it Online! or Verify (almost) all test cases (the larger ones time out)

Port of 05AB1E. Probably a way to shorten `£⁰ƛ¥$vḟ;`, but idk.

## How?

```
żṖµ£⁰ƛ¥$vḟ;Þ/4%∑;h
ż                  # Inclusive length range [1, length]
 Ṗ                 # All permutations
  µ             ;  # Sorting lambda
   £               # Store this item in the register
    ⁰ƛ    ;        # Mapping lambda over the input
      ¥$vḟ         # Get the index of the current character in this list
           Þ/      # Get the main diagonal of this list
             4%    # Modulo each by four to convert -1 to 3
               ∑   # Sum these
                 h # Get the first item of the sorted list

```

# Answer
> 0 votes
# Scala, 378 bytes

378 bytes, it can be golfed more.

---

Golfed version. Try it online!

```
type Q[A]=List[A]
def f(m: Q[Q[Int]])={val L=m.length;var(s,minH)=(List.fill(L)(0),5*L);def permute(input:Q[Int]):Q[Q[Int]]=input match{case Nil=>List(Nil);case _=>for{i<-input.indices.toList;rest=input.patch(i,Nil,1);other<-permute(rest)}yield input(i)::other};for(p<-permute((1 to L).toList)){val h=(0 until L).map(i=>(m(i):+p(i)).indexOf(p(i))).sum;if(h<minH){minH=h;s=p}};s}

```

Ungolfed version. Try it online!

```

import scala.util.control.Breaks._
import scala.collection.mutable.ArrayBuffer

object Main {
  def f(m: List[List[Int]]): List[Int] = {
    val L = m.length
    val H = 5 * L
    var s = List.fill(L)(0)
    var minH = H

    def permute(input: List[Int]): List[List[Int]] = {
      input match {
        case Nil => List(Nil)
        case _ => for {
          i <- input.indices.toList
          rest = input.patch(i, Nil, 1)
          other <- permute(rest)
        } yield input(i) :: other
      }
    }

    for (p <- permute((1 to L).toList)) {
      val h = (0 until L).map(i => (m(i) :+ p(i)).indexOf(p(i))).sum
      if (h < minH) {
        minH = h
        s = p
      }
    }
    s
  }

  def main(args: Array[String]): Unit = {
    println(f(List(
      List(1, 2, 3),
      List(1, 3, 4),
      List(1, 4, 5),
      List(1, 5, 6),
      List(1, 6, 7),
      List(1, 7, 8),
      List(2, 3, 8),
      List(2, 6, 5)
    )) == List(1, 3, 4, 5, 6, 7, 8, 2))
  }
}

```

---
Tags: code-golf, optimization
---


title: Calculate the Progressive Mean™

text:
# Question
Title: Calculate the Progressive Mean™
Disclaimer: This challenge is inspired by a coding error I once made.

---

Okay, time for a maths lesson. A normal mean average looks like this:

```
Work out the sum of all numbers in a list
then divide by the size of the list.

```

But what if we don't know all the numbers at the time we're working out the average? We need a way to work out the average which can be added to over time. For this reason, I present the algorithm for a Progressive Mean™

```
The running total is the first number in the list
For each of the remaining numbers
  Add the number to the running total
  Divide the running total by two

```

So in effect we're averaging each number with the current average. (We could add to this later and get the same result)

**BUT**

This doesn't give the same result at all. It gives an average, but it differs from the standard methodology for finding the mean. Now the order of the list of numbers is significant.

Of course, being a curious type, I want to work out if the Progressive Mean™ tells us anything about the order of our list of numbers. So for this reason I want to compare Mean with Progressive Mean™ by means of a simple subtraction:

```
trend = Progressive Mean™ - Standard Mean

```

---

# The Challenge

* Write a piece of code which accepts a list of numbers (in any format) which then calculates three pieces of information about it:
    + Standard Mean
    + Progressive Mean™
    + Trend (Progressive - standard)
* Work in any language you like.
* It's golf, attempt to do the challenge in as few bytes as you can.
* Avoid Standard Loopholes
* I want the output to be human-readable numbers.
* Please include a link to an online interpreter such as tio.run

---

Test Cases:

```
[1,2,3]

Normal Mean:        2.0
Progressive Mean:   2.25
Trend:              0.25

```

```
[3, 2, 1]

Normal Mean:        2.0
Progressive Mean:   1.75
Trend:              -0.25

```

```
[10, 20, 30]

Normal Mean:        20.0
Progressive Mean:   22.5
Trend:              2.5

```

```
[300, 200, 100]

Normal Mean:        200.0
Progressive Mean:   175.0
Trend:              -25.0

```

```
[10, 100, 10]

Normal Mean:        40.0
Progressive Mean:   32.5
Trend:              -7.5

```

```
[4, 4, 9, 8, 1, 8, 6, 9, 1, 1]

Normal Mean:        5.1
Progressive Mean:   2.62890625
Trend:              -2.4710937499999996

```

```
[1, 1, 1, 4, 4, 6, 8, 8, 9, 9]

Normal Mean:        5.1
Progressive Mean:   8.5390625
Trend:              3.4390625000000004

```

```
[9, 9, 8, 8, 6, 4, 4, 1, 1, 1]

Normal Mean:        5.1
Progressive Mean:   1.47265625
Trend:              -3.6273437499999996

```

# Answer
# Jelly, 9 bytes

```
Æm;+H¥/ṄI

```

A full program which accepts a list of decimals which prints:

```
[mean, progressive-mean]
trend

```

**Try it online!**

### How?

```
Æm;+H¥/ṄI - Link: list of numbers, A
Æm        - arithmetic mean       sum(A)/length(A)            = mean
      /   - reduce (A) by:
     ¥    -   the dyad f(leftEntry, rightEntry):
   +      -     addition          leftEntry + rightEntry
    H     -     halve            (leftEntry + rightEntry) / 2 = progressiveMean
  ;       - concatenate           [mean, progressiveMean]
       Ṅ  - print this list and yield it
        I - deltas                [progressiveMean - mean]
          - implicit print (Jelly represents with a single item as the item)

```
> 2 votes

# Answer
# , 57 bytes

```
function(v,`!`=sum,N=!1^v)c(A<-!v/N,P<-!v/2^c(N:1,N),P-A)

```

Try it online!

A clever collaboration with digEmAll and RobinRyder; uses the observation by Grimmy and Kevin's explanation from the comments, which I replicate below:

> For anyone else wondering why the example `[a,b,c,d] -> [a,b,c,c,d,d,d,d]` doesn't match the explanation of the code, it actually transforms `[a,b,c,d]` to `[a,b,b,c,c,c,c,d,d,d,d,d,d,d,d,a]` (so two of each value in comparison to the example). The example confused me for a moment. But nice answer, +1 from me! I also like that it has all these different types of the letter 'A' in the code: `āÅÅAÂÆª`. xD

This uses R's recycling rules to use two copies of `l[1]/2^N` in the sumby just sticking an extra `N` at the end of the decay rate.

# , 62 bytes

```
function(l)c(p<-Reduce(function(x,y)(x+y)/2,l),a<-mean(l),p-a)

```

Try it online!

Straightforward implementation.
> 10 votes

# Answer
# , 17 bytes

Translation of this.

```
-:@+/@|.(,,-)+/%#

```

Anonymous tacit prefix function. Returns list of Progressive Mean™, Standard Mean, Trend.

Try it online! This consists of three parts: `(2÷⍨+)⌿∘⌽``(,,-)``+⌿÷≢`

`+/ % #` is the sum divided by the number of elements

`⌿@|.` reverses the list and then reduces from right to left using the function:
`-:@+` add next value to previous value and halve that

`(,,-)` is the concatenation of the PM and the SM, concatenated to their difference
> 8 votes

# Answer
# Python 3.8 (pre-release), 70 69 bytes

-1 byte thanks to Kyle Gullion

returns `(mean, p_mean, trend)`

```
lambda x:(m:=sum(x)/len(x),[p:=x[0],*[p:=(p+n)/2for n in x]][-1],p-m)

```

Try it online!

Alternate version with more of a reducer implementation (89 bytes):

```
lambda x:(m:=sum(x)/(l:=len(x)),[x:=[sum(x[0:2])/2]+x[2:]for n in range(l-1)][-1],x[0]-m)

```

Although this is longer, I suspect this reducer implementation may be useful for future python 3.8 code golfing.

Try it online!

I know there has to be some more clever tricks to golf this further...
> 7 votes

# Answer
# 05AB1E, 13 bytes

```
ÅAIÅ»+;}θ‚ÂÆª

```

Outputs as a triplet `[mean, progressive-mean, trend]`.

Try it online or verify all test cases.

**Explanation:**

```
ÅA     # Calculate the arithmetic mean of the (implicit) input-list
I      # Push the input-list again
 Å»    # Left-reduce it by:
   +   #  Add the two values together
    ;  #  And halve it
 }θ    # After the reduction, leave only the last value
‚      # Pair it with the earlier calculated arithmetic mean
 Â     # Bifurcate this pair; short for Duplicate & Reverse copy
  Æ    # Reduce it by subtraction
   ª   # And append this trend to the pair
       # (after which the result is output implicitly)

```
> 6 votes

# Answer
# Scratch 2.0/3.0, 35 blocks/263 bytes

SB Syntax:

```
when gf clicked
set[i v]to(2
set[L v]to(length of[I v
set[T v]to(item(1)of[I v
set[P v]to(T
repeat((L)-(1
change[T v]by(item(i)of[I v
change[P v]by(item(i)of[I v
set[P v]to((P)/(2
change[i v]by(1
end
set[T v]to((T)/(L
say(join(join(join(join(P)[,])(T))[,])((P)-(T

```

It's accidentally a polyglot. I accidentally forgot my password and email for my other scratch account so I had to make a new one so y'all can Try it on Scratch!

Y'all need to change the input list shown in the top left corner on the project for this to work properly.
> 6 votes

# Answer
# Python 3, ~~81~~ \\$\cdots\\$ ~~75~~ 71 bytes

Saved ~~1~~5 bytes thanks to Reinstate Monica!!!

```
def f(l):
 m=sum(l)/len(l);p=l[0]
 for n in l:p=(p+n)/2
 return m,p,p-m

```

Try it online!
> 5 votes

# Answer
# JavaScript (ES6), 55 bytes

Returns `[mean, p_mean, trend]`.

```
a=>a.map(v=>t=(s+=v,n++)?(t+v)/2:v,n=s=0)&&[s/=n,t,t-s]

```

Try it online!
> 4 votes

# Answer
# APL (Dyalog Unicode), ~~20~~ 18 bytesSBCS

-2 thanks to Bubbler.

Anonymous tacit prefix function. Returns list of Progressive Mean™, Standard Mean, Trend.

```
(2÷⍨+)⌿∘⌽(,,-)+⌿÷≢

```

Try it online!

This consists of three parts: `(2÷⍨+)⌿∘⌽``(,,-)``+⌿÷≢`

`+⌿ ÷ ≢` is the sum divided by the count

`(``)⌿∘⌽` reverses the list and then reduces from right to left using the function:
`2÷⍨+` add next value to previous value and divide that by two

`(,,-)` is the concatenation of the PM and the SM, concatenated to their difference
> 4 votes

# Answer
# 05AB1E, 12 bytes

```
āÍoîÅΓ‚ÅAÂÆª

```

Try it online!

The progressive mean is equivalent to a weighted arithmetic mean, with exponentially increasing weights. For example, the progressive mean of a 4 element list `[a, b, c, d]` is the arithmetic mean of `[a, b, c, c, d, d, d, d]`.

```
ā              # range [1..length of input]
 Í             # subtract 2 from each
  o            # 2**each: [0.5, 1, 2, ...]
   î           # round up: [1, 1, 2, ...]
    ÅΓ         # run-length decode
      ‚        # pair with the input
       ÅA      # arithmetic mean of each list
         Â     # push a reversed copy
          Æ    # reduce by subtraction
           ª   # append

```
> 4 votes

# Answer
# Factor, ~~80~~ 79 bytes

```
: f ( s -- s ) [ mean ] [ dup first [ + 2. / ] reduce ] bi 2dup swap - 3array ;

```

Try it online!
> 3 votes

# Answer
# Wolfram Language (Mathematica), 31 bytes

```
{a=Mean@#,b=+##/2&~Fold~#,b-a}&

```

Try it online! Pure function. Takes a list of numbers as input and returns a list of rational numbers as output. I'm pretty sure that improper fractions count as human-readable, but if they aren't, adding `N@` (+2 bytes) to the start causes the function to output approximate numbers.
> 3 votes

# Answer
# PowerShell, 54 bytes

```
$args|%{$y+=$_;$z=($_+$z)/(2-!$i++)}
($y/=$i)
$z
$z-$y

```

Try it online!

Takes input by splatting. The only neat trick is the `!$i++` bit which negates the first iteration where `$i` is 0 to 1, and all subsequent numbers to 0.
> 2 votes

# Answer
# Raku(Perl 6), 41 40 bytes

```
{|($/=(.reduce((*+*)/2),.sum/$_)),$0-$1}

```

My original solution had `my \a=`and used `[-]|@a` at the end, but abusing `$/` is always fun, especially with also abusing assignments. Pretty straightforward calculation wise.

Try it online!
> 2 votes

# Answer
# C (gcc), 111 109 bytes

```
#define P printf("%f "
f(a,l,i)int*a;{float s=*a++,p=s;for(i=l-1;i--;p+=*a++,p/=2)s+=*a;P,s/=l);P,p);P,p-s);}

```

Try it online!
> 2 votes

# Answer
# Haskell, 84 bytes

I thought Haskell could do decently here because this challenge works on lists and I tend to think Haskell and lists go well together... But I couldn't come up with anything very clever. Let's see if @xnor drops by and has anything nice :P

```
f(h:l)=g$foldl(\(p,s,w)n->((p+n)/2,s+n,w+1))(h,h,1)l
f[]=f[0]
g(p,s,l)=(s/l,p,p-s/l)

```

I am defining an anonymous function `\(p,s,w) n -> ((p+n)/2, s+n, w+1)` that receives a triplet and the next list element, and does three things: updates the progressive mean, sums the whole list and computes its length. In the end, function `g` does some last-minute calculations.

You can try it online
> 1 votes

# Answer
# Charcoal, 27 bytes

```
≔∕ΣθＬθη≔§θ⁰ζＦθ≔⊘⁺ιζζＩ⟦ηζ⁻ζη

```

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

```
≔∕ΣθＬθη

```

Calculate the arithmetic mean.

```
≔§θ⁰ζ

```

Start with the first element. We therefore end up averaging this element with itself, but that doesn't affect the final result of course.

```
Ｆθ≔⊘⁺ιζζ

```

Loop over each element an average it with the progressive mean so far.

```
Ｉ⟦ηζ⁻ζη

```

Print the arithmetic and progressive means and their difference.

If we had only needed the result once then `ΣＥθ∕ιＸ²⁻Ｌθ∨κ¹` could have been used to calculate the progressive mean directly, saving 3 bytes over the naïve method.
> 1 votes

# Answer
# PHP, ~~90~~ 88 bytes

```
function($i){for($j=$i[0];$x=$i[$c++|0];$s+=$x,$j+=$x,$j/=2);return[$s/=$c-1,$j,$j-$s];}

```

Try it online!
> 1 votes

# Answer
# Perl 5 `-MList::Util=sum,reduce -pa`, ~~51~~ 50 bytes

```
say+($\=reduce{$a=$a/2+$b/2}@F)-($_=(sum@F)/@F.$/)

```

Try it online!

Output format is

```
trend
traditional
progressive

```
> 1 votes

# Answer
# Burlesque, 19 bytes

```
psJr{.+2./}javq.-c!

```

Try it online!

Takes input of the form `300.0 200.0 100.0`. If we didn't have to print the other values would be 3 bytes shorter (i.e. Without the continuation). Returns progressive mean™, arithmetic mean, trend

```
ps    # Parse list to array
J     # Duplicate
r{    # Reduce by (Progressive Mean)
  .+  # Adding
  2./ # Dividing by 2
}
jav   # Calulcate regular mean
q.-   # Quoted (boxed) subtract {.-}
c!    # On a non-destructive stack

```
> 1 votes

# Answer
# Python 3.8, 91 bytes

I wanted to flatten the recursive relation, and I got this:

```
lambda l:(m:=sum(l)/(n:=len(l)),(p:=sum(l[-i]/2**i for i in range(1,n))+l[0]/2**(n-1)),p-m)

```

Try it online!

The use of `range` instead of the list itself makes it much longer.
> 1 votes

# Answer
# Ruby, 54 bytes

```
->x{a=x.sum/x.size;b=x.inject{|a,b|a/2+b/2};[a,b,b-a]}

```

Try it online!

Takes a list of numbers in the format `[1.0, 2.0, 3.0]` and returns an array containing the mean, progressive-mean, and trend, respectively.
> 1 votes

# Answer
# Haskell, 58 bytes

```
s!p=(s,p,p-s)
f x=(sum x/sum[1|_<-x])!foldl1(((/2).).(+))x

```

Try it online!
> 1 votes

# Answer
# Rust, 144 122 bytes

```
let f=|y:&[f64]|{let m=y.iter().sum::<f64>()/y.len()as f64;let pm=y[1..].iter().fold(y[0],|acc,x|(acc+x)/2.);(m,pm,pm-m)};

```

Straightforward approach. Shaved 22 bytes thanks SirBogman, and thanks Mabel for showing TIO's Rust support.

Try it online!
> 1 votes

# Answer
# Java (JDK), ~~116~~ 115 bytes

```
v->{float m=0,p=0;for(int i=0;i<a.length;i++){m+=a[i];p+=a[i];p=i!=0?p/2:p;}m/=a.length;return m+"\n"+p+"\n"+(p-m);

```

Try it online!
> 1 votes

# Answer
# Factor, 48 bytes

```
[ [ unclip [ + 2 / ] reduce ] keep mean 2dup - ]

```

Try it online!
> 1 votes

# Answer
# Arturo, 57 bytes

```
$[b][a:average b@[p:fold.seed:b\0b[x y][//x+y 2]a p p-a]]

```

Try it
> 1 votes

# Answer
# Scala, 126 bytes

Golfed version. Try it online!

```
def f(v:Array[Float])={var m,p:Float=0;for(i<-v.indices){m+=v(i);p+=v(i);p=if(i!=0)p/2 else p;};m/=v.length;s"$m\n$p\n${p-m}"}

```

Ungolfed version. Try it online!

```
object Main extends App {
  val a: Array[Float] = Array(9, 9, 8, 8, 6, 4, 4, 1, 1, 1)
  val f: Array[Float] => String = v => {
    var m, p: Float = 0
    for (i <- v.indices) {
      m += v(i)
      p += v(i)
      p = if (i != 0) p / 2 else p
    }
    m /= v.length
    s"$m\n$p\n${p - m}"
  }
  println(f(a))
}

```
> 1 votes

---
Tags: code-golf, math
---


title: Least Common Multiple

text:
# Question
Title: Least Common Multiple
The least common multiple of a set of positive integers `A` is the smallest postive integer `B` such that, for each `k` in `A`, there exists a positive integer `n` such that `k*n = B`.

Given at least two positive integers as input, output their least common multiple.

## Rules

* Builtins are allowed, but if your solution uses one, you are encouraged to include an alternate solution that does not use GCD/LCM builtins. However, the alternate solution will not count towards your score at all, so it is entirely optional.
* All inputs and outputs will be within the natively-representable range for your language. If your language is natively capable of arbitrarily-large integers, then your solution must work with arbitrarily large inputs and outputs.

## Test cases

```
[7, 2] -> 14
[8, 1] -> 8
[6, 4, 8] -> 24
[8, 2, 1, 10] -> 40
[9, 6, 2, 1, 5] -> 90
[5, 5, 7, 1, 1] -> 35
[4, 13, 8, 8, 11, 1] -> 1144
[7, 2, 2, 11, 11, 8, 5] -> 3080
[1, 6, 10, 3, 4, 10, 7] -> 420
[5, 2, 9, 10, 3, 4, 4, 4, 7] -> 1260
[9, 7, 10, 9, 7, 8, 5, 10, 1] -> 2520

```

# Answer
> 5 votes
# Actually, ~~12~~ 1 byte

Golfing suggestions are still welcome, though I'm not sure how to improve on the raw LCM built-in. Try it online!

A 12-byte version without the built-in. Golfing suggestions welcome. Try it online!

```
╗2`╜@♀%ΣY`╓N

```

**Ungolfing**

```
          Implicit input array.
╗         Save array in register 0.
2`...`╓   Starting with f(0), find the first (two) x where f(x) returns a truthy value.
          These two values will be 0 and our LCM.
  ╜         Push array from register 0.
  @         Swap the top two values. Stack: x, array
  ♀%        Map % over x and array, returning (x % item) for each item in array.
  ΣY        If the sum of all the modulos equals 0, x is either 0 or our LCM.

N         Push the last (second) value of our results. This is our LCM.
          Implicit return.

```

# Answer
> 19 votes
## JavaScript (ES6), 36 bytes

```
f=(a,i=1)=>a.some(v=>i%v)?f(a,i+1):i

```

Starting from `1` it's the first number that can be divided by all.

```
f=(a,i=1)=>a.some(v=>i%v)?f(a,i+1):i
;

console.log(f([7, 2]));
console.log(f([8, 1]));
console.log(f([6, 4, 8]));
console.log(f([8, 2, 1, 10]));
console.log(f([9, 6, 2, 1, 5]));
console.log(f([5, 5, 7, 1, 1]));
console.log(f([4, 13, 8, 8, 11, 1]));
console.log(f([7, 2, 2, 11, 11, 8, 5]));
console.log(f([1, 6, 10, 3, 4, 10, 7]));
console.log(f([5, 2, 9, 10, 3, 4, 4, 4, 7]));
console.log(f([9, 7, 10, 9, 7, 8, 5, 10, 1]));
```

# Answer
> 12 votes
# 05AB1E/2sable, 2 bytes

```
.¿

```

Try it online! in 05AB1E
or 2sable

# Answer
> 11 votes
# Jelly, 3 bytes

```
æl/

```

Reduces by LCM. Try it online! or verify all test cases.

## Alternate version, 6 bytes

```
ÆE»/ÆẸ

```

Try it online! or verify all test cases.

### How it works

```
ÆE»/ÆẸ  Main link. Argument: A (array)

ÆE      Yield all prime exponents of each integer in A.
  »/    Reduce columns (exponents that correspond to the same prime) by maximum.
    ÆẸ  Turn the resulting array of prime exponents into the corresponding integer.

```

# Answer
> 8 votes
# Python, ~~69~~ ~~65~~ ~~52~~ 50 bytes

```
A=lambda l,i=1:any(i%a for a in l)and A(l,i+1)or i

```

2 bytes saved thanks to Dennis!

Pretty straightforward recursive solution, you will need to make the recursion limit a bit higher for some of the test cases to work.

# Answer
> 8 votes
# MATL, 7 bytes

```
&YFX>^p

```

No builtin.

Try it online!

### Explanation

Let's take input `[8, 2, 1, 10]` as an example.

```
&YF    % Take array implicitly. Push vector of prime factors and matrix of exponents
       % of factorization, where each row represents one of the input numbers
       %   STACK: [2 3 5], [3 0 0; 1 0 0; 0 0 0; 1 0 1]
X>     % Maximum of each column
       %   STACK: [2 3 5], [3 0 1]
^      % Element-wise power
       %   STACK: [8 1 5]
p      % Product of array
       %   STACK: 40
       % Implicitly display

```

---

*EDIT (June 9, 2017): `YF` with two outputs has been modified in release 20.1.0: non-factor primes and their (zero) exponents are skipped. This doesn't affect the above code, which works without requiring any changes.*

# Answer
> 6 votes
## PowerShell v2+, ~~73~~ 60 bytes

```
param($a)for($i=1;($a|?{!($i%$_)}).count-ne$a.count){$i++}$i

```

Takes input `$a`, loops upward from `$i=1` with `$i++`, based on a conditional. The condition is `($a|?{!($i%$_)}).count` being `-n`ot`e`qual to `$a.count`. Meaning, the loop ends when the elements of `$a` that *are* divisors of `$i` is equal to the elements of `$a`. Then, a solitary `$i` is left on the pipeline, and output is implicit.

### Test Cases

```
PS C:\Tools\Scripts\golfing> @(7,2),@(8,1),@(6,4,8),@(8,2,1,10),@(9,6,2,1,5),@(5,5,7,1,1),@(4,13,8,8,11,1)|%{($_-join',')+" -> "+(.\least-common-multiple.ps1 $_)}
7,2 -> 14
8,1 -> 8
6,4,8 -> 24
8,2,1,10 -> 40
9,6,2,1,5 -> 90
5,5,7,1,1 -> 35
4,13,8,8,11,1 -> 1144

PS C:\Tools\Scripts\golfing> @(7,2,2,11,11,8,5),@(1,6,10,3,4,10,7),@(5,2,9,10,3,4,4,4,7),@(9,7,10,9,7,8,5,10,1)|%{($_-join',')+" -> "+(.\least-common-multiple.ps1 $_)}
7,2,2,11,11,8,5 -> 3080
1,6,10,3,4,10,7 -> 420
5,2,9,10,3,4,4,4,7 -> 1260
9,7,10,9,7,8,5,10,1 -> 2520

```

# Answer
> 6 votes
# Julia (3 Bytes) \[Working on Non-Built-in\]

```
lcm     # Using LCM built-in (3 Bytes)

```

As Dennis pointed out, I keep forgetting that Julia automatically vectorizes inputs.

## Example:

```
println(lcm(1,2,3,4,5,6,7,8,9)) #Prints 2520

```

# Answer
> 4 votes
# JavaScript (ES6), ~~63~~ 59 bytes

```
f=([x,...a])=>a[0]?x*f(a)/(g=(m,n)=>n?g(n,m%n):m)(x,f(a)):x

```

Recursively finds the LCM of the last two elements.

# Answer
> 4 votes
# Cheddar, 33 bytes

```
(n,i=1)f->n.any(i&(%))?f(n,i+1):i

```

Nothing super new.

## Ungolfed

```
(n, i = 1) f ->
  n.any(j -> i % j) ?
    f(n, i + 1) :
    i

```

Basically this starts at one and keeps increasing until it finds an LCM

# Answer
> 4 votes
# Mathematica, 3 bytes

```
LCM

```

Usage:

```
In[1]:= LCM[9, 7, 10, 9, 7, 8, 5, 10, 1]

Out[1]= 2520

```

# Answer
> 4 votes
# Brachylog v2, 8 bytes

```
{×↙Xℕ₁}ᵛ

```

Try it online!

It's funny just how directly this maps on to the definition given in the challenge.

```
{     }ᵛ    Each element of
            the input
 ×          multiplied by
  ↙X        some arbitrary and inconsistent integer
    ℕ₁      is a natural number,
       ᵛ    which is the same for each element,
            and is the output.

```

A suspiciously slow but significantly shorter solution:

# Brachylog v2, 5 bytes

```
f⊇p~d

```

Try it online!

Takes input through the output variable and gives output through the input variable. Rips right through the first four test cases but I'm still waiting on the fifth... Ordinarily, I'd still make it my primary solution and just trust that it works correctly, but I don't know why it hasn't confirmed that 90 is the LCM of `9, 6, 2, 1, 5` when I *gave it 90* twenty minutes ago.

(Edit: It confirmed the answer after no more than 16 hours, and generated it alongside the LCM of `5, 5, 7, 1, 1` after about two days.)

```
         The output variable
   ~d    with duplicates removed
  p      is a permutation of
 ⊇       a sublist of
f        the factors of
         the input variable.

```

And another completely different predicate that accidentally more-or-less translates Fatalize's Brachylog v1 solution:

# Brachylog v2, 10 bytes

```
;.gᵗ↔z%ᵛ0<

```

Try it online!

This was salvaged from a solution I'd made for this challenge before I realized the output wasn't restricted to being an integer.

```
 .            The output
; gᵗ↔z        paired with each element of
              the input,
      %ᵛ      when the first element of each pair is taken mod the second, is always
        0     zero.
              Furthermore, the output
         <    is strictly greater than
        0     zero.

```

# Answer
> 3 votes
# Dyalog APL, 2 bytes

```
∧/

```

Reduces by LCM. Test it on TryAPL.

# Answer
> 3 votes
# Java 8, ~~75~~ ~~59~~ ~~121~~ 89 bytes

Uses the Euclidean Algorithm and the fact that LCM(A, B)= A * B / GCD(A, B)

* ***16** bytes off. Thanks to @carusocomputing*
* *Added Multi-Input +**62** bytes*
* ***32** bytes off. Thanks to @Olivier Grégoire*

Code:

```
public static int lcm(int l, int c){
  for(int i=1;i<=l&&i<=c;++i)
    if (i%l==0&&i%c==0)
      return l*c/i;
}
public static int lcm(int...x){
  int y=x[0];
  for(int j:x){
    y=lcm(j,y);
  }
  return y;
}

```

Remove line-breaks:

```
int g(int a,int b){return b<1?a:g(b,a%b);}

```

---

```
l->{int l=1;for(int n:a)l=l*n/g(l,n);return l;}

```

# Answer
> 3 votes
## JavaScript (ES6), 52 bytes

```
a=>a.reduce((l,n)=>l*n/(g=(m,n)=>n?g(n,m%n):m)(l,n))

```

I `reduce`d this answer as much as I could but I'm obviously not going to get anywhere near the simplicity of @Hedi's answer.

# Answer
> 2 votes
# MATL, 3 bytes

```
&Zm

```

This uses the builtin function with array input.

Try it online!

# Answer
> 2 votes
# Brachylog, 17 bytes

```
,.#>=g:?z:%a#=h0,

```

Try it online!

### Explanation

```
,.#>=               Output is a strictly positive integer
     g:?z           Zip the Output with the Input
         :%a        Compute Output mod I for each I in the Input
            #=h0,   All results must be equal to 0

```

# Answer
> 2 votes
# C#, 50+18 = 68 bytes

50 bytes for method defintion, +18 bytes for LINQ import.

```
using System.Linq;int L(int[]n,int i=1)=>n.All(x=>1>i%x)?i:L(n,i+1);

```

Pretty much the same as a lot of other answers. Counts up recursively until it finds the LCM. I was a bit surprised this didn't get a StackOverflowException, so I also have a non-recursive version which is actually just 1 byte longer.

```
using System.Linq;n=>{for(int i=1;;i++)if(n.All(x=>1>i%x))return i;};

```

Ungolfed:

```
using System.Linq;            // Import LINQ
int L(int[] n, int i = 1) =>  // Function declaration
    n.All(x => 1 > i % x)     // Check if each x in n divides i
        ? i                   // And if so return i
        : L(n, i + 1)         // Otherwise increment i and recurse
;

```

# Answer
> 2 votes
# Perl 6, 10 bytes

```
{[lcm] @_}

```

basically the same as:

```
sub ( *@_ ) { @_.reduce: &infix:< lcm > }

```

# Answer
> 2 votes
# J, 11 bytes

```
>./&.(_&q:)

```

There is a solution for **3 bytes** using the LCM builtin.

```
*./

```

## Explanation

```
>./&.(_&q:)  Input: array of integers A
      _&q:   Get the prime exponents of each integer in A
>./&         Reduce by maximum on the lists
   &. _&q:   Convert the list of exponents back to an integer

*./  Input: array of integers A
  /  Reduce using
*.     LCM

```

# Answer
> 2 votes
## Racket 13 bytes

lcm is a built-in function in Racket:

```
(apply lcm l)

```

Testing:

```
(define (f l)
   (apply lcm l))

(f (list 7 2))
(f (list 8 1))
(f (list 6 4 8))
(f (list 8 2 1 10))
(f (list 9 6 2 1 5))
(f (list 5 5 7 1 1))
(f (list 4 13 8 8 11 1))
(f (list 7 2 2 11 11 8 5))
(f (list 1 6 10 3 4 10 7))
(f (list 5 2 9 10 3 4 4 4 7))
(f (list 9 7 10 9 7 8 5 10 1))

```

Output:

```
14
8
24
40
90
35
1144
3080
420
1260
2520

```

# Answer
> 2 votes
# CJam, ~~18~~ ~~17~~ 16 bytes

1 byte saved thanks to Martin Ender.

Incrementing until the LCM is found.

```
q~0{)_2$f%:+}g\;

```

Try it online

# Answer
> 2 votes
# R, 36 bytes (not builtin)

```
v=scan();i=1;while(any(i%%v))i=i+1;i

```

Takes the input. Then tests each positive integer by taking the mod.

# Answer
> 2 votes
# APOL, 49 bytes

`v(0 1);v(1 i);w(⊕(ƒ(s(¹) %(⁰ I(∋)))) ∆(0));-(⁰ 1)`

This could almost certaintly be made shorter, maybe I'll come back to it later.

# Answer
> 1 votes
# Pyth, 9 bytes

```
.U/*bZibZ

```

A program that takes input of a list on STDIN and prints the result.

Try it online or verify all test cases

**How it works**

```
.U/*bZibZ  Program. Input: Q
.U         Reduce Q by (implicit input fill):
   *bZ      Product of current and next value
  /   ibZ   divided by GCD of current and next value
           Implicitly print

```

# Answer
> 1 votes
## Haskell, 10 bytes

```
foldr1 lcm

```

Usage example: `foldl1 lcm [5,2,9,10,3,4,4,4,7]` -\> `1260`.

# Answer
> 1 votes
## PHP, ~~42~~ 74 bytes

```
for(;($p=++$f*$argv[1])%$argv[2];);echo$p;

```

straight forward:
loop `$f` from 1 upwards; if `$f*$a` divides through `$b` without a remainder, the LCM is found.

---

I totally had overread the `at least` ... here´s the code for any number of parameters:

```
for(;$i<$argc;)for($p=$argv[$i=1]*++$f;++$i<$argc&$p%$argv[$i]<1;);echo$p;

```

Loop `$f` from 1 upwards while inner loop has not run to $argc.
Loop `$i` from `2` to `$argc-1` while `$f*$argv[1]` divides through `$argv[$i]` without a remainder.
both loops broken: print `$f*$argument 1`.

# Answer
> 1 votes
## Pip, 10 bytes

```
W$+o%g++oo

```

Uses the "try every number until one works" strategy. Try it online!

```
            o is preinitialized to 1, g is list of cmdline args
   o%g      Mod o by each arg
 $+         Sum (truthy if any nonzero, falsy if all zero)
W           Loop while that expression is truthy:
      ++o     Increment o
         o  Autoprint o

```

# Answer
> 1 votes
# Prolog (SWI), 46 bytes

```
l([],1).
l([X|Y],P):-l(Y,Q),P is X*Q/gcd(X,Q).

```

Try it online!

Another solution, 59 bytes:

```
l(A,X):-between(1,inf,X),forall(member(Y,A),X mod Y=:=0),!.

```

# Answer
> 1 votes
# , 34 bytes

```
*/@((0 1+])^:(*@+/@:|*/)^:_>./,1:)

```

A **while** loop iterating through multiples of the largest number in input.

Try it online!

# Answer
> 1 votes
# Scala, 44 bytes

```
Stream.from(1).find(i=>x.forall(i%_==0)).get

```

Try it online!

# Answer
> 1 votes
# Python 3, 83 bytes

```
import math,functools as i
t=lambda t:i.reduce(lambda a,b:int(a*b/math.gcd(a,b)),t)

```

# Answer
> 1 votes
# Pyth, 7 bytes

```
f!s%LTQ

```

Try it online!

# Answer
> 1 votes
# Python 3.9, 20 bytes

```
import math
math.lcm

```

Now Python 3.9 has a builtin in `math` module to calculate LCM of two or more integers.

# Answer
> 1 votes
# Rust, 45 bytes

```
|i:&[_]|(1..).find(|v|i.iter().all(|a|v%a<1))

```

Try it online!

Iterates over all numbers until finding the first one which is divisible by all the numbers in the given slice. Hey, it saves bytes!

# Answer
> 1 votes
# Vyxal, 2 bytes

```
∆Ŀ

```

Try it Online!

# Answer
> 1 votes
# Ruby, 17 bytes

```
->x{x.inject:lcm}
```

Attempt This Online!

# Answer
> 1 votes
# PARI/GP, 3 bytes

`lcm`

Without builtins, 50 bytes:

```
v->fold((a,b)->for(k=a,a*b,k%b||k%a||return(k)),v)

```

The `forstep` version is 1 byte longer. Older versions can shave 2 bytes with `|` in place of `||`.

# Answer
> 1 votes
# Thunno 2, 1 byte

```
ŀ

```

Try it online!

Non built-in,  **~~6 5~~  4 bytes**:

```
ƘŒS~

```

Try it online!

*-1 thanks to @Jacob*

#### Explanation

```
ŀ  # Implicit input. Built-in to calculate LCM. Implicit output.

ƘŒS~  # Implicit input
Ƙ     # Find the first positive integer where:
 Œ    #  The number mod the input (vectorises)
  S~  #  Has a sum of 0 (i.e. it contains only zeros)
      # Implicit output

```

# Answer
> 0 votes
# Pyth - ~~7~~ 6 bytes

No builtin.

```
*F{sPM

```

Try it online here.

# Answer
> 0 votes
# PHP, 65 Bytes

```
<?for($t=1;$t&&++$i;$t=!$t)foreach($_GET as$v)$t*=$i%$v<1;echo$i;

```

Try it online!

or

```
for(;++$i;!$t?:die("$i"))for($n=$t=1;$v=$argv[$n++];)$t*=$i%$v<1;

```

or

```
<?for($t=1;++$i;$t=!$t?:die("$i"))foreach($_GET as$v)$t*=$i%$v<1;

```

PHP, 96 Bytes

with 2 loops

```
while(1<count($a=&$_GET[i])){$e=array_pop($a);for($i=0;($m=++$i*$e)%$a[0];);$a[0]=$m;}echo$a[0];

```

based on set theory 128 Bytes

```
$p=array_product($a=$_GET[i]);echo min(array_intersect(...array_map($r=function($n)use($p){return range($n,$p,$n);},$_GET[i])));

```

# Answer
> 0 votes
## Java 7, 75 bytes

```
int f(int[]a){int i=1,s=1;for(;s>0;i++){s=0;for(int b:a)s+=i%b;}return--i;}

```

A simple two-loop method. Start at one and check to see when all the remainders add to zero.

I had to jump through some dumb hoops with `s`. There's probably a better way to do that, but it's 1:00 AM and it'll have to wait :/

# Answer
> 0 votes
## R, 30 21 bytes

Using the `mLCM` function from the numbers package:

```
numbers::mLCM(scan())

```

Or without builtins (81 bytes):

```
L=function(x,y,g=function(x,y,r=x%%y)`if`(r,g(y,r),y))x*y/g(x,y)
Reduce(L,scan())

```

We first define a function `L` for the pair-wise LCM and then apply it iteratively using `Reduce`.

# Answer
> 0 votes
# Axiom, 19 bytes

```
f(x)==reduce(lcm,x)

```

Could be perhaps better and right but longer

```
f(x:List PI):PI==reduce(lcm,x)

```

# Answer
> 0 votes
# J, 27 bytes

not using built ins, naive solution

```
>:0 i.~+/"1 i|"1 0>:i.*/i=.

```

usage

```
>:0 i.~+/"1 i|"1 0>:i.*/i=.9 6 2 1 5

```

returns 90

# Answer
> 0 votes
# Japt, 8 bytes

```
@e!vX}a1

```

Try it

# Answer
> 0 votes
# Perl 5, 52 + 2 (-pa) = 54 bytes

```
$r=$\=$_;while($r){$r=0;$r||=$\%$_ for@F;$r&&$\++}}{

```

Try it online!

# Answer
> 0 votes
A little late to the party, but I didn't see an `AWK` answer.

# AWK, 49 bytes

```
{for(x=1;x&&++m;)for(x=i=0;i++<NF;)x+=m%$i;$0=m}1

```

Try it online!

NOTE: The link has 2 extra bytes `m=` in front of the `x=1;x...` to simplify testing/allow multiple inputs/outputs. However, the `m=` fails for single/repeated input value of 1. The code as written handles `1` fine.

# Answer
> 0 votes
# Jq 1.5, 67 bytes

Not very smart. Just tests each i from 2 to product of numbers.

```
first(range(2;1+reduce.[]as$x(1;.*$x))as$i|select(all($i%.==0))|$i)

```

More efficient but longer:

```
def g(a;b):if b<1then a else g(b;a%b)end;reduce.[]as$x(1;.*$x/g(.;$x))

```

Try it online!

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


title: Shortest Path Around Obstacle

text:
# Question
Title: Shortest Path Around Obstacle
The task here is simple: given a target location on an XY grid, and a rectangle on that grid, find the length of the shortest path from the origin to the target which does not intersect the rectangle.

All parameter values are integers. You can assume that neither the target point nor the origin is inside or on the border of the rectangle.

The rectangle can be specified in any reasonable format -- e.g. `(<left x coordinate>, <top y coordinate>, <width>, <height>)` or `(<left x coordinate>, <right x coordinate>, <top y coordinate>, <bottom y coordinate>)`. For the purposes of these examples I will use the format `(<left x coordinate>, <top y coordinate>, <width>, <height>)`.

Your answer must be within one percent of the true answer for any input (ignoring errors due to floating point).

Here is the example where the target coordinate is `(5, 5)` (shown in green) and the rectangle has top left corner of `(2, 4)` and width & height of `(2, 3)` (shown in maroon). The shortest path is shown in orange.

In this case, the shortest path has length \\$\sqrt{2^2+4^2} + \sqrt{1^2+3^2}\ \approx 7.63\\$.

Note that the rectangle does *not* need to be obstructing the path between the origin and the target location -- take the same rectangle as the previous example, but with the target point of (-3, 5):

In this case, the answer is \\$\sqrt{3^2 + 5^2} \approx 5.83\\$.

## Test cases

| target x | target y | rectangle x | rectangle y | width | height | answer |
| --- | --- | --- | --- | --- | --- | --- |
| 5 | 5 | 2 | 4 | 2 | 3 | 7.6344136152 |
| 5 | 5 | 4 | 2 | 3 | 2 | 7.0710678119 |
| -3 | 5 | 2 | 4 | 2 | 3 | 5.83095189485 |
| 0 | 0 | 100 | -50 | 50 | 30 | 0 |
| 0 | 100 | -1 | -2 | 3 | 4 | 100 |
| 8 | 0 | 1 | 2 | 3 | 4 | 9.7082039325 |
| 8 | 0 | 1 | 3 | 3 | 5 | 9.7082039325 |

Standard loopholes are forbidden. Since this is , the shortest program wins.

# Answer
# Vyxal , 54 bytes

```
ΠÞx¾pƛ00"p⁰J;'2lƛ¹ΠǔI¨VYƛǔ-:ǔk+v*R¨£Þ•±≈;a;a¬;ƛ¯v∆/∑;g

```

Try it Online!

Takes input in the form of `[[left_x, right_x], [bottom_y, top_y]], [[target_x, target_y]]`.

## How?

The first step is to generate all polygonal chains that begin with \\$(0,0)\\$ and end with the target and the rest of the vertices are some (or none) of the vertices of the rectangle.

```
ΠÞx¾pƛ00"p⁰J;
Π             # cartesian product of [left_x, right_x] and [bottom_y, top_y]
 Þx           # all combinations without replacement
   ¾p         # prepend an empty list
     ƛ      ; # map:
      00"p    #   prepend [0, 0]
          ⁰J  #   append the target

```

The second step is to filter out the chains that intersect the interior of the rectangle. This is done by checking if any of the segments intersects a diagonal of the rectangle at an interior point.

The key observation is that if segments \\$AB\\$ and \\$CD\\$ are not on the same line, they intersect at an interior point iff \\$ACBD\\$ is a non-degenerate convex quadrilateral. This is checked by looking at the vectors \\$C-A\\$, \\$B-C\\$, \\$D-B\\$ and \\$A-D\\$ and for each adjacent pair rotating the second one by 90° and computing the dot product. If all the dot products have the same sign than the quadrilateral must be non-degenerate and convex.

```
'2lƛ¹ΠǔI¨VYƛǔ-:ǔk+v*R¨£Þ•±≈;a;a¬;
'                               ; # filter by:
 2l                               #   all overlapping pairs
   ƛ                       ;      #   map:
    ¹Π                            #     cartesian product of the second to last input
      ǔ                           #     rotate right
       I                          #     split into two halves, this gives us the two diagonals
        ¨VY                       #     interleave vectorized over the right operand
           ƛ             ;        #     map:
            ǔ-                    #       rotate right and subtract from itself
              :                   #       duplicate
               ǔ                  #       rotate right
                k+v*              #       multiply each by [1, -1]
                    R             #       reverse each
                     ¨£Þ•         #       zip and reduce each pair by dot product
                         ±        #       sign
                          ≈       #       are all equal?
                            a     #     any
                              a   #   any
                               ¬  #   not

```

The last step is to calculate the lengths of all the remaining chains and get the minimum.

```
ƛ¯v∆/∑;g
ƛ     ;  # map:
 ¯       #   subtract adjacent pairs
  v∆/    #   get the length of each vector
     ∑   #   sum
       g # minimum

```
> 4 votes

# Answer
# Haskell, 414 bytes

```
import Data.List
t[[[a,b],[c,d]],[[e,f],[g,h]]]=((a-e)*(f-h)-(b-f)*(e-g))/((a-c)*(f-h)-(b-d)*(e-g))
w x=t x>0&&t x<1
v s t=not(w[s,t]&&w[t,s])
s[[x,y],[l,t],[w,h]]=minimum[sum$map(\[[a,b],[c,d]]->((c-a)^2+(d-b)^2)**0.5)q|
 c<-subsequences[[l,t],[l+w,t],[l+w,t-h],[l,t-h]],length c<3,
 p<-permutations c,let r=[0,0]:p++[[x,y]],let q=zipWith(\a b->[a,b])r(tail r),
 all(v[[l,t],[l+w,t-h]])q,all(v[[l+w,t],[l,t-h]])q]

```

Try it online!
> 2 votes

# Answer
# Wolfram Language (Mathematica), 213 bytes

```
(p=Join[{c={0.,0.}},#1,{#2}];Min[ArcLength/@If[RegionDisjoint[Polygon@#1,l=Line@{c,#2}],{l},m=MeshCoordinates@ConvexHullMesh@p;s=m[[FindShortestTour[m][[2]]]];g=Position[s,#2][[1, 1]];Line/@{s[[;;g]],s[[g;;]]}]])&

```

Try it online!
Input must be *float*: array of all vertices and goal point.

There are three main cases (orange is convex hull of all points):

All of them catch by the next (ungolfed, self-explained) algorithm:

```
shortestPath[vertices_, goal_] :=
  Module[{polygon = Polygon@vertices,
    allPoints = Join[{{0., 0.}}, vertices, {goal}],
    directPath = Line[{{0., 0.}, goal}]},
   paths = If[RegionDisjoint[polygon, directPath],
     {directPath},
     convPoints = MeshCoordinates@ConvexHullMesh@allPoints;
     orderPoints = FindShortestTour[convPoints][[2]];
     goalPosition = Position[orderPoints, 6][[1, 1]];
     Line /@ {convPoints[[;; goalPosition]],
       convPoints[[goalPosition ;;]]}
     ];
   Min[ArcLength /@ paths]
   ];

```

Fortunately it is also works for *any convex polygon* (last test):
> 1 votes

# Answer
# Charcoal, 196 bytes

```
¿∨⊙θ¬∨ι∧›⁰§ηκ‹⁰⁺§ηκ§η⁺²κ¬‹⌈Ｅθ∧ι∕⁺§ηκ∧‹ι⁰§η⁺²κ↔ι⌊Ｅθ∨¬ι∕⁺§ηκ∧›ι⁰§η⁺²κ↔ιＩ₂ΣＸθ²«≔⟦⟧ζＦ²Ｆ⟦⁰§η⁻³ι⟧Ｆ²«Ｆ¬›∧λ§θι§ηι⊞⎇λζυＥ…η²⎇⁼ξιν⁺νκＦ¬‹∧λ§θι⁺§ηι§η⁺²ι⊞⎇λζυＥ…η²⎇⁼ξι⁺ν§η⁺²ι⁺νκ»Ｉ⌊Ｅυ⌊ＥζΣ⁺↔Ｅλ⁻ν§ιξＥ⟦ιＥλ⁻§θξν⟧₂ΣＸν²

```

Try it online! Link is to verbose version of code. Takes as input the target and the rectangle using the bottom left corner and size (note that this differs slightly from the test cases in the question). Explanation:

```
¿∨⊙θ¬∨ι∧›⁰§ηκ‹⁰⁺§ηκ§η⁺²κ¬‹⌈Ｅθ∧ι∕⁺§ηκ∧‹ι⁰§η⁺²κ↔ι⌊Ｅθ∨¬ι∕⁺§ηκ∧›ι⁰§η⁺²κ↔ι

```

Use the Liang-Barksy algorithm to test whether the line intersects the rectangle; the first part of the expression covers the first two steps where the line is parallel to but not between two edges, while the rest calculates the intersections in terms of the parametric equation to see whether the line lies outside the rectangle.

```
Ｉ₂ΣＸθ²

```

If it does not intersect the rectangle then just output the Euclidean distance to the target.

```
«≔⟦⟧ζ

```

Otherwise, separately prepare to collect the corners of the rectangle visible from the origin and the target.

```
Ｆ²Ｆ⟦⁰§η⁻³ι⟧Ｆ²«

```

Loop over the two axes, the length along that axis, and the origin and the target point.

```
Ｆ¬›∧λ§θι§ηι⊞⎇λζυＥ…η²⎇⁼ξιν⁺νκ

```

If the point is to the left or below the rectangle respectively, then collect the corners on that "near" side of the rectangle.

```
Ｆ¬‹∧λ§θι⁺§ηι§η⁺²ι⊞⎇λζυＥ…η²⎇⁼ξι⁺ν§η⁺²ι⁺νκ

```

If the point is to the right or above the rectangle respectively, then collect the corners on that "far" side of the rectangle.

```
»Ｉ⌊Ｅυ⌊ＥζΣ⁺↔Ｅλ⁻ν§ιξＥ⟦ιＥλ⁻§θξν⟧₂ΣＸν²

```

For each pair of points, calculate the Euclidean distance from the origin to the first point, the taxicab distance to the second point, and the Euclidean distance to the target, and output the minimum sum.
> 1 votes

---
Tags: code-golf
---


title: Avoid walking into a rectangle

text:
# Question
Title: Avoid walking into a rectangle
Given a rectangle, a start point, and an end point, find any path from start to finish that avoids the rectangle.

## Example

Suppose you were at \\$(1.5, -1.5)\\$ and you needed to get to \\$(2, 4)\\$. However, there is a rectangle with upper left corner \\$(1, 3)\\$ and bottom right corner \\$(4, 1)\\$ in your way. It would look like this:

There are lots of paths you could take to get from the (green) start to the (red) end:

* You could go via \\$(-3, 3)\\$.
* You could go to \\$(-1.5, -0.5)\\$ and then to \\$(-1, 4)\\$.
* Since you're infinitely thin (having perfected your workout routine), you could go via \\$(4, 1)\\$ and \\$(4, 3)\\$.
* Among many others.

Here's what those three options look like (click for full size):

## Challenge

Given a starting point \\$S\\$, an end point \\$E\\$, and the coordinates for the upper left and bottom right corners of a rectangle (in any format reasonable for your language, including complex numbers if you wish), output a series of points \\$A\_1, A\_2, \ldots, A\_n\\$ of any length such that the piecewise linear path \\$S \rightarrow A\_1 \rightarrow A\_2 \rightarrow \ldots \rightarrow A\_n \rightarrow E\\$ does not intersect the interior of the rectangle. Note that:

* The start point and end point will not be inside the rectangle, nor on the edge or corner of the rectangle.
* Your path may touch the corners and edges of the rectangle, but must not intersect the rectangle's interior.
* You may output nothing, an empty list or similar if you wish to traverse \\$S \rightarrow E\\$ directly.
* You may assume that the rectangle has a strictly positive width and height.
* Your approach need not use the same number of points for all testcases.
* The path may have duplicate points, and may intersect itself, if you so wish.

## Testcases

Here, `(sx,sy)` is the start point, `(ex,ey)` is the end point, `(tlx,tly)` is the top left corner of the rectangle and `(brx,bry)` is the bottom right corner. Note that from the spec we will always have `tlx < brx` and `tly > bry`.

```
Input                                  -> Sample output (one of infinite valid answers)
(sx,sy), (ex,ey), (tlx,tly), (brx,bry) -> ...

(1.5,-1.5), (2,4), (1,3), (4,1)        -> (-3,3)
                                       or (-1.5,0.5),(-1,4)
                                       or (4,1),(4,3)

(-5,0), (5,0), (-1,1), (2,-2)          -> (0,5)
                                       or (-5,1),(5,1)

(0.5,-2), (0.5,1), (2,2), (4,-3)       -> []
                                       or (0.5,-0.5)
                                       or (-1,-0.5)

```

## Scoring

The shortest code in bytes wins.

# Answer
# JavaScript (ES6),  ~~66~~  57 bytes

Expects `(Sx,Sy,Ex,Ey,[Tx,Ty],[Bx,By])`. Returns 3 points.

```
(S,s,E,e,T,B,[x,y]=T)=>[S>x&s<y?B:T,[B[0],y],E>x&e<y?B:T]

```

Try it online!

### Method

The first point is \\$(Bx,By)\\$ if the start point is in the gray area or \\$(Tx,Ty)\\$ otherwise.

The second point is always \\$(Bx,Ty)\\$.

The third point is \\$(Bx,By)\\$ if the end point is in the gray area or \\$(Tx,Ty)\\$ otherwise.
> 14 votes

# Answer
# Python 2, 49 bytes

```
lambda S,E,T,B:[(T*(L<B)+L+T)[::3]for L in S,T,E]

```

Try it online!

**53 bytes**

```
def f(S,E,T,B):
 for L in S,T,E:L[L>B]=T[L>B];print L

```

Try it online!

We make a path out of only horizontal or vertical segments, which means that each step changes one coordinate word-ladder-style.

Our path `S->E` always goes through the rectangle's top left vertex `T`.

```
S
?
T
?
E

```

We go from `S` to `T` via a pit stop that's a hybrid between them, changing either the first or second coordinate of `S` to that of `T`:

```
S0, S1      S0, S1
S0, T1  or  T0, S1
T0, T1      T0, T1

```

That is, we go from `S` to `T` by stepping vertical-then-horizontal or horizontal-then-vertical.

We pick one of them to avoid crossing the rectangle's interior, though in many cases either would work. Changing the first coordinate can only fail if we're directly right of the rectangle, and changing the second can only fail if we're directly above it. We can separate those two cases by checking whether we're left or right of `B`.

We similarly hybridize the end point `E` to connect it to `T`.

In the code, each of the three points S,T,E is hybridized with T and printed. For T, the hybridization leaves it unchanged. The 53-byte version of the code uses list mutation, which necessitates a non-`lambda` function. The 49-byte version above does it with list-slicing trickery `(T*(L<B)+L+T)[::3]`, equivalent to `[L+T,T+L][L<B][::3]`.

**49 bytes**

```
def f(B,*R):
 for L in R:L[L>B]=R[1][L>B];print L

```

Try it online!

Takes inputs in order `B,S,T,E` as two-element lists.
> 12 votes

# Answer
# , ~~86~~ ~~82~~ ~~94~~ ~~81~~ 79 bytes

*Edits: -4 bytes by not outputting the start & end points, and then ~~+12~~ -1 byte to fix bug (see below)*

```
function(p,q,r,s=.5:-1)list(r[1+all(p*s>(z=r[1,]*s)),],r[2:3],r[1+all(q*s>z),])

```

Try it online!

Goes directly from starting point to one of the reachable specified rectangle corners\*. Then goes to any of the non-specified corners (along the edge of the rectangle), and from there to a specified corner (this might or might not be a backtrack), from which it can go directly to the end point.

A slightly-modified version of the program can avoid any detours if the rectangle isn't actually in the way, for 90 bytes.

(\* The bug fix: I initially assumed that the *closest* specified corner was always reachable, but this isn't necessarily the case if the rectangle is very wide & flat, and the starting-point is below it but close to the left-hand end, for instance).
> 10 votes

# Answer
# C 125 bytes

```
z(a,b){printf("%d:%d|",a,b);}d(m,n,p,q,r,s,u,v){(p-m)*(s-n)>(r-m)*(q-n)?z(m,s):z(r,n);(u-m)*(n-s)>(r-m)*(v-s)?z(r,s):z(m,n);}

```

try it online

code explanation

```
z(a,b){printf("%d:%d|",a,b);}   // print routine
d(m,n,p,q,r,s,u,v)              // function take x0 y0 xa ya x1 y1 xb yb
                                // x0 y0  - top left corner of rectangle
                                // xa ya  - start point a
                                // x1 y1  - bottom right corner of rectangle
                                // xa ya  - end point b
{(p-m)*(s-n)>(r-m)*(q-n)?z(m,s):z(r,n);
                                // 1st cross product to decide P1 (see below)
(u-m)*(n-s)>(r-m)*(v-s)?z(r,s):z(m,n);}
                                // 2nd cross product to decide P2 (see below)

```

method

if we go from **a** to **b** below then we can first choose one point on the rectangle that will definitely connect with a without crossing by looking to see which side of the diagonal **a** is on - below we choose **P1**. Similarly, by comparing the position of **b** with the other diagonal we can choose a second point **P2** that will connect with **b** without crossing the rectangle - as indicated in the diagram. Now **P1** and **P2** will always connect without crossing the rectangle and we are done. The list is

> **P1**
>
> **P2**

(note to find which side of the diagonal we are we can use the cross product - if positive one side - if negative the other.)
> 7 votes

# Answer
# Charcoal, 19 bytes

```
ＩＥ⟦θζη⟧Ｅι⎇⁼μ›ιε§ζμλ

```

Try it online! Link is to verbose version of code. I wanted to do this using at most two points but I couldn't come up with an easy way of deciding which direction to jump. I then tried adding a third point, but this quickly simplified into a port of @xnor's algorithm. Takes input as 4 tuples. Explanation:

```
  ⟦θζη⟧             List of points S, T, E
 Ｅ                  Map over list
        ι           Current point
       Ｅ           Map over coordinates
            ›ιε     Is the current point to the right of B
          ⁼μ        If this is the appropriate coordinate
               §ζμ  Take the relevant coordinate from T
                  λ Otherwise keep the coordinate
Ｉ                   Cast to string
                    Implicitly print

```
> 3 votes

# Answer
# Scala, 126 bytes

Modified from @Arnauld's answer.

---

Golfed version. Try it online!

```
type D=Double
type Q=(D,D)
def f(S:D,s:D,E:D,e:D,T:Q,B:Q)={val(x,y)=T;Seq(if(S>x&&s<y)B else T,(B._1,y),if(E>x&&e<y)B else T)}

```

Ungolfed version. Try it online!

```
object Main {
  type D=Double

  def f(S: D, s: D, E: D, e: D, T: (D, D), B: (D, D)): List[(D, D)] = {
    val (x, y) = T

    val first = if (S > x && s < y) B else T
    val second = (B._1, y)
    val third = if (E > x && e < y) B else T

    List(first, second, third)
  }

  def main(args: Array[String]): Unit = {
    println(f(1.5, -1.5, 2, 4, (1, 3), (4, 1)))
    println(f(-5, 0, 5, 0, (-1, 1), (2, -2)))
    println(f(0.5, -2, 0.5, 1, (2, 2), (4, -3)))
  }
}

```
> 0 votes

---
Tags: code-golf, math
---


title: Divinacci Sequence

text:
# Question
Title: Divinacci Sequence
# Divinacci (OEIS)

**Perform the Fibonacci sequence but instead of using:**

```
f(n) = f(n-1)+f(n-2)

```

**Use:**

```
f(n) = sum(divisors(f(n-1))) + sum(divisors(f(n-2)))

```

For an input of `n`, output the nth term, your program should only have 1 input.

---

**First 14 terms (0-indexed, you may 1-index; state which you used):**

```
0  | 0     # Initial               | []
1  | 1     # Initial               | [1] => 1
2  | 1     # [] + [1]              | [1] => 1
3  | 2     # [1] + [1]             | [1,2] => 3
4  | 4     # [1] + [1,2]           | [1,2,4] => 7
5  | 10    # [1,2] + [1,2,4]       | [1,2,5,10] => 18
6  | 25    # [1,2,4] + [1,2,5,10]  | [1,5,25] => 31
7  | 49    # [1,2,5,10] + [1,5,25] | [1,7,49] => 57
8  | 88    # [1,5,25] + [1,7,49]   | [1, 2, 4, 8, 11, 22, 44, 88] => 180
9  | 237   # [1,7,49] + [180]      | [1, 3, 79, 237] => 320
10 | 500   # [180] + [320]         | [1, 2, 4, 5, 10, 20, 25, 50, 100, 125, 250, 500] => 1092
11 | 1412  # [320] + [1092]        | [1, 2, 4, 353, 706, 1412] => 2478
12 | 3570  # [1092] + [2478]       | [1, 2, 3, 5, 6, 7, 10, 14, 15, 17, 21, 30, 34, 35, 42, 51, 70, 85, 102, 105, 119, 170, 210, 238, 255, 357, 510, 595, 714, 1190, 1785, 3570] => 10368
13 | 12846 # [2478] + [10368]      | [1, 2, 3, 6, 2141, 4282, 6423, 12846] => 25704
Etc...

```

*You may choose whether or not to include the leading 0. For those who do: the divisors of `0` are `[]` for the purpose of this challenge.*

It's lowest byte-count wins...

# Answer
> 12 votes
# 05AB1E, 9 bytes

```
XÎFDŠ‚ÑOO

```

Try it online!

**Explanation**

```
XÎ          # initialize stack with 1,0,input
  F         # input times do
   D        # duplicate
    Š       # move down 2 places on the stack
     ‚      # pair the top 2 elements on the stack
      Ñ     # compute divisors of each
       OO   # sum twice

```

# Answer
> 9 votes
## Mathematica, ~~45~~ 40 bytes

```
If[#<3,1,Tr@Divisors@#0[#-i]~Sum~{i,2}]&

```

Mathematica's divisor related functions `Divisors`, `DivisorSum` and `DivisorSigma` are all undefined for **n = 0** (rightly so), so we start from `f(1) = f(2) = 1` and don't support input `0`.

Defining it as an operator instead of using an unnamed function seems to be two bytes longer:

```
±1=±2=1
±n_:=Sum[Tr@Divisors@±(n-i),{i,2}]

```

# Answer
> 6 votes
# Perl 6, 58 bytes

```
{my&d={sum grep $_%%*,1..$_};(0,1,{d($^a)+d $^b}...*)[$_]}

```

Try it online!

# Answer
> 5 votes
# Haskell, 55 bytes

```
f n=sum[a|n>1,k<-f<$>[n-1,n-2],a<-[1..k],mod k a<1]+0^n

```

Try it online!

One-indexed.

# Answer
> 4 votes
# Jelly, ~~10~~ 9 bytes

```
ð,ÆDẎSð¡1

```

Try it online!

Thanks to Dennis for -1.

# Answer
> 4 votes
# Python 3, ~~88~~ ~~83~~ 81 bytes

```
f=lambda n:+(n<3)or g(f(n-1))+g(f(n-2))
g=lambda n,i=1:n>=i and(n%i<1)*i+g(n,i+1)

```

Try it online!

Excludes the `0`

# Answer
> 4 votes
# Python 2, 76 bytes

```
f=lambda n:sum(a for k in[1,2][:n]for a in range(1,3**n-8)if f(n-k)%a<1)or n

```

Try it online!

Ridiculously slow.

# Answer
> 4 votes
# MATL, ~~16~~ 15 bytes

```
Oliq:",yZ\s]+]&

```

This solution uses 0-based indexing.

Try it at MATL Online

**Explanation**

```
O        % Push the number literal 0 to the stack
l        % Push the number literal 1 to the stack
i        % Explicitly grab the input (n)
q        % Subtract 1
:        % Create the array [1...(n - 1)]
"        % For each element in this array...
  ,      % Do the following twice
    y    % Copy the stack element that is 1-deep
    Z\   % Compute the divisors
    s    % Sum the divisors
  ]      % End of do-twice loop
  +      % Add these two numbers together
]        % End of for loop
&        % Display the top stack element

```

# Answer
> 3 votes
# Haskell, ~~64~~ 60 bytes

```
d n=sum[a|a<-[1..n],mod n a<1]
f=0:scanl((.d).(+).d)1f
(!!)f

```

Try it online!

# Answer
> 3 votes
# PHP, 97 bytes

```
for($f=[0,$y=1];++$i<$argn;$x=$y,$y=$r)for($f[]=$r=$v=$n=$x+$y;--$v;)$n%$v?:$r+=$v;echo$f[$argn];

```

Try it online!

# PHP, 101 bytes

```
for($f=$d=[0,1];$i<$argn;$d[]=$r)for($f[]=$r=$v=$n=$d[$i]+$d[++$i];--$v;)$n%$v?:$r+=$v;echo$f[$argn];

```

Try it online!

# Answer
> 3 votes
# Pari/GP, 39 bytes

```
f(n)=if(n<3,1,sum(i=1,2,sigma(f(n-i))))

```

Based on Martin Ender's Mathematica answer.

Try it online!

# Answer
> 2 votes
# R, 81 bytes

```
f=function(n,a=1,b=1,d=numbers::divisors)`if`(n-1,f(n-1,b,sum(d(a))+sum(d(b))),a)

```

1-indexed, and excludes the 0 at the start of the sequence. That zero gave me a lot of trouble to implement, because the builtin `numbers::divisors` doesnt handle it well.

The rest is a modified version of the standard recursive function that implements the fibonacci sequence.

```
> f(1)
[1] 1
> f(2)
[1] 1
> f(3)
[1] 2
> f(5)
[1] 10
> f(13)
[1] 12846

```

# Answer
> 2 votes
# Vyxal, 9 bytes

```
1{~"vKf∑…

```

Try it Online!

Prints the sequence forever.

```
1         # Push 1
 {        # Forever...
  ~"      # Grab top two elements, without popping
    vK    # Get divisors of each
      f∑  # Deep sum
        … # Print that without popping

```

# Answer
> 2 votes
# Julia, <sup>~~47~~</sup> 44 bytes

```
~n=(n.%(r=1:n).<1)'r
!N=N<3||~!(N-1)+~!(N-2)
```

Attempt This Online!

-3 bytes thanks to Czylabson Asa. (I forgot how `a'*b` worked)

# Answer
> 1 votes
# Husk, 11 bytes

```
!¡ȯΣṁḊ↑_2ŀ2

```

Try it online!

## Explanation

```
!¡ȯΣṁḊ↑_2ŀ2
         ŀ2 array [0,1]
 ¡          iterate on the array, expanding it:
  ȯ         using the following 4 functions:
      ↑_2   get last 2 elements
    ṁḊ      get divisors of both
   Σ        sum them
!           Get element at index n

```

# Answer
> 1 votes
# Factor \+ `math.primes.factors math.unicode`, 53 bytes

```
[ 0 1 rot [ tuck [ divisors Σ ] bi@ + ] times drop ]

```

Try it online!

0-indexed.

# Answer
> 1 votes
# C (gcc), 93 87 86 bytes

```
f(n){return n<2?n:s(f(n-1))+s(f(n-2));}s(n,c,i){for(c=i=0;n/++i;)c+=n%i?0:i;return c;}

```

Try it online!

A simple recursive solution that finds divisors by brute force.

Thanks to @ceilingcat for -6 bytes on the for loop and -1 on some superfluous parens.

# Answer
> 1 votes
# Burlesque, 23 bytes

```
0 1 2{fc++jfc++.+}C~j!!

```

Try it online!

```
0 1   # Initial
2     # Keep top 2 stack elements
{
 fc++ # Factors, Sum
 j    # Swap stack
 fc++ # Factors, Sum
 .+   # Sum
}C~   # Continue forever
j!!   # Get input element

```

# Answer
> 1 votes
# 05AB1E, 7 bytes

```
1λè‚Ñ˜O

```

Outputs the 1-based \\$n^{th}\\$ value.

Try it online.

With some small modifications, we could output:

* **7 bytes:** The first 1-based \\$n\\$ values by replacing `è` with `£`: try it online.
* **5 bytes:** The infinite 1-based sequence by removing the `1` and `è`: try it online.
* Or with 0-based sequence by adding `Ý` after the `1`:

So with default sequence rules, this could have been 5 bytes.

**Explanation:**

```
 λ       # Start a recursive environment,
  è      # to output the a(input)'th value
         # (which is output implicitly at the end)
1        # Starting at a(0)=1
         # And where every following a(n) is calculated as:
   ‚     #  Pair the (implicit) previous two terms together: [a(n-2),a(n-1)]
         #  (a(n-2) is unknown in the first iteration, so will default to 0)
    Ñ    #  Get the divisors of both inner values
     ˜   #  Flatten this list of lists of integers
      O  #  Sum them together

```

**Explanation of the 5-bytes infinite 1-based sequence:**

```
λ        # Start a recursive environment,
         # to output the infinite sequence
         # (which is output implicitly at the end)
         # Implicitly starting at a(0)=1
         # And where every following a(n) is calculated as:
 ‚Ñ˜O    #  See above

```

# Answer
> 1 votes
# Scala, 123 bytes

Golfed version. Attempt it online!

```
def f(n:Int):Int=if(n<3)1 else{def g(n:Int,i:Int=1):Int=if(n>=i)if(n%i<1)i+g(n,i+1)else g(n,i+1)else 0;g(f(n-1))+g(f(n-2))}

```

Ungolfed version. Attempt it online!

```
object Main {
  def main(args: Array[String]): Unit = {
    val sequence = (1 to 10).map(f).toList
    println(sequence)
  }

  def f(n: Int): Int = {
    if (n < 3) 1
    else g(f(n - 1)) + g(f(n - 2))
  }

  def g(n: Int, i: Int = 1): Int = {
    if (n >= i) {
      if (n % i < 1) i + g(n, i + 1)
      else g(n, i + 1)
    } else 0
  }
}

```

# Answer
> 1 votes
# Japt, 11 bytes

Starts with `0` and outputs the `n`th term, zero-indexed. Replace `g` with `h` to output the first `n` terms instead.

```
@Zo2 câ x}g

```

Try it

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


title: Calculate Bloons RBE

text:
# Question
Title: Calculate Bloons RBE
In Bloons Tower Defense 6, the strength of different bloons can be measured by their Red Bloon Equivalent (RBE), or the number of single pops it takes to completely defeat the bloon.

The RBE for the bloon types are as follows (sourced from the wiki)

| Bloon | RBE |
| --- | --- |
| red | 1 |
| blue | 2 |
| green | 3 |
| yellow | 4 |
| pink | 5 |
| black | 11 |
| white | 11 |
| purple | 11 |
| lead | 23 |
| zebra | 23 |
| rainbow | 47 |
| ceramic | 104 |
| moab | 616 |
| bfb | 3164 |
| zomg | 16656 |
| ddt | 816 |
| bad | 55760 |

## The Challenge

Given a run-length encoded list of bloon types, **calculate the total RBE.** More specifically, find the RBE of each bloon type according to the table, multiply by the given count, and sum them all.

### Notes

* Input can be taken in any reasonable format (comma-separated string, list of tuples, etc.)
* You must output a single integer
* Assume that input will never be invalid
* Bloon types must be given *exactly* as shown in the table above, in lowercase
* This is , so the lowest score in bytes wins!

## Test Cases

```
Input: 1 red
Output: 1

Input: 7 green
Output: 21

Input: 5 bfb, 11 moab
Output: 22596

Input: 1 red, 2 yellow, 3 white, 4 zebra, 5 moab, 6 ddt
Output: 8110

Input: 1 moab, 1 bfb, 1 zomg, 1 ddt, 1 bad, 1 red, 1 blue, 1 green, 1 yellow, 1 pink, 1 black, 1 white, 1 purple, 1 lead, 1 zebra, 1 rainbow, 1 ceramic
Output: 77257

```

# Answer
# JavaScript (ES6), 111 bytes

Expects a list of `[count, bloon]` pairs.

```
a=>a.reduce((t,[k,s])=>t+k*[23,3,104,616,3164,1,16656,4,47,23,816,55760,5,11,2][parseInt(s,36)*53%437%44%15],0)

```

Try it online!

### How?

The hash function was found by brute force:

```
parseInt(s, 36) * 53 % 437 % 44 % 15

```

It's a bit long but almost perfect:

* all slots from 0 to 14 are used
* *black*, *white* and *purple* (all scoring 11) gracefully collide on the same slot
* however, two distinct slots are used for *lead* and *zebra* (both scoring 23)

Below is a summary table sorted by final lookup index:

```
 string    | parseInt()  |      * 53     | mod 437 | mod 44 | mod 15 | value
-----------+-------------+---------------+---------+--------+--------+-------
 "lead"    |      998293 |      52909529 |   191   |   15   |    0   |    23
 "green"   |    28152239 |    1492068667 |   339   |   31   |    1   |     3
 "ceramic" | 27013759860 | 1431729272580 |   134   |    2   |    2   |   104
 "moab"    |     1057907 |      56069071 |   223   |    3   |    3   |   616
 "bfb"     |       14807 |        784771 |   356   |    4   |    4   |  3164
 "red"     |       35509 |       1881977 |   255   |   35   |    5   |     1
 "zomg"    |     1664872 |      88238216 |    50   |    6   |    6   | 16656
 "yellow"  |  2080372496 |  110259742288 |    37   |   37   |    7   |     4
 "rainbow" | 59409106160 | 3148682626480 |   243   |   23   |    8   |    47
 "zebra"   |    59454982 |    3151114046 |   127   |   39   |    9   |    23
 "ddt"     |       17345 |        919285 |   274   |   10   |   10   |   816
 "bad"     |       14629 |        775337 |    99   |   11   |   11   | 55760
 "pink"    |     1190576 |      63100528 |   350   |   42   |   12   |     5
 "black"   |    19468964 |    1031855092 |   204   |   28   |   13   |    11
 "white"   |    54565250 |    2891958250 |   189   |   13   |   13   |    11
 "purple"  |  1563335762 |   82856795386 |   336   |   28   |   13   |    11
 "blue"    |      541526 |      28700878 |    29   |   29   |   14   |     2

```
> 8 votes

# Answer
# Python 3.9, 104 + 17 = 121 bytes

```
lambda l:sum([47,11,3164,616,16656,4,1,5,23,104,11,23,3,2,11,816,55760][hash(a*9828)%17]*b for a,b in l)

```

You also need to set an environment variable (I included it in the byte count).

```
PYTHONHASHSEED=65

```

Input is a list of tuples of the form `(name, amount)`
> 4 votes

# Answer
# Jelly, 47 bytes

```
ḋɓ“µCḅṃ’,14ḥⱮị⁽%xBŻ€ṁ@“£t¢Bƈ/¦£¤Bh¥ç¤¿€ƥṣ½‘¤ḅØ⁵

```

A dyadic Link that accepts the frequencies on the left and the respective bloons on the right and yields the total RBE.

**Try it online!**

### How?

```
ḋɓ“...’,14ḥⱮị⁽%xBŻ€ṁ@“...‘¤ḅØ⁵ - Link: frequencies, bloons
           Ɱ                   - map across the bloons applying:
          ḥ                    -   hash...
  “...’                        -   ...with salt: 160553470
       ,14                     -   ...and values: [1,2,...,14]
                          ¤    - nilad followed by link(s) as a nilad
             ⁽%x               -   10371
                B              -   convert to binary -> [1,0,1,0,0,0,1,0,0,0,0,0,1,1]
                 Ż€            -   zero range each -> [[0,1],[0],[0,1],[0],[0],[0],[0,1],[0],[0],[0],[0],[0],[0,1],[0,1]]
                     “...‘     -   code-page indices = [2,116,1,66,156,47,5,2,3,66,104,4,23,3,11,12,164,223,10]
                   ṁ@          -   mould -> [[2,116],[1],[66,156],[47],[5],[2],[3,66],[104],[4],[23],[3],[11],[12,164],[223,10]]
            ị                  - (hashed bloons) index into (that)
                            Ø⁵ - 250
                           ḅ   - convert from base (250) -> bloon RBEs
 ɓ                             - dyadic chain:
ḋ                              -   (frequencies) dot-product (bloon RBEs)

```
> 3 votes

# Answer
# Excel, 203 bytes

```
=LET(
    a,TEXTSPLIT(A1," ",","),
    SUM(LOOKUP(TAKE(a,,-1),
    {"b","bf","bla","blu","c","d","g","l","m","p","pu","r","re","w","y","z","zo"},
    {55760,3164,11,2,104,816,3,23,616,5,11,47,1,11,4,23,16656})*TAKE(a,,1))
)

```

Input is comma-separated string, e.g. `1 red, 2 yellow, 3 white, 4 zebra, 5 moab, 6 ddt`, in cell `A1`.
> 1 votes

# Answer
# C (gcc), 200 bytes

Takes an array of strings and its length as input.

```
f(s,n,c,t)char**s;{int L[]={47,23,55760,4,0,0,0,0,0,816,2,0,0,0,0,0,3,0,0,5,3164,0,0,0,616,16656,1,0,11,23,0,104};for(t=0;n--;t+=c*L[((**s*2[*s++]*7711)>>15)&31])for(c=atoi(*s);*(*s)++-32;);return t;}

```

Try it online!
> 1 votes

# Answer
# Swift 2.2, 128 bytes

```
{$0.reduce(0){$0+$1.1*[0,16656,3164,0,5,616,3,0,0,11,1,816,0,23,0,0,23,0,55760,11,104,2,4,0,0,47][($1.0.hashValue>>8&63^6)%26]}}

```

Try it on SwiftFiddle!

Takes a dictionary, e.g. `["red": 3, "blue": 7]`.

It turns out that after some bit twiddling, each bloon type has a unique\* hashValue mod 26. So far I haven't found a way to get the modulus any lower. Since Swift 3, hash values differ between runs of the same program, so this strategy is no longer viable.

\*"white" and "black" map to the same value, but they also have the same RBE, so it works out.
> 1 votes

# Answer
# Charcoal, 86 bytes

```
ＩΣＥ⪪Ｓ, ΠＩＥ⪪ι ⎇μ§⪪”)¶⊟S|4ηJ?α8⊕rüQG§﹪⊗βⅉ№8℅jo”9⌕⪪”&⌈⊟²…x⦃P⦄h¿◨Ｔ-α～⁶？Ｔ÷`´Cgψ↥b·CQq”³…λ³λ

```

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

```
    Ｓ                               Input string
   ⪪ ,                              Split on literal string `, `
  Ｅ                                 Map over substrings
           ι                        Current substring
          ⪪                         Split on literal string ` `
         Ｅ                          Map over words
             ⎇μ                     If second word then
                         ”...”      Compressed lookup table
                        ⪪     ³     Split into substrings of length `3`
                       ⌕            Find index of
                                λ   Second word
                               …    Truncated to length
                                 ³  Literal integer `3`
               §                    Index into
                 ”...”              Compressed lookup table
                ⪪     9             Split on literal string `9`
                                  λ Otherwise first word
        Ｉ                           Cast to integer
       Π                            Take the product
 Σ                                  Take the sum
Ｉ                                   Cast to string
                                    Implicitly print

```

77 bytes using the newer version of Charcoal on ATO by taking the input as a dictionary:

```
ＩΣＥＡ×ιＩ§⪪”)¶⊟S|4ηJ?α8⊕rüQG§﹪⊗βⅉ№8℅jo”9⌕⪪”&⌈⊟²…x⦃P⦄h¿◨Ｔ-α～⁶？Ｔ÷\`´Cgψ↥b·CQq”³…κ³

```

Attempt This Online! Link is to verbose version of code.
> 1 votes

# Answer
# Retina, 146 bytes

```
.+ed
*
.+ue
*2*
.+en
*3*
.+y
*4*
.+nk
*5*
.+[khp]
*11*
.+e[ab]
*23*
.+n
*47*
.+c
*104*
.+ab
*616*
.+f
*3164*
.+g
*16656*
.+dt
*816*
.+ad
*55760*
_

```

Try it online! Takes input on separate lines but link is to test suite splits on `,`  for convenience. Explanation: Each stage matches a colour of balloon to multiply its quantity appropriately. The shortest possible unique remaining substring is used at each point, with preference being given to the rightmost such substrings as this will be deleted and therefore can be ignored when matching subsequent substrings. In this way for instance `.+nk` matches and deletes the whole of `pink` allowing `.+[khp]` to only match `black`, `white` and `purple`. The final `_` then calculates the total RBE which is converted back to decimal.
> 1 votes

# Answer
# 05AB1E, 81 bytes

```
ø`.•4в#‡fÕçòÖ¹<÷E¤E%ÝÙ/J“Å;>Íslζ₂θ…•3ôs3δ£k•Ì¥δвιλùEmæâåÇÛZ•₄в•Cƒ2œÝù•3äÁ«.¥>sè*O

```

I suck at finding magic numbers, so this will have to do for now.. Replacing `.•4в#‡fÕçòÖ¹<÷E¤E%ÝÙ/J“Å;>Íslζ₂θ…•3ô3δ£k` with `C`, optional `Ø`, and some modulos will probably save some bytes.

Try it online or verify all test cases.

**Explanation:**

```
ø                     # Zip/transpose the (implicit) input-list
 `                    # Pop and push the list of Bloons and list of counts separated to the stack
.•4в#‡fÕçòÖ¹<÷E¤E%ÝÙ/J“Å;>Íslζ₂θ…•
                      # Push compressed string "redblugreyelpinblawhipurleazebraicermoaddtbfbzombad"
  3ô                  # Split it into parts of size 3
    s                 # Swap so the input-list of Bloons is at the top
      δ               # Map over each Bloon:
     3 £              #  Leave just its first 3 characters
        k             # Get the index of each in the list of strings
•Ì¥δвιλùEmæâåÇÛZ•     # Push compressed integer 1001001001006000000012000024057512200
  ₄в                  # Convert it to base-1000 as list:
                      #  [1,1,1,1,6,0,0,12,0,24,57,512,200]
    •Cƒ2œÝù•          # Push compressed integer 13492391042348
            3ä        # Split it into 3 equal-sized parts: [13492,39104,2348]
              Á       # Rotate it once: [2348,13492,39104]
               «      # Merge the two lists together
                .¥    # Undelta it with leading 0: [0,1,2,3,4,10,10,10,22,22,46,103,615,815,3163,16655,55759]
                  >   # Increase each by 1
                   sè # Index the earlier indices into this list
*                     # Multiply each value by its count
 O                    # Sum this list together
                      # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (sections *How to compress strings not part of the dictionary?*, *How to compress large integers?*, and *How to compress integer lists?*) to understand why `.•4в#‡fÕçòÖ¹<÷E¤E%ÝÙ/J“Å;>Íslζ₂θ…•` is `"redblugreyelpinblawhipurleazebraicermoaddtbfbzombad"`; `•Ì¥δвιλùEmæâåÇÛZ•` is `1001001001006000000012000024057512200`; `•Ì¥δвιλùEmæâåÇÛZ•₄в` is `[1,1,1,1,6,0,0,12,0,24,57,512,200]`; and `•Cƒ2œÝù•` is `13492391042348`.
> 1 votes

# Answer
# Scala, 162 bytes

Try it online!

```
val f:Seq[(Int,String)]=>Int=data=>data.foldLeft(0){case(t,(k,s))=>t+k*Seq(23,3,104,616,3164,1,16656,4,47,23,816,55760,5,11,2)((BigInt(s,36)*53%437%44%15).toInt)}

```
> 0 votes

# Answer
# Pyth, 61 bytes

```
sm*@[616C\/5 816J2K11ZKy8328hZ23KZZ3y52Z3164yJ55760)%Ced8027h

```

Try it online!

Takes input as a list of lists. The lookup portion could probably be compressed some more but who knows.

### Explanation

```
sm*@[...)%Ced8027hdQ    # implicitly add dQ
                        # implicitly assign Q = eval(input())
s                       # sum of
 m                 Q    # map lambda d over Q
  *              hd     #   multiply the first element of d by
           ed           #   the last element of d
          C             #   converted to int using base 256 and code points
         %   8027       #   modulo 8027
   @[...)               #   modularly indexed into the lookup table

```
> 0 votes

# Answer
# C#, 123 bytes

```
x=>x.Sum(y=>new[]{616,1,4,0,5,47,3164,104,16656,816,3,23,0,11,55760,2}[y.Key.Aggregate(0,(a,n)=>3*a+n)*75%1847%16]*y.Value)

```

Try it online!

Pretty similar to the existing JavaScript answer. I brute-forced another hash function:

```
y.Key.Aggregate(0,(a,n)=>3*a+n)*75%1847%16

```

C# has no built-in way to parse base 36 numbers (which the JavaScript answer uses), so I had to use `Aggregate` to get a unique int for each string which worked here (`GetHashCode` returns different values between program executions for strings so can't be used).

```
string  | aggregate |*75%1847%16
--------------------------------
red     |   1429    |     1
blue    |   4070    |     15
green   |   12743   |     10
yellow  |   41924   |     2
pink    |   4406    |     4
purple  |   41204   |     13
black   |   12131   |     13
white   |   13841   |     13
zebra   |   13930   |     11
lead    |   4216    |     11
rainbow |   119486  |     5
ceramic |   109962  |     7
moab    |   4331    |     0
bfb     |   1286    |     6
zomg    |   4723    |     8
ddt     |   1316    |     9
bad     |   1273    |     14

```
> 0 votes

---
Tags: code-golf, game, parsing
---


title: Gödel encoding - Part II (decoding)

text:
# Question
Title: Gödel encoding - Part II (decoding)
Part I

Previous part was considered encoding of non-empty nested lists with a positive integer.

Reminding the coding procedure \\$G(x)\\$:

1. If \\$x\\$ is a number, \\$G(x) = 2^x\\$
2. If \\$x\\$ is a list \\$\[n\_0, n\_1, n\_2, n\_3, …\]\\$, \\$G(x) = 3^{G(n\_0)} \cdot 5^{G(n\_1)} \cdot 7^{G(n\_2)} \cdot 11^{G(n\_3)} \cdot...\\$
Bases are *consecutive primes*.

The number *will be unique* (it can be proved, but you don’t have to do it). So always there is *valid reverse procedure*: determine an array-structure from a given number, or verify that no structure exists for that number. This is the task of this challenge.

### Input

Positive integer (possibly very large)
**UPD**
I know that in CG does not approve strict validation of input.
But here *invalid in general* number means: negative, float, with typo etc.
You don’t have to check it out!
But figuring out if a number is *valid encoding* or not is part of the challenge.

### Output **UPD**

*Very sorry I missed the important thing ((*
Single number (if it is suitable for the first part of the procedure, see test cases)
or
non-empty list of non-negative integers (possibly nested, without empty sub-lists) that is encoded with given number; printed in any appropriate form: as pure array, string, json etc.
*OR*
any appropriate message (`[ ], None, -1` etc), if there is no decoding for this number.

### Test cases

```
1 → 0
2 → 1
3 → [0]
4 → 2
5 → None
6 → None
7 → None
8 → 3
9 → [1]
10 → None
666 → None
729 → None
1024 → 10
1215 → None
3375 → [[0], [0]]
77777 → None
5859375 → [0, [1]]
666777666 → None
2210236875 → [3, 2, 1, 0]
7625597484987 → [[[0]]]
1111111111111111111111111111 → None

```

# Answer
# JavaScript (ES6), 167 bytes

Expects a Bigint. Returns `-1` if the encoding is invalid.

This is probably longer than it should, but validating the encoding is costly (see below).

```
n=>(e=h=(n,F=n>1&&n%2n?(n,k=3n,i=0n)=>n%k?i?[h(i),...k>n?[]:F(n,-~k)]:(g=d=>k%--d?g(d):e|=d<2)(k)?[]:F(n,-~k):F(n/k,k,-~i):n=>n%2n?e|=n>1:-~F(n/2n))=>o=F(n))(n)&&-e||o

```

Try it online!

### 111 bytes (for information only)

A large part of the code is dedicated to Gödel encoding validation. If we assume that the input is a valid encoding, then several sanity checks can be removed and we don't even have to include a primality test:

```
f=(n,F=n>1&&n%2n?(n,k=3n,i=0n)=>n%k?[...i?[f(i)]:[],...k>n?[]:F(n,-~k)]:F(n/k,k,-~i):n=>n%2n?0:-~F(n/2n))=>F(n)

```

Try it online!
> 7 votes

# Answer
# , ~~168~~ ~~149~~ ~~132~~ ~~117~~ 116 bytes

*Edits: -9 and -1 bytes thanks to pajonk (re-defining `if` as `[`, now no longer needed, and then function as ``~``), -7 bytes by switching to `\` instead of `function`, and -35 more bytes by re-arranging.*

```
`~`=\(x,p=2,y=0)`if`(!x%%p,`~`(x/p,p,y+1),`if`(p==2&x<2,y,c(if(sum(!p%%1:p)<3&p>2|y)list(~y[!y|p>2]),if(x>1)x~p+1)))

```

Attempt This Online!

Outputs the number or list whose Gödel encoding is the input. Errors if no such number/list exists.

**Ungolfed code:**

```
D=function(x,p=2,y=0){
    if(!x%%p)D(x/p,p,y+1) else
    if(p==2&x<2)y else
    c(if(is_prime(p)&p>2|y)list(D(y*(!y|p>2))),if(x>1)D(x,p+1))
}
is_prime=function(x)sum(!x%%1:x)<3

```
> 6 votes

# Answer
# Vyxal, 20 bytes

```
λ1>[∆Ǐḣvx₌∨∧ßu›:A∧]‹

```

Try it Online!

Returns `-1` for invalid inputs. Times out on the last test case.
> 4 votes

# Answer
# PARI/GP, 101 bytes

```
n->iferr(g(n),e,x)
g(n)=if(n==2^q=logint(n,2),q,primes(1+#t=factor(n)~)[^1]-t[1,],0/0,apply(g,t[2,]))

```

Attempt This Online!

Returns `x` for invalid inputs.
> 3 votes

# Answer
# Jelly, 17 bytes

```
ȯ6ÆEsß€Ḣ?ḢḊ?0
ÇŒṘ

```

A full-program that accepts a positive integer and either:

* prints the decoded value and exits with a code of `0`; or
* prints nothing to STDOUT and exits with a code of `1` (printing a traceback to STDERR).

**Try it online!** Or see the test-suite (in Zsh to catch the exit code).

### How?

```
ȯ6ÆEsß€Ḣ?ḢḊ?0 - Helper Link: positive integer, N
ȯ6            - logical OR with 6 (when N=0 use 6 - this is so that recursive calls
                                   handle zeros in the ÆE result in a way that will
                                   produce the error we want)
  ÆE          - prime factorisation list (e.g. 56=2*2*2*7 -> [3,0,0,1])
           ?  - if...
          Ḋ   - ...condition: dequeue (i.e. is of length 2 or more)
        ?     - ...then: if...
       Ḣ      -          ...condition: remove and yield the head (exponent of 2)
    s       0 -          ...then (i.e. non-zero): split into chunks of length zero
                                                  (this will error out)
      €       -          ...else: for each (of the rest of the exponents):
     ß        -                     call this Link with that number
         Ḣ    - ...else: head (i.e. yield the power of two that N is)

ÇŒṘ - Main Link: positive integer, N
Ç   - call the helper Link, above
 ŒṘ - print a Python representation of the result

```
> 2 votes

# Answer
# Charcoal, 100 bytes

```
⊞υ⟦Ｘ³Ｎ⟧Ｆυ«≔⊟ιθ¿﹪θ²«≔²η≔⟦⟧ζＷ⊖θ¿﹪θη«≦⊕η¿⬤…²η﹪ηλ⊞ζ⁰»«⊞ζ⊕⊟ζ≧÷ηθ»Ｆζ¿∧κ¬＆⊖κκ⊞ι⊖Ｌ↨κ²«≔⟦κ⟧κ⊞ικ⊞υκ»»⊟ι»⭆¹⊟§υ⁰

```

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

```
⊞υ⟦Ｘ³Ｎ⟧

```

The main loop only works on lists of odd numbers, so fake it out by starting with a list of `3ⁿ`.

```
Ｆυ«

```

Loop over the input and any sublists that may be generated while processing it.

```
≔⊟ιθ

```

Get the value to turn into a list.

```
¿﹪θ²«

```

If it's odd, then:

```
≔²η≔⟦⟧ζ

```

Start finding prime factor multiplicities.

```
Ｗ⊖θ

```

Repeat until the all the factors have been found.

```
¿﹪θη«

```

If the current prime is not a factor, then:

```
≦⊕η

```

Try the next integer.

```
¿⬤…²η﹪ηλ

```

If this is a prime, then...

```
⊞ζ⁰

```

... start counting its multiplicity.

```
»«

```

Otherwise:

```
⊞ζ⊕⊟ζ

```

Increment the multiplicity.

```
≧÷ηθ

```

Divide the value by the prime.

```
»Ｆζ

```

Loop over the multiplicities.

```
¿∧κ¬＆⊖κκ

```

If this is a power of `2`, then...

```
⊞ι⊖Ｌ↨κ²«

```

... push its logarithm to the list, otherwise:

```
≔⟦κ⟧κ⊞ικ⊞υκ

```

... push the wrapped value to both the list and also the list of sublists to be processed.

```
»»⊟ι

```

Otherwise, crash the program, because the input is invalid.

```
»⭆¹⊟§υ⁰

```

Output the final value.

Since the above program has to find the logarithm to base `3` of `3ⁿ` the slow way, here's a slightly less slow 112 byte version which special-cases inputs of powers of `2` to avoid this:

```
Ｎθ¿＆θ⊖θ«⊞υ⟦θ⟧Ｆυ«≔⊟ιθ¿﹪θ²«≔²η≔⟦⟧ζＷ⊖θ¿﹪θη«≦⊕η¿⬤…²η﹪ηλ⊞ζ⁰»«⊞ζ⊕⊟ζ≧÷ηθ»Ｆζ¿∧κ¬＆⊖κκ⊞ι⊖Ｌ↨κ²«≔⟦κ⟧κ⊞ικ⊞υκ»»⊟ι»⭆¹§υ⁰»Ｉ⊖Ｌ↨θ²

```

Try it online! Link is to verbose version of code.
> 1 votes

# Answer
# Pyth, 32 bytes

```
L?sIlbslbCWneJCr8Pb.fP_ZleJ3yMhJ

```

Try it online!

Defines a decoding function `y(b)` which returns the decoded list or throws a TypeError if the input is invalid.

### Explanation

```
L                                   # define y(b)
 ?                                  # if
    lb                              # log base 2 of b
  sI                                # is an integer:
      slb                           #   return int(log(b))
                                    # otherwise
             J                      # assign J to
                 Pb                 #   the list of prime factors of b
               r8                   #   length encoded
              C                     #   and transposed
          W                         # if
            eJ                      # the last element of J
           n                        # is not equal to
                   .fP_ZleJ3        # the first length(eJ) primes (starting at 3):
         C                          #   apply transposition (this will result in a TypeError)
                                    # otherwise
                            yM      # apply y to every element of
                              hJ    # the first element of J

```
> 1 votes

---
Tags: code-golf, number, primes, encoding, ragged-list
---