Double-reduce a sequence of integers

Question

Consider a function \$r\$ where

$$ r(i,k)= \begin{cases} L_{i+1}-L_i, & \text{if}\ k =0\ \text{ (1st reduction)} \\ r(i,0)-r(\lfloor \log_2{k} \rfloor,k-2^{\lfloor \log_2{k} \rfloor}) & \text{if}\ k \geq 1\ \text{ (2nd reduction)} \end{cases} $$

where \$k<2^i\$ and \$L\$ is a finite sequence of integers.

For example, assuming that \$L = \{0, 1, 1, 2, 3, 5\}\$,

for \$i=0\$,

• \$r(0,0) = L_1-L_0 = 1-0 = 1\$.

for \$i=1\$,

• \$r(1,0) = L_2-L_1 = 1-1 = 0\$.
• \$r(1,1) = r(1,0)-r(0,0) = 0-1 = -1\$.

for \$i=2\$,

• \$r(2,0) = L_3-L_2 = 2-1 = 1\$.
• \$r(2,1) = r(2,0)-r(0,0) = 1-1 = 0\$.
• \$r(2,2) = r(2,0)-r(1,0) = 1-0 = 1\$.
• \$r(2,3) = r(2,0)-r(1,1) = 1+1 = 2\$.

The double-reduction of \$L\$ is created by concatenating results from \$i=0\$, \$i=1\$, ..., until every consecutive pair of elements of \$L\$ are visited.

In layperson's terms, this function subtracts two consecutive terms of \$L\$, and then subtract every previous-calculated subtraction from that result. Note that every call of \$r(i,k)\$, for \$i>0\$ and \$k>0\$, is already computed.

Input

A list of integers L. You can assume its size will be always greater or equal to 3.

Output

A sequence representing the double-reduction of L.

• Indexing: Both \0ドル\$- and \1ドル\$-based indexing are allowed, and the following rules can be applied with both these types of indexing.
• Format: The answers can use one of the following output methods:
  • Given some index \$n\$, it can return the \$n\$-th entry of the list.
  • Given some index \$n\$, it can return all entries up to the \$n\$-th one in the sequence.
  • Without taking any index, it can output all entries by printing them one by one or by returning a list.

Test cases

Here's the test cases for positive numbers, even numbers, prime numbers, Fibonacci numbers, power-of-2 numbers, lucky numbers and signed Fibonacci numbers, respectively:

[1, 2, 3] -> [1, 1, 0]
[2, 4, 6, 8] -> [2, 2, 0, 2, 0, 0, 2]
[2, 3, 5, 7, 11] -> [1, 2, 1, 2, 1, 0, 1, 4, 3, 2, 3, 2, 3, 4, 3]
[0, 1, 1, 2, 3, 5] -> [1, 0, -1, 1, 0, 1, 2, 1, 0, 1, 2, 0, 1, 0, -1, 2, 1, 2, 3, 1, 2, 1, 0, 1, 2, 1, 0, 2, 1, 2, 3]
[1, 2, 4, 8, 16, 32] -> [1, 2, 1, 4, 3, 2, 3, 8, 7, 6, 7, 4, 5, 6, 5, 16, 15, 14, 15, 12, 13, 14, 13, 8, 9, 10, 9, 12, 11, 10, 11]
[1, 3, 7, 9, 13, 15, 21] -> [2, 4, 2, 2, 0, -2, 0, 4, 2, 0, 2, 2, 4, 6, 4, 2, 0, -2, 0, 0, 2, 4, 2, -2, 0, 2, 0, 0, -2, -4, -2, 6, 4, 2, 4, 4, 6, 8, 6, 2, 4, 6, 4, 4, 2, 0, 2, 4, 6, 8, 6, 6, 4, 2, 4, 8, 6, 4, 6, 6, 8, 10, 8]
[0, 1, -1, 2, -3, 5, -8] -> [1, -2, -3, 3, 2, 5, 6, -5, -6, -3, -2, -8, -7, -10, -11, 8, 7, 10, 11, 5, 6, 3, 2, 13, 14, 11, 10, 16, 15, 18, 19, -13, -14, -11, -10, -16, -15, -18, -19, -8, -7, -10, -11, -5, -6, -3, -2, -21, -20, -23, -24, -18, -19, -16, -15, -26, -27, -24, -23, -29, -28, -31, -32]

Your solution should be implemented with fewest bytes as possible.

_{Brownie points for beating or matching my 70-bytes Python answer.}

Answer 1

Charcoal, 24 bytes

⊞υ0FEΦθκ−ι§θκ≔+υ−ιυυIΦυκ

Try it online! Link is to verbose version of code. Explanation: Adapted from both @Arnauld's and @loopywalt's answers.

⊞υ0

Start with a list of just 0.

FEΦθκ−ι§θκ

Loop over the list of differences of the input array.

≔+υ−ιυυ

Subtract all of the elements of the output array from the current difference and then concatenate the result onto the output array.

IΦυκ

Output all but the first element of the output array.

Answer 2

Python, 63 bytes

f=lambda l,*L,a=[]:L and f(*L,a=a+[L[0]-l-b for b in[0]+a])or a

Attempt This Online!

Takes splatted input. Returns the entire double-reduction.

How?

Once one all but ignores the confusing double indexing there is an obvious rather simple recursion.

Answer 3

JavaScript (ES6), 61 bytes

An implementation of what the function really does, as described in the layman's terms paragraph of the challenge.

a=>a.map(v=>a=[0,...b].map(k=>1/a&&b.push(v-a-k))&&v,b=[])&&b

Try it online!

Commented

a => // a[] = input
a.map(v => // for each value v in a[]:
 a = // update a:
 [0, ...b] // for 0 and each value in b[]
 .map(k => // loaded in k:
 1 / a // do nothing if this is the 1st iteration,
 && // i.e. a is still the input array (*)
 b.push( // otherwise, push in b[]:
 v - a - k // the current value, minus the previous one,
 ) // minus k
 ) // end of inner map()
 && v, // save v in a
 b = [] // start with b[] = empty array
) // end of outer map()
&& b // return b[]

_{(*) The input is guaranteed to contain at least 3 integers, as per the challenge rules. So it can't be coerced to a number.}

---

JavaScript (V8), 92 bytes

This was an attempt at implementing the definition literally.

L=>{for(n=1;L[-~(g=Math.log2)(n)];)print((r=k=>~(k-=2**(i=~~g(k)))&&L[i+1]-L[i]-r(k))(n++))}

Try it online!

Answer 4

Haskell, 48 bytes

r a[_]=a
r a(x:y:l)=r(a++[y-x-z|z<-0:a])$y:l
r[]

Answer 5

05AB1E, 10 bytes

Î\vDyα‚ ̃}¦

Inspired by @Neil's Charcoal answer.

Try it online or verify all test cases.

Explanation:

Î # Push 0 and the input-list
 \ # Get the deltas/forward-differences of the input-list
 v # Loop over each of its integers `y`:
 D # Duplicate the current list,
 # which is the 0 in the first iteration
 yα # Get the absolute difference of each value with integer `y`
 ‚ # Pair this list together with the duplicated list (or the 0)
 ̃ # Flatten it to a single list
 }¦ # After the loop: remove the leading 0
 # (after which the list is output implicitly as result)