# Question
Title: Output a random value from the last 16 values outputted
Output the numbers 1-16 (or any other set of 16 distinct items). Then, repeatedly, output a random value chosen uniformly from the last 16 items outputted.

After the same item is printed 16 times in a row, halt.

If a number appears multiple times in the last 16 values, it should have proportionally more chance to be chosen as the next number. If a number did *not* appear in the last 16 elements, it can't be chosen ever again.

0 bonus points to whoever can provide the probability distribution of each number becoming the last one standing.

# Answer
> 10 votes
# Python, ~~102 88 86 85~~ 84 bytes

```
from random import*;*t,=range(16)
while~-len({*(x:=t[-16:])}):t+=choice(x),
print(t)

```

Attempt This Online!

* -14 thanks to mousetail
* -1 thanks to loopy walt

Prints a list of numbers from 0 to 15.

#### Commented

```
from random import*;     # Import the random module for later
*t,=range(16)            # Set t equal to [0, 1, ..., 15]
                         # ([* ... ] unpacks it into a list)
while~-len(              # Loop while the number of unique items
      {*(x:=t[-16:])}):  # in the last 16 elements of t is not 1
                         # (setting x to the last 16 elements of t)
    t+=choice(x),        # Append a random element of x to t
print(t)                 # At the end, output t

```

# Answer
> 10 votes
# Ruby, ~~55 51~~ 48 bytes

```
puts x=[*1..16];_,*x=x<<p(x.sample)while(x|x)[1]

```

Try it online!

# Answer
> 8 votes
# Vyxal, ~~15~~ ~~13~~ ~~12~~ 9 bytes

```
k6≬℅+Ḣ↔ƒ⋎

```

Try it Online! Outputs characters from the string `"0123456789abcdef"`

*-3 thanks to emanresu*

## Explained (old)

```
k6≬℅+Ḣ↔ḣvt∑+
k6           # The string "0123456789abcdef"
  ≬   ↔      # apply the following and collect results while invariant:
   ℅+        #  append a random item of the string to the string
     Ḣ       #  remove the first character
       ḣvt   # separate the first item from that list and get the tail of each remaining item
          ∑+ # join that into a single string and append to the previously separated head

```

# Answer
> 8 votes
# , ~~66~~ 61 bytes

```
x=Map(show,L<-1:16)
while(sd(L))L=c(L[-1],print(sample(L,1)))

```

Try it online!

### Explanation outline:

1. `Map` the `show` function over `1:16` (and save the vector to variable `L`).
2. We assign the result of the `Map` to `x` to avoid outputting its value (ugly list of nulls).
3. Then we `sample` one element from `L` and append to `L[-1]` (`L` without the first element).
4. Loop until `sd(L)==0` (this means that the last 16 numbers are all the same).

# Answer
> 8 votes
# JavaScript (ES7), 74 bytes

Same algorithm as the other version, but using the weirder set `"5368709124,false"`.

```
f=(s=2**29+[4,k=!1])=>/(.)\1{15}/.test(s)?s:f(s+s[Math.random()*16+k++|0])

```

Try it online!

### How?

\\$2^{29}=536870912\\$ contains all digits from \\$0\\$ to \\$9\\$ exactly once, except \\$4\\$. Adding `[4,!1]` forces a coercion to a string and appends `"4"`, followed by a comma, followed by `"false"`.

---

# JavaScript (ES6), 83 bytes

Uses the hexadecimal characters `0-9` and `A-F`.

```
f=(s=(k=0)+'123456789ABCDEF')=>/(.)\1{15}/.test(s)?s:f(s+s[Math.random()*16+k++|0])

```

Try it online!

### Commented

```
f = (                 // f is a recursive function taking:
  s = (k = 0) +       //   s = output string
    '123456789ABCDEF' //   k = counter
) =>                  //
/(.)\1{15}/.test(s)   // if s contains the same character repeated
?                     // 16 times in a row:
  s                   //   stop and return s
:                     // else:
  f(                  //   do a recursive call:
    s +               //     append to s
    s[                //     the character from s
      Math.random()   //     whose index is randomly chosen in
      * 16 + k++ | 0  //     [k .. k+15] (increment k afterwards)
    ]                 //     i.e. one of the last 16 characters
  )                   //   end of recursive call

```

# Answer
> 8 votes
# , 52 bytes

```
a=b=16:1;while(sd(a[b]))a=c(sample(a[b],1),a);rev(a)

```

Try it online!

Full program that yields an  vector containing the sequence of values.
displays this by default with index numbers (in square brackets) at the start of each line. If this is annoying, add 5 bytes more to wrap the output into a call to `cat()` like this.

# Answer
> 7 votes
# Brachylog, 18 bytes

```
15⟦ẉ₂ᵐ{=|ṛRẉ&b,R↰}

```

Try it online!

```
15⟦                  The list [0, …, 15]
   ẉ₂ᵐ               Map writeln
      {           }  If
       =               All elements of the list are equal, then stop
        |            Else
         ṛR            R is a random element of the list
          Rẉ           writeln R
            &b         Remove the first element of the list
              ,R       Append R to the list
                ↰      Recursive call on this list

```

# Answer
> 6 votes
# C (gcc), 105 bytes

```
j,k;a[16];f(i){for(k=i=16;a[--i]=i;);for(;k;j-(a[i++%16]=a[rand()%16])?k=16:--k)printf("%d ",j=a[i%16]);}

```

Try it online!

# Answer
> 6 votes
# Japt, ~~20~~ 19 bytes

Far too long but seeing as Japt has no infinite loops and can't loop until invariant, it'll have to do for now.

```
Go
@òÎÌÊ¨G}a@pUsX ö

```

Test it

```
Go\n@òÎÌÊ¨G}a@pUsX ö
G                        :16
 o                       :Range [0,G)
  \n                     :Assign to variable U
    @                    :Left function
     ò                   :  Partition U between elements where
      Î                  :    Sign of difference is truthy (non-zero)
       Ì                 :  Last element
        Ê                :  Length
         ¨G              :  >=16
           }             :End function
            a            :Run right function until left function returns true and return final result
             @           :Right function, taking 0-based iteration index X as argument
              p          :  Push to U
               UsX       :    Slice U from index X
                   ö     :    Random element

```

# Answer
> 5 votes
# 05AB1E `--no-lazy`, ~~15~~ 14 bytes

```
16L€=[DΩ=ª¦DË#

```

Try it online!

* -1 thanks to Kevin Cruijssen

### Alternative 15 bytes solution (thanks to Kevin Cruijssen)

```
16L[D16.£©Ωª®Ë#

```

Try it Online!

#### Explanation

```
16L             # Push [1..16]
   €=           # Print each item
     [          # Start an infinite loop:
      DΩ        #  Duplicate and push a random element of the list
        =ª      #  Print and append to the list
          ¦     #  Remove the first item
           DË#  #  If all items are equal, break

```

# Answer
> 5 votes
# , 31 bytes

```
(,1}._1{"1(}.,?@#{])^:a:)@i.@16

```

Try it online!

> 0 bonus points to whoever can provide the probability distribution of each number becoming the last one standing.

```
┌──┬──────┐
│0 │1/136 │
├──┼──────┤
│1 │2/136 │
├──┼──────┤
│2 │3/136 │
├──┼──────┤
│3 │4/136 │
├──┼──────┤
│4 │5/136 │
├──┼──────┤
│5 │6/136 │
├──┼──────┤
│6 │7/136 │
├──┼──────┤
│7 │8/136 │
├──┼──────┤
│8 │9/136 │
├──┼──────┤
│9 │10/136│
├──┼──────┤
│10│11/136│
├──┼──────┤
│11│12/136│
├──┼──────┤
│12│13/136│
├──┼──────┤
│13│14/136│
├──┼──────┤
│14│15/136│
├──┼──────┤
│15│16/136│
└──┴──────┘

```

Proof: For example, the system of equations you'd solve for the n=3 case is:

$$ \begin{align} x\_1 &= \frac{x\_3}{3} \\ x\_2 &= x\_1 + \frac{x\_3}{3} \\ x\_3 &= x\_2 + \frac{x\_3}{3} \\ x\_1 + x\_2 + x\_3 &= 1 \end{align} $$

where \\$x\_1\\$ is the chance that number in positon 1 wins, etc -- where 1, if it is not picked the first round, vanishes forever.

The first equation represents that 1/3 of the time \\$x\_1\\$ will be picked and move into position 3, and the rest of the time of vanish. Thus its "value" is 1/3 of \\$x\_3\\$'s.

Similarly, \\$x\_2\\$ will always move into slot 1, where it has \\$x\_1\\$ chance of winning, and 1/3 of the time will also move into slot 3, giving it \\$x\_3\\$ chance of winning. And so on...

# Answer
> 5 votes
# Python, 77 bytes

```
from random import*
t=range(16)
while t:T,*s=*t,choice(t);t=s[t==s:];print(T)

```

Attempt This Online!

Prints one number per line.

### How?

The two mildly clever bits are

1. the rolling tail end of the sequence is all equal if and only if it's equal to its next iteration
2. for the winding down it doesn't matter whether we truncate from the right (more logical) or the left (shorter) since all elements are equal

# Answer
> 5 votes
# Nibbles, 10 bytes (20 nibbles)\*

```
/`.,16>>:$=`#$16$:/

```

*Nibbles is a pure functional language and has no random number capability.
So, this program uses the hash-modulo-16 of the last 16 values after each pick to select the next index. This is pseudo-random, but obviously will be the same on each run of the program.
To more-closely mimic PRNGs from other programming languages, we can select a 'salt' value for the hash, to act as a 'seed': this needs to be appended to the program, and, additionally, the otherwise-implicit variables of the program then need to be explicitly specified, costing +3 nibbles (+1.5 bytes, so 11.5 bytes not including the 'seed' itself).

```
/`.,16>>:$=`#$16$:/
 `.                     # iterate while unique
   ,16                  # starting with 1..16:
        :$              #   join the last list to
          =     $       #   its element at index
           `#$          #   itself hashed
              16        #   modulo-16
/                       # now, fold over this list from the right:
                 :      #   joining
                  /     #     the (implicit) first element of the (implicit) left argument
                        #     to the (implicit) right argument

```

# Answer
> 4 votes
# Excel (ms365), 109 bytes

I do hope that this could get OP's approval. Since volatility would stand in the way of using a list of elements, the only way I could think about a repetitive function that would auto-stop when last 16 elements are exactly the same is to use a custom function made with the name-manager. In this case my function is called 'Z':

```
=LAMBDA(x,LET(y,RIGHT(x,16),IF(y=REPT(RIGHT(y),16),x,Z(x&MID(y,RANDBETWEEN(1,16),1)))))

```

Formula in `A1`:

```
=Z("ABCDEFGHIJKLMNOP")

```

This would make for a combined total of 87 + 22 = 109 bytes.

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

```
pK<TGWt{=t+KpOK

```

Try it online!

Thanks @isaacg for -1 byte

### Explanation

```
 K<TG              # K = "abcdefghijklmnop" (all but the last ten elements of the alphabet)
p                  # print(K)
     Wt{           # while deduplicated K has more than one element
            pOK    #   print a random element of K
          +K       #   append this to K
        =t         #   remove the first element of K

```

# Answer
> 4 votes
# TI-Basic, 54 bytes

```
For(I,1,16
Disp I
End
cumSum(1 or rand(16
While max(Ans≠max(Ans
augment(ΔList(cumSum(Ans)),{Ans(randInt(1,16
Disp Ans(16
End

```

`max(abs(ΔList(Ans` can be used instead of `max(Ans≠max(Ans` alternatively.

# Answer
> 3 votes
# Retina, 43 bytes

```

16*.
Y`.`L
/(.)\1{15}$/^+-16,@v`(.).*
$&$1

```

Try it online! Uses `ABCDEFGHIJKLMNOP`. Explanation:

```

16*.

```

Insert 16 `.`s.

```
Y`.`L

```

Transliterate them to uppercase letters using a different letter each time.

```
/(.)\1{15}$/^+

```

Repeat until the last 16 letters are identical.

```
-16,@v`

```

Randomly choose between one of the last 16 overlapping matches.

```
(.).*

```

Match any character and the rest of the string.

```
$&$1

```

Append the initial character to the match, i.e. append it to the string.

# Answer
> 3 votes
# Julia, ~~73~~ ~~70~~ 69 bytes

```
^,~=last,rand
s=[1:16;]
while s∩s^16!=s^1
push!(s,~s^16)end
show(s)

```

Attempt This Online!

* -1 byte thanks to MarcMush: reassign operators on the same line
    + (Otherwise, a space is needed between `^` and `=`)
* -2 bytes thanks to MarcMush: replace `!allequal(s^16)` with `s∩s^16!=s^1`
    + (`!allequal(last(s,16))` with `s∩last(s,16)!=last(s,1)`)
* -1 byte thanks to MarcMush: remove the newline before `end`
* Thanks also to MarcMush for spotting an error or two!

# Answer
> 3 votes
# Go, 177 bytes

```
import."math/rand"
func f(){N,M,l:=[]int{},1,16;for i:=1;i<17;i++{N=append(N,i);println(i)}
for M<16{k:=Intn(16)
x:=N[k]
println(x)
N=append(N[1:],x)
if x!=l{l=x;M=1}else{M++}}}

```

Attempt This Online!

# Answer
> 3 votes
## Zsh, 73 bytes

```
set {a..p};<<<${(F)@};while 17=$@[RANDOM%16+1];shift;<<<$16;((${#@:#$1}))

```

Try it online!

I use single letters instead of up-to-two-digit numbers as the “16 distinct items”, which saves a byte. (It also gives extra flexibility, which I took advantage of in an earlier version of this answer with a more complex termination condition.)

Expanded and commented:

```
set {a..p}                    # set positional arguments 1=a, 2=b, ...
<<<${(F)@}                    # join arguments with newline, call implicit cat
while
  17=$@[RANDOM%16+1];         # append a random element
  shift;                      # remove the first element
  <<<$16;                     # print the last element
  ((${#@:#$1}))               # termination condition (see below)
                              # no loop body = empty loop body

```

For those unfamiliar with zsh: the positional arguments can be accessed through `$1`, `$2`, … like in other shells, and also through the variable `@` which mostly behaves like an array. Zsh array indexes start at 1. `RANDOM` is a special variable that returns a random number each time it's accessed; fortunately the range 0..32767 is dividible by 16 so all values are equally likely modulo 16.

Now for the termination condition. It's the arithmetic expression `${#@:#$1}`: the command is true if the integer expression has a nonzero value. The expression uses several parameter expansion features. From the outside in, first, we have `${#*spec*}` to count the number of elements in the parameter expansion of `*spec*`. Inside, we have `${*name*:#*pattern*}` which, when `*name*` is an array, removes the elements that match `*pattern*`. The `*name*` is `@`, i.e. the positional parameters. The `*pattern*` is `$1`. Thus we count the number of positional parameters that are not equal to the first one: this is 0 if and only if all the positional parameters are equal.

# Answer
> 2 votes
# Charcoal, 24 bytes

```
≔…α¹⁶θθＷ∧⁻θ⌊θ‽θ«ι≔⁺Φθλιθ

```

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

```
≔…α¹⁶θθ

```

Get and print the first `16` uppercase letters.

```
Ｗ∧⁻θ⌊θ‽θ«ι

```

While there is a choice of at least two different letters, pick and output a random letter from those remaining.

```
≔⁺Φθλιθ

```

Update the string of available letters.

23 bytes if the last letter does not need to be printed (it will be the same as the preceding 15):

```
≔…α¹⁶θＷ⁻θ⌊θ«→Ｐθ≔⁺Φθλ‽θθ

```

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

# Answer
> 2 votes
# Pip, 21 bytes

```
P*Y,16T$=yY SyAE PRCy

```

Uses 0 to 15. Attempt This Online!

### Explanation

```
P*Y,16T$=yY SyAE PRCy
   ,16                 ; Range(16)
  Y                    ; Yank, storing in y variable
P*                     ; Print each
      T                ; Loop till
       $=y             ; all elements of y are equal:
                  RCy  ;  Choose a random element of y
                 P     ;  Print it
              AE       ;  Append that element to
            Sy         ;  y without its first element
          Y            ;  Yank that list as the new value of y

```

# Answer
> 2 votes
# Factor, 69 bytes

```
16 iota [ dup 16 tail* dup all-eq? ] [ random suffix ] until drop ...

```

Try it online!

# Answer
> 2 votes
# Raku, 56 bytes

```
|(1..16),{@_.tail(16).pick}...{~@_~~/(\d+)[' '$0]**15$/}

```

Try it online!

This is a sequence of the form `initial-elements, { generator } ... { termination-check }`.

* The initial elements are from the range `1..16`, flattened with `|`.
* The generator takes the entire sequence generated so far in `@_`, then randomly picks an element from the last sixteen of them.
* The termination check stringifies the sequence, then checks that the string satisfies a regex: a space-separate sequence of digits that repeats sixteen times before the end of the string.

# Answer
> 2 votes
# Arturo, ~~74~~ ~~70~~ 67 bytes

```
a:@0..15prints a until[prints->a\0[]=a--a\0][a:@[sample a]++chop a]

```

Try it

# Answer
> 2 votes
# CJam, ~~24~~ 23 bytes

```
G,_:p;{_mR_p+(;__|,(}g;

```

Try it online!

**Explanation**

```
G,_:p;                        create and print an array [0-16)
      {             }g        do...
       _mR                      pick a random number from the last 16
          _p+(;                 print, add to the list, and remove the oldest number
               __|,(          ...while the number of unique numbers in the last 16 != 1
                      ;       cleanup

```

**(-1 byte)** *replacing `1-` with `(`, courtesy of my bestie*

# Answer
> 1 votes
# Swift 5.6+, 107 bytes

```
var a=[_](1...16),i=0
a.map{print($0)}
while Set(a).count>1{a[i]=a.randomElement()!
print(a[i])
i=(i+1)%16}

```

Uses `a` as a circular buffer, overwriting a different position each run through the loop. For lack of a builtin "all elements are the same" operation, the loop condition converts it to a Set to count the number of unique elements.

SwiftFiddle link

Ungolfed:

```
var arr = Array(1...16)

for el in arr {
  print(el)
}

var i = 0
while Set(arr).count > 1 {
    let x = arr.randomElement()!
    print(x)
    arr[i] = x
    i = (i + 1) % arr.count
}

```

# Answer
> 1 votes
# Zsh, 101 bytes

```
seq 16|tee a;set `shuf a`
while shift;16=`shuf -n1 a`;<<<$16;s=(${(n)@});((s[1]<s[16]))&&<<<${(F)@}>a

```

Try it online! ~~114 bytes~~ ~~117b~~

Writes/reads from file `a`. Uses the shell `$argv` array to randomise and pick new values, and a sorted array `$s` to check equality.

Whoops, the initial version incorrectly ran forever. And then the second version was not uniformly random. Fixed now. Thanks to @Gillies for -13 bytes.

# Answer
> 1 votes
# Java 8, 135 bytes

```
()->{int a,m=16,i=0,c=1,t[]=new int[m];for(;c<m;c=a==t[(i+++15)%m]?c+1:1)System.out.println(t[i%m]=a=i<m?i:t[(int)(Math.random()*m)]);}

```

Try it online!

Even if Java always loses by far, it was still a fun challenge to code!

# Answer
> 1 votes
# PHP 8, 110 bytes

```
$o=range(1,16);do$o[]=$o[count($o)-rand(1,16)];while(count(array_unique(array_slice($o,-16)))>1);print_r($o);

```

I wish PHP's array syntax was a little less verbose...

Works by building up an array by appending a random element from the last 16 elements, then printing it all at once, when the last 16 elements are all the same.

# Answer
> 1 votes
# Mathematica, 84 bytes

Modified from @The Thonnu's answer

Try it online!

```
t=Range@16;While[Length[Union[x=t[[-16;;]]]]!=1,t~AppendTo~RandomChoice@x;];t//Print

```

Ungolfed version:

```
t = Range[0, 15];
While[Length[Union[x = t[[-16 ;;]]]] != 1,
  AppendTo[t, RandomChoice[x]];
];
t//Print

```

# Answer
> 1 votes
# Wolfram Language (Mathematica), 53 bytes

```
If[#==##,#.##2,#.##2~#0~RandomChoice@{##}]&@@Range@16

```

Try it online!

Returns a `Dot` of integers.

To print, wrap with `Print/@(` `)` (+9 bytes).

---
Tags: code-golf, random
---


# Question
Title: Exponential transform of an integer sequence
The exponential generating function (e.g.f.) of a sequence \\$a\_n\\$ is defined as the formal power series \\$f(x) = \sum\_{n=0}^{\infty} \frac{a\_n}{n!} x^n\\$.

When \\$a\_0 = 0\\$, we can apply the exponential function \\$\exp\\$ on this formal power series:

\\$\begin{align} \exp(f(x)) &= \sum\_{n=0}^{\infty} \frac{1}{n!} f(x)^n \\ &= \sum\_{n=0}^{\infty} \frac{1}{n!} \left(\sum\_{m=1}^{\infty} \frac{a\_m}{m!} x^m\right)^n \\ &= \sum\_{n=0}^{\infty} \frac{b\_n}{n!} x^n \\ \text{where} \\ b\_0 &= 1 \\ b\_n &= \sum\_{k=1}^n \binom{n-1}{k-1} a\_k b\_{n-k} \text{ when } n\>0 \end{align}\\$

This is the exponential generating function of the sequence \\$b\_n\\$. If all \\$a\_n\\$ are integers, then all \\$b\_n\\$ are also integers. So this is a tranformation of integer sequences.

It seems that OEIS call this the Exponential transform. But I can't find a reference to its definition.

Here are some examples on OEIS:

* A001477 (the nonnegative integers, \\$0,1,2,3,4,\dots\\$) -\> A000248 (\\$1,1,3,10,41,\dots\\$)
* A001489 (the nonpositive integers, \\$0,-1,-2,-3,-4,\dots\\$) -\> A292952 (\\$1, -1,-1,2,9,\dots\\$)
* A000045 (Fibonacci numbers, \\$0,1,1,2,3,\dots\\$) -\> A256180 (\\$1,1,2,6,21,\dots\\$)
* A160656 (\\$0\\$ and the odd primes, \\$0,3,5,7,11,\dots\\$) -\> A353079 (\\$1,3,14,79,521,\dots\\$)
* A057427 (\\$0,1,1,1,1,\dots\\$) -\> A000110 (Bell numbers, \\$1,1,2,5,15,\dots\\$)

## Task

Given a finite integer sequence, compute its Exponential transform.

The length of the input sequence is always greater than \\$0\\$. Its \\$0\\$th term is always \\$0\\$. You can omit the leading \\$0\\$ in the input.

If the input sequence has length \\$n\\$, you only need to output the first \\$n\\$ terms of the output sequence.

Input and output can be in any reasonable format, e.g., a list, an array, a polynomial, a function that takes \\$i\\$ and returns the \\$i\\$th term (0-indexed or 1-indexed), etc.

You may also take the input sequence and an integer \\$i\\$, and output the \\$i\\$th term (0-indexed or 1-indexed) of the output sequence.

This is , so the shortest code in bytes wins.

## Example Python code

This example code uses the above recurrence formula. There are other formulas that might give shorter answers.

```
import math

def exponential_transform(a):
    b = [0] * len(a)
    b[0] = 1
    for i in range(1, len(a)):
        b[i] = sum(math.comb(i-1, j-1) * a[j] * b[i - j] for j in range(1, i + 1))
    return b

```

## Testcases

```
[0, 0, 0, 0, 0] -> [1, 0, 0, 0, 0]
[0, 1, 0, -1, 0, 1, 0, -1] -> [1, 1, 1, 0, -3, -8, -3, 56]
[0, 1, 2, 3, 4, 5, 6, 7] -> [1, 1, 3, 10, 41, 196, 1057, 6322]
[0, -1, -2, -3, -4, -5, -6, -7] -> [1, -1, -1, 2, 9, 4, -95, -414]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] -> [1, 1, 2, 6, 21, 86, 404, 2121, 12264, 77272, 525941]
[0, 3, 5, 7, 11, 13, 17, 19] -> [1, 3, 14, 79, 521, 3876, 31935, 287225]
[0, 1, 1, 1, 1, 1] -> [1, 1, 2, 5, 15, 52]
[0, 1, 2, 5, 15, 52] -> [1, 1, 3, 12, 60, 358]
[0, 1, 3, 12, 60, 358] -> [1, 1, 4, 22, 154, 1304]
[0, 1, 4, 22, 154, 1304] -> [1, 1, 5, 35, 315, 3455]
[0, 1, 5, 35, 315, 3455] -> [1, 1, 6, 51, 561, 7556]

```

# Answer
> 11 votes
# 05AB1E, ~~21~~ ~~20~~ ~~18~~ 16 bytes

```
L©ææʒ˜{®Q}€€gèPO

```

Try it online!

Returns the \\$ i \\$-th term, zero indexed. It runs in complexity \\$ \Omega(2^{2^i}) \\$, so it can only work in a reasonable time for \\$ i \leq 4 \\$.

# Explanation

We will define \\$ c\_n = \frac{a\_n x^n}{n!} \\$.

In the expression $$ \left(\sum\_{m=1}^{\infty} \frac{a\_m}{m!} x^m\right)^n = \left(\sum\_{m=1}^{\infty} c\_m\right)^n $$

we know from the multinomial theorem that the coefficient of \\$ \prod {c\_m ^ {k\_m}} \\$ is $$ \frac{n!}{\prod{k\_m !}} $$ The \\$ n! \\$ cancels with the \\$ \frac{1}{n!} \\$ in \\$ \sum\_{n=0}^{\infty} \frac{1}{n!} \left(\sum\_{m=1}^{\infty} \frac{a\_m}{m!} x^m\right)^n \\$, so we get $$ \exp(f(x)) = \sum \frac{\prod{c\_m ^ {k\_m}}}{\prod{k\_m!}} $$ If the exponent of \\$ x \\$ in the equation is \\$ j \\$, we get that \\$ \sum k\_m m = j \\$. If we create a sequence \\$ d\_m \\$ by repeating \\$ m \\$ \\$ k\_m \\$ times, we get that \\$ d\_m \\$ is a partition of \\$ j \\$.

Now that we have a mathematical expression for how much time each partition of \\$ i \\$ occurs, we can think of a combinatorical one.

By playing with equations, we can find out that the coefficient of \\$ \prod {a\_{d\_i}} \\$ is the number of unique ways to divide a set with \\$ j \\$ elements to sets of sizes \\$ d\_i \\$. Therefore, we can generate a set of size \\$ j \\$, list all of its separations to other sets, take the size of each set in those separations, index that size to \\$ a \\$, take the product of each, and take the total sum.

```
L       push the list 1...input index
©       save it in register ® (without popping)
æ       take its powerset
æ       take the powerset's powerset
ʒ       and only keep sets such that
 ˜       if you flatten them
 {       and sort the result
 ®       and then push the original list
 Q       they compare equal
}
€        for each of those sets
 €       map each of its sets
  g      to its size
è        index that size into the input list
P        take the product of each list
O        and take the sum

```

If the index is 0, `L` returns `[1, 0]`, and no array sorted can be equal to it, so the filter returns an empty list. The map and index then do nothing, then `P` multiplies it to get `1`, which `O` preserves.

# Answer
> 4 votes
# Wolfram Language (Mathematica), ~~37~~ 24 bytes

```
BellY[#,,#2]~Sum~{,0,#}&

```

Try it online!

Based on the Mathematica code given by Vladimir Reshetnikov on OEIS A256180. Takes the 0-indexed item to output and the list.

*-13 bytes thanks to alephalpha*

# Answer
> 4 votes
# Haskell, 59 bytes

```
f@(a:b)&g@(c:d)=a*c:zipWith(+)(b&g)(f&d)
_&_=[]
e b=1:e b&b

```

Try it online!

`e` accepts the sequence as a list of integers without the leading 0.

If \\$f(x)\\$ is the e.g.f. of \\$a\_n\\$, then \\$f(0) = a\_0\\$ and \\$f'(x)\\$ is the e.g.f. of \\$a\_{n + 1}\\$. So this program is a direct encoding of the product rule \\$\[f(x)g(x)\]' = f'(x)g(x) + f(x)g'(x)\\$ and the chain rule \\$\[e^{f(x)}\]' = e^{f(x)}f'(x)\\$.

# Answer
> 3 votes
# Vyxal `R`, 16 bytes

```
ṗṗ'fs¹ɾ⁼;vvLİvΠ∑

```

Try it Online!

Port of Command Master's 05AB1E answer, upvote that!

# Answer
> 2 votes
# PARI/GP, ~~103~~ 92 bytes

saved 11 bytes thanks to the comment of @alephalpha

Golfed vesrion, try it online!

```
f(a)=b=vector(#a,i,0);b[1]=1;for(i=2,#a,b[i]=sum(j=1,i-1,binomial(i-2,j-1)*a[j+1]*b[i-j]));b

```

Ungolfde version, modified from the provided Python example code

```
exponential_transform(a) = {
    b = vector(#a, i, 0); \\ Initialize b as a zero vector of the same length as a
    b[1] = 1; \\ Set the first element of b to 1

    for(i=2, #a,
        b[i] = sum(j=1, i-1, binomial(i-2, j-1) * a[j+1] * b[i-j])
    );
    return(b);
}
print("Test case 1: ", exponential_transform([0, 0, 0, 0, 0]));
print("Test case 2: ", exponential_transform([0, 1, 0, -1, 0, 1, 0, -1]));
print("Test case 3: ", exponential_transform([0, 1, 2, 3, 4, 5, 6, 7]));
print("Test case 4: ", exponential_transform([0, -1, -2, -3, -4, -5, -6, -7]));
print("Test case 5: ", exponential_transform([0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]));
print("Test case 6: ", exponential_transform([0, 3, 5, 7, 11, 13, 17, 19]));
print("Test case 7: ", exponential_transform([0, 1, 1, 1, 1, 1]));
print("Test case 8: ", exponential_transform([0, 1, 2, 5, 15, 52]));
print("Test case 9: ", exponential_transform([0, 1, 3, 12, 60, 358]));
print("Test case 10: ", exponential_transform([0, 1, 4, 22, 154, 1304]));
print("Test case 11: ", exponential_transform([0, 1, 5, 35, 315, 3455]));

```

# Answer
> 1 votes
# Python, 85 bytes

```
import math
f=lambda n,l:sum(math.comb(n-1,i)*l[i]*f(n-i-1,l)for i in range(n))+(n<1)
```

Attempt This Online!

Doesn't take the leading zero in the input. If that's not allowed, I will change. Based on the Maple code given by Alois P. Heinz in A007446 and A353079.

# Answer
> 1 votes
# Charcoal, 36 bytes

```
ＦＬθ⊞υ∨¬ιΣＥυ××κ§θ⁻ιλ∨¬λ÷Π…⁻ιλιΠ…·¹λＩυ

```

Try it online! Link is to verbose version of code. Explanation: A translation of the recurrence formula given in the question, except the subscript of `b` is used as the loop index, and the combination has to be written out as a ratio of products of ranges.

33 bytes using the newer version of Charcoal on ATO:

```
ＦＬθ⊞υ∨¬ιΣＥυ××κ§θ⁻ιλ÷Π…⁻ιλιΠ…·¹λＩυ

```

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

---
Tags: code-golf, math, sequence, integer, polynomials
---


# Question
Title: How many steps does it take from n to 1 by subtracting the greatest divisor?
Inspired by this question over at Mathematics.

---

**The Problem**

> Let `n` be a natural number `≥ 2`. Take the biggest divisor of `n` – which is different from `n` itself – and subtract it from `n`. Repeat until you get `1`.

**The Question**

*How many steps does it take to reach `1` for a given number `n ≥ 2`.*

**Detailed Example**

> Let `n = 30`.

The greatest divisor of:

```
1.   30 is 15  -->  30 - 15 = 15
2.   15 is  5  -->  15 -  5 = 10
3.   10 is  5  -->  10 -  5 =  5
4.    5 is  1  -->   5 -  1 =  4
5.    4 is  2  -->   4 -  2 =  2
6.    2 is  1  -->   2 -  1 =  1

```

It takes *6 steps* to reach `1`.

**Input**

* Input is an integer `n`, where `n ≥ 2`.
* Your program should support input up to the language's maximum integer value.

**Output**

* Simply output the number of steps, like `6`.
* Leading/trailing whitespaces or newlines are fine.

**Examples**

```
f(5)        --> 3
f(30)       --> 6
f(31)       --> 7
f(32)       --> 5
f(100)      --> 8
f(200)      --> 9
f(2016^155) --> 2015

```

**Requirements**

* You can get input from `STDIN`, command line arguments, as function parameters or from the closest equivalent.
* You can write a program or a function. If it is an anonymous function, please include an example of how to invoke it.
* This is so shortest answer in bytes wins.
* Standard loopholes are disallowed.

---

This series can be found on OEIS as well: **A064097**

> A quasi-logarithm defined inductively by `a(1) = 0` and `a(p) = 1 + a(p-1)` if `p` is prime and `a(n*m) = a(n) + a(m)` if `m,n > 1`.

# Answer
# Jelly, 9 bytes

```
ÆṪÐĿÆFL€S

```

Try it online! or verify all test cases.

### Background

The definition of sequence A064097 implies that

$$\small{a(p)-a(p-1)=1}\text{ for all primes }p\text{ and }a(km)=a(k)+a(m)\text{ for all }k,m\in \mathbb{N}$$

By Euler's product formula

$$\small{\varphi(n)=n\prod\_{p|n}\left(1-{1\over p}\right)=n\prod\_{p|n}{{p-1}\over p}}$$

where \\$\varphi\\$ denotes Euler's totient function and \\$p\\$ varies only over prime numbers.

Combining both, we deduce the property

$$\small{a(\varphi(n))=a\left(n\prod\_{p|n}{{p-1}\over p}\right)=a(n)+\sum\_{p|n}\left(a(p-1)-a(p)\right)=a(n)-\sum\_{p|n}{1=a(n)-\omega(n)}}$$

where \\$\omega\\$ denotes the number of distinct prime factors of \\$n\\$.

Applying the resulting formula \\$k + 1\\$ times, where \\$k\\$ is large enough so that \\$\varphi^{k+1}(n)=1\\$, we get

$$\small{ \begin{aligned} 0=a\left(\varphi^{k+1}(n)\right)=a\left(\varphi^k(n)\right)-\omega\left(\varphi^k(n)\right)&=a\left(\varphi^{k-1}(n)\right)-\omega\left(\varphi^{k-1}(n)\right)-\omega\left(\varphi^k(n)\right) \\ &= \cdots = a(n)-\sum\_{j=0}^k\omega\left(\varphi^j(n)\right) \end{aligned} }$$

From this property, we obtain the formula

$$\small{a(n)=\sum\_{j=0}^k\omega\left(\varphi^j(n)\right)=\sum\_{j=0}^{+\infty}\omega\left(\varphi^j(n)\right)}$$

where the last equality holds because \\$\omega(1)=0\\$.

### How it works

```
ÆṪÐĿÆFL€S  Main link. Argument: n

  ÐĿ       Repeatedly apply the link to the left until the results are no longer
           unique, and return the list of unique results.
ÆṪ           Apply Euler's totient function.
           Since φ(1) = 1, This computes φ-towers until 1 is reached.
    ÆF     Break each resulting integer into [prime, exponent] pairs.
      L€   Compute the length of each list.
           This counts the number of distinct prime factors.
        S  Add the results.

```
> 24 votes

# Answer
# 05AB1E, ~~13~~ 11 bytes

Code:

```
[DÒ¦P-¼D#]¾

```

Explanation:

```
[        ]   # An infinite loop and...
       D#        break out of the loop when the value is equal to 1.
 D           # Duplicate top of the stack (or in the beginning: duplicate input).
  Ò          # Get the prime factors, in the form [2, 3, 5]
   ¦         # Remove the first prime factor (the smallest one), in order to get
               the largest product.
    P        # Take the product, [3, 5] -> 15, [] -> 1.
     -       # Substract from the current value.
      ¼      # Add one to the counting variable.
          ¾  # Push the counting variable and implicitly print that value.

```

Uses **CP-1252** encoding. Try it online!.
> 15 votes

# Answer
# Pyth, 11 bytes

```
fq1=-Q/QhPQ

```

Test suite

A straightforward repeat-until-true loop.

Explanation:

```
fq1=-Q/QhPQ
               Implicit: Q = eval(input())
f              Apply the following function until it is truthy,
               incrementing T each time starting at 1:
         PQ    Take the prime factorization of Q
        h      Take its first element, the smallest factor of Q
      /Q       Divide Q by that, giving Q's largest factor
    -Q         Subtract the result from Q
   =           Assign Q to that value
 q1            Check if Q is now 1.

```
> 12 votes

# Answer
## Python 2, ~~50~~ 49 bytes

```
f=lambda n,k=1:2/n or n%(n-k)and f(n,k+1)or-~f(k)

```

This isn't going to finish that last test case any time soon...

Alternatively, here's a 48-byte which returns `True` instead of `1` for `n=2`:

```
f=lambda n,k=1:n<3or n%(n-k)and f(n,k+1)or-~f(k)

```
> 7 votes

# Answer
# Retina, 12

* 14 bytes saved thanks to @MartinBüttner

```
(1+)(?=\1+$)

```

This assumes input given in unary and output given in decimal. If this is not acceptable then we can do this for 6 bytes more:

# Retina, 18

* 8 bytes saved thanks to @MartinBüttner

```
.+
$*
(1+)(?=\1+$)

```

Try it online - 1st line added to run all testcases in one go.

Sadly this uses unary for the calculations, so input of 2016155 is not practical.

* The first stage (2 lines) simply converts the decimal input to unary as a string of `1`s
* The second stage (1 line) calculates the largest factor of n using regex matching groups and lookbehinds to and effectively subtracts it from n. This regex will match as many times as is necessary to reduce the number as far as possible. The number of regex matches will be the number of steps, and is output by this stage.
> 7 votes

# Answer
# Jelly, 10 bytes

```
ÆfḊPạµÐĿi2

```

Try it online! or verify most test cases. The last test cases finishes quickly locally.

### How it works

```
ÆfḊPạµÐĿi2  Main link. Argument: n (integer)

Æf          Factorize n, yielding a list of primes, [] for 1, or [0] for 0.
  Ḋ         Dequeue; remove the first (smallest) element.
   P        Take the product.
            This yields the largest proper divisor if n > 1, 1 if n < 2.
    ạ       Yield the abs. value of the difference of the divisor (or 1) and n.
     µ      Convert the chain to the left into a link.
      ÐĿ    Repeatedly execute the link until the results are no longer unique.
            Collect all intermediate results in a list.
            For each starting value of n, the last results are 2 -> 1 -> 0 (-> 1).
        i2  Compute the 1-based index of 2.

```
> 6 votes

# Answer
# Pyth - ~~15~~ ~~14~~ 13 bytes

Special casing `1` is really killing me.

```
tl.u-N/Nh+PN2

```

Try it online here.

```
tl                One minus the length of
 .u               Cumulative fixed point operator implicitly on input
  -N              N -
   /N             N /
    h             Smallest prime factor
     +PN2         Prime factorization of lambda var, with two added to work with 1

```
> 5 votes

# Answer
# Julia, ~~56~~ ~~50~~ ~~45~~ 39 bytes

```
f(n)=n>1&&f(n-n÷first(factor(n))[1])+1

```

This is a recursive function that accepts an integer and returns an integer.

Ungolfed:

```
function f(n)
    if n < 2
        # No decrementing necessary
        return 0
    else
        # As Dennis showed in his Jelly answer, we don't need to
        # divide by the smallest prime factor; any prime factor
        # will do. Since `factor` returns a `Dict` which isn't
        # sorted, `first` doesn't always get the smallest, and
        # that's okay.
        return f(n - n ÷ first(factor(n))[1]) + 1
    end
end

```

Try it online! (includes all test cases)

Saved 6 bytes thanks to Martin Büttner and 11 thanks to Dennis!
> 5 votes

# Answer
# JavaScript (ES6), ~~\*44~~ 38

*Edit* 6 bytes saved thanks @l4m2

(\* 4 striked is still 4)

Recursive function

```
f=(n,d=n)=>n>1?n%--d?f(n,d):f(n-d)+1:0

```

Less golfed

```
f=(n, d=n-1)=>{
  if (n>1)
    if(n % d != 0)
      return f(n, d-1) // same number, try a smaller divisor
    else
      return f(n-d)+1  // reduce number, increment step, repeat
  else
    return 0
}

```

**Test**

```
f=(n,d=n)=>n>1?n%--d?f(n,d):f(n-d)+1:0

console.log=x=>O.textContent+=x+'\n';

[5,30,31,32,100,200].forEach(x=>console.log(x+' -> '+f(x)))
```

```
<pre id=O></pre>
```
> 5 votes

# Answer
# Regex  (ECMAScript or better), 12 bytes

```
(x+)(?=\1+$)

```

Takes its input in unary, as a sequence of `x` characters whose length represents the number. Returns its output as the number of matches.

This of course has already been done in Digital Trauma's Retina answer, but here it is demonstrated to work on a much wider variety of regex engines.

Try it online! \- ECMAScript
Try it online! \- Perl
Try it online! \- Java
Try it online! \- PCRE
Try it online! \- Boost
Try it online! \- Python
Try it online! \- Ruby
Try it online! \- .NET

```
(x+)(?=\2+$)   # \2 = largest proper divisor of tail; tail -= \2;
               # return \2 as a match

```

Try it online!

# Regex  (.NET), 15 bytes

```
((x+)(?=\2+$))*

```

Try it online!

Returns its output as the capture count of group `\1`.

```
                   # tail = input number; no need to anchor, as all inputs return a result
(
    (x+)(?=\2+$)   # \2 = largest proper divisor of tail; tail -= \2
)*                 # Loop the above as many times as possible, minimum zero, and push each
                   # match onto the \1 capture stack

```

# Regex (Perl / Java / PCRE2 v10.34 or later), 26 bytes

```
((?=(\2?+(x*))x(x\3)+$)x)*

```

Returns its output as the length of the match.

Try it online! \- Perl
Try it online! \- Java
Attempt This Online! \- PCRE2 v10.40+

We can't just do a direct port of the .NET version, because we need to subtract at least 1 from tail on each iteration (as a regex loop terminates after a zero-width match), and with most inputs, the iteration count exceeds the cumulative result of subtracting the largest divisor before the last iteration has finished. So instead, we let `\2` be the sum of the subtracted divisors minus the iteration count:

```
                    # tail = input number; no need to anchor, as all inputs return a result
(
    (?=
        (\2?+(x*))  # \3 = {conjectured largest proper divisor of tail-\2} - 1;
                    # \2 = {\2, or 0 if \2 is unset} + \3; tail -= \2; note that the
                    # subtraction of 1 from this divisor compensates for the "tail -= 1"
                    # on each iteration (below)
        x(x\3)+$    # assert tail - 1 is divisible by \3 + 1
    )
    x               # head += 1; tail -=1
)*                  # Loop the above as many times as possible, minimum zero

```

(The PCRE version requirement is because PCRE2 v10.33 and earlier automatically makes any group containing a nested backreference atomic, thus `\3` always captures the entire remaining tail, making the regex always return 0.)

# Regex (.NET), 28 bytes

```
(?=((x+)(?=\2+$))*)(?<-1>x)*

```

Try it online!

A simple port of the 15 byte .NET version, that returns its output as the length of the match instead.

## Regex (Perl / Java / PCRE2 v10.34 or later / .NET), ~~29~~ bytes

Obsoleted by the 29 byte regex below, which supports a superset of regex engines.

# Regex (Perl / Java / PCRE / Python`regex` / Ruby / .NET), ~~33~~ 29 bytes

```
((?=.*(?=\3$|^)(x+)(\2+$))x)*

```

Try it online! \- Perl
Try it online! \- Java
**Try it online! \- PCRE1
Try it online! \- PCRE2 v10.33**
Attempt This Online! \- PCRE2 v10.40+
**Try it online! \- Python `import regex`
Try it online! \- Ruby**
Try it online! \- .NET

For regex engines that lack nested backreferences but support forward-declared backreferences, we switch to a different approach. In this version, each iteration, while inside a lookahead, stores the new value of tail in the capture group `\3`, so that the next iteration can then recall that value rather directly. Since this directly sets `\3` instead of building it up incrementally, there's no need to emulate a nested backreference.

```
                     # tail = N = input number;
                     # no need to anchor, as all inputs return a result
(
    (?=
        .*(?=\3$|^)  # tail = \3, or N if \3 is unset
        (x+)(\2+$)   # \2 = largest proper divisor of tail; \3 = tail - \2
    )
    x                # Increment the return value
)*                   # Loop the above as many times as possible, minimum zero

```

# Regex (Perl / PCRE / Python`regex`), 63 bytes

```
(?=(xx+?)\1*(?=\1$)((?R)))(?=(x+)\3*(?=\3$)((?R)))\2\4|x\B(?R)|

```

This implements the recursive definition of the function:

\\$a(1) = 0\\$
\\$a(p) = 1 + a(p-1)\\$ if \\$p\\$ is prime
\\$a(nm) = a(n) + a(m)\\$ if \\$m,n \> 1\\$

Try it online! \- Perl
Try it online! \- PCRE1
Try it online! \- PCRE2 v10.33
Attempt This Online! \- PCRE2 v10.40+
Try it online! \- Python `import regex`

```
                # tail = input number; no need to anchor, as all inputs return a result
    (?=
        (xx+?)\1*(?=\1$)  # Assert tail isn't prime;
                          # tail = \1 = smallest prime factor of tail
        ((?R))            # \2 = recursive result of f(tail)
    )
    (?=
        (x+)\3*(?=\3$)    # tail = \3 = largest proper divisor of tail
        ((?R))            # \4 = recursive result of f(tail)
    )
    \2\4                  # return \2 + \4 as the match
|       # or if tail is prime:
    x                     # tail -= 1; return result += 1
    \B                    # Assert tail > 0
    (?R)                  # return 1 + recursive result of f(tail)
|       # or if tail == 1:
                          # return 0 at the match

```

Note that `(?0)` could have been used as a synonym for `(?R)`.

# Regex (Perl / PCRE / Boost / Python`regex`), 65 bytes

```
((?=(xx+?)\2*(?=\2$)((?1)))(?=(x+)\4*(?=\4$)((?1)))\3\5|x\B(?1)|)

```

The intent of the 63 byte version was to create a version that works under Boost, but as it turned out Boost has a bug (which I've reported) in which it ignores top-level alternatives in a top-level recursive call (i.e. `(?R)`), trying only the first top-level alternative. The workaround is to nest the entire regex in a capture group, so that Boost sees the other alternatives. Either `(?R)` or `(?1)` would work, but the latter is used for slightly better efficiency.

Try it online! \- Perl
Try it online! \- PCRE2
**Try it online! \- Boost**
Try it online! \- Python `import regex`

# Regex (Ruby), ~~76~~ 71 bytes

```
(?=(xx+?)\1*(?=\1$)(\g<0>))(?=(x+)\3*(?=\3$)(\g<0>))\k<2+0>\4|x\B\g<0>|

```

Try it online!

This is a port to Ruby's style of recursion; `(?R)` is replaced with `\g<0>`. Also, the backreference `\2` needs to be replaced with `\k<2+0>` to get its value at the current level of recursion, rather than its global value which may have been overwritten at deeper levels of recursion.
> 5 votes

# Answer
## Mathematica, 36 bytes

```
f@1=0;f@n_:=f[n-Divisors[n][[-2]]]+1

```

An unnamed function takes the same bytes:

```
If[#<2,0,#0[#-Divisors[#][[-2]]]+1]&

```

This is a very straightforward implementation of the definition as a recursive function.
> 4 votes

# Answer
## PowerShell v2+, 81 bytes

```
param($a)for(;$a-gt1){for($i=$a-1;$i-gt0;$i--){if(!($a%$i)){$j++;$a-=$i;$i=0}}}$j

```

Brutest of brute force.

Takes input `$a`, enters a `for` loop until `$a` is less than or equal to `1`. Each loop we go through another `for` loop that counts down from `$a` until we find a divisor (`!($a%$i`). At worst, we'll find `$i=1` as a divisor. When we do, increment our counter `$j`, subtract our divisor `$a-=$i` and set `$i=0` to break out of the inner loop. Eventually, we'll reach a condition where the outer loop is false (i.e., `$a` has reached `1`), so output `$j` and exit.

**Caution**: This will take a *long* time on larger numbers, especially primes. Input of 100,000,000 takes ~35 seconds on my Core i5 laptop. *Edit* -- just tested with `[int]::MaxValue` (2^32-1), and it took ~27 minutes. Not *too* bad, I suppose.
> 4 votes

# Answer
# Octave, ~~59~~ ~~58~~ 55 bytes

```
function r=f(x)r=0;while(x-=x/factor(x)(1));r++;end;end

```

> Updated thanks to Stewie Griffin, saving 1 byte
>
> Further update, saving three more bytes by using result of factorization in while-check.

Sample runs:

```
octave:41> f(5)
ans =  3
octave:42> f(30)
ans =  6
octave:43> f(31)
ans =  7
octave:44> f(32)
ans =  5
octave:45> f(100)
ans =  8
octave:46> f(200)
ans =  9

```
> 4 votes

# Answer
# Haskell, 59 bytes

```
f 1=0;f n=1+(f$n-(last$filter(\x->n`mod`x==0)[1..n`div`2]))

```

Usage:

```
Prelude> f 30
Prelude> 6

```

It may be a little inefficient for big numbers because of generating the list.
> 4 votes

# Answer
# Python 3, ~~75, 70~~, 67 bytes.

```
g=lambda x,y=0:y*(x<2)or[g(x-z,y+1)for z in range(1,x)if x%z<1][-1]

```

This is a pretty straight forward recursive solution. It takes a VERY long time for the high number test cases.
> 3 votes

# Answer
# Matlab, 58 bytes

```
function p=l(a),p=0;if(a-1),p=1+l(a-a/min(factor(a)));end

```
> 3 votes

# Answer
## Japt, 12 bytes

```
@!(UµUk Å×}a

```

Test it online!

### How it works

```
@   !(Uµ Uk Å  ×   }a
XYZ{!(U-=Uk s1 r*1 }a
                       // Implicit: U = input integer
XYZ{               }a  // Return the smallest non-negative integer X which returns
                       // a truthy value when run through this function:
         Uk            //   Take the prime factorization of U.
            s1         //   Slice off the first item.
                       //   Now we have all but the smallest prime factor of U.
               r*1     //   Reduce the result by multiplication, starting at 1.
                       //   This takes the product of the array, which is the
                       //   largest divisor of U.
      U-=              //   Subtract the result from U.
    !(                 //   Return !U (which is basically U == 0).
                       //   Since we started at 0, U == 1 after 1 less iteration than
                       //   the desired result. U == 0 works because the smallest
                       //   divisor of 1 is 1, so the next term after 1 is 0.
                       // Implicit: output result of last expression

```

This technique was inspired by the 05AB1E answer. A previous version used `²¤` (push a 2, slice off the first two items) in place of `Å` because it's one byte shorter than `s1` (note trailing space); I only realized after the fact that because this appends a 2 to the *end* of the array and slices from the *beginning*, it in fact fails on any odd composite number, though it works on all given test cases.
> 3 votes

# Answer
# Vyxal `s`, 6 bytes

```
⁽∆ṫ↔v†

```

Try it Online!

Port of Jelly.

```
⁽∆ṫ↔v†
⁽  ↔    # Repeatedly apply until the result does not change, collecting intermediate results:
 ∆ṫ     #  Euler's totient
    v†  # For each, get the number of distinct prime factors
        # s flag sums

```
> 3 votes

# Answer
# Vyxal `l`, ~~6~~ 5 bytes

```
≬K¯÷ẋ

```

Try it Online!

This is the same as the 6 byte answer below except the length is taken by the `l` flag rather than a `L` element.

# Vyxal, ~~7~~ 6 bytes

```
≬K¯÷ẋL

```

Try it Online!

```
≬    # 3-element lambda:
  K  # Push a list of the divisors, from 1 to the number itself in increasing order
  ¯  # Deltas - returns a list of the consecutive differences in the list.
     # The resulting list has a length of 1 less than the one fed to it.
  ÷  # Unwrap the list onto the stack. For a non-empty list, this is effectively
     # equivalent to t (Tail - get the last item). But for an empty list, the
     # result is effectively whatever was already on the stack, i.e. the the
     # number whose list of divisors was taken, i.e., 1, the only one that yields
     # an empty deltas list. This makes 1, instead of 0, the fixed point.
ẋ    # Repeat the lambda on the number at the top of the stack (which is initially
     # the input) until the result no longer changes, returning a list of the
     # results. The last result will be 1, our fixed point.
L    # Length

```

This is very slow for most numbers of more than 60 decimal digits or so, since it has to generate a full list of divisors (even if it only uses the largest two). Prime factorization is still fast enough at that level, but unless the number has only one distinct prime factor, the list of divisors will be orders of magnitude longer.
> 3 votes

# Answer
# \>\<\>, 32 bytes

```
<\?=2:-$@:$/:
1-$:@@:@%?!\
;/ln

```

Expects the input number, `n`, on the stack.

This program builds the complete sequence on the stack. As the only number that can lead to `1` is `2`, building the sequence stops when `2` is reached. This also causes the size of the stack to equal the number of steps, rather than the number of steps +1.
> 2 votes

# Answer
# C99, ~~62~~ 61 bytes

1 byte golfed off by @Alchymist.

```
f(a,c,b)long*c,a,b;{for(*c=0,b=a;a^1;a%--b||(++*c,b=a-=b));}

```

Call as f(x,&y), where x is the input and y is the output.
> 2 votes

# Answer
# Haskell, 67 bytes

Here's the code:

```
a&b|b<2=0|a==b=1+2&(b-1)|mod b a<1=1+2&(b-div b a)|1<2=(a+1)&b
(2&)

```

And here's one reason why Haskell is awesome:

```
f = (2&)

(-->) :: Eq a => a -> a -> Bool
(-->) = (==)

h=[f(5)        --> 3
  ,f(30)       --> 6
  ,f(31)       --> 7
  ,f(32)       --> 5
  ,f(100)      --> 8
  ,f(200)      --> 9
  ,f(2016^155) --> 2015
  ]

```

Yes, in Haskell you can define `-->` to be equivalent to `==`.
> 2 votes

# Answer
# Matlab, 107 bytes

```
a=input('');b=factor(a-isprime(a));c=log2(a);while(max(b)>1),b=max(factor(max(b)-1));c=c+1;end,disp(fix(c))

```
* Non-competing, this is not the iterative translation of my last submission, just another direct algerbraic method, it sums up all binary-logs of all prime factors, kinda ambiguous to illustrate.
* I will golf this more when i have time.
> 2 votes

# Answer
# Ruby, 43 bytes

```
f=->x{x<2?0:1+f[(1..x).find{|i|x%(x-i)<1}]}

```

Find the smallest number `i` such that `x` divides `x-i` and recurse until we reach `1`.
> 2 votes

# Answer
# MATL, ~~17~~ 16 bytes

```
`tttYfl)/-tq]vnq

```

**Try it Online**

**Explanation**

```
        % Implicitly grab input
`       % Do while loop
    ttt % Make three copies of top stack element
    Yf  % Compute all prime factors
    l)  % Grab the smallest one
    /   % Divide by this to get the biggest divisor
    -   % Subtract the biggest divisor
    t   % Duplicate the result
    q   % Subtract one (causes loop to terminate when the value is 1). This
        % is functionally equivalent to doing 1> (since the input will always be positive)
        % with fewer bytes
]       % End do...while loop
v       % Vertically concatenate stack contents (consumes entire stack)
n       % Determine length of the result
q       % Subtract 1 from the length
        % Implicitly display result

```
> 2 votes

# Answer
# Julia, ~~39~~ 36 bytes

```
\(n,k=2)=n%k>0?n>1&&n\-~k:\(n-n/k)+1

```

Try it online!
> 2 votes

# Answer
# Clojure, ~~116~~ 104 bytes

```
(fn[n](loop[m n t 1](let[s(- m(last(filter #(=(rem m %)0)(range 1 m))))](if(< s 2)t(recur s (inc t))))))

```

-12 bytes by filtering a range to find multiples, then using `last` one to get the greatest one

Naïve solution that basically just solves the problem as it's described by the OP. Unfortunately, finding the greatest divisor alone takes up like half the bytes used. At least I should have lots of room to golf from here.

Pregolfed and test:

```
(defn great-divider [n]
  ; Filter a range to find multiples, then take the last one to get the largest
  (last
     (filter #(= (rem n %) 0)
             (range 1 n))))

(defn sub-great-divide [n]
  (loop [m n
         step 1]
    (let [g-d (great-divider m) ; Find greatest divisor of m
          diff (- m g-d)] ; Find the difference
      (println m " is " g-d " --> " m " - " g-d " = " diff)
      (if (< diff 2)
        step
        (recur diff (inc step))))))

(sub-great-divide 30)

30  is  15  -->  30  -  15  =  15
15  is  5  -->  15  -  5  =  10
10  is  5  -->  10  -  5  =  5
5  is  1  -->  5  -  1  =  4
4  is  2  -->  4  -  2  =  2
2  is  1  -->  2  -  1  =  1
6

```
> 2 votes

# Answer
# Perl 6, 35 bytes

```
{+({$_ -first $_%%*,[R,] ^$_}...1)}

```

Try it online!

### How it works

```
{                                 }   # A bare block lambda.
                    [R,] ^$_          # Construct range from arg minus 1, down to 0.
        first $_%%*,                  # Get first element that is a divisor of the arg.
    $_ -                              # Subtract it from the arg.
   {                        }...1     # Do this iteratively, until 1 is reached.
 +(                              )    # Return the number of values generated this way.

```
> 2 votes

# Answer
# Stax, ~~9~~ 7 bytes

```
Åiw^Å♫┌

```

Run and debug it

These two operations are identical.

1. Take the biggest divisor of `n` – which is different from `n` itself – and subtract it from `n`.
2. Let `d` be the smallest prime divisor of `n`. Calculate `n * (d - 1) / d`.

I like #2 better, so let's count how many times we can do that one instead. So at each step, we decrement the smallest prime factor. Let's work an example starting with 30.

```
Step    n   Factors             Operation
0       30  [2, 3, 5]           Replace 2 with 1
1       15  [1, 3, 5] = [3, 5]  Replace 3 with 2
2       10  [2, 5]              Replace 2 with 1
3       5   [1, 5] = [5]        Replace 5 with 4
4       4   [4] = [2, 2]        Replace 2 with 1
5       2   [1, 2] = [2]        Replace 2 with 1
6       1   [1] = []            End of the line

```

From the example we can see a recursive definition for `steps(x)` that solves the problem. Presented here in python-ish pseudo-code.

```
def steps(n):
    pf = primeFactors(n)
    return sum(steps(d - 1) for d in pf) + 1

```

The stax program, unpacked into ascii looks like this.

```
Z       push a zero under the input
|fF     for each prime factor of the input, run the rest of the program
  v     decrement the prime factor
  G     run the *whole* program from the beginning
  +^    add to the running total, then increment

```

Run this one
> 2 votes

# Answer
# Jelly, 8 bytes

```
ÆḌṀạƊƬL’

```

Try it online!

A different approach that takes advantage of Jelly's newer features.

## How it works

```
ÆḌṀạƊƬL’ - Main link. Takes n on the left
    Ɗ    - Group the previous 3 links as a monad f(n):
ÆḌ       -   Proper divisors of n
  Ṁ      -   The largest
   ạ     -   Absolute different with n
     Ƭ   - Repeatedly run f(n) on n, updating n with the result, until
             reaching a fixed point (1), collecting intermediate steps
      L  - Take the length
       ’ - Decrement to account for the 1

```
> 2 votes

# Answer
# C (clang), 45 bytes

```
g;l(f){for(g=f;f%--g;);return f<3?:1+l(f-g);}

```

inspired by this answer to a similar question.

Try it online!
> 2 votes

# Answer
# BQN, 24 bytes

```
{1:0;1+-⊢´↕⊸(⊣/˜0=|)}

```

Anonymous function that takes a number and returns the number of steps. Try it at BQN online!

The algorithm works for any number in theory. In practice, since it constructs a range from 0 to N-1, it runs out of memory for large inputs. For inputs above \\$2^{32}-1\\$, BQN refuses to even make an array that big; but fortunately, the OP has commented that those inputs do not need to be handled.

### Explanation

```
{1:0;1+-⊢´↕⊸(⊣/˜0=|)}
{                       }  Anonymous block function
 1:                        If the argument is 1:
   0                         Return 0
    ;                      Otherwise:
                            Apply the following tacit function to the argument:
             ↕⊸(      )        Use range(argument) as the left arg to this binary function:
                     |         Mod (i.e. take  mod each number in range())
                   0=          Compare each with 0
                ⊣/˜            Keep only the ones that compared equal to 0 (perfect divisors)
          ⊢´                Get the last element of the list of divisors
        -                  Subtract it from the argument
                           Call this function on that value recursively
     1+                     Add 1 to the result

```
> 2 votes

# Answer
# Pyth, ~~17~~ 16 bytes

```
L?tbhy-b*F+1tPb0

```

Try it online! (The `y.v` at the end is for function calling)

---

### Original 17 bytes:

```
L?tb+1y-b*F+1tPb0

```

Try it online! (The `y.v` at the end is for function calling)

(I actually answered that question with this Pyth program.)
> 1 votes

# Answer
## JavaScript (ES6), ~~70~~ 54 bytes

```
f=(n,i=2)=>n<i?0:n%i?f(n,i+1):n>i?f(i)+f(n/i):1+f(n-1)

```

Implementation of the provided recursive formula, but now updated to use recursion to find the divisor too.
> 1 votes

# Answer
# Java (JDK 10), 60 bytes

```
n->{int c=0,d;for(;n>1;c++,n-=d)for(d=n;n%--d>0;);return c;}

```

Try it online!
> 1 votes

# Answer
## Pyke, 11 bytes (noncompeting)

```
D3Phf-oRr;o

```

This uses a new behaviour where if there is an exception raised after a goto, it restores the state from before the goto (except variable definitions) and continues. In this case it is equivalent to the following python code:

```
# Implicit input and variable setup
inp = input()
o = 0
# End implicit
try:
    while 1:
        inp -= factors(inp)[0] # If factors is called on the value 1, it returns an empty
                               # list which when the first element tries to be accessed
                               # raises an exception
        o += 1 # Using `o` returns the current value of `o` and increments it
except:
    print o # This in effect gets the number of times the loop went

```

This is all possible using Pyke without a while loop construction - yay goto!

Try it here!
> 1 votes

# Answer
## Perl, 57 + 1 (`-p` flag) = 58 bytes

```
$n=$_;$n-=$n/(grep!($n%$_),2..$n/2,$n)[0],$\++while$n>1}{

```

Usage:

```
> echo 31 | perl -pe '$n=$_;$n-=$n/(grep!($n%$_),2..$n/2,$n)[0],$\++while$n>1}{'

```

Ungolfed:

```
while (<>) {
# code above added by -p
    # $_ has input value
    # $\ has undef (or 0)
    my $n = $_;
    while ($n > 1) {
        my $d = 1;
        for (2 .. ($n / 2)) {
            if ($n % $_ == 0) {
                $d = $n / $_;
                last;
            }
        }
        $n -= $d;
        $\++;
    }
} {
# code below added by -p
    print;  # prints $_ (undef here) and $\
}

```
> 1 votes

# Answer
## Clojure, ~~98~~ 96 bytes

```
#(loop[n % i -1](if n(recur(first(for[j(range(dec n)0 -1):when(=(mod n j)0)](- n j)))(inc i))i))

```

uses `for` `:when` to find the largest divisor, loops until no such value larger than one is found.
> 1 votes

# Answer
# x86, ~~24~~ 23 bytes

Straightforward implementation of problem. Input in `ecx`, output in `edi`.

I wonder if there's a way to test if `n > 1` in less than 3 bytes...

-1 by using `cdq` to zero `edx`. This requires the input to be a positive signed number (\<=2^31-1), which I think is reasonable.

```
.section .text
.globl main
main:
        mov     $100, %ecx      # n = 100

start:
        xor     %edi, %edi      # result = 0
loop1:
        mov     %ecx, %ebx      # d = n
loop2:
        dec     %ebx            # --d
        mov     %ecx, %eax
        cdq
        div     %ebx            # n % d
        test    %edx, %edx
        jnz     loop2           # do while (n % d)

        inc     %edi            # ++result
        sub     %ebx, %ecx      # n -= d
        cmp     $1, %ecx
        ja      loop1           # do while (n > 1)

        ret

```

Hexdump:

```
00000039  31 ff 89 cb 4b 89 c8 99  f7 f3 85 d2 75 f6 47 29  |1...K.......u.G)|
00000049  d9 83 f9 01 77 ec c3                              |....w..|

```
> 1 votes

# Answer
# Japt v1.4.5, 8 bytes

Had to switch to Japt v1.4.5 and sacrifice a byte to get around a bug with the `â` method in v1.4.6+. `@µk Å×}f` would work for the same bytes count in those versions, but that's just a golfed version of ETH's solution.

```
@Uµâ¬Ì}f

```

Try it
> 1 votes

# Answer
# Husk, 9 bytes

```
LU¡Ṡ-ȯ→hḊ

```

Try it online!
> 1 votes

# Answer
# Haskell, 42 bytes

```
f 1=0
f n=1+f(n-maximum(gcd n<$>[1..n-1]))

```

Try it online!
> 1 votes

# Answer
## Batch, ~~139~~ 136 bytes (Uses LF line delimiters)

```
@set/an=%1-1
:]
@for /l %%n in (1 1 %n%)do @((cmd/c"set/a1/((n+1)%%%%n)")||set[=%%n)>x 2>y
@set/at+=1,n-=[
@if %n% NEQ 0 goto]
@echo %t%

```

`n` should be supplied as the first command line argument `%1`.
`n` is limited to **32-bit** integers.

---

If passing arbitrary command line arguments is allowed, the code above can be shortened by another 6 bytes

## 124 (code) + 6 (extra argument length) = 130 bytes

```
%2n=%1-1
:]
@for /l %%n in (1 1 %n%)do @((cmd/c"%21/((n+1)%%%%n)")||%2[=%%n)>x 2>y
%2t+=1,n-=[
@if %n% NEQ 0 goto]
@echo %t%

```

Run it like `code.bat <n> @set/a`
> 1 votes

# Answer
# Brachylog, 15 bytes

```
;.{fkt;?-ṅ}ⁱ⁾1∧

```

Try it online!

### Explanation

```
;.{       }ⁱ⁾1∧     Iterate <Output> times until you get 1
   f                  Get the factors of the input, ordered
    kt                Take the penultimate one
      ;?-             Subtract the input
         ṅ            Negate

```
> 1 votes

# Answer
# Excel VBA, ~~121~~ ~~110~~ 107 bytes

```
Sub a
o=[A1]
For i=o-1To 1Step-1
If o=WorksheetFunction.Lcm(o,i)Then[A1]=o-i:[B1]=[B1]+1:a
Next
End
End Sub

```

This presumes you start with a new, blank sheet (what you get when you open a new file). Input is in cell `A1`. Output is in cell `B1`. VBA will add spaces automatically then that code is pasted in. It is equivalent to this formatted and commented version:

```
Sub a()
  o = [A1]                                    'Store the starting value to save bytes later
  For i = o - 1 To 1 Step -1                  'Start at 1 less than the starting value and count down
    If o = WorksheetFunction.Lcm(o, i) Then   'If the LCM is the starting value then the current value is a divisor
      [A1] = o - i                            'Subtract the current value from the starting value and set it as the new starting value
      [B1] = [B1] + 1                         'Increase the count by 1
      a                                       'Recurse
    End If
  Next
  End   'You only get here if the for loop was skipped meaning o=1 (since "For i=0 to 1 Step -1" will just skip) so we can end all code now
End Sub

```

The maximum integer value in VBA is 32767 and the program above output 21 given that input as shown in the GIF below (with an added 1 second pause between each calculation).
> 1 votes

# Answer
# dc, 39 bytes

```
0[1+rd[d3R1-d_4R%0<t]dstxr-d_3R1<l]dslx

```

Try it online!

Takes input as number on top of stack, and leaves result as top of stack
> 1 votes

# Answer
# APL, 21 bytes

```
{1=⍵:0⋄1+∇⍵-⍵⌈.∨⍳⍵-1}

```
> 0 votes

# Answer
# PARI/GP, 61 bytes

Try it online!

```
f(1)=0;
f(n)=if(n==1,0,f(n-divisors(n)[#(divisors(n))-1])+1);

```
> 0 votes

# Answer
# PowerShell, 75 bytes

```
param($i)$a=0;while($i-gt1){$i=$i-(($i-1)..1|%{($_)[$i%$_-ne0]})[0];$a++}$a

```

Try it online!
> 0 votes

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


title: Parse a CSV file

text:
# Question
Title: Parse a CSV file
In this challenge, given a CSV file as a string, you'll return the data contained as a 2d array of strings.

**Spec:**

* The input consists of one or more **records**, delimited with `\r\n` (CRLF), `\n` (line feed), or some other reasonable newline sequence of your choice
* A record consists of one or more **fields**, delimited with `,` (commas), `;` (semicolons), `\t` (tabs), or some other reasonable delimiter of your choice. You may assume each record contains the same number of fields
* A field can either be quoted or un-quoted. An un-quoted field will not contain a field delimiter, newline sequence, or quote character, but may otherwise be an arbitrary non-empty string (within reason; you can assume things like invalid UTF-8, null characters, or unpaired surrogates won't appear if doing so is justifiable)
* A quoted string will be delimited on both sides by a quote character, which will be `"` (double quotes), `'` (single quotes), ``` (backticks), or some other reasonable delimiter of your choice. This character will be escaped within the string by being repeated twice (the string unquoted `a"bc` would be represented as `"a""bc"`). Quoted strings may contain field delimiters, newline sequences, escaped quote characters, and any other sequences of characters which may appear in an unquoted field. Quoted strings will always be non-empty
* You may choose to ignore the first record (as if it is a header record)

**Output:**

You may represent a 2d array in any reasonable format (excluding CSV or any of it's variants for obvious reasons).

**Scoring:**

This is , so shortest answer (in bytes) per language wins.

**Test cases:**

In:

```
1,2
abc,xyz

```

Out:

```
[["1","2"],["abc","xyz"]]

```

In:

```
"abc",xyz
"a""bc",""""
",",";"
"
"," "

```

Out:

```
[["abc","xyz"],["a\"bc","\""],[",",";"],["\n"," "]]

```

In:

```
"\
,"""

```

Out:

```
[["\\\n,\""]]

```

$$$$$$$$

# Answer
> 7 votes
# JavaScript (Node.js), 113 bytes

```
s=>s.match(/"([^"]|"")*"|\n|[^,\n]+/g).map(v=>v<' '?t.push(r=[]):r.push(v.replace(/^"|"("?)/g,'$1')),t=[r=[]])&&t

```

Try it online!

# Answer
> 6 votes
# PowerShell, 15 bytes

```
ConvertFrom-Csv

```

Try it online!

Finally something where a rather verbose language like PowerShell can make use of a built-in function.
`ConvertFrom-Csv` covers all the tricky cases.
The test cases in the TIO have an added header record, based on "*You may choose to ignore the first record (as if it is a header record)*"
Output in the TIO both as a table and JSON to show that the input was correctly parsed.

# Answer
> 5 votes
# Factor \+ `csv`, 10 bytes

```
string>csv

```

Try it online!

# Answer
> 4 votes
# Retina 0.8.2, 48 bytes

```
mM!`"([^"]|"")*"|[^,¶]+|$
"(([^"]|"")*)"
$1
""
"

```

Try it online! Retina doesn't have an array type, so I'm just listing each string on its own line with records double-spaced from each other. Explanation:

```
mM!`"([^"]|"")*"|[^,¶]+|$

```

Extract all of the fields, plus insert a blank line at the end of each record.

```
"(([^"]|"")*)"
$1

```

Remove the outer quotes from quoted fields.

```
""
"

```

Unquote the inner quotes.

39 bytes in Retina 1:

```
mL$`"(([^"]|"")*)"|([^,¶]+)|$
$1$3
""
"

```

Try it online! Explanation: Retina 1's `$` flag makes a substitution of the listed matches, collapsing the first two stages of my Retina 0.8.2 program into one.

# Answer
> 3 votes
# Wolfram Language (Mathematica), 21 bytes

```
#~ImportString~"CSV"&

```

Try it online!

# Answer
> 3 votes
# APL (Dyalog APL), 10 bytes

```
{⎕CSV⍵'S'}

```

Attempt This Online!

Builtins ftw. If a filename would a valid input format, just `⎕CSV` would do. The `'S'` indicates input from a \[S\]tring.

# Answer
> 2 votes
# Bash + ShellShoccar-jpn/Parsrs, 9 bytes

```
parsrc.sh

```

Trivial answer.

## Test runs

```
~/wkdir $ parsrc.sh i.1|cat -A
1 1 1$
1 2 2$
2 1 abc$
2 2 xyz$
~/wkdir $ parsrc.sh i.2|cat -A
1 1 abc$
1 2 xyz$
2 1 a"bc$
2 2 ""$
3 1 ,$
3 2 ;$
4 1 \n$
4 2  $
~/wkdir $ parsrc.sh i.3|cat -A
1 1 \\\n,"$
~/wkdir $

```

# Answer
> 2 votes
# Go, 112 bytes

```
import(."encoding/csv";S"strings")
func f(s string)[][]string{o,_:=NewReader(S.NewReader(s)).ReadAll()
return o}

```

Attempt This Online!

Uses the CSV reader from the standard library.

# Answer
> 2 votes
# Haskell \+ hgl, 66 bytes

```
g=χ'

```

```
gk$(g*>my((g<*g)#|nχ '\'')<*g)#|rX"[^,\n]*"$|$ʃ","$|$ʃ NL

```

Attempt This Online!

Uses `'` as a quote delimeter

# Haskell \+ hgl, ~~71~~, 68 bytes

```
g=χ '"'

```

```
gk$(g*>my((g<*g)#|nχ '"')<*g)#|rX"[^,\n]*"$|$ʃ","$|$ʃ NL

```

Attempt This Online!

Uses `"` as a quote delimiter.

## Explanation

First we set up a parser to parse a single quote. We are going to use this a bunch of times:

```
g=χ '"'

```

Now we build a parser for unquoted fields:

```
rX"[^,\n]*"

```

This parses any number of characters that aren't either a comma or a newline using a regex.

Next we have quoted fields, which are parsed with:

```
g*>my((g<*g)#|nχ '"')<*g

```

`g*>...<*g` means it has to start and end with a quote and that those quotes do not contribute to the value.

`g<*g` parses two quotes but returns a single one. `nχ '"'` parses anything other than a quote character. We combine them to get a parser which either parses two quotes or a single non-quote character, but never a single quote. We use `my` to repeat this an arbitrary number of times.

Next we combine these two parsers with `#|`. `#|` means that it will try the first one (quoted field) and then try the second iff the first failed. That means if it finds a legal quoted field it won't bother with unquoted fields. This makes the field parser.

To make a record parser we just interleave `,`s, by adding `$|$ʃ","`. To make the CSV parser we just interleave newlines into our record parser with `$|$ʃ NL`.

Finally once we have a parser we use `gk` to request the first complete parse.

## Reflection

This is very long. There's lots to improve here:

* `χ '"'` and `ʃ"\""` and `χ Nl` and `ʃ NL` should all exist. These are common characters for code golf and it's ridiculous that I have to build these parsers manually.
* In an earlier version I used `kB<fE` to parse any character not in a blacklist. It ended up being shorter to use a regex for this. That means this should definitely exist! And to be honest, I'm a bit shocked it doesn't.
* There should be a version of `cM` which uses `(#|)`. I really feel like there might be, but I can't find it.
* Should probably be something like `sqs x y = x *> y <* x`. This is comes up pretty frequently.
* Regex does help save a couple of bytes here, but it could save way more. The unquoted field parser is a good deal bloated. The suggestions above would help trim things down, but it would be nice if we could have replaced it with a regex. But we can't, because hgl-regex currently can't do what that parser needs to do. The issue is that a hgl regex can only really take a chunk off the front of a string. It can't manipulate that chunk at all. That means `g<*g`, a parser which consumes 2 `"`s but returns only 1, is impossible to express in a regex. I have two solutions to this:
    + Add a `_` modifier to the regex which causes the the group to be ignored from the output. So `(ab)_cd` parses `abcd` but only returns the `cd`. This could be extended to include not just silencing a particular part but also replacing it with a new value. With this the parser could be:
    ```
    rX"\"_(\"_\"|^\")*\"_"

    ```
    or if we chose to use `'` as the quote delimiter:
    ```
    rX"'_('_'|^')*'_"

    ```
    Both options are shorter than the parser we have right now.
    + Add a way to pass a custom parser to be referenced inside a regex:
    ```
    rXw(i$>g)"/p(/p\"|^\")*/p"

    ```
    or if we chose to use `'` as the quote delimiter:
    ```
    rXw(g$>i)"/p(/p'|^')*/p"

    ```
    Both would save bytes, but not compared to the last solution, however this method is way more flexible than the previous solution, since non-regex parsers can be made to do basically anything.

# Answer
> 1 votes
# Python 3, ~~69~~ 59 bytes

```
lambda d:print([*csv.reader(io.StringIO(d))])
import csv,io

```

Try it online!

-10 with thanks to @Neil

Not sure if the output format is valid as it does not exactly match the test cases (uses single quotes around each element). Please comment if not and I can fix it with a `json.dumps()`

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


title: There's more than one way to skin a set

text:
# Question
Title: There's more than one way to skin a set
Given a set of positive integers \\$ S \\$, output the set of all positive integers \\$ n \\$ such that \\$ n \\$ can be made by summing a subset of \\$ S \\$ in more than one different way, i.e., that are the sums of more than one subset of \\$ S \\$.

To be clear, a subset of \\$ S \\$ means that you can't use numbers from \\$ S \\$ more than once.

## Example

For example, given \\$ S = \\{2, 3, 5, 6\\} \\$, the following numbers can be made:

* \\$ 2 = \sum\\{2\\} \\$
* \\$ 3 = \sum\\{3\\} \\$
* \\$ 5 = \sum\\{5\\} = \sum\\{2, 3\\} \\$
* \\$ 6 = \sum\\{6\\} \\$
* \\$ 7 = \sum\\{2, 5\\} \\$
* \\$ 8 = \sum\\{2, 6\\} = \sum\\{3, 5\\} \\$
* \\$ 9 = \sum\\{3, 6\\} \\$
* \\$ 10 = \sum\\{2, 3, 5\\} \\$
* \\$ 11 = \sum\\{5, 6\\} = \sum\\{2, 3, 6\\} \\$
* \\$ 13 = \sum\\{2, 5, 6\\} \\$
* \\$ 14 = \sum\\{3, 5, 6\\} \\$
* \\$ 16 = \sum\\{2, 3, 5, 6\\} \\$

Of these, only \\$ 5 \\$, \\$ 8 \\$, and \\$ 11 \\$ can be made in more than one way. Therefore, `[5, 8, 11]` is the output.

## Rules

* The input will be non-empty and contain no duplicate numbers
* Output may be in any order, but it must not contain duplicate numbers
* You may use any standard I/O method
* Standard loopholes are forbidden
* This is , so the shortest code in bytes wins

## Test cases

```
[1]                   -> []
[4, 5, 2]             -> []
[9, 10, 11, 12]       -> [21]
[2, 3, 5, 6]          -> [5, 8, 11]
[15, 16, 7, 1, 4]     -> [16, 20, 23, 27]
[1, 2, 3, 4, 5]       -> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

```

# Answer
> 7 votes
# BQN, 15 bytesSBCS

```
(1=⊒)⊸/·⥊(∾∾+)˝

```

Run online!

---

# BQN, 19 bytesSBCS

```
(1=⊒)⊸/<+´∘×¨⟜⥊⟜↕2¨

```

Run online!

A 2 for each value in the input array.
Indices of an array of shape 2 × ... × 2. These are all combinations of 0's and 1's of the length of the input.
Flatten into a list of lists.
`< ×¨` Multiply each of the indices with the input element-wise.
Take the sum of each result.
`(1=⊒)⊸/` Keep only elements which occur the second time.

# Answer
> 7 votes
# Wolfram Language (Mathematica), ~~34~~ 33 bytes

```
Set@@@Gather[Tr/@Subsets@#]⋃{}&

```

Try it online!

```
             Tr/@Subsets@#      subset sums
      Gather[             ]     group by value
Set@@@                          drop first per group and join
                           ⋃{}  union (unique)

```

In normal usage, `Set` is just assignment, e.g. `Set[a,1]` ~ `a=1`, returning the assigned value. Importantly,

* It always returns that assigned value, even when the assignment target is invalid, and
* When called with ≠2 arguments, it reasonably interprets that as assigning a target to a `Sequence` of the remaining arguments, i.e. `Set[a,1,2]` ~ `a=Sequence[1,2]`.
(On a side note, Mathics does *not* do this, possibly because `Set` already has `SequenceHold`)

Together, these mean that `Set` can (usually) replace `##2&` to save one byte.

# Answer
> 5 votes
# Vyxal, 8 bytes

```
ṗṠsĠ~Ḣvh

```

Try it online or run all test cases.

`sĠ~Ḣvh` is the shortest way I can think of to keep only duplicates, so...

`~Ḣvh` could alternatively be `vḢfU` for same byte count.

## How?

```
ṗṠsĠ~Ḣvh
ṗ        # Powerset of (implicit) input
 Ṡ       # Sum of each
  s      # Sort
   Ġ     # Group consecutive identical items
    ~    # Filter for:
     Ḣ   #  Remove the head (this means if it is only one item long, it will be falsey, else truthy)
      vh # Get the first item of each

```

# Answer
> 5 votes
# , 66 bytes

```
\(S,t=table(unlist(Map(\(i)combn(S,i,sum),seq(!S)))))names(t[t>1])
```

Attempt This Online!

# Answer
> 4 votes
# JavaScript (V8), 69 bytes

```
a=>(g=([v,...a],s=0)=>v?g(a,s+v)|g(a,s):(g[s]=-~g[s])-2||print(s))(a)

```

Try it online!

### Commented

```
a => (              // a[] = input array
  g = (             // g is a recursive function taking:
    [v,             //   v = next value
        ...a],      //   a[] = remaining values
    s = 0           //   s = sum
  ) =>              //
  v ?               // if v is defined:
    g(a, s + v) |   //   do a recursive call where v is added to s
    g(a, s)         //   do a recursive call where s is left unchanged
  :                 // else:
    (g[s] = -~g[s]) //   using g as an object, increment a counter for
                    //   the sum s
    -2 ||           //   if this is the 2nd time we reach this sum:
      print(s)      //     print it
)(a)                // initial call to g

```

# Answer
> 4 votes
# , 28 19 bytes

```
[:~.@(#~1-~:)(,,+)/

```

Try it online!

*-9 thanks to ovs for the `(,,+)/` trick for calculating all subset sums!*

* `(,,+)/` All subset sums
* `[:(#~1-~:)` Keep only repeats
* `~.@` Dedup

# Answer
> 3 votes
# Jelly, 8 bytes

```
ŒP§œ-Q$Q

```

Try it online!

## How it works

```
ŒP§œ-Q$Q - Main link. Takes S on the left
ŒP       - Powerset of S
  §      - Sum of each
      $  - To the list of sums:
     Q   -   Deduplicate
   œ-    -   Set difference
       Q - Deduplicate

```

# Answer
> 3 votes
# Desmos, 96 bytes

```
n=L.length
S=[total(floor(mod(i/2^{[0...n]},2))L)fori=[0...2^n-1]].sort
f(L)=S[S[2...]=S].unique

```

Try it on Desmos!

### How it works

Conceptually similar to Steffan's Vyxal solution but lacks builtins :)

```
S=[total(floor(mod(i/2^{[0...n]},2))L)fori=[0...2^n-1]].sort
 for i=[0...2^n-1]                        # Powerset of input as bitmasks
  total(floor(mod(i/2^{[0...n]},2))L)     # Sum of each
  .sort                                   # Sort
f(L)=
 S[        ]        # Filter for:
  S[2...]=S         # Next element is equal to current element
            .unique # Remove duplicates

```

Note on the slice comparison: `S[2...]` is the list `S` except for the first element. Since broadcasting takes the shorter list, `S[2...]=S` is equivalent to `S[2...n]=S[1...n-1]`, or `[{S[i+1] = S[i]} for i=[1...n-1]] = 1`.

# Answer
> 3 votes
# Attache, 33 bytes

```
${{_~x>1}\Unique@x}##Sum=>Subsets

```

Try it online!

*Happy 1,000 answers on this site to me?*

## Explanation

```
${{_~x>1}\Unique@x}##Sum=>Subsets    pure function
                          Subsets    get all Subsets
                     Sum=>           and map Sum to each subset
                   ##                then
${                }                  x = the set of subsets sums
          Unique@x                   get those unique sums
  {     }\                           and filter each sum
   _~x                               ...by counting how often it appears in x
      >1                             ...and asserting it is more than 1

```

## Other approaches

Unfortunately, while there are a few builtins which have similar behavior, wrangling them into a manageable format proves to be too verbose.

**50 bytes:** `Flat@Betail@{Commonest[_,1:#_]^^nil}##Sum=>Subsets`

**39 bytes:** `${{_&Count!x>1}\Unique@x}##Sum=>Subsets`

**38 bytes:** `First=>{_@1@1}\Positions##Sum=>Subsets`

**37 bytes:** ``@&0=>{_@1@1}\Positions##Sum=>Subsets`

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

```
a->[k-1|c<-Vec(prod(i=!k=0,#a,1+x^a[i])),c>#k++]
```

Attempt This Online!

Using generating functions. For input \\$\\{a\_1,\dots,a\_n\\}\\$, finds all \\$k\\$s such that the coefficient of \\$x^k\\$ in \\$\prod\_{i=1}^n(1+x^{a\_i})\\$ is greater than \\$1\\$.

# Answer
> 2 votes
# Factor \+ `math.combinatorics math.unicode`, 37 bytes

```
[ all-subsets [ Σ ] map duplicates ]

```

Try it online!

# Answer
> 2 votes
# Haskell, 120 bytes

```
g(s,d)i=(i:s,if i`elem`s&&i`notElem`d then i:d else d)
f c=snd.foldl g([],[])$map(sum.zipWith(*)c)(sequence[[0,1]|_<-c])

```

Try it online!

* `g :: ([Int], [Int]) -> Int -> ([Int], [Int])` is a straightforward function which keeps track of all 'seen' integers in the first list in the tuple, and all 'duplicates' in the second list.
* `sequence [[0,1] | _ <- c]` generates the Cartesian product of *n* copies of `[0, 1]`, where *n* is the length of the input, i.e. it generates all permutations of 0 and 1 with length *n*.
* `map (sum . zipWith (*) c)` takes the dot product of each of these permutations with the input, which generates all possible sums (plus a stray zero, which is inconsequential, since the input is positive).

# Answer
> 2 votes
# Python, ~~79~~ 75 bytes

-4 bytes thanks to pxeger!

```
def f(a,*o):
 for x in a:
  for d in*o,0:o.count(v:=x+d)==1!=print(v);o+=v,
```

Attempt This Online!

---

# Python 2, 102 bytes

Much longer, but more fun ;) (and much faster)

```
s=1;p=0
for x in input():
 r=s&s<<x&~p|p<<x&~s;p|=r;s|=s<<x;k=0
 while r:
  if r%2:print k
  r/=2;k+=1
```

Attempt This Online!

# Answer
> 2 votes
# SageMath, 123 bytes

Golfed vesrion. Run it on SageMathCell!

```
def f(a):return[k for k,m in enumerate(prod(1+PolynomialRing(QQ,'x').gen()^b for b in a).coefficients(sparse=False))if m>1]

```

Ungolfed vesrion. Run it on SageMathCell!

```
def find_ks(a):
    # Create a polynomial ring
    R = PolynomialRing(QQ, 'x')
    x = R.gen()

    # Calculate the generating function
    gen_function = prod(1 + x^a_i for a_i in a)

    # Find the coefficients of the generating function
    coeffs = gen_function.coefficients(sparse=False)

    # Iterate over the coefficients and return the k-values for which the coefficients are greater than 1
    ks = [k for k, coeff in enumerate(coeffs) if coeff > 1]

    return ks

input_lists = [[1], [4, 5, 2], [9, 10, 11, 12], [2, 3, 5, 6], [15, 16, 7, 1, 4], [1, 2, 3, 4, 5]]

for a in input_lists:
    print(f"{a} -> {find_ks(a)}")

```

Using generating functions. For input \\$\\{a\_1,\dots,a\_n\\}\\$, finds all \\$k\\$s such that the coefficient of \\$x^k\\$ in \\$\prod\_{i=1}^n(1+x^{a\_i})\\$ is greater than \\$1\\$.

# Answer
> 1 votes
# Python 3.8, 152 bytes

*-5 bytes thanks to `ovs`, -4 bytes thanks to `pxeger`, and -2 bytes thanks to `AndyB`*

Outputs a set of numbers or an empty `set()` if the condition is not met.

```
lambda s:(r:=range(len(s)))and{T(l)for j in r for l in c(s,j+1)if T(T(k)==T(l)for i in r for k in c(s,i+1))>1}
from itertools import*;c=combinations;T=sum

```

Attempt This Online!

# Answer
> 1 votes
# Burlesque, 12 bytes

```
R@)++JNB\\NB

```

Try it online!

```
R@     # All subsequences
)++    # Map sum
J      # Dup
NB     # Remove duplicates
\\     # List elements in set A not in B
NB     # Remove duplicates

```

# Answer
> 1 votes
# Python 3, 106 bytes

```
g=lambda s:{s}|{q for n in s for q in g(s-{n})}
def f(s):*q,=map(sum,g(s));*map(q.remove,{*q}),;return{*q}

```

Try it online!

Requires a `frozenset` as input.

# Answer
> 1 votes
# 05AB1E, 7 bytes

```
æOÐ¢≠ÏÙ

```

Try it online or verify all test cases.

Or alternatively:

```
æO{Åγ≠Ï

```

Try it online or verify all test cases.

**Explanation:**

```
æ        # Get the powerset of the (implicit) input-list
 O       # Sum each inner list
  Ð      # Triplicate it
   ¢     # Pop the top two, and get the counts of each item
    ≠    # Check which counts are NOT 1 (thus >= 2)
     Ï   # Only keep those values from the remaining list
      Ù  # Uniquify it
         # (after which the result is output implicitly)

æO       # Same as above
  {      # Sort them
   Åγ    # Pop and run-length encode this list, pushing the list of values and
         # list of counts as two separated lists
     ≠Ï  # Same as above
         # (after which the result is output implicitly)

```

# Answer
> 1 votes
# Brachylog, 13 bytes

```
⊇ᶠ+ᵐ{⊇Ċ=}ᶠhᵐd

```

Try it online!

### Explanation

```
⊇ᶠ               Find all subsets of the input
  +ᵐ             Compute the sum for each of these subsets
    {   }ᶠ       Find all:
     ⊇Ċ=           Subset of 2 elements which are equal
          hᵐ     Get the head of each of these subsets
            d    Remove duplicates (necessary if 3 or more subsets sum to the same number)

```

There are other similar approaches which are also 13 bytes, such as `⊇ᶠ+ᵐọ{t>1&h}ˢ` or `⊇ᶠ+ᵍ{l>1&h+}ˢ`.

# Answer
> 1 votes
# Desmos, 148 bytes

```
L=[∑_{n=1}^{2^{l.length}-1}bfori=[0...l.total]]
b=\{\total(l\mod(\floor(2n/{2^{[l.\length...1]}}),2))=i,0\}
K=[0...L.\length]\{L>1,0\}
f(l)=K[K>0]

```

Try It On Desmos!

Try It On Desmos! - Prettified

# Answer
> 1 votes
# Charcoal, 21 bytes

```
⊞υ⁰ＦＡＦ⁺υι⊞υκＩΦ⌈υ‹¹№υι

```

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

```
⊞υ⁰

```

Start with `0` as the sum of the empty subset of `S`.

```
ＦＡ

```

Loop over the elements of `S`.

```
Ｆ⁺υι⊞υκ

```

Add the element to all of the existing sums and append the results.

```
ＩΦ⌈υ‹¹№υι

```

Output the values that occur more than once.

# Answer
> 1 votes
# Japt, 12 bytes

```
à mx ü lÉ câ

```

Try it

# Answer
> 1 votes
# Zsh, 75 bytes

```
for i;a=({$i,}+0$^a)
for s ($a)((++S[s]))
for s ("$S[@]")((++k,s>1))&&<<<$k

```

Try it online!

Accidentally out-golfed my old power set implementation, whoops! :)

```
for i
    a=({$i,}+0$^a)       # Recursively generate sum strings (e.g.: +0+02+0+04)
for s ($a)
    ((++S[s]))           # Count how many times a sum occurs
for s ("$S[@]")
    ((++k,s>1))&&<<<$k   # If sum $k is bigger than 1, print $k.

```

# Answer
> 1 votes
# T-SQL, 114 bytes

Using a table variable as input

```
WITH D(s,b)as(SELECT*FROM @
UNION ALL SELECT
S+Q,L
FROM @,D WHERE b<l)SELECT
s FROM D GROUP BY s HAVING SUM(1)>1

```

**Try it online**

# Answer
> 1 votes
# C (clang), ~~131 129~~ 123 bytes

*saved 2 bytes thanks to @ceilingcat*

```
*c,i,j;f(*a,n){for(i=n,j=1;i--;)c=calloc(j+=a[i],8);for(i=n*j,*c=1;j;)i?c[i%j+a[i/j]]+=c[--i%j]:c[--j]>1&&printf("%d ",j);}

```

This leaks horribly. Try it online!

# Answer
> 1 votes
# Haskell + hgl, 17 bytes

```
(!!1)~<<bg<fo<<ss

```

## Explanation

* `ss` get all subsequences
* `fo` sum them
* `bg` group like elements
* `(!!1)` get the second element from each group

`(!!1)~<<bg` appeared in this answer previously as a way to get all elements that appear more than once.

## Reflection

If you click on the linked answer you can see in that answer I said:

> `(!!)` should have a prefix function, and a bunch of versions with the index prefilled. I noticed this earlier but still didn't fix it, and now it's coming back to haunt me.

Well guess what, I *still* haven't fixed it, and it's still losing me bytes.

On top of that the fact that I've used the exact same code `(!!1)~<<bg` now in two different answers is probably a good indicator that it should receive a standalone function.

# Answer
> 1 votes
# Arturo, 58 bytes

```
$=>[powerset&|map=>sum|tally|select[k,v]->v>1|map[k,v]->k]

```

Try it

# Answer
> 1 votes
# Stax, 14 bytes

```
ü÷┬┼╔ª8┐b▼¶╦S╟

```

Run and debug it

definitely golfable, cant seem to find any way to right now

unpacked:

# Stax, 16 bytes

```
S{|+mX{x#1=!fu|u

```

Run and debug it

```
S{|+mX{x#1=!fu|u # whole program taking input array S
S                # powerset of S
 {  m            # across this powerset, map...
  |+             # sum
      {     f    # and filter it by
     X x#        # the count of the element in the summed powersets
          =!     # is not equal to
         1       # 1
             u   # uniquify
              |u # uneval, produces string representation of array (no idea if this is required or not, otherwise stax outputs the array as an array of charcodes)

```

---
Tags: code-golf, number, set-partitions, integer-partitions
---