Bumping Series Implementation

Question

I have a follow-up question here from my previous question on Math SE. I am lazy enough to explain the content again, so I have used a paraphraser to explain it below:

I was considering arbitrary series, springing up as a top priority, when I considered one potential series in my mind. It is as per the following:

The essential thought is, take a line of regular numbers \$\mathbb{N}\$ which goes till boundlessness, and add them. Something apparent here is that the most greatest biggest number \$\mathbb{N}_{max}\$ would be \$\mathbb{N}_{i}\$. In essential words, on the off chance that we go till number 5, \$\mathbb{N}_5\$ the level it comes to by summation is 5.

Further, continuing, we can get:

The essential ramifications here is that we knock the numbers by unambiguous \$\mathbb{N}\$. At start, we take the starting number, for our situation it is 1, we move once up and afterward once down. Then we do it two times, threefold, etc. So 1 3 2 as per my outline is one knock. At the closure \$\mathbb{N}\$ which is 2 here, we will hop it by 2 and make it low by 2. So it gets 2 5 12 7 4. Here, expect \$\mathbb{N}_i\$ as the quantity of incrementation, before it was 1, presently it is 2. We get various sets, with various terms, however absolute number of terms we overcome this would be \$2 \mathbb{N}_i + 1\$. Presently, it will begin from 4, continue taking 3 leaps prior to arriving by three terms. By this, we get series featured by circles in that three-sided exhibit as:

1, 3, 2, 5, 12, 7, 4, 9, 20, 44, 24, 13, 7, 15, 32, 68, 144, 76, 40, 21, 11, 23, 48, 100, 208, 432, 224, 116, 60, 31, 16...

The series appear to be disparate, my particular inquiry this is the way to address this series in Numerical terms.

Challenge: Implement the algorithm which can build this series.

Scoring Criteria: It is ranked by fastest-algorithm so the answer with lowest time complexity is considered (time complexity is loosely allowed to be anywhere) but the program must have been running accurate result.

Answer 1

Charcoal, 21 bytes

ＮθＩ⊘×⊕θＸ²↔⁻θ⊕×⊖⌈₂θ⌈₂θ

Try it online! Link is to verbose version of code. Outputs the nth term. Explanation:

Ｎθ                      First input as a number
      θ                 First input
     ⊕                  Incremented
    ×                   Multiplied by
        ²               Literal integer `2`
       Ｘ                Raised to power
           θ            First input
         ↔⁻             Absolute difference with
                 θ      First input
                ₂       Square root
               ⌈        Ceiling
              ⊖         Decremented
             ×          Multiplied by
                    θ   First input
                   ₂    Square root
                  ⌈     Ceiling
   ⊘                    Halved
  Ｉ                     Cast to string

30 bytes in integer arithmetic:

ＮθＩ⊘×⊕θＸ²↔⁻θ⊕×⊖⌈₂θ⌈₂θ

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

Answer 2

Jelly, 13 bytes

Port of Neil's answer (I was working towards it myself but he nailed it).

Unsure of the complexity of this closed-form formula, but think it is \$O(M(B(n))B(n))\$ where \$n\$ is the input, \$M(x)\$ is the multiplication of two \$x\$ bit numbers and \$B(x)\$ is the bit-length of \$x\$.

½Ċ’×$‘ạ⁸’2*ב

A monadic Link that accepts \$n\$ and yields \$a(n)\$.

Try it online!

How?

½Ċ’×$‘ạ⁸’2*ב - Link: positive integer, n
½             - square-root
 Ċ            - ceiling
    $         - last two links as a monad - f(x=that):
  ’           -   decrement (x)
   ×          -   (that) multiply (x)
     ‘        - increment (that) -> A
       ⁸      - chain's left argument = n
      ạ       - (A) absolute difference (n)
        ’     - decrement (that) -> E
         2    - two
          *   - (2) exponentiate (E)
           ×  - (that) multiply (n)
            ‘ - increment

---

To avoid floating point arithmetic we could instead do it in  17 16  14 bytes (-2 thanks to Neil!):

’ƽ‘×$‘ạ⁸2*בH

Try it online!

This replaces ½Ċ’×$ with ’ƽ‘×$ and moves the decrement out of the exponent, instead halving at the end (H).

’ƽ‘×$ - chain: integer n
’      - decrement -> n-1
 ƽ    - integer-square-root (n-1) (uses only integer arithmetic)
     $ - last two links as a monad - f(x=that):
   ‘   -   increment (x)
    ×  -   (that) multiply (x)

Answer 3

C (gcc), 97 + 3 bytes

+3 bytes from -lm. Runs in O(n) time, where n is the index.

f(M,n,v,l,c){l=0;for(n=c=1;M--;l+=v&&v--?:-1)n=((v=l?v:c++)?2*n:n/2+.5)+pow(2,v?l:l-2);return n;}

Try it online!

Answer 4

05AB1E, 13 bytes

tîD<*-<ÄoI>*;

Another port of @Neil's Charcoal answer, so make sure to upvote him as well!

Try it online or verify all test cases.
_{The TIO-links use the legacy version of 05AB1E, because the regular 05AB1E on TIO is out-of-date, and still contains an already fixed bug when using o on decimal values ending with .0.}

Explanation:

Basically implements the formula found by @Neil:

$$a(n) = \frac{(n+1)\times 2^{\left|n-\left\lceil\sqrt{n}\right\rceil\times(\left\lceil\sqrt{n}\right\rceil-1)-1\right|}}{2}$$

t              # Get the square root of the (implicit) input-integer
 î             # Ceil it
  D            # Duplicate it
   <           # Decrease the copy by 1
    *          # Multiply the two together
     -         # Subtract this from the (implicit) input-integer
      <        # Decrease that by 1
       Ä       # Get the absolute value of that
        o      # Take 2 to the power that
         I>    # Push the input+1
           *   # Multiply the two together
            ;  # Halve it
               # (after which the result is output implicitly)

Answer 5

JavaScript, 49 bytes

Port of Neil's answer

n=>-~n*2**~-Math.abs(n+(c=(n**=.5)%1?~n:-n)*~c-1)

Formula:

$$ f(n) = \frac{(n+1)\times 2^{\left|n-\left\lceil\sqrt{n}\right\rceil\times(\left\lceil\sqrt{n}\right\rceil-1)-1\right|}}{2} $$

Try it:

f=n=>-~n*2**~-Math.abs(n+(c=(n**=.5)%1?~n:-n)*~c-1)

for(i=0;i<20;)console.log(f(++i))

Upd 54 -> 49

Thanks to Arnauld for the tip to reduce bytes count