7
\$\begingroup\$

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:

image

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:

image1

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.

\$\endgroup\$
3

6 Answers 6

11
+100
\$\begingroup\$

Charcoal, 21 bytes

NθI⊘×⊕θX²↔⁻θ⊕×⊖⌈₂θ⌈₂θ

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

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

30 bytes in integer arithmetic:

NθI⊘×⊕θX²↔⁻θ⊕×⊖⌈₂θ⌈₂θ

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

\$\endgroup\$
1
  • 3
    \$\begingroup\$ @AiraThunberg I derived it myself without looking anything up so for all I know it may only be an independent rediscovery. \$\endgroup\$
    – Neil
    Feb 26 at 19:55
5
\$\begingroup\$

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)
\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$
    – Neil
    Feb 26 at 22:58
  • \$\begingroup\$ (just tried it and ’ƽ‘×$‘ạ⁸2*בH seems to work for 14 bytes) \$\endgroup\$
    – Neil
    Feb 26 at 23:01
  • \$\begingroup\$ Thanks @Neil! Yeah, that is a valid simplification. \$\endgroup\$ Feb 27 at 20:25
1
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ Flags don't count for extra bytes anymore, so this is just 96 \$\endgroup\$
    – noodle man
    Mar 5 at 20:05
  • \$\begingroup\$ Suggest l-!v*2 instead of v?l:l-2 \$\endgroup\$
    – ceilingcat
    Mar 19 at 8:01
1
\$\begingroup\$

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)
\$\endgroup\$
0
1
\$\begingroup\$

Mathematica, 53 bytes

Formula:

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

f=((#+1)*2^Abs[#-⌈Sqrt@#⌉*(⌈Sqrt@#⌉-1)-1])/2&

Try it online!

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

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

\$\endgroup\$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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