17
\$\begingroup\$

Background

Binomial transform is a transform on a finite or infinite integer sequence, which yields another integer sequence. The binomial transform of a sequence \$\{a_n\}\$ is given by

$$s_n = \sum_{k=0}^{n}{(-1)^k \binom{n}{k} a_k}$$

It has an interesting property that applying the transform twice will yield the original, i.e. the transform is an involution.

Example

Take the sequence 1, 3, 9, 27, 81. The binomial transform of this sequence is computed as follows:

$$ \begin{align} s_0 &= a_0 = 1\\ s_1 &= a_0 - a_1 = -2\\ s_2 &= a_0 - 2a_1 + a_2 = 4\\ s_3 &= a_0 - 3a_1 + 3a_2 - a_3 = -8\\ s_4 &= a_0 - 4a_1 + 6a_2 - 4a_3 + a_4 = 16 \end{align} $$

So the binomial transform of 1, 3, 9, 27, 81 is 1, -2, 4, -8, 16. Verifying that the binomial transform of 1, -2, 4, -8, 16 is indeed 1, 3, 9, 27, 81 is left as an exercise to the reader.

Task

Compute the binomial transform of a given finite integer sequence.

Standard rules apply. The shortest code in bytes wins.

Test cases

Note that each test case works in both directions, i.e. if the left side is given as input, then the right side must be output, and vice versa.

[0] <-> [0]
[20, 21] <-> [20, -1]
[1, 3, 9, 27, 81] <-> [1, -2, 4, -8, 16]
[20, 21, 6, 15, 8, 48] <-> [20, -1, -16, -40, -80, -183]
[0, 1, 2, 3, 4, 5, 6] <-> [0, -1, 0, 0, 0, 0, 0]
[0, 1, 1, 2, 3, 5, 8, 13, 21]
    <-> [0, -1, -1, -2, -3, -5, -8, -13, -21]
[1, 1, 0, -1, -1, 0, 1, 1, 0, -1, -1, 0]
    <-> [1, 0, -1, -1, 0, 1, 1, 0, -1, -1, 0, 1]
\$\endgroup\$
2
  • \$\begingroup\$ Must we handle the case of integer sequences of length 0? \$\endgroup\$ – NoLongerBreathedIn Jun 19 at 19:10
  • \$\begingroup\$ No, you can assume the input is not empty. \$\endgroup\$ – Bubbler Jun 20 at 3:13

20 Answers 20

13
\$\begingroup\$

Jelly, 5 bytes

_ƝƬZḢ

Try it online!

_ƝƬZḢ  Main Link
  Ƭ    While results are unique (until we hit the empty list)
 Ɲ     To each (overlapping) pair,
_      Subtract
   Z   Zip; columns to rows
    Ḣ  The first column

On the Wikipedia page, it says that the binomial transform is just the Nth forward differences. So, we just keep getting the difference array until we hit the empty list and stop, and then just grab the left column.

\$\endgroup\$
9
\$\begingroup\$

Python 3.8, 45 bytes

def f(h,*t):print(h);f(*[h-(h:=x)for x in t])

Try it online!

Takes input splatted like f(1,2,3), outputs by printing entries one per line, terminates with error.

Computes repeated differences, taking advantage of the Python 3.8 walrus operator := to do so in a list comprehension.

\$\endgroup\$
1
  • \$\begingroup\$ As usual you nailed it..... \$\endgroup\$ – wasif Jun 16 at 1:58
7
\$\begingroup\$

K (ngn/k), 12 bytes

,/*'(-/'2')\

Try it online!

  • (...)\ run a converge-scan, repeating until consecutive executions return the same result, or a result matches the initial input
  • -/'2' take the forward differences
  • ,/*' take the first value of each row, and flatten to remove the trailing empty list, ()
\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6),  47  45 bytes

Using forward differences, as hyper-neutrino first did.

Returns a comma-separated string.

f=([n,...a])=>a+a?n+[,f(a.map(v=>n-(n=v)))]:n

Try it online!

How?

At each iteration, we extract the leading term \$n\$ of the array, append it to the final output and do recursive calls with the forward differences until the array is empty.

Example:

[   20,   21,    6,   15,    8,   48 ] < input
[   -1,   15,   -9,    7,  -40 ]
[  -16,   24,  -16,   47 ]
[  -40,   40,  -63 ]
[  -80,  103 ]
[ -183 ]
     ^
   output

JavaScript (ES6), 74 bytes

A naive implementation that actually computes the binomial coefficients.

a=>a.map((_,n)=>a.reduce((t,v,i)=>t+(g=k=>k?g(--k)*(k-n)/~k:i&1?-v:v)(i)))

Try it online!

\$\endgroup\$
4
\$\begingroup\$

J, 13 bytes

-/@:*!/~@i.@#

Try it online!

For e.g. 1 3 9 27:

!/~@i.@# table of bionimal coefficients

1 1 1 1
0 1 2 3
0 0 1 3
0 0 0 1

* times the input

1 1 1  1
0 3 6  9
0 0 9 27
0 0 0 27

-/@: reduce bottom to top with minus

  1 1 1  1 => + 1 1 1  1
- 0 3 6  9    - 0 3 6  9
- 0 0 9 27    + 0 0 9 27
- 0 0 0 27    - 0 0 0 27
              ----------
                1_2 4 _8
\$\endgroup\$
4
\$\begingroup\$

Factor, 48 bytes

[ [ dup first . differences vneg ] until-empty ]

Try it online!

Output the first member of the input sequence to stdout followed by a newline, take the differences, and flip the sign of each element until empty.

\$\endgroup\$
4
\$\begingroup\$

R, 45 bytes

function(x)for(i in x){show(x[1]);x=-diff(x)}

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ Recursive 44-byter... \$\endgroup\$ – Dominic van Essen Jun 16 at 8:12
  • \$\begingroup\$ @DominicvanEssen - post it! I tried recursion, but somehow it all came out longer... \$\endgroup\$ – pajonk Jun 16 at 8:54
4
\$\begingroup\$

Charcoal, 18 bytes

Wθ«I…θ¹≔EΦθλ⁻§θλκθ

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

Wθ«

Repeat until there are no more terms.

I…θ¹

Output the next term on its own line.

≔EΦθλ⁻§θλκθ

Calculate reverse differences.

The binomial transform can be represented as a sort of reverse Pascal's Triangle where each value is the sum of the two below (here using the original 1, 3, 9, 27, 81 example):

             1
          3    -2
       9    -6     4
   27   -18    12    -8
81   -54    36   -24    16

The transform then appears on the rightmost entries on each row. Since addition is commutative, the symmetry demonstrates that transform is thus an involution.

The above code calculates the transform by calculating the bottomleft-topright diagonals in turn from topleft to bottomright. It's also possible to calculate the topleft to bottomright diagonals in turn from bottomleft to topright. The natural code to do this in Charcoal would normally take 17 bytes but unfortunately a combination of factors prevents this from working:

F⮌θ≔⁻ιE⊕LυΣ…υλυIυ

Don't try it online! Explanation:

F⮌θ

Loop over the terms in reverse order.

≔⁻ιE⊕LυΣ…υλυ

Theoretically calculate the next diagonal by vectorised subtraction of sums of prefixes (i.e. cumulative sums but including a leading zero term) from the next term. This doesn't work because a) Charcoal can't calculate CycleChop([], 0) at all and b) Charcoal returns None for Sum([]). The cheapest fix for both of these is to use And(l, ...) at a cost of 2 bytes to avoid trying to sum the empty prefix at all, or alternatively each issue can be worked around separately at a cost of 1 byte each.

Iυ

Output the final diagonal.

\$\endgroup\$
3
\$\begingroup\$

Stax, 10 7 bytes

É¿F▒x"╢

Run and debug it

the lack of a short method to get fixpoint made this a bit more interesting.

Explanation

rwcHP:-c
r        reverse
 w       do-while top of stack is truthy
  cHP     print last element of the array
     :-   get deltas (returns [] for 2-element arrays)
       c  copy
\$\endgroup\$
3
\$\begingroup\$

Vyxal, 5 bytes

⁽¯↔vh

Try it Online!

Me when very many yes.

\$\endgroup\$
1
2
\$\begingroup\$

Jelly, 10 bytes

J’cþ`NÐeZḋ

Try it online!

Explanation

J          | 1..length of sequence
 ’         | Decrement by 1
  cþ`      | Outer product using nCr
     NÐe   | Negate even indices
        Z  | Transpose
         ḋ | Dot product with input
\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog Unicode), 27 bytes

,\(+/⊣×⊢(!⍨ׯ1*⊢)1⍳⍤+⊢)¨⍳∘≢

Try it online!

I was too lazy to read the article, here's a stupid solution. I don't know why it doesn't work in TIO, but it does work on my computer. Requires zero-indexing.

\$\endgroup\$
4
  • \$\begingroup\$ I think you forgot to set ⎕IO←0 in the header. Also having an R there looks pretty sus, so I suggest to change it to the actual symbol (just in the post). \$\endgroup\$ – Bubbler Jun 15 at 23:19
  • \$\begingroup\$ @Bubbler Oh yeah, let me change those \$\endgroup\$ – user Jun 15 at 23:21
  • \$\begingroup\$ {⊃2-/⍣⍵⊢a}¨⍳≢a←⎕ \$\endgroup\$ – rak1507 Jun 15 at 23:22
  • \$\begingroup\$ @rak1507 That's a lot better than mine, you should post your own answer :) \$\endgroup\$ – user Jun 15 at 23:27
2
\$\begingroup\$

Python 3, 62 bytes

f=lambda a:len(a)>1and f([x-y for x,y in zip(a,a[1:])])or a[0]

Try it online!

Recursive deltas until one element left.

\$\endgroup\$
2
\$\begingroup\$

Red, 95 bytes

func[v][v: make vector! v until[print v/1 u: copy v
move back tail u u take v: u - v empty? v]]

Try it online!

\$\endgroup\$
2
\$\begingroup\$

R, 44 bytes

f=function(x)if(sum(x|1))c(x[1],f(-diff(x)))

Try it online!

Recursive function, taking inspiration from pajonk's answer.

\$\endgroup\$
2
\$\begingroup\$

Japt -g, 9 bytes

Nc¡=ä-})y

Try it

Nc¡=ä-})y     :Implicit input of array U
N             :Array of all inputs
 c            :Concatenate
  ¡           :  Map U
   =          :    Reassign to U
    ä-        :    Consecutive pairs, reduced by subtraction
      }       :  End map
       )      :End concat
        y     :Transpose
              :Implicit output of first element
\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 34 31 bytes

(a=Most@a-{##2};#)&@@a&/@(a=#)&

Try it online!

Uses the differences method.

                         (a=#)  assign a to input
                       /@       step through input:
 a=Most@a-{##2};                    update a to its forward differences
(               #)&@@a&             while taking its first element (pre-update)
\$\endgroup\$
1
\$\begingroup\$

Ruby, 49 43 42 bytes

f=->a{k,*a=a;k ?[k]+f[a.map{|x|k-k=x}]:[]}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Java (JDK), 69 bytes

a->{for(int l=a.length,i=0,j;++i<l;)for(j=l;j-->i;)a[j]=a[j-1]-a[j];}

Try it online!

\$\endgroup\$
0
0
\$\begingroup\$

MMIX, 52 bytes (13 instrs)

Prototype: void __mmixware bintran(int64_t *seq, size_t len)

jxd:

00000000: 3b020101 5a010002 f8000000 27020201  ;£¢¢Z¢¡£ẏ¡¡¡'££¢
00000010: 2c030200 8d040308 8dff0300 2604ff04  ,¤£¡⁽¥¤®⁽”¤¡&¥”¥
00000020: ad040308 5b02fffa 27010101 e7000008  Ḍ¥¤®[£”«'¢¢¢ḃ¡¡®
00000030: f0fffff4                             ṅ””ṡ

Disassembly:

bintran SUB   $2,$1,1       // i = len - 1
        PBNZ  $2,0F         // if(i) goto loop
        POP   0,0           // return
0H      SUBU  $2,$2,1       // loop: i--
        8ADDU $3,$2,$0      // int64_t t = seq + i
        LDO   $4,$3,8       // a = t[1]
        LDO   $255,$3,0     // b = t[0]
        SUBU  $4,$255,$4    // a = b - a
        STO   $4,$3,8       // t[1] = a
        PBNZ  $2,0B         // if(i) goto loop
        SUBU  $1,$1,1       // len--
        INCL  $0,8          // seq++
        JMP   bintran       // bintran(seq, len) (tail recursion eliminated)

If you wish to add early exit on zero length, this costs four bytes more.

bintran BZ   $1,1F
2H      PBNZ $2,0F
1H      POP  0,0
0H      SUBU $2,$2,1
        (etc)
        JMP  2B

The resulting machine code is identical except by prefixing of 42010001 (B¢¡¢).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.