title: Digital Sumorial

text:
# Question
Title: Digital Sumorial
Given an input `n`, write a program or function that outputs/returns the sum of the digital sums of `n` for all the bases 1 to `n`.

$$n + \sum\_{b=2}^n \sum\_{i=0}^\infty \left\lfloor \frac{n}{b^i} \right\rfloor \bmod b$$

### Example:

`n = 5`

---

Create the range `[1...n]`: `[1,2,3,4,5]`

---

For each element `x`, get an array of the base-`x` digits of `n`: `[[1,1,1,1,1],[1,0,1],[1,2],[1,1],[1,0]]`

bijective base-`1` of `5` is `[1,1,1,1,1]`

base-`2` (binary) of `5` is `[1,0,1]`

base-`3` of `5` is `[1,2]`

base-`4` of `5` is `[1,1]`

base-`5` of `5` is `[1,0]`

---

Sum the digits: `13`

---

### Test cases:

```
1    1
2    3
3    6
4    8
5    13
6    16
7    23
8    25
9    30
10   35

36   297
37   334

64   883
65   932

```

The sequence can be found on OEIS: A131383

### Scoring:

: The submission with the lowest score wins.

# Answer
# Canvas, 3 bytes

```
┬］∑

```

Try it here!

Canvas beating Jelly?

```
{ ]   map over 1..input (implicit "{")
 ┬      decode input from that base
   ∑  sum the resulting (nested) array

```
> 9 votes

# Answer
# Haskell, 46 bytes

```
f n=sum$do a<-[1..n];mapM(pure[0..a])[1..n]!!n

```

Try it online!

## Explanation

The function `\b n -> mapM(pure[0..b])[1..n]`, generates all strings \\$\[0 \dotsc b\]^n\\$ in lexicographic order. For example:

```
mapM(pure[0..2])[0..1] == [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]

```

By indexing into it with `(!!n)` this can be used to convert `n` to base `b+1`, however this won't work for unary (base-\\$1\\$), but we're summing the results.. We can even save some bytes with `a <- [1..n]` and using base-\\$(n+1)\\$ rather than a work-around for base-\\$1\\$ since we're missing \\$\[\underset{n\text{ times}}{\underbrace{1,\dotsc,1}}\]\\$ which is the same as \\$\[n\]\\$ when summing.

Using `do`-notation just concatenates all the lists instead of nesting them:

```
λ [ mapM (pure [0..a]) [1..5] !! n | a <- [1..5] ]
[[0,0,1,0,1],[0,0,0,1,2],[0,0,0,1,1],[0,0,0,1,0],[0,0,0,0,5]]

λ do a <- [1..5]; mapM (pure [0..a]) [1..5] !! n
[0,0,1,0,1,0,0,0,1,2,0,0,0,1,1,0,0,0,1,0,0,0,0,0,5]

```
> 9 votes

# Answer
# Ruby, ~~39~~ 37

```
->n{(2..n).sum{|b|n.digits(b).sum}+n}

```

The only golfing here is removing some whitespace. Try it online
> 7 votes

# Answer
# Python 2, 57 bytes

```
lambda n:sum(n/(k/n+2)**(k%n)%(k/n+2)for k in range(n*n))

```

This uses the formula $$a(n)=\sum\_{b=2}^{n+1}\sum\_{i=0}^{n-1}\left\lfloor\frac{n}{b^i}\right\rfloor\bmod b,$$ which works since \\$\left\lfloor\frac{n}{(n+1)^0}\right\rfloor\bmod(n+1)=n\\$.

Try it online!
> 6 votes

# Answer
# APL (Dyalog Unicode), 14 bytes

```
+/∘∊⊢,⊢(⍴⊤⊣)¨⍳

```

Try it online!

### Explanation

Some parentheses are implied and can be added (lighter than the "official" parenthesizing):

```
+/∘∊(⊢,(⊢(⍴⊤⊣)¨⍳))

```

This is a monadic atop. Given an argument `Y`, this function behaves like:

```
+/∘∊(⊢,(⊢(⍴⊤⊣)¨⍳))Y

```

The two functions are applied in order. We'll start from the right one:

```
⊢,(⊢(⍴⊤⊣)¨⍳)

```

The are three functions in this train, so this is a fork. Given an argument `Y`, it acts as:

```
(⊢Y),((⊢Y)(⍴⊤⊣)¨⍳Y)

```

We can easily reduce to this (monadic  returns its argument, hence called *identity*):

```
Y,Y(⍴⊤⊣)¨⍳Y

```

Now, we know that `Y` is an integer (simple scalar, i.e. number or character), since we're given one. Therefore `⍳Y`, with `⎕IO=1`, returns `1 2 ... Y`. `⍳Y` actually returns an array with shape `Y` (`Y` must be a vector), where every scalar is the index of itself in the array (that's why monadic  is called the *index generator*). These indices are vectors, except for the case where `1≡⍴Y`, where they are scalars (this is our case).

Let's parse the middle function, `(⍴⊤⊣)¨`, next. `⍴⊤⊣` is the operand of `¨` (*each*), and the function is dyadic, so the `¨` operator will first reshape each length-1 argument to the shape of the other (that is, take the element and use it to replace every scalar in the other argument), and then apply the function to each pair of the two arguments. In this case, `⍳Y` is a vector and `Y` is a scalar, so, if `n≡⍴⍳Y`, then `Y` will be converted to `n⍴Y` ( represents the *shape* (monadic) and *reshape* (dyadic) functions). That is, in simpler terms, `Y` will be converted to an array containing `Y` times `Y`.

Now, for each pair, let's call the left argument `X` and the right `Z` (so that we don't conflict with the input `Y`). `⍴⊤⊣` is a dyadic fork, so it will expand to:

```
(X⍴Z)⊤X⊣Z

```

Let's make the easy first step of reducing `X⊣Z` to `X` (dyadic  is the *left* function):

```
(X⍴Z)⊤X

```

The  in `X⍴Z` is, again, the *reshape* function, so `X⍴Z`, in our case, is simply `X` times `Z`.  is the *encode* function. Given two arrays of numbers, where the left array is the base of each digit in the result (doesn't need to be integer or positive), i.e. the encoding, and the right is an array of numbers, returns the transposed array of those numbers in the specified encoding (transposition is the reversal of an array's dimensions relative to its elements). The representation of a digit is based on the quotient of the division of the number and the product of the less significant bases. If any base is `0`, it acts as base +∞. The arguments' scalars are all simple. Since `X` is a positive integer, and `X⍴Z` is a vector of equal elements, this is really just a case of converting `X` to base `Z` and reshaping to `X` digits. For \\$X,Z\in\mathbb N\\$, \\$X\_Z\\$ (\\$X\\$ in base \\$Z\\$) can't have more than \\$X\\$ digits, since \\$X\_1\\$ has \\$X\\$ digits. Therefore, `X⍴Z` is enough for our purposes.

The result of `Y(⍴⊤⊣)¨⍳Y` is, therefore, `Y` converted to each base from 1 to `Y`, possibly with leading zeroes. However, there is one issue: in APL, base 1 isn't special-cased, while this challenge does special-case it, so we have to include the sum of the base-1 digits of `Y` ourselves. Fortunately, this sum is just `Y`, since \\$Y\_1=\underbrace{\[1,1,...,1\]}\_Y\\$, so the sum is simply \\$Y\times1=Y\\$. It follows that we have to add `Y` somewhere into the array. This is how we do it:

```
Y,Y(⍴⊤⊣)¨⍳Y

```

I have already included this part here. Dyadic `,` is the *catenate* function, it concatenates its arguments on their last axes, and errors if that's not possible. Here, we simply concatenate the scalar `Y` to the vector `Y(⍴⊤⊣)¨⍳Y`, so that we increment the sum we're going to calculate by `Y`, as explained above.

The final part is the left function of our atop, `+/∘∊`:

```
+/∘∊Y,Y(⍴⊤⊣)¨⍳Y

```

is the *compose* operator. `f∘g Y` is the same as `f g Y`. However, we're using it here so that our train doesn't fork on the . So, we can reduce:

```
+/∊Y,Y(⍴⊤⊣)¨⍳Y

```

Now, it's time for the sum, but wait... there's a problem. The array isn't flat, so we can't just sum its elements before flattening it first. The *enlist* function  flattens an array. Now that the array has been flattened, we finally use `+/` to sum it. `/` is the *reduce* operator, it applies a dyadic function between an array's elements on its second-to-last axis, with right-to-left priority. If the rank (number of dimensions, i.e. length of shape) of the array doesn't decrease, the array is then enclosed, although this is not the case here. The function that's applied here is `+`, which is the *plus* function that adds the pairs on the last axes of two arrays (and errors if the arrays can't be added like that). Here, it simply adds two numbers a number of times so that the reduce is completed.

Lo and behold, our train:

```
+/∘∊⊢,⊢(⍴⊤⊣)¨⍳

```
> 6 votes

# Answer
# Java 8, ~~76~~ 65 bytes

```
n->{int r=n,b=n,N;for(;b>1;b--)for(N=n;N>0;N/=b)r+=N%b;return r;}

```

-11 bytes thanks to *@OlivierGrégoire*.

Try it online.

**Explanation:**

```
n->{           // Method with integer as both parameter and return-type
  int r=n,     //  Result-sum, starting at the input to account for Base-1
      b=n,     //  Base, starting at the input
      N;       //  Temp integer
  for(;b>1     //  Loop the Base `b` in the range [n, 1):
      ;b--)    //    After every iteration: Go to the next Base (downwards)
    for(N=n;   //   Set `N` to the input `n`
        N>0;   //   Loop as long as `N` isn't 0 yet:
        N/=b)  //     After every iteration: Divide `N` by the Base `b`
      r+=N%b;  //    Increase the result `r` by `N` modulo the Base `b`
  return r;}   //  Return the result-sum `r`

```
> 5 votes

# Answer
# Whitespace, 153 bytes

```
[S S S N
_Push_0][S N
S _Duplicate_0][T   N
T   T   _Read_STDIN_as_integer][T   T   T   _Retrieve_input][S N
S _Duplicate_input][N
S S N
_Create_Label_OUTER_LOOP][S N
S _Duplicate_top][S S S T   N
_Push_1][T  S S T   _Subtract][N
T   S S N
_If_0_Jump_to_Label_PRINT][S S S N
_Push_0][S N
S _Duplicate_0][T   T   T   _Retrieve_input][N
S S T   N
_Create_Label_INNER_LOOP][S N
S _Duplicate][N
T   S S S N
_If_0_Jump_to_Label_AFTER_INNER_LOOP][S N
T   _Swap_top_two][S T  S S T   N
_Copy_1st_item_to_top][S T  S S T   T   N
_Copy_3rd_item_to_top][T    S T T   _Modulo][T  S S S _Add][S N
T   _Swap_top_two][S T  S S T   S N
_Copy_2nd_item_to_top][T    S T S _Integer_divide][N
S N
T   N
_Jump_to_Label_INNER_LOOP][N
S S S S N
_Create_Label_AFTER_INNER_LOOP][S N
N
_Discard_top][S T   S S T   S N
_Copy_2nd_item_to_top][T    S S S _Add][S N
T   _Swap_top_two][S S S T  N
_Push_1][T  S S T   _Subtract][N
S N
N
_Jump_to_Label_OUTER_LOOP][N
S S S N
_Create_Label_PRINT][S N
N
_Discard_top][T N
S T _Print_as_integer]

```

Letters `S` (space), `T` (tab), and `N` (new-line) added as highlighting only.
`[..._some_action]` added as explanation only.

**Try it online** (with raw spaces, tabs and new-lines only).

Port of my Java 8 answer, because Whitespace has no Base conversion builtins at all.

**Example run: `input = 3`**

```
Command    Explanation                     Stack            Heap   STDIN  STDOUT  STDERR

SSSN       Push 0                          [0]
SNS        Duplicate 0                     [0,0]
TNTT       Read STDIN as integer           [0]              {0:3}  3
TTT        Retrieve input from heap 0      [3]              {0:3}
SNS        Duplicate 3                     [3,3]            {0:3}
NSSN       Create Label_OUTER_LOOP         [3,3]            {0:3}
 SNS       Duplicate 3                     [3,3,3]          {0:3}
 SSSTN     Push 1                          [3,3,3,1]        {0:3}
 TSST      Subtract (3-1)                  [3,3,2]          {0:3}
 NTSSN     If 0: Jump to Label_PRINT       [3,3]            {0:3}
 SSSN      Push 0                          [3,3,0]          {0:3}
 SNS       Duplicate 0                     [3,3,0,0]        {0:3}
 TTT       Retrieve input from heap 0      [3,3,0,3]        {0:3}
 NSSTN     Create Label_INNER_LOOP         [3,3,0,3]        {0:3}
  SNS      Duplicate 3                     [3,3,0,3,3]      {0:3}
  NTSSSN   If 0: Jump to Label_AFTER_IL    [3,3,0,3]        {0:3}
  SNT      Swap top two                    [3,3,3,0]        {0:3}
  STSSTN   Copy (0-indexed) 1st            [3,3,3,0,3]      {0:3}
  STSSTTN  Copy (0-indexed) 3rd            [3,3,3,0,3,3]    {0:3}
  TSTT     Modulo (3%3)                    [3,3,3,0,0]      {0:3}
  TSSS     Add (0+0)                       [3,3,3,0]        {0:3}
  SNT      Swap top two                    [3,3,0,3]        {0:3}
  STSSTSN  Copy (0-indexed) 2nd            [3,3,0,3,3]      {0:3}
  TSTS     Integer divide (3/3)            [3,3,0,1]        {0:3}
  NSNTN    Jump to LABEL_INNER_LOOP        [3,3,0,1]        {0:3}

  SNS      Duplicate 1                     [3,3,0,1,1]      {0:3}
  NTSSSN   If 0: Jump to Label_AFTER_IL    [3,3,0,1]        {0:3}
  SNT      Swap top two                    [3,3,1,0]        {0:3}
  STSSTN   Copy (0-indexed) 1st            [3,3,1,0,1]      {0:3}
  STSSTTN  Copy (0-indexed) 3rd            [3,3,1,0,1,3]    {0:3}
  TSTT     Modulo (1%3)                    [3,3,1,0,1]      {0:3}
  TSSS     Add (0+1)                       [3,3,1,1]        {0:3}
  SNT      Swap top two                    [3,3,1,1]        {0:3}
  STSSTSN  Copy (0-indexed) 2nd            [3,3,1,1,3]      {0:3}
  TSTS     Integer divide (1/3)            [3,3,1,0]        {0:3}
  NSNTN    Jump to LABEL_INNER_LOOP        [3,3,1,0]        {0:3}

  SNS      Duplicate 0                     [3,3,1,0,0]      {0:3}
  NTSSSN   If 0: Jump to Label_AFTER_IL    [3,3,1,0]        {0:3}
 NSSSSN    Create Label_AFTER_IL           [3,3,1,0]        {0:3}
  SNN      Discard top                     [3,3,1]          {0:3}
  STSSTSN  Copy (0-indexed) 2nd            [3,3,1,3]        {0:3}
  TSSS     Add (1+3)                       [3,3,4]          {0:3}
  SNT      Swap top two                    [3,4,3]          {0:3}
  SSSTN    Push 1                          [3,4,3,1]        {0:3}
  TSST     Subtract (3-1)                  [3,4,2]          {0:3}
  NSNN     Jump to LABEL_OUTER_LOOP        [3,4,2]          {0:3}

 SNS       Duplicate 2                     [3,4,2,2]        {0:3}
 SSSTN     Push 1                          [3,4,2,2,1]      {0:3}
 TSST      Subtract (2-1)                  [3,4,2,1]        {0:3}
 NTSSN     If 0: Jump to Label_PRINT       [3,4,2]          {0:3}
 SSSN      Push 0                          [3,4,2,0]        {0:3}
 SNS       Duplicate 0                     [3,4,2,0,0]      {0:3}
 TTT       Retrieve input from heap 0      [3,4,2,0,3]      {0:3}
 NSSTN     Create Label_INNER_LOOP         [3,4,2,0,3]      {0:3}
  SNS      Duplicate 3                     [3,4,2,0,3,3]    {0:3}
  NTSSSN   If 0: Jump to Label_AFTER_IL    [3,4,2,0,3]      {0:3}
  SNT      Swap top two                    [3,4,2,3,0]      {0:3}
  STSSTN   Copy (0-indexed) 1st            [3,4,2,3,0,3]    {0:3}
  STSSTTN  Copy (0-indexed) 3rd            [3,4,2,3,0,3,2]  {0:3}
  TSTT     Modulo (3%2)                    [3,4,2,3,0,1]    {0:3}
  TSSS     Add (0+1)                       [3,4,2,3,1]      {0:3}
  SNT      Swap top two                    [3,4,2,1,3]      {0:3}
  STSSTSN  Copy (0-indexed) 2nd            [3,4,2,1,3,2]    {0:3}
  TSTS     Integer divide (3/2)            [3,4,2,1,1]      {0:3}
  NSNTN    Jump to LABEL_INNER_LOOP        [3,4,2,1,1]      {0:3}

  SNS      Duplicate 1                     [3,4,2,1,1,1]    {0:3}
  NTSSSN   If 0: Jump to Label_AFTER_IL    [3,4,2,1,1]      {0:3}
  SNT      Swap top two                    [3,4,2,1,1]      {0:3}
  STSSTN   Copy (0-indexed) 1st            [3,4,2,1,1,1]    {0:3}
  STSSTTN  Copy (0-indexed) 3rd            [3,4,2,1,1,1,2]  {0:3}
  TSTT     Modulo (1%2)                    [3,4,2,1,1,1]    {0:3}
  TSSS     Add (1+1)                       [3,4,2,1,2]      {0:3}
  SNT      Swap top two                    [3,4,2,2,1]      {0:3}
  STSSTSN  Copy (0-indexed) 2nd            [3,4,2,2,1,2]    {0:3}
  TSTS     Integer divide (1/2)            [3,4,2,2,0]      {0:3}
  NSNTN    Jump to LABEL_INNER_LOOP        [3,4,2,2,0]      {0:3}

  SNS      Duplicate 0                     [3,4,2,2,0,0]    {0:3}
  NTSSSN   If 0: Jump to Label_AFTER_IL    [3,4,2,2,0]      {0:3}
 NSSSSN    Create Label_AFTER_IL           [3,4,2,2,0]      {0:3}
  SNN      Discard top                     [3,4,2,2]        {0:3}
  STSSTSN  Copy (0-indexed) 2nd            [3,4,2,2,4]      {0:3}
  TSSS     Add (2+4)                       [3,4,2,6]        {0:3}
  SNT      Swap top two                    [3,4,6,2]        {0:3}
  SSSTN    Push 1                          [3,4,6,2,1]      {0:3}
  TSST     Subtract (2-1)                  [3,4,6,1]        {0:3}
  NSNN     Jump to LABEL_OUTER_LOOP        [3,4,6,1]        {0:3}

 SNS       Duplicate 1                     [3,4,6,1,1]      {0:3}
 SSSTN     Push 1                          [3,4,6,1,1,1]    {0:3}
 TSST      Subtract (1-1)                  [3,4,6,1,0]      {0:3}
 NTSSN     If 0: Jump to Label_PRINT       [3,4,6,1]        {0:3}
NSSSSN     Create Label_PRINT              [3,4,6,1]        {0:3}
 SNN       Discard top                     [3,4,6]          {0:3}
 TNST      Print top (6) to STDOUT as int  [3,4]            {0:3}         6
                                                                                error

```

Program stops with an error: No exit found. (Although I could add three trailing newlines `NNN` to get rid of that error.)
> 5 votes

# Answer
**SAS, ~~81~~ 74 bytes**

```
data;input n;s=n;do b=2to n;do i=0to n;s+mod(int(n/b**i),b);end;end;cards;

```

Input is entered after the `cards;` statement, on newlines, like so:

```
data;input n;s=n;do b=2to n;do i=0to n;s+mod(int(n/b**i),b);end;end;cards;
1
2
3
4
5
6
7
8
9
10
36
37
64
65

```

Outputs a dataset containing the answer `s` (along with helper variables), with a row for each input value

Ungolfed:

```
data; /* Implicit dataset creation */
input n; /* Read a line of input */

s=n; /* Sum = n to start with (the sum of base 1 digits of n is equal to n) */
do b=2to n; /* For base = 2 to n */
    do i=0to n; /* For each place in the output base (output base must always have less than or equal to n digits) */

        /* Decimal value of current place in the output base = b^i      */
        /* Remainder = int(b / decimal_value)                           */
        /* Current place digit = mod(remainder, base)                   */
        s+mod(int(n/b**i),b);
    end;
end;

cards;
1
2
3

```
> 4 votes

# Answer
# Japt `-x`, 6 bytes

```
ÆìXÄ x

```

Try it

```
õ!ìU c

```

Try it
> 3 votes

# Answer
# , ~~24~~ 23 bytes

```
+1#.1#.]#.inv"0~2+i.@<:

```

Try it online!
> 3 votes

# Answer
# , 60 bytes

```
function(n){if(n-1)for(i in 2:n)F=F+sum(n%/%i^(0:n)%%i)
n+F}

```

Try it online!

Fails for `n>143` since `144^144` is larger than a `double` can get. Thanks to Josh Eller for suggesting replacing `log(n,i)` with simply `n`.

The below will work for `n>143`; not sure at what point it will stop working.

# , 67 bytes

```
function(n){if(n-1)for(i in 2:n)F=F+sum(n%/%i^(0:log(n,i))%%i)
n+F}

```

Try it online!

Uses the classic `n%/%i^(0:log(n,i))%%i` method to extract the base-`i` digits for `n` for each base `b>1`, then sums them and accumulates the sum in `F`, which is initialized to `0`, then adding `n` (the base `1` representation of `n`) to `F` and returning the result. For `n=1`, it skips the bases and simply adds `n` to `F`.
> 3 votes

# Answer
# Perl 6, ~~45~~ 41 bytes

```
{$^a+sum map {|polymod $a: $_ xx*},2..$a}

```

*-4 bytes thanks to Jo King*

Try it online!
> 3 votes

# Answer
# Husk, 6 bytes

I really wish that there was something like `M` for `cmap` :(

```
Σ§ṁ`Bḣ

```

Try it online or test all!

### Explanation

```
Σ§ṁ`Bḣ  -- example input: 5
 §      -- fork the argument..
     ḣ  -- | range: [1,2,3,4,5]
   `B   -- | convert argument to base: (`asBase` 5)
  ṁ     -- | and concatMap: cmap (`asBase` 5) [1,2,3,4,5]
        -- : [1,1,1,1,1,1,0,1,1,2,1,1,1,0]
Σ       -- sum: 13

```

## Alternatively, 6 bytes

```
ΣΣṠMBḣ

```

Try it online or test all!

### Explanation

```
ΣΣṠMBḣ  -- example input: 5
  Ṡ     -- apply ..
     ḣ  -- | range: [1,2,3,4,5]
           .. to function applied to itself
   MB   -- | map over left argument of base
        -- : [[1,1,1,1,1],[1,0,1],[1,2],[1,1],[1,0]]
 Σ      -- flatten: [1,1,1,1,1,1,0,1,1,2,1,1,1,0]
Σ       -- sum: 13

```
> 3 votes

# Answer
# 05AB1E (legacy), 5 bytes

```
LвOO+

```

Try it online!

Explanation:

```
LвOO+  //Full program
L      //push [1 .. input]
 в     //for each element b, push digits of input converted to base b
  O    //sum each element
   O   //sum each sum
    +  //add input

```

In 05AB1E (legacy), base 1 of 5 is \[0,0,0,0,0\], not \[1,1,1,1,1\]. Therefore after summing the range, add the input to account for the missing base 1.

I am using 05AB1E (legacy) because in current 05AB1E, base 1 of 5 is \[1\]. In order to account for this, I would either need to decrement the result by 1 or remove the first element of the range, both of which would cost 1 byte.
> 3 votes

# Answer
# Desmos, 127 bytes

$$f\left(n\right)=\sum\_{b=2}^{n+1}\sum\_{i=0}^{n-1}\operatorname{mod}\left(\operatorname{floor}\left(\frac{n}{b^i}\right),b\right)$$

```
f\left(n\right)=\sum_{b=2}^{n+1}\sum_{i=0}^{n-1}\operatorname{mod}\left(\operatorname{floor}\left(\frac{n}{b^i}\right),b\right)

```

Try it here! Defines a function \\$f\\$, called as \\$f\left(n\right)\\$. Uses the formula given in Dennis's answer.

Here is the resulting graph (point at \\$(65, 932)\\$):

## Desmos, 56 bytes

This might not work on all browsers, but it works on mine. Just copy and paste the formula. This is \\$f\_2(n)\\$ in the above link.

```
f(n)=\sum_{b=2}^{n+1}\sum_{i=0}^{n-1}mod(floor(n/b^i),b)

```
> 3 votes

# Answer
# Python 2, 61 bytes

```
f=lambda n,b=2.:n and n%b+f(n//b,b)+(n//b>1/n==0and f(n,b+1))

```

Try it online!

Though this is longer the Dennis's solution off which it's based, I find the method too amusing to not share.

The goal is to recurse both on lopping off the last digit `n->n/b` and incrementing the base `b->b+1`, but we want to prevent the base from being increased after one or more digits have been lopped off. This is achieved by make the base `b` a float, so that after the update `n->n//b`, the float `b` infects `n` with its floatness. In this way, whether `n` is a float or not is a bit-flag for whether we've removed any digits from `n`.

We require that the condition `1/n==0` is met to recurse into incrementing `b`, which integers `n` satisfy because floor division is done, but floats fails. (`n=1` also fails but we don't want to recurse on it anyway.) Otherwise, floats work just like integers in the function because we're careful to do floor division `n//b`, and the output is a whole-number float.
> 3 votes

# Answer
# JavaScript (without recursion), 77 bytes

Returns correct value for "any" number. Try it online

```
f=(n,b,s)=>{while((s=s||(t=b=n))>1){t+=b%s;b=(m=(b/s|0))||n;s=s-!m}return t;}

```

# JavaScript (with recursion), 54 bytes

Returns correct value for maximum number 3867 ("Maximum call stack size exceeded" is thrown for larger input). Try it online

```
f=(n,b,s)=>(s=s||(b=n))-1?b%s+f(n,(m=b/s|0)||n,s-!m):b

```
> 3 votes

# Answer
# Jelly, 4 bytes

```
bRFS

```

Try it online!

### How it works

```
bRFS  Main link. Argument: n

 R    Range; yield [1, ..., n].
b     Convert n to back k, for each k to the right.
  F   Flatten the resulting 2D array of digits.
   S  Take the sum.

```
> 2 votes

# Answer
# JavaScript (ES6), 42 bytes

This version is almost identical to my main answer but relies on arithmetic underflow to stop the recursion. The highest supported value depends on the size of the call stack.

```
f=(n,b=1,x)=>b>n?n:~~x%b+f(n,b+!x,x?x/b:n)

```

Try it online!

---

# JavaScript (ES6),  ~~51 48~~  44 bytes

```
f=(n,b=2,x=n)=>b>n?n:x%b+f(n,b+!x,x?x/b|0:n)

```

Try it online!

### Commented

```
f = (             // f = recursive function taking:
  n,              // - n = input
  b = 2,          // - b = current base, initialized to 2
  x = n           // - x = current value being converted in base b
) =>              //
  b > n ?         // if b is greater than n:
    n             //   stop recursion and return n, which is the sum of the digits of n
                  //   once converted to unary
  :               // else:
    x % b +       //   add x modulo b to the final result
    f(            //   and add the result of a recursive call:
      n,          //     pass n unchanged
      b + !x,     //     increment b if x = 0
      x ?         //     if x is not equal to 0:
        x / b | 0 //       update x to floor(x / b)
      :           //     else:
        n         //       reset x to n
    )             //   end of recursive call

```
> 2 votes

# Answer
# APL (Dyalog Unicode), 22 bytes

```
{1⊥⍵,∊(1+⍳⍵-1)⊥⍣¯1¨⊂⍵}

```

Try it online!
> 2 votes

# Answer
# Pari/GP, 30 bytes

```
n->n+sum(b=2,n,sumdigits(n,b))

```

Try it online!
> 2 votes

# Answer
# C (gcc), ~~67~~ 56 bytes

```
b,a,s;e(n){for(b=a=n;a>1;a--)for(s=n;s;s/=a)b+=s%a;n=b;}

```

Port of my Java 8 answer.
-11 bytes thanks to *@OlivierGrégoire*'s golf on my Java answer.

Try it online.

**Explanation:**

```
b,             // Result integer
a,             // Base integer
s;             // Temp integer
e(n){          // Method with integer as parameter
  for(b=a=n;   //  Set the result `b` to input `n` to account for Base-1
               //  And set Base `a` to input `n` as well
      a>1      //  Loop the Base `a` in the range [input, 1):
      ;a--)    //    After every iteration: Go to the next Base (downwards)
    for(s=n;   //   Set `s` to input `n`
        s;     //   Inner loop as long as `s` is not 0 yet:
        s/=a)  //     After every iteration: Divide `s` by Base `a`
      b+=s%a;  //    Add `s` modulo Base `a` to the result `b`
  n=b;}        //  Set input `n` to result `b` to 'return it'

```
> 2 votes

# Answer
# tinylisp, 71 bytes

```
(load library
(d S(q((N)(sum(map sum(map* to-base(1to N)(repeat-val N N

```

Try it online!
> 2 votes

# Answer
# Pyth, 7 bytes

```
+ssjLQS

```

Test suite

##### Explanation:

```
+ssjLQS   | Full program
+ssjLQSQQ | with implicit variables filled
----------+--------------------------------------------------
    L SQ  | Map over each d in [1..input]:
   j Q    |  input to base d as a list (unary is a list of 0)
 ss       | Sum of sums
+       Q | Add input (to account for unary)

```
> 2 votes

# Answer
# Attache, 25 bytes

```
{Sum!`'^^ToBase[_,2:_]'_}

```

Try it online!

## Explanation

```
{Sum!`'^^ToBase[_,2:_]'_}
{                       }   anonymous lambda, input: _
                            example: 5
         ToBase[_,   ]      convert `_`
                  2:_       ...to each base from 2 to `_`
                            example: [[1, 0, 1], [1, 2], [1, 1], [1, 0]]
                      '_    append `_`
                            example: [[1, 0, 1], [1, 2], [1, 1], [1, 0], 5]
       ^^                   fold...
     `'                     the append operator over the list
                            example: [1, 0, 1, 1, 2, 1, 1, 1, 0, 5]
 Sum!                       take the sum
                            example: 13

```
> 1 votes

# Answer
# Charcoal, 12 bytes

```
ＩΣＥＩθΣ↨Ｉθ⁺²ι

```

Try it online! Link is to verbose version of code. Charcoal can't convert to base 1, but fortunately the digit sum is the same as the conversion to base \\$n + 1\\$. Explanation:

```
    θ           First input
   Ｉ            Cast to integer
  Ｅ             Map over implicit range
        θ       First input
       Ｉ        Cast to integer
      ↨         Converted to base
           ι    Current index
         ⁺      Plus
          ²     Literal 2
     Σ          Sum
 Σ              Grand total
Ｉ               Cast to string
                Implicitly print

```
> 1 votes

# Answer
# Retina 0.8.2, 49 bytes

```
.+
$*
1
11$`;$_¶
+`\b(1+);(\1)+
$1;$#2$*1,
1+;

1

```

Try it online! Link includes test cases. Explanation:

```
.+
$*

```

Convert to unary.

```
1
11$`;$_¶

```

List all the numbers from 2 to \\$n + 1\\$ (since that's easier than base 1 conversion).

```
+`\b(1+);(\1)+
$1;$#2$*1,

```

Use repeated divmod to convert the original number to each base.

```
1+;

```

Delete the list of bases, leaving just the base conversion digits.

```
1

```

Take the sum and convert to decimal.
> 1 votes

# Answer
# Desmos, 51 bytes

Inspired by Conor O'Brien's answer and looking at the OEIS-entry I came up with my own Desmos-solution:

```
h(n)=n^2-\sum_{p=2}^n(p-1)\sum_{k=1}^n floor(n/p^k)

```

Try it online!
> 1 votes

# Answer
# APL(NARS), 29 chars, 58 bytes

```
{+/+/¨⍵{(⍺⍴⍨⌊1+⍺⍟⍵)⊤⍵}⍨¨1+⍳⍵}

```

little test on how to use:

```
  h←{+/+/¨⍵{(⍺⍴⍨⌊1+⍺⍟⍵)⊤⍵}⍨¨1+⍳⍵}
  h¨1 2 4 10 36 37 64 65
1 3 8 35 297 334 883 932

```
> 0 votes

---
Tags: code-golf, math, sequence, integer, base-conversion
---


title: Make an interweaving quine

text:
# Question
Title: Make an interweaving quine
Your task is to create a program that, when run, returns itself as output (this is known as a quine). However, this quine must, when it is copied `n` times, returns the quine, but with each of its characters duplicated in place `n` times, where `n` is a positive integer.

If your original program is `Derp`:

```
Derp -> Derp (must return itself as output to be a quine)

DerpDerp -> DDeerrpp
(the "Derp" is copied twice, so each character in the output has to be copied twice)

DerpDerpDerp -> DDDeeerrrppp
etc. etc.

```

Keep in mind you're allowed to have whitespace in your "base" program, but they are counted when "interweaving". Say your program is

```
Derp
{newline}

```

(The newline signifies a trailing newline, and there's an extra space after the `Derp`). When duplicated to become

```
Derp
Derp
{newline}

```

You must output

```
DDeerrpp
{newline}
{newline}

```

Keep in mind that there's `2` extra spaces after the `DDeerrpp`.

## Rules and Specs:

* Your program must contain at least two distinct characters (which implies that your code must be at least 2 bytes long).
* Standard quine rules apply.

This is , so shortest code in bytes wins!

# Answer
## Fission, 6 bytes

```
'!+OR"

```

Try it online! Try two copies! Try three!

### Explanation

This is just the Fission standard quine. It happens to work for this challenge, because Fission has explicit entry points into the program. In particular, by duplicating the program, we add another `R` which adds another atom (instruction pointer). Since the source code is toroidal, the effective code being executed doesn't change otherwise — to each atom, the code still looks the same locally. However, the atoms are executed in lock step, so that the things they print are interleaved and we get an additional copy of each character in the output.

For completeness' sake I'll just shortly reiterate how the program itself works. Regardless of whether we repeat the program or not (e.g. `'!+OR"'!+OR"'!+OR"`), each atom sees the following code:

```
R"'!+OR"'!+O

```

The `"` toggles string printing mode, so that the program starts by printing `'!+OR` directly to STDOUT, which is all of the quine except the quote. Then `'!` sets the atom's mass to the character code of `!`, `+` increments it, which gives `"`, and `O` prints it while simultaneously destroying the atom. The program then terminates, because there are no atoms left.
> 17 votes

# Answer
# Python 2.7, 377 310 304 194 191 bytes!

This is my first golf, so I didn't expect it to be too good. But I thought the concept in the solution I came up with was somewhat funny, so I'm posting it anyway.

```
def f():
 import threading as T,inspect as i;global t,a,i
 try:t.cancel()
 except:a=0
 a+=1;t=T.Timer(1,d);t.start()
def d():print''.join(c*a for c in i.getsource(f)+i.getsource(d)+"f()")
f()

```

Indeed, this is a quine; you can try it here. It abuses the inspect module pretty hard.

If we try running it with the same source code x2, we get the right output as well; you can try that here. x3, x4, etc. all work as expected.

Ungolfed with explanation:

```
def f():                                   # Defines a central function f
    import threading as T,inspect as i     # Imports threading and inspect
    global t,a,i                           # Global vars
    try:
        t.cancel()                         # Tries to cancel Timer from previous code
    except:
        a = 0                              # Reached when code is 1st copy; initializes a.
    a += 1                                 # a++; this is the number of copies thus far.
    t = T.Timer(1,d)               # Creates, then starts a timer to call function
    t.start()                              # d in 1 second.

def d():                                   # Prints out the source code; the quine part.
    print''.join(c*a for c in i.getsource(f)+i.getsource(d)+"f()")

f()                                        # Calls f()!

```
> 12 votes

# Answer
# CJam, 19 bytes

```
{]W=s"_~"+T):Te*}_~

```

Try it online!

### How it works

```
{               }_~  Define an anonymous code block (function).
                 _~  Push a copy, and execute the copy.
 ]W=                 Wrap the entire stack in an array and select its last element.
                     This discards whatever was on the stack before the original
                     code block, which is needed for subsequent iterations.
    s"_~"+           Cast the code block to string, push "_~", and concatenate.
                     This pushes the stringified source code on the stack.
          T):T       Push T (initially 0), increment it, and save the result in T.
              e*     Repeat each character in the stringified source code T times.

```
> 3 votes

# Answer
# RProgN, 66 bytes

*Significant Whitespace be the death of me*

```
[ "[ %q ] F 0 1 + `0 = `. { 0 m } R " ] F 0 1 + `0 = `. { 0 m } R

```

## Explained

```
[ "[ %q ] F 0 1 + `0 = `. { 0 m } R " ] F 0 1 + `0 = `. { 0 m } R   #
[                                                                   # Pop whatever is already on the stack, if anything.
  "[ %q ] F 0 1 + `0 = `. { 0 m } R "                               # This string contains basically the entire function.
                                      ] F                           # ] F duplicates the string, and then F formats it, which in this case puts the first string into the second at %q, surrounded by qoutes.
                                          0 1 + `0 =                # I needed an Incrementer, so I chose 0. 0, is conveniently, pre initilized at 0. And because RProgN is horrifying, you can remap the number functions as they're just more variables. So this increments 0 every time the group is called.
                                                     `. { 0 m } R   # Replace each character with itself repeated '0' times. Because '0' is an incrementer, each time the script is called, the amount of times the characters are repeated increase.

```

*Good lord I'm a monster...*

Try it online!
> 3 votes

# Answer
# Python 3, ~~122~~ ~~121~~ 112 bytes

```
s='try:from atexit import*;n+=1\nexcept:n=1;register(lambda:[print(end=c*n)for c in"s=%r;exec(s);"%s])';exec(s);

```

**Try It Online:** one copy **|** two copies **|** three copies **|** four copies, with automatic verification

### How it works

This uses the standard Python quine: Store the code you want to execute in a variable (as a string); include some logic in that string to print itself, everything before it, and everything after it; then execute that string.

The code that is executed via the string **s** is the following.

```
try:from atexit import*;n+=1
except:n=1;register(lambda:[print(end=c*n)for c in"s=%r;exec(s);"%s])

```

The first line unconditionally imports the *atexit* module, which will allow us to register an exit handler. Trying to import the same module multiple times doesn't affect the script in any way. Then it *tries to* increment the variable **n**, to keep track of how many copies of the source code were executed.

The second line is executed only if the first one contains an error. This will be the case in the first iteration, since **n** is still undefined. In this case, we initialize **n** as **1** and register a lambda that performs the actual magic.

The registered exit handler

```
lambda:[print(end=c*n)for c in"s=%r;exec(s);"%s]

```

will be called right before the program finishes. The lambda itself creates the string `"s=%r;exec(s);"%s``%r` creates a string representation of the right argument (**s**), which includes everything between the single quotes and the quotes themselves – then iterates over its characters. For each character **c**, we simply print **n** copies of **c**. Passing `c*n` as the named argument `end` to `print` means that no linefeed will be appended.
> 3 votes

# Answer
# Python 3.8 (pre-release), 68 bytes

```
for c in(s:='for c in(s:=%r)%%s:\n print(end=c)#')%s:
 print(end=c)#

```

Try it online!

## How it works:

* Based on the quine `print((s:='print((s:=%r)%%s)')%s)`
* when repeated multiple time, the code become something like:

```
for c in "string for the quine":
 print(end=c)#comment
 print(end=c)#comment
 print(end=c)#

```
> 3 votes

# Answer
# Perl 5, 107 bytes

```
$_=q[$_=q[S];s/S/$_/;$a++;END{s/./$&x$a/eg;print if$a;$a=0}];s/S/$_/;$a++;END{s/./$&x$a/eg;print if$a;$a=0}

```

Ungolfed:

```
$_ = '...INSERT_SOURCE_HERE...';      # Standard quine
s/INSERT_SOURCE_HERE/$_;
$a++;                                 # Count the number of repetitions
END {
    s/./$&x$a/eg;                     # Interweave
    print if $a;                      # Print...
    $a=0;                             # ...but only once
}

```

Try it online!
> 2 votes

# Answer
# CJam, 14 bytes

```
{s"_~"+]:.+}_~

```

Try it online!

### Explanations

```
{s"_~"+]:.+}_~
{s"_~"+    }_~ Basic quine operator.
       ]:.+    Append each character to corresponding element of the previous result if existed.

```
> 2 votes

# Answer
# Vyxal `D`, 18 bytes

```
`£_›:¥q\`:Ė\`+•`:Ė

```

Try it Online! | Try it Double! | Try it x5!

```
`              `:Ė # Evaluate the following piece of code on itself:
 £                 # Store (itself) to the register
  _                # Pop
                   # The previous copy (if there is one) will've left its code on top of the stack; we don't want that, so we pop it
                   # This exposes the counter to the top of stack
   ›:              # Increment the counter
     ¥             # Push the code
      q            # Unevaluate (stringify) it
       \`:Ė\`+     # Append an eval (this is the quine bit)
              •    # Repeat each character (counter) times
                   # Now [counter, output] is left on the stack

```

# Vyxal `D`, 25 bytes

```
`q\`:Ė\`+$:["21/÷Y∑|_]`:Ė

```

Try it Online!

A quite neat solution that interleaves its code with the previous iteration

```
`                     `:Ė # Evaluate on itself...
 q\`:Ė\`+                 # Quine part - uneval, append code to eval
         $                # Get the previous code
          :[              # If it exists (There's a copy of the code before it)
            "21/          # Divide each into 21 pieces
                ÷Y        # Interleave them
                  ∑       # Summate
                   |_]    # Else (If this is the first copy) pop (the 0 on top) leaving the source

```
> 1 votes

# Answer
# Vyxal `D`, 8 bytes

```
`I!•`I!•

```

Try it Online! | Try it Online!Try it Online! | Try it Online!Try it Online!Try it Online!

## Explanation

```
`I!•`    # push `I!•` to the stack => [ I!• ]
     I   # quote and prepend => [ `I!•`I!• ]
      !  # push the len of the stack => [ `I!•`I!• , 1 ]
       • # duplicate each char of the string by => [ `I!•`I!• ]
         # implicit output

# each time the program repeat, the length of the stack increment and the end become :

      !  # push the len of the stack => [ `I!•`I!• , `I!•`I!• , 2 ]
       • # duplicate each char of the string by => [ `I!•`I!• , ``II!!••``II!!•• ]
         # implicit output the top element of the stack

```

# Vyxal `D`, 11 bytes

```
`q‛:Ė+!•`:Ė

```

Try it Online! | Try it Online!Try it Online! | Try it Online!Try it Online!Try it Online!

## Explanation :

```
`q‛:Ė+!•`   # push `q‛:Ė+!•` to the stack => [ q‛:Ė+!• ]
         :  # duplicate the element on top of the stack => [ q‛:Ė+!• , q‛:Ė+!• ]
          Ė # pop and execute the element on top of the stack => [ q‛:Ė+!• ]
 q          # quote => [ `q‛:Ė+!•` ]
  ‛:Ė+      # add `:Ė` to the top of the stack =>  [ `q‛:Ė+!•`:Ė ]
      !     # push the len of the stack => [ `q‛:Ė+!•`:Ė , 1 ]
       •    # multiply each char by => [ `q‛:Ė+!•`:Ė ]
            # implicit output

# each time the program repeat, the length of the stack increment and the end become :

      !     # push the len of the stack => [ `q‛:Ė+!•`:Ė , `q‛:Ė+!•`:Ė , 2 ]
       •    # multiply each char by => [ `q‛:Ė+!•`:Ė , ``qq‛‛::ĖĖ++!!••``::ĖĖ ]
            # implicit output

```
> 1 votes

---
Tags: code-golf, quine, source-layout
---


# Question
Title: A sequence of sums of integers that aren't in the sequence
## Background

Consider a sequence defined as follows:

* The first element is 0;
* The second element is 4;
* From the third element onwards, its value can be calculated by:
    + Taking the set of integers from 0 up to the previous element of the sequence (inclusive or exclusive, it doesn't matter);
    + Removing any integers that have already appeared earlier in the sequence from the set;
    + Adding together the remaining elements of the set; that's the value you want.

Interestingly, this sequence doesn't seem to be on OEIS yet.

## The task

Write a program or function which takes an integer *n* as input, and outputs the *n*th element of the sequence.

## Test cases

The first few elements of the sequence are:

* 0
* 4
* 6 (1+2+3)
* 11 (1+2+3+5)
* 45 (1+2+3+5+7+8+9+10)
* 969 (1+2+3+5+7…10+12…44)
* 468930 (1+2+3+5+7…10+12…44+46…968)

## Clarifications

* Your program should in theory be able to handle arbitrary *n* if run on a variant of your language that has unboundedly large integers and access to an unlimited amount of memory. (Languages without bignums are unlikely to be able to get much beyond 468930, but that's no excuse to hardcode the answers.)
* You may choose either 0-based or 1-based indexing for the sequence (e.g. it's up to you whether *n*=1 returns the first element, *n*=2 the second element, and so on; or whether *n*=0 returns the first element, *n*=1 the second element, and so on).
* There are no requirements on the algorithm you use, nor on its efficiency; you may implement the definition of the sequence directly (even though it's really inefficient), and you may also implement a different algorithm which leads to the same results.

## Victory condition

This is , so the shortest correct program, measured in bytes, wins.

# Answer
# Jelly, ~~13~~ ~~12~~ 9 bytes

```
rSạo4¥ð@¡

```

Uses 0-based indexing.

Try it online!

### How it works

```
rSạo4¥ð@¡  Main link. No arguments. Implicit argument: 0

      ð    Collect everything to the left into a chain and start a new, dyadic one.
           The arity of the first chain is unknown at this point, as it isn't
           prefixed by ø, µ, or ð.
       @   Swap the arguments of the first chain. Swapping  arguments is only
           implemented for dyadic links, so this makes the chain dyadic.
        ¡  Read an integer n from STDIN and execute the chain n times. Taking the
           argument swap into account, the chain is executed first with 0 as left
           and right argument, then with the previous right argument as left
           argument and the previous return value as right argument.
           The return value of the last call is the return value of the quicklink
           and becomes the implicit output.

           Let's call the left argument x and the right argument y.
r            Range; yield [x, ..., y].
 S           Compute the sum of all integers in the range.
     ¥       Convert the two atoms to the left into a dyadic chain, and call that
             chain with arguments x and y.
   o4          Take the logical OR of x and 4, replacing a 0 with 4 and leaving
               positive integers untouched.
  ạ          Take the absolute difference of the sum to the left and the result of
             the logical OR to the right.

```
> 11 votes

# Answer
# Python, ~~66~~ 60 bytes

Thanks to @Dennis for shaving off 6 bytes!

```
f=lambda n:n>2and(f(n-1)-~f(n-2))*(f(n-1)-f(n-2))/2or(5-n)*n

```

It's not the golfiest piece of code ever, but it uses a formula that I made:

Where `x` on the right-hand side is `f(n - 1)`, and `y` is `f(n - 2)`.

## Explanation:

The sum of continuous integers from `a` to `b` (inclusive) can be described by this formula:

```
amount * average

```

Where `amount` (amount of numbers) is described like so:

```
((a - b) - 1)

```

And `average` (the average of all numbers) is described like so:

```
(a + b) / 2

```

So the full formula is now:

```
  ((a - b) - 1)(a + b) / 2
= (a - b - 1)(a + b) / 2

```

The way we implement this formula into the final formula is to substitute `a` for `f(n - 1)`, `b` for `f(n - 2)`, which basically calculates the sum of all of the new terms, and add another `f(n - 1)` (which is now `a`) on, which is the sum of all previous terms.

Combining that together, we get:

```
  a + ((a - b - 1)(a + b) / 2)
= a + ((a^2 + ab - ab - b^2 - a - b) / 2)
= a + ((a^2 - b^2 - a - b) / 2)
= (a^2 - b^2 - a - b + 2a) / 2
= (a^2 - b^2 + a - b) / 2
= ((a + b)(a - b) + (a - b)) / 2
= (a + b + 1)(a - b) / 2

```

Replace `a` with `x` and `b` with `y`, and hey presto, you have to formula above.
> 11 votes

# Answer
# Mathematica, ~~49~~ 48 bytes

```
±2=4;±1=0;±n_:=Tr@Range@±(n-1)-Tr@Array[±#&,n-1]
(* or *)
±2=4;±1=0;±n_:=-Tr@Array[(k=±#)&,n-1]+Tr@Range@k

```

Uses CP-1252 encoding. Defines function `PlusMinus (±)`. 1-indexed.

# Explanation

```
±2=4;±1=0;±n_:=Tr@Range@±(n-1)-Tr@Array[±#&,n-1]

±2=4;±1=0;                                        (* Define ±1 and ±2 *)
          ±n_:=                                   (* ±n equals ... *)
               Tr@Range@±(n-1)                    (* Sum of (1, 2, ..., ±(n-1)) ... *)
                              -Tr@Array[±#&,n-1]  (* Minus the sum of previous terms *)

```
> 10 votes

# Answer
# Python 2, ~~58~~ ~~54~~ 50 bytes

```
r=t=0
exec'r,t=t+r*~-r/2or 4,t-r;'*input()
print r

```

Try it online!
> 10 votes

# Answer
# Oasis, 11 bytes

### Code:

```
+>bc-*2/640

```

### Explanation:

To visualize the relation of **fn**, let's take the example **f5**. To calculate **f5**, let's take a look at the following sum:

**1 + 2 + 3 + 5** \+ 7 + 8 + 9 + 10

The bold part is just the same as **f4**. The **7 + 8 + 9 + 10** part is the range **\[fn-2 \+ 1, fn-1 \- 1\]**. That makes the formula **fn-1 \+ Σ \[fn-2 \+ 1 ... fn-1 \- 1\]** (Wolfram link):

**fn = 0.5 × (fn-12 \- fn-22 \+ fn-1 \- fn-2)**

Which can be rewritten to:

**fn = 0.5 × ((fn-1 \- fn-2)(fn-1 \+ fn-2) + (fn-1 \- fn-2))**

**fn = 0.5 × ((fn-1 \- fn-2)(fn-1 \+ fn-2 \+ 1))**

Which is the formula that we will be using in the code:

### Code explanation

The `640` part gives us the base cases:

```
a(0) = 0
a(1) = 4
a(2) = 6

```

The code that will be executed (which defines **a(n)**):

```
+>bc-*2/

+          # Add a(n + 1) and a(n + 2) implicitly
 >         # Add one to get a(n + 1) + a(n + 2) + 1
  b        # Push a(n + 1)
   c       # Push a(n + 2)
    -      # Subtract from each other
     *     # Multiply with the previous result
      2/   # Halve the result

```

Try it online!
> 9 votes

# Answer
# Julia, ~~39~~ ~~33~~ 32 bytes

```
!n=n<3?5n-n^2:sum(!(n-2)+1:!~-n)

```

0-based.

Thanks to @Dennis, saved 6 bytes.

Thanks to @GlenO, saved a byte.

Try it online!

Previous answer 1- based:

```
!n=n<4?2(n>1)n:sum(!(n-2)+1:!~-n)

```

Try it online!

Previous ungolfed answer 1-based :

```
f(n)=n<4?n<2?0:n*2:sum(f(n-2)+1:f(n-1))

```

Try it online!
> 6 votes

# Answer
# PowerShell, ~~84~~ ~~89~~ ~~88~~ 87 bytes

```
$OFS='+'
for($a=0,4;$a.Count-le($n="$args")){$a+=("$(1..$a[-1])"|iex)-("$a"|iex)}$a[$n]

```

Try it online!

### Explanation

0-based indexing. Only works through `n = 6` (on my Windows machine it crashes with a stack overflow for `n = 7`).

Using the same method as JungHwan Min's answer (sum of the range minus sum of previous terms).

Summing a range/array in PowerShell is long, so I'm using a trick of joining a n array with `+` to create a long expression (like `1+2+3+4...etc`) and then sending it through `iex` (`Invoke-Expression`).

Since I need to do it twice, instead of using `-join` I'm setting the special variable `$OFS`, which stands for output field separator. When you stringify an array, this is the character used to the join the elements; it default to a space. So by setting it to `+` (once), I can replace something like `$a-join'+'|iex` with `"$a"|iex`.

A simple `for` loop keeps going until the sequence count is less than or equal to the input integer, then I return the `$n`th element.
> 5 votes

# Answer
## JavaScript (ES6), 47 bytes

```
f=(n,b=4,a=6)=>n?--n?f(n,a,(a+b+1)*(a-b)/2):b:0

```

Uses the recurrence relation that `f(n) = sum(range(f(n-2) + 1, f(n-1) + 1))` for n \> 2.
> 5 votes

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

```
OKi:"tP:yX-sv]G)

```

`1`-based indexing is used. The code is very inefficient. For `n = 6` it already exceeds the memory limit of the online compiler.

Try it online!

### How it works

```
O       % Push 0
K       % Push 4
i       % Input n
:"      % Do the following n times
  t     %   Push a copy of the top array (or number)
  P:    %   Range from 1 to the last element of array
  y     %   Push a copy of the second-top number/array
  X-    %   Set difference
  s     %   Sum
  v     %   Concatenate everything into a column vector
]       % End
G)      % Get n-th entry of the array. Implicity display

```

---

For **20 bytes**, the following version avoids the memory limitation. But there's still the data type limitation (`double` type can only guarantee that integers are accurately represented up to `2^53`), so results are valid up to `n = 8` only.

```
OKi:"t0)tQ*2/ys-v]G)

```

Try it online too!
> 4 votes

# Answer
## JavaScript, ~~123~~ 119 bytes

```
(a,i=x=y=0)=>{r=[0,4];while(r.length<a){x++;y=0;for(i=0;i<r[x];i++){if(!r.includes(i)){y+=i;}}r.push(y)}return r[a-1];}

```

Try it online! This solution is 1-based, `f(1) => 0`.
> 3 votes

# Answer
# Haskell, 42 bytes

```
f 0=0
f 1=4
f 2=6
f n=sum[1+f(n-2)..f$n-1]

```

Try it online!

This directly implements the recurrence that for `n>2`, `f(n)` equals `f(n-1)` plus the sum of the open interval from `f(n-2)` to `f(n-1)` which again is equal to the sum of the half-open interval from `f(n-2)` to `f(n-1)` inclusive.

```
f(0) = 0
f(1) = 4
f(2) = 6 = 1+2+3
f(3) = 11 = 1+2+3+5 = 6 + 5 = 6 + sum]4,6[ = f(2)+ sum]f(1),f(2)[ = sum]f(1),f(2)]
...
f(n) = sum]f(n-2),f(n-1)] = sum[f(n-2)+1,f(n-1)]

```
> 3 votes

# Answer
## Haskell, 31 bytes

```
m#s=m:s#sum[m+1..s]
((0:4#6)!!)

```

Usage example: `((0:4#6)!!) 6` -\> `468930`. Try it online!.

Simple recursion, that keeps track of the maximum element `m` so far and the next value `s`.
> 3 votes

# Answer
# Perl 6,  ~~52 49 44~~  35 bytes

```
{(|(0,4 X 0),{[+](^.[0])-.[1],.[0]+.[1]}...*)[$_;0]}

```

Try it

```
{(0,(4,0),{[+](^.[0])-.[1],.[0]+.[1]}...*)[$_;0]}

```

Try it

```
{(0,(4,0),{[+](^.[0])-.[1],.sum}...*)[$_;0]}

```

Try it

```
{(0,4,6,{[+] $^a^..$^b}...*)[$_]}

```

Try it

## Expanded:

```
{ # bare block lambda with implicit parameter ｢$_｣

  (
    # generate a sequence

    0, 4, 6,      # seed the sequence

    {             # lambda with placeholder parameters ｢$a｣ ｢$b｣
      [+]         # reduce with ｢&infix:<+>｣
          $^a     # n-2
          ^..     # Range that excludes the first value
          $^b     # n-1
    }
    ...           # keep generating values until
    *             # never stop

  )[ $_ ]         # get the value that was asked for (0 based index)
}

```
> 3 votes

# Answer
# PowerShell, ~~77~~ 73 bytes

```
param($n)$a=0,4;1..$n|%{$a+=(0..$a[-1]|?{$_-notin$a})-join'+'|iex};$a[$n]

```

Try it online!

Implements the algorithm as defined, and is 0-indexed. Input of `6` is too much for TIO to handle.

Sets `$a` to be an array `[0,4]`. Loops from `1` up to input `$n`. In the loop, we take the range of numbers from `0` up to the biggest number we have `$a[-1]`, and use a `Where-Object` clause `|?{...}` to pull out only those numbers that are not already present. That array of numbers is `-join`ed together with `+`s, and then fed to `iex` (short for `Invoke-Expression` and similar to `eval`). That value is then array-concatenated onto the end of `$a`. Finally, we exit our loop, and take the `$n`th number in our array. That number is left on the pipeline, and output is implicit.
> 3 votes

# Answer
# Python 2, 85 bytes

```
def g(n):
 if n<2:return n*4
 s=set(map(g,range(n)));return sum(set(range(max(s)))-s)

```

Try it online!
> 2 votes

# Answer
## Batch, 108 bytes

```
@if %1==0 echo 0&exit/b
@set/ab=4,a=6
@for /l %%i in (2,1,%1)do @set/ac=(a+b+1)*(a-b)/2,b=a,a=c
@echo %b%

```

Port of my JavaScript answer.
> 2 votes

# Answer
# dc, 47 bytes

```
?d1-scd/4*dd[d1+*2/r-dsn+dlnlc1-dsc0<x]sxlc0<xp

```

Works with integers as large as you want, up to the memory capacity of the computer.

Try it online!

0-based indexing, input on stdin, output on stdout. (There's also output on stderr, which is to be ignored.)

Sample runs:

```
$ for ((j=0;j<12;j++)){ echo -n "$j ";dc -f sumseq.dc <<<"$j";echo;} 2>/dev/null
0 0

1 4

2 6

3 11

4 45

5 969

6 468930

7 109947436950

8 6044219445882138462810

9 18266294354989892462984673364511343859409730

10 166828754731567805766174036610844675771635260155825966927845486666328\
837158267993261860

11 139159167026428037700805570917048711514125048327321592278500415852500\
422178720517080334552793040951056255170819719745908378102737875659900\
61575545777065220385544711322919415

```

This uses the same algorithm as the following solution in bash, which is (a little) more readable:

# Pure bash, 60 bytes

```
for((n=s=$1?4:0,k=1;k<$1;k++,s+=(n=n++*n/2-s))){ :;}
echo $n

```

But the bash program only works for inputs up to 7, since it hits integer overflow beyond that.
> 2 votes

# Answer
# Pyth - 15 bytes

```
ePu+Gs-UeGGQ,Z4

```

Test Suite.
> 1 votes

# Answer
# C# - 74 bytes

```
int A(int f){int e=4,i=1,s=0;for(;i++<f;)e=e*-~e/2-(s+=e);return f>0?e:0;}

```

Ungolfed:

```
int A(int f)
{
    int e = 4,
        i = 1,
        s = 0; // e is the last element, s is the sum of all previous elements
    for (; i++ < f; ) // calculate for indexes 1 through max (don't need the index, just a correct number of loop cycles)
        e = e * -~e / 2 - (s += e); // -~e => (e + 1), higher precedence to remove parentheses
    return f > 0 ? e : 0; //handle input 0 as a special case, which is 0
}

```

There is probably a way to convert this to a lambda to save even more, or something using the .Aggregate Function. Although currently I have no imports, so maybe it evens out?
> 1 votes

# Answer
# \>\<\>, 43+3 = 46 bytes

Makes use of the formula presented in Adnan's and Qwerp-Derp's answers.

```
:2(?^&46v
}v?=&:&l<,2*{-$@:}+1+@:{::
*>n;>4

```

Expects the input to be present on the stack, so +3 bytes for the `-v` flag.

Try it online!
> 1 votes

# Answer
# Stax, 14 bytes

```
╟s╒π4╬╪♀○¢fΦå┼

```

Run and debug it

0-indexed.
> 1 votes

# Answer
# Vyxal, 14 bytes

```
04"?(Dtɽ$F∑J)i

```

Try it Online!
> 0 votes

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


title: A Semi-palindrome Puzzle

text:
# Question
Title: A Semi-palindrome Puzzle
An palindrome is a word that is its own reverse.

Now there are some words that might look like palindromes but are not. For example consider the word `sheesh`, `sheesh` is not a palindrome because its reverse is `hseehs` which is different, however if we consider `sh` to be a single letter, then it's reverse is `sheesh`. This kind of word we will call a semi-palindrome.

Specifically a word is a semi-palindrome if we can split up the word in to some number of chunks such that when the order of the chunks are reversed the original word is formed. (For `sheesh` those chunks are `sh e e sh`) We will also require no chunk contains letters from both halves of the word (otherwise every word would be a semi-palindrome). For example `rear` is not a semi-palindrome because `r ea r` has a chunk (`ea`) that contains letters from both sides of the original word. We consider the central character in an odd length word to be on neither side of the word, thus for words with odd length the center character must always be in it's own chunk.

Your task will be to take a list of positive integers and determine if they are a semi-palindrome. Your code should output two consistent unequal values, one if the input is a semi-palindrome and the other otherwise. However the byte sequence of your code ***must be a semi-palindrome*** itself.

Answers will be scored in bytes with fewer bytes being better.

## Test-cases

```
[] -> True
[1] -> True
[2,1,2] -> True
[3,4,2,2,3,4] -> True
[3,5,1,3,5] -> True
[1,2,3,1] -> False
[1,2,3,3,4,1] -> False
[11,44,1,1] -> False
[1,3,2,4,1,2,3] -> False

```

Program to generate more testcases.

---

borrible pointed out that these are similar to generalized Smarandache palindromes. So if you want to do some further reading that's one place to start.

# Answer
# Retina 0.8.2, ~~85~~ 69 bytes

```
M`^(.+,)*(\d+,)?(?<-1>\1)*$(?(1)^)|M`^(.+,)*(\d+,)?(?<-1>\1)*$(?(1)^)

```

Try it online! Explanation:

```
M`

```

Selects Match mode. In fact, Retina defaults to Match mode for a single-line program, but the second copy of the code would always match if not for these extra characters.

```
^

```

Match must start at the beginning.

```
(.+,)*

```

Capture a number of runs of characters. Each run must end in a comma.

```
(\d+,)?

```

Optionally match a run of digits and a comma.

```
(?<-1>\1)*

```

Optionally match all of the captures in reverse order, popping each one as it is matched.

```
$

```

Match must end at the end.

```
(?(1)^)

```

Backtrack unless all of the captures were popped. It works by requiring the match to still be at the start of the string if we have an unpopped capture, which is impossible.
> 6 votes

# Answer
# Jelly, ~~27~~ 23 bytes

```
ṖUṁ@Ƒ€ṚẸHḢŒŒHḢŒṖUṁ@Ƒ€ṚẸ

```

Returns **1** for semi-palindromes, **0** otherwise.

Try it online!

### How it works

```
ṖUṁ@Ƒ€ṚẸHḢŒŒHḢŒṖUṁ@Ƒ€ṚẸ  Main link. Argument: A (array)

          Œ              Invalid token. Everything to its left is ignored.
           ŒH            Halve; divide A into two halves similar lengths. The middle
                         element (if there is one) goes into the first half.
             Ḣ           Head; extract the first half.
              ŒṖ         Generate all partitions of the first half.
                U        Upend; reverse each chunk of each partition.
                         Let's call the result C.

                     Ṛ   Yield R, A reversed.
                   Ƒ€    Fixed each; for each array P in C, call the link to the left
                         with arguments P and R.
                         Return 1 if the result is P, 0 if not.
                 ṁ@          Mold swapped; replace the n integers of C, in reading
                             order, with the first n integers of R.
                     Ẹ   Exists; check if one of the calls returned 1.

```
> 6 votes

# Answer
# 05AB1E, ~~59~~ ~~47~~ ~~43~~ 41 bytes

```
2äøø€.œ`âʒ`RQ}gĀIg_^q2äøø€.œ`âʒ`RQ}gĀIg_^

```

-12 bytes thanks to *@Emigna*.

Try it online or verify all test cases.

**Explanation:**

```
2ä               # Split the input into two parts
                 #  i.e. [3,4,2,0,2,3,4] → [[3,4,2,0],[2,3,4]]
  øø             # Zip twice without filler
                 # This will remove the middle item for odd-length inputs
                 #  i.e. [[3,4,2,0],[2,3,4]] → [[3,2],[4,3],[2,4]] → [[3,4,2],[2,3,4]]
    €.œ          #  Then take all possible partitions for each inner list
                 #   i.e. [[3,4,2],[2,3,4]]
                 #    → [[[[3],[4],[2]],[[3],[4,2]],[[3,4],[2]],[[3,4,2]]],
                 #       [[[2],[3],[4]],[[2],[3,4]],[[2,3],[4]],[[2,3,4]]]]
`                # Push both lists of partitions to the stack
 â               # Take the cartesian product (all possible combinations) of the partitions
                 #  i.e. [[[[3],[4],[2]],[[2],[3],[4]]],
                 #        [[[3],[4],[2]],[[2],[3,4]]],
                 #        ...,
                 #        [[[3,4,2]],[[2,3,4]]]]
  ʒ   }          # Filter this list of combinations by:
   `             #  Push both parts to the stack
    RQ           #  Check if the second list reversed, is equal to the first
                 #   i.e. [[3,4],[2]] and [[2],[3,4]] → 1 (truthy)
       gĀ        # After the filter, check if there are any combinations left
                 #  i.e. [[[[3,4],[2]],[[2],[3,4]]]] → 1 (truthy)
         Ig_     # Check if the length of the input was 0 (empty input-list edge-case)
                 #  i.e. [3,4,2,0,2,3,4] → 7 → 0 (falsey)
            ^    # Bitwise-XOR
                 #  i.e. 1 XOR 0 → 1 (truthy)
             q   # Stop the program (and then implicitly output the top of the stack)
2äøø€.œ`âʒ`RQ}gĀIg_^
                 # Everything after the `q` are no-ops to comply to the challenge rules

```
> 4 votes

# Answer
# Python 2, ~~157~~ ~~153~~ ~~147~~ 143 bytes

-4 bytes thanks to tsh.

```
s=lambda x,i=0:len(x)<2or[]<x[i:]and(x[-i:]==x[:i])&s(x[i:-i])|s(x,i+1)
s=lambda x,i=0:len(x)<2or[]<x[i:]and(x[-i:]==x[:i])&s(x[i:-i])|s(x,i+1)

```

Try it online!
> 4 votes

# Answer
# Jelly,  ~~33~~  32 bytes

-1 Thanks to Erik the Outgolfer
Thanks also to Dennis for a bug fix and looking into changing an implementation detail in Jelly.

```
ẸƇŒḂƇƊ$ƊĊHṀċÄẈṖŒŒṖẈÄċṀHĊƊ$ƊƇŒḂƇẸ

```

Semi-palindromes yield `1`, others yield `0`.

**Try it online!** (slow as it's \\$O(2^n)\\$ in input length)

Or see the test-suite.

The only chunks are the `ŒḂ`s ({3rd & 4th} vs {29th & 30th} bytes), just to allow the code to parse.

### How?

All the work is performed by the right-hand side - the "Main Link":

```
ŒṖẈÄċṀHĊƊ$ƊƇŒḂƇẸ - Main Link: list
ŒṖ               - all partitions
           Ƈ     - filter keep those for which this is truthy (i.e. non-zero):
          Ɗ      -   last three links as a monad:
  Ẉ              -     length of each
         $       -     last two links as a monad:
   Ä             -       cumulative addition
        Ɗ        -       last three links as a monad:
     Ṁ           -         maximum
      H          -         halve
       Ċ         -         ceiling
    ċ            -     count
              Ƈ  - filter keep those for which this is truthy:
            ŒḂ   -   is palindrome?
               Ẹ - any?

```
> 4 votes

# Answer
# 05AB1E, 37 bytes

Utilizes roughly the same technique Jonathan came up with.

```
.œʒ€gηOZ;îå}εÂQ}ZĀqĀZ}QÂε}åî;ZOηg€ʒ.œ

```

Try it online!

---

```
.œʒ€gηOZ;îå}εÂQ}ZĀqĀZ}QÂε}åî;ZOηg€ʒ.œ

```

Full program. Receives a list from STDIN, outputs **1** or **0** to STDOUT.

```
.œʒ        }

```

Filter-keep the partitions that satisfy...

```
   €gηOZ;îå

```

This condition: The lengths of each (`€g`) are stored in a list, whose prefixes (`η`) are then summed (`O`), hence giving us the cumulative sums of the lengths list. Then, the ceiled halve of the maximum of that list is pushed onto the stack – but keeping the original list on it as well (`Z;î`) and if it occurs (`å`) in the cumulative sums then the function returns truthy.

```
εÂQ}

```

For each, compare (`Q`) **a** with **a** reversed, which are pushed separately on the stack by `Â`. Returns a list of **0**s and **1**s.

```
ZĀq

```

Maximum. If any is truthy, then **1** else **0**. End execution. Everything that follows is completely ignored.
> 4 votes

# Answer
# Perl 6, ~~87~~ 79 bytes

*-8 bytes with some tricks from Jo King's answer*

```
$!={/\s/&&/^(.+)\s[(.+)\s]*$0$/&&$1.$!}#$!={/\s/&&/^(.+)\s[(.+)\s]*$0$/&&$1.$!}

```

Try it online!

Port of tsh's JavaScript answer. Returns two different Regex objects.
> 4 votes

# Answer
# Python 2, ~~275~~ ~~251~~ 205 bytes

-24 bytes thanks to @KevinCruijssen

-44 bytes thanks to @PostLeftGhostHunter

-2 more bytes thanks to @KevinCruijssen

```
def s(x):
 l=len(x)
 if l<2:return 1>0
 for i in range(1,l/2+1):
	if x[l-i:]==x[:i]:return s(x[i:l-i])
def s(x):
 l=len(x)
 if l<2:return 1>0
 for i in range(1,l/2+1):
	if x[l-i:]==x[:i]:return s(x[i:l-i])

```

Returns True for semi-palindrome, None otherwise

Try it online!
> 3 votes

# Answer
# Ruby, 129 bytes

```
f=->l{!l[1]||(1...l.size).any?{|x|l[0,x]==l[-x,x]&&f[l[x..~x]]}}#f=->l{!l[1]||(1...l.size).any?{|x|l[0,x]==l[-x,x]&&f[l[x..~x]]}}

```

Try it online!
> 2 votes

# Answer
# Japt, 66 bytes

```

@¯X eUsXn}a1 "
Ê§V?UÊ<2:ßUéV sVÑ
@¯X eUsXn}a1 "
Ê§V?UÊ<2:ßUéV sVÑ

```

Japt Interpreter

Big improvement this version, it actually beats most of the practical languages now. Now operates on an array of integers since the previous method had a bug.

Explanation:

```
@        }a1         Find the first number n > 0 such that...
 ¯X                   the first n elements
     UsXn             and the last n elements
    e                 are the same

"
Ê§V?UÊ<2:ßUéV sVÑ    String literal to make it a Semi-palindrome
@¯X eUsXn}a1 "

Ê§V?                 If n >= length of input...
    UÊ<2              return true if the length is less than 2
        :            Otherwise...
          UéV         move n elements from the end of the input to the start
              sVÑ     remove the first 2*n elements
         ß            and repeat on the remaining elements

```
> 1 votes

# Answer
# JavaScript (Node.js), 139 bytes

```
f=a=>(s=(''+a).replace(/^(.*),((.*),)?\1$/,'$3'))!=a?f(s):/,/.test(s)//^(.*),((.*),)?\1$/,'$3'))!=a?f(s):/,/.test(s)f=a=>(s=(''+a).replace(

```

Try it online!
> 1 votes

# Answer
## C (gcc) (X86), 216 bytes

```
p(L,a,n)int*a;{return n?(memcmp(a,a+L-n,n*4)|p(L-2*n,a+n,L/2-n))&&p(L,a,n-1):1<L;}
#define p(L,a)p(L,a,L/2)//p(L,a,n)int*a;{return n?(memcmp(a,a+L-n,n*4)|p(L-2*n,a+n,L/2-n))&&p(L,a,n-1):1<L;}
#define p(L,a)p(L,a,L/2)

```

Try it online!

`p(L,a,n)` returns 0 if array `a` of length `L` is a semi-palindrome, 1 otherwise. Given that all prefixes of length `>n` are already checked, it compares the prefix of length `n` with the suffix of length `n`. `p(L,a)` is the entry point.

Unfortunately, the more interesting solution is longer:

## 224 bytes

```
(f(L,a,n))//#define p(L,a)(n=L/2,
int*a,n;
{return n?(memcmp(a,a+L-n,n*4)|f(L-2*n,a+n,L/2-n))&&f(L,a,n-1):1<L;}//{return n?(memcmp(a,a+L-n,n*4)|f(L-2*n,a+n,L/2-n))&&f(L,a,n-1):1<L;}
int*a,n;
#define p(L,a)(n=L/2,f(L,a,n))//(

```

Try it online!

Ungolfed:

```
(f(L,a,n)) //#define p(L,a)(n=L/2,
int*a,n;
{
  return n
    ? (memcmp(a, a+L-n, n*4) | f(L-2*n, a+n, L/2-n)) &&
      f(L,a,n-1)
    : 1 < L;
} // { ... }
int*a,n;
#define p(L,a)(n=L/2,f(L,a,n)) //(

```
> 1 votes

# Answer
# Perl 6, 81 bytes

```
($!={/../&&/^(.+)(.*)$0$/&&$1.$!})o&chrs#($!={/../&&/^(.+)(.*)$0$/&&$1.$!})o&chrs

```

Try it online!

Returns the regex `/../` for True and the regex `/^(.+)(.*)$0$/` for False. Works similarly to nwellnhof's answer, but converts the list to a string beforehand.
> 1 votes

# Answer
# Brachylog, 21 bytes

```
ḍ{|b}ᵗ~cᵐ↔ᵈḍ{|b}ᵗ~cᵐ↔

```

Try it online!

```
ḍ              Split the input in half, with the second half longer if uneven.
 {|b}ᵗ         Maybe remove the first element of the second half.
      ~cᵐ      Partition both halves.
         ↔ᵈ    Is it possible for one to be the other's reverse?
ḍ{|b}ᵗ~cᵐ↔     The remainder of the program always succeeds.

```
> 1 votes

# Answer
# PHP 237 bytes

```
function f($a){for($x=2>$c=count($a);++$i<=$c/2;)$x|=($s=array_slice)($a,0,$i)==$s($a,-$i)&f($s($a,$i,-$i));return$x;}#function f($a){for($x=2>$c=count($a);++$i<=$c/2;)$x|=($s=array_slice)($a,0,$i)==$s($a,-$i)&f($s($a,$i,-$i));return$x;}

```

recursive function, returns `true` (for input containing less than two elements) or `1` for truthy,
`0` for falsy. Try it online (contains breakdown).

Actual code length is 118 bytes; semi-palindrome created via code duplication.

For better performance, replace `&` with `&&` and insert `!$x&&` before `++$i`.
> 0 votes

# Answer
# Scala, 252 bytes

```
def^(s:Seq[Int]):Int={val l=s.size;if(l>1)(1 to l/2).map(i=>if(s.take(i)==s.takeRight(i))^(s.slice(i,l-i))else 0).max else 1}//def^(s:Seq[Int]):Int={val l=s.size;if(l>1)(1 to l/2).map(i=>if(s.take(i)==s.takeRight(i))^(s.slice(i,l-i))else 0).max else 1}

```

Try it online!

PS. Apparently, solution is 2 times longer just to satisfy a requirement that source code is semi palindrome as well.

PPS. Not a code-golf candidate but purely functional solution using pattern matching:

```
  def f(s:Seq[Int], i:Int=1):Int = {
    (s, i) match {
      case (Nil ,_) => 1
      case (Seq(_), _) => 1
      case (l, _) if l.take(i) == l.takeRight(i) => f(l.slice(i,l.size-i), 1)
      case (l, j) if j < l.size/2 => f(l, i+1)
      case (_, _) => 0
    }
  }

```
> 0 votes

---
Tags: code-golf, decision-problem, restricted-source, self-validating
---


title: In for a bumpy ride

text:
# Question
Title: In for a bumpy ride
Your task is to write a computer program or function that takes a list of nonnegative integers of at least length 2 and determines if they are a "zigzag". A sequence is a zigzag if and only if the numbers alternate in being larger and smaller than the number that comes before them. For example \\$\[1,2,0,3,2\]\\$ and \\$\[4,2,3,0,1\]\\$ are zigzags but \\$\[1,2,0,0,3,1\]\\$ and \\$\[1,2,3,1\]\\$ are not.

For your decision you should output one of two different consistent values for each possibility (zigzag and not zigzag).

The code-points of your program or function must also be a zigzag itself. This means that when you take the sequence of code-points it should be a zigzag.

This is so answers will be scored in bytes with fewer bytes being better.

# Answer
> 9 votes
# Jelly, 5 bytes

```
IṠIỊẸ

```

Returns \\$0\\$ (zigzag) or \\$1\\$ (not zigzag).

The code points are \\$\[73, 205, 73, 176, 174\]\\$ in the Jelly code page.

Try it online!

### How it works

```
IṠIỊẸ  Main link. Argument: A (array)

I      Increments; compute the forward differences of A.
 Ṡ     Take their signs.
       A is zigzag iff the signs are alternating.
  I    Take the increments again.
       Alternating signs result in an increment of -2 or 2.
       Non-alternating signs result in an increment of -1, 0, or 1.
   Ị   Insignificant; map each increment j to (|j| ≤ 1).
    Ẹ  Any; return 0 if all results are 0, 1 in any other case.

```

# Answer
> 5 votes
# K (ngn/k), 23 bytes

```
{*/ 0 >1_ *':1_ -': x }

```

Try it online!

# Answer
> 4 votes
# Haskell, 87 bytes

```
f(a:b:c:d)|(>)a b,b<c=f$b:c:d |(<)a b,b>c=f$b:c:d |1>0=1>12
f[a ] =1<12
f(a:b:_)= a/= b

```

Try it online!

I wanted to get the ball rolling in terms of Haskell answers. I can't see a way to improve this yet, but I am convinced it can be done. I'm looking forward to what people can do from here.

# Answer
> 4 votes
# Python 2, ~~225~~ ~~223~~ ~~161~~ 139 bytes

-2 bytes thanks to Jakob
-62 bytes thanks to Dennis

```
e={eval }.pop()
p ="i"+"n"+"p"+"u"+"t ( "
s=e(p +")")
e(p +"` a"+"l"+"l([(x<y>z)+(x>y<z)f"+"o"+"r x,y,z i"+"n zip(s,s [1: ],s [2: ])])` )")

```

Try it online!

Credits for the bumpy algorithm goes to this answer

`input`, `print`, `exec`, `def` and `lambda` aren't bumpy so I only got `eval` left, which is stored on `e`
There are 2 main ways to bypass the restriction, placing `"+"` or  between the non-bumpy pairs, I opted for the former ( is shorter for each use, but it would need `replace(' ','')` resulting in more bytes)
Since `print` isn't bumpy, I can't use it directly, and since it isn't a funcion I can't use it inside `eval()`, so I had to use `input(result)` to output the result

# Answer
> 4 votes
# MATL, 9 bytes

```
dt?ZSd]pA

```

Try it online! Or verify all test cases

My first ever MATL program! The penultimate `p` was added for the zigzag requirement.

Explanation:

```
d    %take the difference between successive elements of input
t    %duplicate that
?    %if that is all non-zero
  ZS %take the sign of those differences (so input is all `-1`s and `1`s now)
  d  %take the difference of that (so if there are successive `1`s or `-1`s, this will have a 0)
]    %end-if
p    %take the product of topmost stack vector (will be 0 if either the original difference or
     % the difference-of-signs contained a 0)
A    %convert positive products to 1 (since OP specifies "you should output one of two different consistent values for each possibility ")

```

# Answer
> 3 votes
# Ohm v2, 5 bytes

```
δyδ½Å

```

Try it online!

The indices of the characters are \\$\[131,121,131,16,165\]\\$ in the linked code page.

### How it works

```
δyδ½Å – Full program / Single-argument block.
δy    – The signs of the deltas of the input
  δ   – The differences of the signs. Results in a sequences of 2's or -2's for
        bumpy arrays, as the signs alternate, giving either -1-1=-2 or 1-(-1)=2.
    Å – Check if all elements yield truthy results when...
   ½  – Halved.

```

# Answer
> 3 votes
# 05AB1E, ~~7~~ 5 bytes

```
¥ü*dZ

```

-2 bytes by taking the answer from the same challenge without source restriction. All credit goes to *@Grimmy*, so make sure to upvote his answer as well!!

Outputs `0` for zigzagging and `1` for non-zigzagging sequences.

The code points are `[165,252,42,100,90]` in the 05AB1E code page.

Try it online.

**Original 7-byter:**

```
¥.±¥Ä;P

```

Outputs `1.0` for zigzagging and `0.0` for non-zigzagging sequences.

The code points are `[165,46,177,165,196,59,80]` in the 05AB1E code page.

Try it online.

**Explanation:**

```
¥        # Take the forward differences (deltas) of the (implicit) input-list
         #  i.e. [1,2,0,3,2,3] → [1,-2,3,-1,1]
 ü       # For each overlapping pair:
  *      #  Multiply them together
         #   → [[1,-2],[-2,3],[3,-1],[-1,1]] → [-2,-6,-3,-1]
   d     # Check for each whether it's non-negative (>= 0)
         #  → [0,0,0,0]
    Z    # Take the maximum of that
         #  → 0
         # (after which it is output implicitly as result)

¥        # Take the forward differences (deltas) of the (implicit) input-list
         #  i.e. [1,2,0,3,2,3] → [1,-2,3,-1,1]
 .±      # Calculate the sign for each of them (-1 if a<0; 0 if 0; 1 if a>0)
         #  → [1,-1,1,-1,1]
   ¥     # Calculate the deltas of those
         #  → [-2,2,-2,2]
    Ä    # Take the absolute value of each
         #  → [2,2,2,2]
     ;   # Halve each
         #  → [1.0,1.0,1.0,1.0]
      P  # Take the product of the list resulting in either 1.0 or 0.0
         #  → 1.0
         # (after which it is output implicitly as result)

```

# Answer
> 2 votes
# Japt `-!`, ~~16~~ 14 bytes

Well, this ain't pretty but I'm just happy it works!

Outputs `true` for zig-zag or `false` if not.

```
ä'- m'g ä'a èÍ

```

Try it

Codepoints are `[228,39,45,32,109,39,103,32,228,39,97,32,232,205]` and included as the test in the link above.

---

## Explanation

```
                   :Implicit input of array
ä'-                :Consecutive differences
    m'g            :Map signs
        ä'a        :Consecutive absolute differences
             Í     :Subtract each from 2
            è      :Count the truthy (non-zero) elements
                   :Implicitly negate and output resulting boolean.

```

# Answer
> 2 votes
# tinylisp, 154 bytes

```
(d Z(q ( ( X Y T )(i T(i(l X Y )(i(l(h T)Y )(F(c Y T ) ) 0 )(i(l Y X )(i(l Y(h T ) )(F(c Y T ) ) 0)0 ) )(e(e X Y)0
( d F(q ( ( L )(Z(h L )(h(t L ) )(t(t L

```

Tr y i t o n lin e!

### Explanation

`(load library)` is disallowed by the source restriction, so we have to use only builtins. Since these are each one character, we can just add spaces wherever necessary to make the codepoints zigzag.

The solution uses a pair of mutually recursive functions. `F` takes a list of at least two elements and calls `Z` with three arguments: the first two elements (`X` and `Y`) and the remainder of the list (`T`). `Z` does most of the work:

* If `T` is not empty:
    + If `X` is less than `Y`:
        - If head of `T` is also less than `Y`, call `F` with `Y` prepended to `T`
        - Otherwise, return false
    + Else, if `Y` is less than `X`:
        - If `Y` is also less than head of `T`, call `F` with `Y` prepended to `T`
        - Otherwise, return false
    + Else (`X` equals `Y`), return false
* Else (`T` is empty, `X` and `Y` represent a two-element list):
    + Return true if `X` is not equal to `Y`, false otherwise

Ungolfed:

```
(load library)
(def zigzag?
 (lambda (X Y T)
  (if T
   (if (less? X Y)
    (if
     (less? (head T) Y)
     (zigzag-list? (cons Y T))
     0)
    (if (less? Y X)
     (if
      (less? Y (head T))
      (zigzag-list? (cons Y T))
      0)
     0))
   (equal? (equal? X Y) 0))))
(def zigzag-list?
 (lambda (L)
  (zigzag?
   (head L)
   (head (tail L))
   (tail (tail L)))))

```

# Answer
> 1 votes
# Jelly, 6 bytes

```
IṠµaIẠ

```

Try it online!

Returns `1` for truthy, `0` for falsy.

Codepoints: `[73, 205, 9, 97, 73, 171]` (valid)

# Answer
> 1 votes
# Perl 6, 61 bytes

```
{ [*] ($_[{1…*} ] Z<@$_)Z+^ ($_[{1…*} ] Z>@$_[{2…*} ])}

```

Try it online!

The code points are:

```
(123 32 91 42 93 32 40 36 95 91 123 49 8230 42 125 32 93 32 90 60 64 36 95 41 90 43 94 32 40 36 95 91 123 49 8230 42 125 32 93 32 90 62 64 36 95 91 123 50 8230 42 125 32 93 41 125)

```

And yes, those are unicode characters in there. This is more or less my original solution, with a few spaces and curly braces mixed in.

# Answer
> 1 votes
# 05AB1E, 10 bytes

```
¥DÄ/¥(Ä2QP

```

Try it online!

**Explanation**

```
¥           # calculate deltas of input
 DÄ/        # divide each by its absolute value
    ¥       # calculate deltas
     (      # negate each
      Ä     # absolute value of each
       2Q   # equals 2
         P  # product

```

Code points are: `[165, 68, 196, 47, 165, 40, 196, 50, 81, 80]`

---
Tags: code-golf, number, sequence, decision-problem, self-validating
---


title: Every Possible Cycle Length

text:
# Question
Title: Every Possible Cycle Length
A function (or program) which takes inputs and provides outputs can be said to have a cycle if calling the function on its own output repeatedly eventually reaches the original number. For instance, take the following function:

```
Input:  n    1 2 3 4 5 6
Output: f(n) 5 7 1 3 4 9

```

If we start with `n=1`, `f(n)=5`, `f(f(n))=f(5)=4`, `f(f(f(n)))=f(4)=3`, `f(f(f(f(n))))=f(3)=1`.

This is written `(1 5 4 3)`. Since there are 4 unique numbers in this loop, this is a cycle of length 4.

---

Your challenge is to write a program or function which has cycles of every possible length. That is, there must be a cycle of length 1, of length 2, and so on.

In addition, your function/program must be from the positive integers to positive integers, and it must be bijective, meaning that there must be a exactly one input value for every possible output value, over all positive integers. To put it another way, the function/program must compute a permutaion of the positive integers.

---

Details: Any standard input/output system is allowed, including STDIN, STDOUT, function argument, return, etc. Standard loopholes prohibited.

You do not need to worry about the limitations of your data types - the above properties need only hold under the assumption that an `int` or `float` can hold any value, for instance.

There are no restrictions on the behavior of the function on inputs which are not positive integers, and those inputs/outputs will be ignored.

---

Scoring is code golf in bytes, shortest code wins.

# Answer
# Pyth, 11 8 bytes

```
.<W-0zz1

```

A lot more boring than my previous answer.

Every number that contains a 0 digit maps to itself. Any other number maps to the number that has its digits rotated by 1. So for example:

```
1 -> 1
10 -> 10
15 -> 51 -> 15
104 -> 104
123 -> 231 -> 312 -> 123

```
> 14 votes

# Answer
# Python 2, ~~56~~ ~~55~~ 54 bytes

```
n=input()
a=b=1
while a+b<=n:a+=b;b+=1
print(n+~a)%b+a

```

Here's the first 21 outputs:

```
[1, 3, 2, 6, 4, 5, 10, 7, 8, 9, 15, 11, 12, 13, 14, 21, 16, 17, 18, 19, 20]

```

The pattern is obvious if we break the list up into chunks like so:

```
 1    2  3    4  5  6    7  8  9  10    11  12  13  14  15    16  17  18  19  20  21
[1]  [3, 2]  [6, 4, 5]  [10, 7, 8, 9]  [15, 11, 12, 13, 14]  [21, 16, 17, 18, 19, 20]

```
> 9 votes

# Answer
# Pyth, 25 bytes

```
+hK/*J/h@h*8tQ2 2tJ2%-QKJ

```

This is the same sequence as @Sp3000, but with a closed form. The closed form is:
> 8 votes

# Answer
# Python3, 40 bytes

```
n=input();print([n[1:]+n[0],n]['0'in n])

```

Every number that contains a 0 digit maps to itself. Any other number maps to the number that has its digits rotated by 1. So for example:

```
1 -> 1
10 -> 10
15 -> 51 -> 15
104 -> 104
123 -> 231 -> 312 -> 123

```
> 5 votes

# Answer
# Ruby, 16+1=17

With command-line flag `-p`, run

```
$_=$_[/.0*$/]+$`

```

This is a more complicated function than my other answer, but happens to be more golfable (and tolerant to trailing newlines). It takes the last nonzero digit of the input, plus any trailing zeroes, and moves it to the beginning of the number. So `9010300` becomes `3009010`. Any number with n nonzero digits will be part of an n-length cycle.

Input is a string in any base via STDIN, output is a string in that base.
> 4 votes

# Answer
# Ruby, 22+1=23

With command-line flag `-p`, run

```
~/(.)(.?)/
$_=$1+$'+$2

```

When given as input a string representation of a number (with no trailing newline), it keeps the first digit constant, then rotates the remainder left, so `1234` becomes `1342`.

This can be reduced to 21 characters with `$_=$1+$'+$2if/(.)(.)/`, but prints a warning.
> 3 votes

# Answer
# Pyth, 15 bytes

The shortest answer so far that uses numeric operations rather than string operations.

```
.|.&Q_=.&_=x/Q2

    Q                input
            /Q2      input div 2
           x   Q     that XOR input
          =          assign that to Q
         _           negate that
       .&       Q    that AND Q
      =              assign that to Q
     _               negate that
  .&                 input AND that
.|               Q   that OR Q

```

The effect of this function on the binary representation is to extend the rightmost block of 1s into the next 0; or if there is no 0, to reset it back to a single 1:

```
10010110100000 ↦
10010110110000 ↦
10010110111000 ↦
10010110111100 ↦
10010110111110 ↦
10010110111111 ↦
10010110100000

```

### Pyth, 26 bytes, fun variant

```
.|.&Q_h.&/Q2+Qy=.&/Q2_h.|y

    Q                           input
         /Q2                    input div 2
             Q                  input
                  /Q2           input div 2
                         yQ     twice input
                       .|  Q    that OR input
                     _h         NOT that
                .&              (input div 2) AND that
               =                assign that to Q
              y                 twice that
            +                   input plus that
       .&                       (input div 2) AND that
     _h                         NOT that
  .&                            input AND that
.|                          Q   that OR Q

```

Performs the above operation simultaneously to *all* blocks of 1s, not just the rightmost one—still using only bitwise and arithmetic operations.

```
1000010001001 ↦
1100011001101 ↦
1110011101001 ↦
1111010001101 ↦
1000011001001 ↦
1100011101101 ↦
1110010001001 ↦
1111011001101 ↦
1000011101001 ↦
1100010001101 ↦
1110011001001 ↦
1111011101101 ↦
1000010001001

```
> 3 votes

# Answer
# Python, 43

The inverse of Sp3000's function, implemented recursively.

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

```

The function is a one-cycle followed by a two-cycle followed by a three-cycle, ...

```
(1)(2 3)(4 5 6)(7 8 9 10)(11 12 13 14 15)...

```

The operation `n%k+1` acts as a `k`-cycle on the numbers `1..k`. To find the appropriate `k` to use, shift everything down by `k=1`, then `k=2`, and so on, until `n<=k`.
> 2 votes

# Answer
# Brachylog, 5 bytes

```
∋0&|↺

```

Try it online!

Port of @orlp's Pyth answer. Comes out simple and neat:

```
∋0    % If input contains a 0 (since input is a single number, "contains" ∋ treats it as an array
      %   of its digits, so this means "if any of input's digits are 0")
&     % Then output is the input
|     % Otherwise
↺     % Circularly shift the input once, and unify that with the output

```

I originally wanted to port @Sp3000's Python solution, but that took a whopping **23 bytes**:

```
⟧∋B-₁⟦++₁A≤?;A--₁;B%;A+

```

Try it online!
> 2 votes

# Answer
# x86 32-bit machine code, 16 bytes

```
0F BC C1 0F B3 C1 E3 01 40 0F AB C1 91 14 00 C3

```

Try it online!

Uses the `fastcall` calling convention – argument in ECX, result in EAX.

This function leaves values with only one 1 bit (powers of 2) unchanged; other values are modified by moving the lowest 1 bit one place up, or to the bottom if the position above it is already 1. Thus, a non-power-of-2 is in a cycle of length equal to the position of its second-lowest 1 bit.

In assembly:

```
.global f
f:
    bsf eax, ecx    # Set EAX to the position of the lowest 1 bit in ECX.
    btr ecx, eax    # Remove that 1 bit from ECX.
    jecxz s         # Jump if ECX is 0 (had only one 1 bit).
    inc eax         # (Otherwise) Increase EAX by 1.
s:  bts ecx, eax    # Set to 1 the bit in ECX at position EAX,
                    #  and set the carry flag (CF) to its former value.
    xchg ecx, eax   # Exchange registers, moving the number into EAX.
    adc al, 0       # Add 0+CF to the low byte of EAX.
    ret             # Return.

```
> 2 votes

# Answer
# Swift 1.2, 66 bytes

```
func a(b:Int){var c=0,t=1,n=b
while n>c{n-=c;t+=c++}
print(n%c+t)}

```

```
Input:  1,   2, 3,  4, 5, 6,   7, 8, 9, 10,   11, 12, 13, 14, 15
Output: 1,   3, 2,  5, 6, 4,   8, 9, 10, 7,   12, 13, 14, 15, 11

```
> 1 votes

# Answer
## JavaScript (ES6), 43 bytes

```
f=(n,i=1,j=1)=>n>j?f(n,++i,j+i):n++<j?n:n-i

```
> 0 votes

# Answer
## Matlab(189)

```
  function u=f(n),if(~n|n==1)u=n;else,u=n;y=factor(n);z=y(y~=2);if ~isempty(z),t=y(y~=max(y));if isempty(t),u=y(end)*2^(nnz(y)-1);else,g=max(t);e=primes(g*2);u=n/g*e(find(e==g)+1);end,end,end

```

---

* **The function:**

Maps any integer according to its prime factors, if the number is nil or factorised into 2 or 1, the number is mapped to itself, otherwise we pick the biggest prime factor of this number, then we increment the remaining different prime factors by the closest bigger prime factor until we reach the number `biggest_prime^n` where `n` is the sum of all exponents of all factors, once we reach that amount, we turn to `max_prime*2^(n-1)` and we reproduce the same cycle again.
> 0 votes

# Answer
## Matlab(137)

```
  function u=h(n),if(~n|n==1)u=n;else,u=n;y=factor(n);z=y(y~=2);if~isempty(z),e=nnz(y);f=nnz(z);if(~mod(e,f)&e-f)u=n/2^(e-f);else,u=u*2;end

```

---

* A slightly similar approach, multiplying gradually any number not equal to {0,1,2^n} by `2` until we stumble upon an exponent of `2` which is divisible by sum of exponents of other prime factors. then we move to the beginning of the cycle dividing by `2^(sum of exponents of other primes)`. the other numbes are mapped to themselves.
> 0 votes

# Answer
# 05AB1E, 4 bytes

```
WĀiÁ

```

Port of *@orlp*'s Pyth answer, so make sure to upvote him/her as well.

Try it online or verify some test cases.

**Explanation:**

```
W     # Push the smallest digit of the (implicit) input-integer (without popping)
 Āi   # If this is NOT 0:
   Á  #  Rotate the integer once towards the right
      # (after which the resulting integer is output implicitly)

```
> 0 votes

# Answer
# x86 32-bit machine code, 11 bytes

```
0F BD C8 D1 E8 73 FC 0F AB C8 C3

```

Try it online!

Uses the `regparm(1)` calling convention – argument in EAX, result in EAX.

This function takes a number's binary digits (without leading zeroes) and rotates them right until the highest one is again a 1.

In assembly:

```
f:  bsr ecx, eax    # Set ECX to the highest position of a 1 bit in EAX.
r:  shr eax, 1      # Shift EAX right by 1 bit, with the lowest bit going into CF.
    jnc r           # Repeat if CF=0.
    bts eax, ecx    # Set to 1 the bit in EAX at position ECX.
    ret             # Return.

```
> 0 votes

---
Tags: code-golf, math, permutations, open-ended-function
---


title: Climbing the Bookshelf

text:
# Question
Title: Climbing the Bookshelf
## Introduction

You're making a robot that can navigate a set of books of varying heights. It can climb books and jump off books, but if the distance is too big it will stop to prevent damage. To figure out the ideal design, you're writing a simulator.

Your program will take as input a list of numbers, representing the heights of the books in the bookshelf, as well as a number indicating the durability of the robot. Starting from the first item of the list, your robot will traverse the bookshelf. If the robot comes across a change in height, it will only be able to continue if the change is less than or equal to the robot's durability. Your job is to output which book the robot is on when it stops, starting from either 0 or 1. You may safely assume that the height of the first book the robot is on will be equal to or less than the robot's durability.

## Scoring

This is code-golf, so shortest answer wins.

## Examples (starting from 1)

```
[1, 1, 1], 1 -> 3
[0, 1, 0], 0 -> 1
[1, 2, 3, 2], 1 -> 4
[1, 3, 4, 4, 0], 2 -> 4
[1, 3, 4, 4, 0, 1], 2 -> 4

```

# Answer
> 11 votes
# Wolfram Language (Mathematica), 33 bytes

```
dIf[Abs[#2-#]>d,0,1+#0@##2,0]&

```

Try it online!

Input `[durability][heights...]`. Returns 0-indexed.

```
If[Abs[#2-#]>d             ]    is the next height difference out of limits?
              ,0                  yes: 0
                ,1+#0@##2         no : recurse on tail and add 1
                         ,0       err: 0 (input len <2)

```

# Answer
> 7 votes
# Octave / MATLAB, ~~37~~ 35 bytes

*2 bytes saved thanks to @Giuseppe!*

```
@(x,d)sum(cumprod(abs(diff(x))<=d))

```

Output is 0-based.

Try it online!

# Answer
> 6 votes
# JavaScript (ES7), 41 bytes

*-6 thanks to @emanresu A*

```
d=>f=([a,...x])=>(a-x[0])**2<=d*d&&-~f(x)

```

# JavaScript (ES7), 42 bytes

```
d=>f=([a,...x])=>(a-x[0])**2<=d*d?f(x)+1:1

```

Recursive solution. Takes input via currying, robot durability first.

Relies on `NaN <= x` always being false, saving a check to see if `x` is long enough.

# Answer
> 6 votes
# Vyxal, 7 bytes

```
¯ȧ<1JTh

```

Try it Online!

```
¯ȧ      # Get absolute differences
  <     # Find all less than the input
   1J   # Append a 1
      h # Get the first...
     T  # Index of a 1

```

# Answer
> 6 votes
# Perl 5 \+ `-pa`, 40 bytes

```
//,$\++while!eof&&"@F">=abs+($_=<>)-$'}{
```

Try it online!

## Explanation

Thanks to `-pa` the durability is stored in `$_` (although this is quickly overwritten) and `@F`. This then loops `while` STDIN is not `eof` and `"@F"` (interpolates the values in `@F`, just the durability in this case) is greater than the next input (retrieved with `<>` and stored in `$_`) subtracted from the remainder of the previous `m//`atch (which starts out empty, `0` in numeric context). The body of the `while` is matching against nothing, purely to store the previous value in `$'` without having to set manually, and incrementing `$\`, which is automatically output thanks to `-p`. The final `}{` is to break out of the implicit `while (<STDIN>)` from `-p` (well, `-n` which is implied by `-p`) to prevent `$_` being output as well.

# Answer
> 6 votes
# Emojicode, 272 bytes

```
❗❗➡d❗❗➡l l➡a 0➡ca 0❗v a↪v❗➖l c❗❗▶dc❗c⬅➕1c❗

```

Try it online!

# Answer
> 5 votes
# Python 3, 80 bytes

Returns 0-based index.

```
lambda l,n:next((i for i,(a,b)in enumerate(zip(l,l[1:]))if abs(a-b)>n),len(l)-1)

```

Try it online!

# Answer
> 5 votes
# Factor, ~~50~~ 43 bytes

```
[ differences vabs [ >= ] with count-head ]

```

count-head postdates build 1525, the one TIO uses, so here's a screenshot running this in Factor's REPL:

## Explanation

Takes input as `durability heights`. 0-indexed. `count-head` is a combinator that applies a quotation to each element of a sequence, counting how many times the quotation returns `t` and stopping once an `f` is encountered.

```
                        ! 2 { 1 3 4 4 0 }
differences             ! 2 { 2 1 0 -4 }
vabs                    ! 2 { 2 1 0 4 }
[ >= ] with count-head  ! 3

```

# Answer
> 5 votes
# Jelly, 7 bytes

5 if we may output 1-indexed and modular (i.e. yield 0 for the rightmost) - remove `;1`

```
IA>;1TḢ

```

A dyadic Link accepting a list and an integer that yields the 1-indexed stopping point.

**Try it online!**

### How???

```
IA>;1TḢ - Link: list, B; integer, D
I       - incremental differences of B
 A      - absolute values
  >     - greater than D?
   ;1   - concatenate a one
     T  - truthy 1-indexed indices
      Ḣ - head

```

# Answer
> 5 votes
# Haskell, 42 bytes

```
(a:b:r)!s|s<abs(a-b)=1
(h:t)!s=1+t!s
x!_=0

```

Try it online!

Three definitions of infix `!`

* 1st: guards against big step stopping the robot.
* 2nd: step was fine, continue.
* 3rd: end of list.
Due to 1 indexing it was possible to save something by reaching end of list instead of ending at a single element e.g. \[x\]!\_=0

# Answer
> 5 votes
# C (gcc), ~~56~~ ~~51~~ 49 bytes

```
f(a,n,d)int*a;{n=!--n||(*a-*++a)/~d?:1+f(a,n,d);}

```

Try it online!

*Saved 5 bytes thanks to att!!!*
*Saved 2 bytes thanks to AZTECCO!!!*

Inputs a pointer to an array of integers, its length (because pointers in C carry no length info), and the durability of the robot.
Returns to the number of the book (starting at \\$1\\$) that the robot stops at.

# Answer
> 5 votes
# 05AB1E, 7 bytes

```
¥Ä‹1ª1k

```

0-based.

Try it online or verify all test cases.

**Explanation:**

```
¥        # Get the deltas/forward-differences of the first (implicit) input-list
 Ä       # Convert each to its absolute value
  ‹      # Check for each integer in the list whether the second (implicit)
         # input-integer is smaller than it
   1ª    # Append a trailing 1
     1k  # Pop the list, and push the (0-based) index of the first 1
         # (which is output implicitly as result)

```

---

Could be 5 bytes if we're allowed to output a modular index, so it'll output `-1` if it's able to travel across all books:

```
¥ÄÅΔ‹

```

Try it online or verify all test cases.

**Explanation:**

```
¥Ä     # Same as above
  ÅΔ   # Push the first 0-based index which is truthy for
       # (or -1 if none were truthy)
    ‹  #  Check if the second (implicit) input-integer is smaller than the
       #  current integer
       # (after which the found index is output implicitly as result)

```

# Answer
> 5 votes
# Python 3, 53 bytes

```
s=lambda d,f,*t,p=0:d<abs(f-p)or t==()or-~s(d,*t,p=f)

```

Try it online!

Input is taken as varargs. Surprisingly the 1-based indexing makes the code shorter, since "or" is a byte shorter than "and".

# Answer
> 5 votes
# Japt, 10 bytes

I am ridiculously out of practice! 0-indexed.

```
äa pVÄ b>V

```

Try it

# Answer
> 4 votes
# Wolfram Language (Mathematica), 40 bytes

Output is 0-base

```
LengthWhile[Abs@Differences@#-#2,#<=0&]&

```

Try it online!

# Answer
> 4 votes
# Charcoal, 20 bytes

```
Ｉ⌕Ｅθ∨⁼κ⊖Ｌθ‹η↔⁻ι§θ⊕κ¹

```

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

```
   θ                    Input list
  Ｅ                     Map over values
      κ                 Current index
     ⁼                  Equals
         θ              Input list
        Ｌ               Length
       ⊖                Decremented
    ∨                   Logical Or
           η            Input durability
          ‹             Is less than
              ι         Current value
            ↔⁻          Absolute difference with
                θ       Input list
               §        Indexed by
                  κ     Current index
                 ⊕      Incremented
 ⌕                      Find index of
                   ¹    Literal integer `1`
Ｉ                       Cast to string
                        Implicitly print

```

# Answer
> 4 votes
# K (ngn/k), 21 bytes

```
{*&(y<x|-x:1_-':x),1}

```

Try it online!

# Answer
> 4 votes
# Julia 1.0, 37 bytes

```
h/r=findfirst(abs.(diff([h;Inf])).>r)

```

Try it online!

**35 bytes** porting @LuisMendo's Octave solution: `h/r=sum(cumprod(abs.(diff(h)).<=r))`

# Answer
> 3 votes
# APL+WIN, ~~12~~ 14 bytes

Plus 2 bytes to accomodate new example suggested by @chunes

Prompts for heights then durability. Index = 1

```
+/^\1,⎕≥|-2-/⎕

```

Try it online! Thanks to Dyalog Classic

# Answer
> 3 votes
# Python 3, 71 bytes

```
lambda h,d:([abs(h[i+1]-h[i])>d for i in range(len(h)-1)]+[1]).index(1)

```

Try it online!

# Answer
> 3 votes
# Desmos, 96 50 47 bytes

*\- a whopping **46** bytes thanks to Aiden Chow
\- 3 bytes thanks to Aiden Chow again*

```
L=l.length
\min(\{(l[2...]-l)^2>aa:[1...L],L\})

```

Probably not the right language, but I had a lot of fun coding this.
Receives a list `l` and durability `a` as input.
Online Version

# Answer
> 3 votes
# Retina 0.8.2, 58 bytes

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

```

Try it online! Link includes test cases. 0-indexed. Takes the durability first followed by the list of heights. Explanation:

```
\d+
$*

```

Convert to unary.

```
,(1*)(1*)(?=,\1(1*))
,$2$3

```

Take the absolute difference between each height and the next (`$2` is for the positive difference, `$3` for the negative). Note that the last height remains in the input.

```
(1*)(,(?!1\1)1*)*,.*
$#2

```

Match the durability and as many differences that don't exceed the durability, then replace everything with the count of those differences. (The comma is necessary to avoid matching the last height.)

# Answer
> 3 votes
# x86-16 machine code, 17 bytes

```
00000000: 33ff 47ac 2a04 7302 f6d8 3ac4 7702 e2f2  3.G.*.s...:.w...
00000010: c3                                       .

```

Listing:

```
33 FF       XOR  DI, DI         ; zero jump counter
        BOOK_LOOP:
47          INC  DI             ; increment jump counter
AC          LODSB               ; AL = current height
2A 04       SUB  AL, [SI]       ; AL = AL - next height
73 02       JAE  IS_POS         ; is positive?
F6 D8       NEG  AL             ; if not, negate to get abs value
        IS_POS:
3A C4       CMP  AL, AH         ; over threshold?
77 02       JA   DONE           ; if so, push the AZ-5 button
E2 F2       LOOP BOOK_LOOP      ; otherwise, keep plugging
        DONE:
C3          RET                 ; return to caller

```

Input list at `[SI]`, length in `CX`, threshold in `AH`. Output stopping index (1 based) in `DI`.

About as vanilla asm as you can get. Any time I tried to get clever it was more bytes...

# Answer
> 3 votes
# , ~~43~~ 42 bytes

*Edit: -1 byte thanks to pajonk (who anyway found a better approach...)*

```
function(x,y)which(c(abs(diff(x))>y,T))[1]

```

Try it online!

# Answer
> 3 votes
# , 41 bytes

```
function(x,y)match(T,c(abs(diff(x))>y,T))

```

Try it online!

Based on @Dominic van Essen's answer, so test harness taken from there.

The idea emerged when golfing Dominic's answer and using `which`: "hmm, we need the first index and I remember that there's a function that returns only the first index (which is annoying in some challenges). Oh, it's `match`!"

---
Tags: code-golf, simulation, algorithm
---