# Bumping Series Implementation

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.

• Feb 26 at 15:49
• Sorry, I used camscanner to do it from my diary, I write it in dutch and would even prefer using a dutch Q&A site Feb 26 at 15:52
• ChatGPT or even Google translate would probably help you write a clearer post in English. Mar 2 at 19:35
• I am confident about my English @Jacob Mar 3 at 6:46
• Sorry @Jacob yes, auto selector did this Mar 3 at 11:58

# 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.

• I honestly wish you could get some recognition for this, this is a marvel! Splendid job, I really cannot express a thanks to you @Neil Feb 26 at 19:38
• Can I confirm you are the founder of this algorithm? Feb 26 at 19:39
• or was it already discovered? Feb 26 at 19:39
• @AiraThunberg I derived it myself without looking anything up so for all I know it may only be an independent rediscovery.
– Neil
Feb 26 at 19:55
• Definitely a marvel, if no one does, I congratulate you for finding an algorithm I and my BFF thought no one could discover, we literally toured some universities and the CS professors had one answer, "We do not know" Feb 26 at 20:49

# 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)

• square-root ceiling decrement is the same as decrement square-root floor for positive integer n which doesn't make a difference in floating point but in integer it should save you some bytes.
– Neil
Feb 26 at 22:58
• (just tried it and ’Æ½‘×\$‘ạ⁸2*×‘H seems to work for 14 bytes)
– Neil
Feb 26 at 23:01
• Thanks @Neil! Yeah, that is a valid simplification. Feb 27 at 20:25

# 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!

• Flags don't count for extra bytes anymore, so this is just 96 Mar 5 at 20:05
• Suggest l-!v*2 instead of v?l:l-2 Mar 19 at 8:01

# 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)


# JavaScript, 49 bytes

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

• 49 bytes Mar 6 at 14:48