25
\$\begingroup\$

Let's consider the sequence \$S\$ consisting of one \$1\$ and one \$0\$, followed by two \$1\$'s and two \$0\$'s, and so on:

$$1,0,1,1,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,0,...$$

(This is A118175: Binary representation of n-th iteration of the Rule 220 elementary cellular automaton starting with a single black cell.)

Given \$n>0\$, your task is to output \$a(n)\$, defined as the number of \$1\$'s among the \$T(n)\$ first terms of \$S\$, where \$T(n)\$ is the \$n\$-th triangular number.

The first few terms are:

$$1,2,3,6,9,11,15,21,24,28,36,42,46,55,65,70,78,91,99,105,...$$

One way to think of it is to count the number of \$1\$'s up to the \$n\$-th row of a triangle filled with the values of \$S\$:

1 (1)
01 (2)
100 (3)
1110 (6)
00111 (9)
100001 (11)
1111000 (15)
00111111 (21)
000000111 (24)
1111000000 (28)
01111111100 (36)
...

Rules

You may either:

  • take \$n\$ as input and return the \$n\$-th term, 1-indexed
  • take \$n\$ as input and return the \$n\$-th term, 0-indexed
  • take \$n\$ as input and return the \$n\$ first terms
  • take no input and print the sequence forever

This is a challenge.

\$\endgroup\$
  • 1
    \$\begingroup\$ OEIS draft: A338546 \$\endgroup\$ – Arnauld Nov 2 at 12:23
  • \$\begingroup\$ Can we output as a list? \$\endgroup\$ – SunnyMoon Nov 2 at 14:24
  • \$\begingroup\$ @SunnyMoon Sure, that's one way of implementing the 3rd output method. \$\endgroup\$ – Arnauld Nov 2 at 14:31
  • 2
    \$\begingroup\$ Tip: You can use n^{\text{th}} in mathjax to get: \$n^{\text{th}}\$. \$\endgroup\$ – Noodle9 Nov 2 at 18:14
  • \$\begingroup\$ It would be nice if you could explain the automaton at least a little bit in the post. \$\endgroup\$ – Wheat Wizard Nov 4 at 12:33

29 Answers 29

7
\$\begingroup\$

Jelly, 9 bytes

ḤR>)FŒHṪS

A monadic Link accepting \$n\$ which yields \$a(n)\$.

Try it online! Or see the test-suite.

How?

We can think of \$S\$ as being built in blocks of length \$2i\$ where each block is a string of \$i\$ ones followed by \$i\$ zeros: 10 1100 111000 ....

If we stop at \$i=x\$ and call the result \$S_x\$ we know that \$S_x\$ necessarily contains an equal number of ones and zeros.

We also know that the length of \$S_x\$ will be \$\sum_{i=1}^{x}2i = 2 \sum_{i=1}^{x}i = 2T(x)\$.

So the value of \$a(x)\$ is the count of ones in the first half of \$S_x\$.

An alternative way to get this same result is to subtract the count of the zeros in the first half of \$S_x\$ from \$T(x)\$, and since \$S_x\$ contains an equal number of ones and zeros this must also be the count of zeros in the second half of \$S_x\$. Therefore we can form the complement of \$S_x\$ and count the ones in its second half:

ḤR>)FŒHṪS - Link: integer, n
   )      - for each (i in [1..n]): e.g. i=3
Ḥ         -   double                       6
 R        -   range                        [1,2,3,4,5,6]
  >       -   greater than i?              [0,0,0,1,1,1]
    F     - flatten -> [0,1,0,0,1,1,0,0,0,1,1,1,...]
     ŒH   - split into two equal length parts
       Ṫ  - tail
        S - sum
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Ah, this means I can drop the v from my Gaia answer. Neat observation! \$\endgroup\$ – Giuseppe Nov 3 at 1:30
6
\$\begingroup\$

Wolfram Language (Mathematica), 41 bytes

Sum[1-⌈s=√n⌉+Round@s,{n,#(#+1)/2}]&

Try it online!

-2 bytes from @ZippyMagician

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

Husk, 8 bytes

Σ↑ṁṘḋ2NΣ

Try it online! or Verify first 12 values

Returns the \$n^{th}\$ value of the sequence, 1 indexed.

Explanation

Σ↑ṁṘḋ2NΣ
  ṁ   N  map the following across natural numbers and concatenate
   Ṙḋ2   replicate [1,0] n times
 ↑       take all values
       Σ till the triangular number of the input
Σ        sum them
| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

Python 2, 47 bytes

f=lambda n,k=8:k>n*-~n*2or(-k**.5%2<1)+f(n,k+4)

Try it online!

52 bytes

lambda n:sum(-(k+1)**.5%1<.5for k in range(n*-~n/2))

Try it online!

Based on the formula for \$S\$ that user's noted from the OEIS page of A118175. We simplify it to the following, one-indexed using Booleans for 0/1: $$ S(k) = \mathrm{frac}(-\sqrt{k}) < \frac{1}{2},$$ where \$\mathrm{frac}\$ takes the fractional part, that is the difference between the number and its floor. For example, \$\mathrm{frac}(-2.3)=0.7\$. This is equivalent to \$\sqrt{k}\$ being at most \$\frac{1}{2}\$ lower than its ceiling.

The code simply sums $$\sum_{k=1}^{n(n+1)/2} S(k),$$ but shifting the argument \$k\$ by one to account for the zero-indexed Python range.


57 bytes

def f(n):N=n*-~n/2;a=round(N**.5);print(a+N-abs(a*a-N))/2

Try it online!

Outputs floats. A direct arithmetic formula. Thanks to Arnauld for -1 byte

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

Haskell, 48 bytes

f n=sum$sum[1..n]`take`do z<-[1..];[1,0]<*[1..z]

Try it online!

Haskell, 48 bytes

sum.(take.sum.r<*>(([1,0]<*).r=<<).r)
r n=[1..n]

Try it online!

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

05AB1E, 12 9 bytes

LxL@˜2äнO

-2 bytes by taking inspiration from @JonathanAllan's Jelly answer for generating the [1,0,1,1,0,0,1,1,1,0,0,0,...] list.

Outputs the \$n^{th}\$ value. (Thanks to @ovs.)

Try it online or verify the first 10 test cases.

10 bytes version that outputs the infinite sequence instead:

∞xL@˜∞£OηO

Try it online.

Explanation:

L           # Push a list in the range [1, (implicit) input]
            #  i.e. input=5 → [1,2,3,4,5]
 x          # Double each value (without popping)
            #  [2,4,6,8,10]
  L         # Convert each value to a [1,n] list as well
            #  [[1,2],[1,2,3,4],[1,2,3,4,5,6],[1,2,3,4,5,6,7,8],[1,2,3,4,5,6,7,8,9,10]]
   @        # Check for each value in the [1,input] list that it's >= the values in the
            # inner ranged lists
            #  [[1,0],[1,1,0,0],[1,1,1,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,0,0,0,0,0]]
    ˜       # Flatten it
            #  [1,0,1,1,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,1,0,0,0,0,0]
     2ä     # Split it into 2 equal-sized parts
            #  [[1,0,1,1,0,0,1,1,1,0,0,0,1,1,1],[1,0,0,0,0,1,1,1,1,1,0,0,0,0,0]]
       н    # Only leave the first item
            #  [1,0,1,1,0,0,1,1,1,0,0,0,1,1,1]
        O   # And sum this list
            #  9
            # (after which this sum is output implicitly as result)

∞           # Push an infinite list of positive integers
            #  [1,2,3,...]
 xL@˜       # Same as above
            #  [1,0,1,1,0,0,1,1,1,0,0,0,...]
     ∞      # Push an infinite list again
      £     # Split the list into parts of that size
            #  [[1],[0,1],[1,0,0],[1,1,1,0],...]
       O    # Sum each inner list
            #  [1,1,1,3,...]
        η   # Take the prefixes of that list
            #  [[1],[1,1],[1,1,1],[1,1,1,3],...]
         O  # Sum each inner list
            #  [1,2,3,6,...]
            # (after which the infinite list is output implicitly)
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ LTs×€{íS2äнO is the same length but outputs \$a(n)\$ given \$n\$. \$\endgroup\$ – ovs Nov 2 at 14:47
  • \$\begingroup\$ @ovs Thanks, I've added it as well. :) \$\endgroup\$ – Kevin Cruijssen Nov 2 at 14:59
3
\$\begingroup\$

Jelly, 11 bytes

⁵DxⱮRFḣRS$S

Try it online!

Takes \$n\$, outputs \$a(n)\$, 1-indexed

How it works

⁵DxⱮRFḣRS$S - Main link. Takes n on the left
⁵           - 10
 D          - [1, 0]
    R       - [1, 2, ..., n]
   Ɱ        - For each i in [1, 2, ..., n]:
  x         -   Repeat [1, 0] i times
     F      - Flatten the array
         $  - Group the previous two commands into a monad T(n):
       R    -   [1, 2, ..., n]
        S   -   Sum
      ḣ     - Take the first T(n) elements of the sequence
          S - Take the sum, essentially counting the 1s
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Charcoal, 24 13 bytes

IΣ∕⭆⊕N⭆10×ιλ²

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

     N          Input `n`
   ⭆⊕           Map over inclusive range
      ⭆10       Map over characters of literal string `10`
           λ    Current character
         ×      Repeated by
          ι     Outer index
  ∕         ²   First half of resulting string
 Σ              Digital sum (i.e. count `1`s)
I               Cast to string
                Implicitly print

Previous 24-byte more Charoal-y solution:

NθGLθψ¤⭆θ⭆²⭆⊕ιλ≔№KA0θ⎚Iθ

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

Nθ

Input n.

GLθψ

Draw an empty right triangle of side n.

¤⭆θ⭆²⭆⊕ιλ

Fill it using the string 010011000111.... (The string is always twice as long as the triangle.) Charcoal's fill paints the provided string into the area to fill (see for example Bake a slice of Pi). Note that the 0s and 1s are swapped.

≔№KA0θ

Get the number of 0s that were actually printed.

⎚Iθ

Clear the canvas and print the result.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ +1 for literally drawing a triangle. \$\endgroup\$ – Razetime Nov 2 at 13:59
  • \$\begingroup\$ @Razetime Shame I don't have to do that any more though. \$\endgroup\$ – Neil Nov 2 at 14:39
3
\$\begingroup\$

Python 2, 62 bytes

a=lambda n,k=1:-~n*n>k*k*2and k+a(n,k+1)or max(0,k-~n*n/2-k*k)

Try it online!

This is based on

$$ \begin{align} a(n) &= f(\frac{n\cdot(n+1)}{2}, 1) \\ \\ f(n, k) &= \begin{cases} k+f(n-2k, k+1), & \text{if $n > k$} \\ \operatorname{max}(0, n), & \text{if $n \le k$} \end{cases} \end{align} $$

but the conditions and the base case are more convoluted to get this into a single recursive function.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

K (oK), 30 25 24 bytes

-6 bytes thanks to coltim

{+/(x+/!x)#,/x{0,x,1}\1}

Try it online!

Returns the n-th term 1-indexed.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I think you can trim a couple bytes by doing (t:1+!x)#'\:1 0 instead of +(t:1+!x)#\:/:1 0. \$\endgroup\$ – coltim Nov 2 at 16:07
  • 1
    \$\begingroup\$ And three more using &l, i.e. {+/(+/t)#,/(|&2#)'t:1+!x} \$\endgroup\$ – coltim Nov 2 at 16:23
  • \$\begingroup\$ @coltim Great, thanks! I did't know that & works like J's I. \$\endgroup\$ – Galen Ivanov Nov 2 at 18:23
  • 1
    \$\begingroup\$ Another byte can be saved by doing {+/(x+/!x)#,/x{0,x,1}\1} \$\endgroup\$ – coltim Nov 2 at 22:18
  • \$\begingroup\$ @coltim That's really nice, good job! Thank you once again! \$\endgroup\$ – Galen Ivanov Nov 3 at 7:10
3
\$\begingroup\$

JavaScript (Node.js), 100 89 85 84 77 bytes

-11: Change a**2 to a*a and simplify 1-Math.ceil(c)+Math.round(c) to Math.ceil(c)-c<0.5 (@xnor)

-4: Move c=Math.sqrt(b+1) inside Math.ceil(c) and omit the f= (@user)

-1: Change ...c<0.5 to ...c<.5 (@xnor)

-7: Remove unnecessary ( and ), and change Math.sqrt(...) to ...**.5 (@Samathingamajig)

a=>(x=0,Array((a*a+a)/2).fill().map((a,b)=>x+=Math.ceil(c=(b+1)**.5)-c<.5),x)

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You can simplify to x+=Math.ceil(c)-c<0.5, based on the simplified formula in my Python answer. It also looks like a**2 can be a*a. \$\endgroup\$ – xnor Nov 2 at 23:28
  • \$\begingroup\$ You can put c=... directly inside Math.ceil(c=Math...) and omit the f= (I think) \$\endgroup\$ – user Nov 2 at 23:42
  • \$\begingroup\$ I realized the 0.5 I wrote can be .5. \$\endgroup\$ – xnor Nov 2 at 23:43
  • \$\begingroup\$ You can remove 2 bytes ( and ) with a=>(x=0,Array((a*a+a)/2).fill().map((a,b)=>x+=Math.ceil(c=Math.sqrt(b+1))-c<.5),x) TIO \$\endgroup\$ – Samathingamajig Nov 3 at 0:10
  • \$\begingroup\$ Down to 77 by removing unnecessary ( and ), and changing how sqrt is done... Try it online! \$\endgroup\$ – Samathingamajig Nov 3 at 0:26
3
\$\begingroup\$

APL+WIN, 26 21 bytes.

minus 5 bytes thanks to Adam.

Prompts for integer:

+/(+/m)↑∊(m←⍳⎕)∘.⍴1 0

Try it online! Thamks to Dyalog Classic

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You shouldn't need to parenthesise a trailing expression …↑() \$\endgroup\$ – Adám Nov 3 at 21:33
  • \$\begingroup\$ 22: +/(+/m)↑∊n,¨~n←×⍳¨m←⍳⎕ \$\endgroup\$ – Adám Nov 3 at 21:35
  • \$\begingroup\$ 21: +/(+/m)↑∊(m←⍳4)∘.⍴1 0 \$\endgroup\$ – Adám Nov 3 at 21:36
  • \$\begingroup\$ @Adám Thanks. I assume (m←⍳4) is a typo and should be (m←⍳⎕) \$\endgroup\$ – Graham Nov 4 at 8:02
  • \$\begingroup\$ Yeah, that was from my testing. :-) \$\endgroup\$ – Adám Nov 4 at 8:07
2
\$\begingroup\$

Python 3, 69 bytes

lambda n:sum([j for i in range(1,n+1)for j in[1]*i+i*[0]][:n*-~n//2])

Try it online!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Scala, 66 58 51 bytes

n=>1 to n flatMap(i=>""*i+"\0"*i)take(n*n+n>>1)sum

Try it online

There is an unprintable character 0x01 inside the first quote.

An anonymous function that takes an integer n and returns the nth element of the sequence (1-indexed).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Nice answer! You can also use 48<, I think. Also, I think 1 to n should work instead of the stream. \$\endgroup\$ – user Nov 2 at 14:17
  • 1
    \$\begingroup\$ Thanks for the tips! I initially wanted to return the stream and later realized I needed the n. \$\endgroup\$ – corvus_192 Nov 2 at 14:25
  • 1
    \$\begingroup\$ I think take(n*n+n>>1) works for -1 byte. \$\endgroup\$ – ovs Nov 2 at 16:27
  • \$\begingroup\$ You might be able to use unprintable characters and do something like 0< to save a byte, but I don't know how to do that. \$\endgroup\$ – user Nov 2 at 16:35
2
\$\begingroup\$

Haskell, 46 bytes

f n=sum[1|a<-[1..n],b<-[1..a],a*a-b<n*(n+1)/2]

Try it online!


46 bytes

f n=sum[max 0$min a$n*(n+1)/2-a*a+a|a<-[1..n]]

Try it online!


48 bytes

f n=sum[1|k<-[2,4..n*n+n],even$ceiling$sqrt$2*k]

Try it online!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

C (gcc), 84 82 61 bytes

Saved 2 bytes thanks to ErikF!!!

c;p;f(n){for(c=p=0,n=n*-~n/2;n>2*p;n-=2*p++)c+=p;c+=n<p?n:p;}

Try it online!

Inputs a \$1\$-based number \$n\$ and returns the \$n^{\text{th}}\$ term.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Haskell, 50 bytes

r?x|q<-sum[0..x]-r*r,r>q=min q 0|l<-r+1=l+l?x
(0?)

Try it online!

Slightly longer but complete different approach from the existing Haskell answer. This one is basically all arithmetic whereas the existing one builds the list from scratch.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Retina 0.8.2, 41 bytes

.+
$*
1
$`1$.`$*00
((.)+?)(?<-2>.)+$
$1
1

Try it online! Link includes test cases. Explanation:

.+
$*
1
$`1$.`$*00

Create the string 101100111000... up to n 1s and n 0s, which is twice as long as the desired triangle.

((.)+?)(?<-2>.)+$
$1

Delete the second half of the string.

1

Count the number of 1s remaining.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

J, 25 bytes

(1#.2&!$&;1 0<@#"{~i.)@>:

Try it online!

(1#.2&!$&;1 0<@#"{~i.)@>:
(                    )@>. increment n by 1 and then
                   i.     for every i in 0 … n+1:
          1 0  #"{~         take i 1s and i 0s,
             <@             and box the result (;1 0;1 1 0 0;…)
    2&!                   T(n) by binominal(n+1, 2)
       $&;                raze the boxes to a list (1 0 1 1 0 0…)
                            and take the first T(n) elements
 1#.                      sum the list, i.e. count the 1s
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

MATL, 15 14 bytes

:"@:t~]vG:s:)z

Input is 1-based.

Try it online! Or verify the first values.

How it works

       % Implicit input: n
:      % Range: [1 2 ... n].
"      % For each
  @    %   Push iteration index, k (goes from 1 to n)
  :    %   Range: gives [1 2 ... k]
  t    %   Duplicate
  ~    %   Negate, element-wise: gives [0 0 ... 0] (k zeros)
]      % End
v      % Concatenate everything into a column vector
G      % Push n again
:      % Range: [1 2 ... n]
s      % Sum: gives n-th triangular number, T(n)
:      % Range
)      % Index: keeps the first T(n) values
z      % Number of nonzeros
       % Implicit output
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

R, 55 bytes

sum(unlist(Map(rep,list(1:0),e=n<-1:scan()))[1:sum(n)])

Try it online!

Generates A118175 and sums the first \$T(n)\$ terms.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Desmos, 85 bytes

\$\sum_{n=1}^{x(x+1)/2}(1-\operatorname{ceil}(\sqrt{n})+\operatorname{round}(\sqrt{n}))\$

\sum_{n=1}^{x(x+1)/2}(1-\operatorname{ceil}(\sqrt{n})+\operatorname{round}(\sqrt{n}))

I haven't been able to find a nice formula myself, so I used the \$a(n) = 1 - \operatorname{ceil}(\sqrt{n+1}) + \operatorname{round}(\sqrt{n+1})\$ formula provided on A118175's page.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Gaia, 12 11 10 bytes

┅2…&¦_2÷eΣ

Try it online!

Uses the observation from Jonathan Allan's answer to save a byte (so go upvote that), namely that constructing the complement sequence and counting the 1s in the second half is equivalent to counting the 1s in the first half.

		# implicit input n
┅		# push [1, 2, ..., n]
2…		# push [0,1]
&¦		# for each i in [1, 2, ..., n] repeat each element of [0,1] i times
_2÷		# flatten and divide into two sublists of equal length
eΣ		# take the second sublist and sum
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

MathGolf, 19 12 bytes

╒♂░*mzyh½<iΣ

Outputs the 1-based \$n^{th}\$ value.

Try it online.

Original 19 bytes answer:

╒♂░*mzykæî‼<≥]╡imΣΣ

Outputs the 1-based \$n^{th}\$ value as well.

Try it online.

Explanation:

╒               # Push a list in the range [1, (implicit) input]
 ♂░             # Push 10, and convert it to a string: "10"
   *            # Repeat the "10" each value amount of times: ["10","1010","101010",...]
    m           # Map over each inner string:
     z          #  Revert sort its digits: ["10","1100","111000",...]
      y         # Join it together to a single string: "101100111000..."
       h        # Push its length (without popping the string itself)
        ½       # Halve it
         <      # Only keep the first length/2 amount of digits in this string
          i     # Convert the string to an integer
           Σ    # And sum its digits
                # (after which the entire stack joined together is output implicitly)

╒♂░*mzy         # Same as above
                # Get its prefixes (unfortunately there isn't a builtin for this):
       k        #  Push the input-integer
        æ       #  Loop that many times,
                #  using the following four characters as body:
         î      #   Push the 1-based loop index
          ‼     #   Apply the following two commands separated:
           <    #    Slice to get the first n items
           ≥    #    Slice to remove the first n items and leave the remainder
        ]       #  After the loop, wrap all values on the stack into a list
         ╡      # Remove the trailing item
          i     # Convert each string of 0s/1s to an integer
           mΣ   # Sum the digits of each inner integer
             Σ  # And sum the entire list together
                # (after which the entire stack joined together is output implicitly)
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ @Arnauld Thanks for noticing! Should be fixed now. I initially had my current 19-byter and noticed it still worked correctly if I remove the m, so I thought it was doing the sum on each digit implicitly, but after debugging a bit just yet it apparently does something different, not sure what though. :/ Anyway, adding the explicit map should fix it. I've also added some larger test cases to my TIO. \$\endgroup\$ – Kevin Cruijssen Nov 3 at 9:51
1
\$\begingroup\$

Raku, 40 bytes

{sum flat({1,0 Xxx++$}...*)[^sum 1..$_]}

Try it online!

  • { ... } ... * is an infinite sequence, where the bracketed expression is a function that generates each successive element.
  • ++$ increments the anonymous state variable $ each time the generating function is evaluated. The first time it's called, ++$ is 1, then 2, etc.
  • 1, 0 is just a two-element list.
  • xx is the replication operator. Prefixed with the cross-product metaoperator X, Xxx crosses the list 1, 0 with the incrementing value of ++$, generating the sequence (((1), (0)), ((1, 1), (0, 0)), ((1, 1, 1), (0, 0, 0)), ...).
  • flat lazily flattens that infinite sequence into the given sequence S, ie: 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, ....
  • [^sum 1..$_] takes the first N elements from that sequence, where N is the sum of the numbers from 1 up to $_, the argument to the function.
  • The leading sum sums the selected elements.
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Arn -rlx, 14 bytes

&♦r┬f½▀╔î¾rl¥Æ

Try it!

Explained

Unpacked: $.(|{|a{a>}\~:+}\

            Mutate STDIN from N → [1, N]
$.                Partition down middle
  (
    |..\            Fold N with concatenation
          _             Where N is a variable; implied
     {                After mapping with block, key of `_`
       |..\
            ~:+             Where N is a one-range to _ * 2
        a{                Block with key of `a`
             a
           >                Is greater than
             _                Implied
        }                 End block
     }                End block   
               Last entry, sum

Alternate 14 byte solution with the same flags: $.(a{~:+a@>a}\):_

Arn, 23 bytes

W▀Q$µgˆÎ§Ò"ˆÞC5fbA┐V-7J

Try it! Thinking of adding a round fix to Arn, that'll help this pretty high byte count.

1-indexed, returns the Nth term. Based off of @J42161217's answer

Explained

Unpacked: +{1-(:^:/)+:v(0.5+:/}\~:-*++

+...\ Fold with addition after mapping
  ~ Over the one-range to
    :-*++ n * (n + 1) / 2
{ Begin map, key of `_`
    1
  - Subtract
    (
      :^ Ceiling
        _ Implied
      :/ Square root
    )
  + Add
    :v(0.5+:/ Round `:/_`, ending implied
} End map
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Swift, 80 bytes

Adapted from the Python 2 answer by @ovs

func a(_ n:Int,_ k:Int=1)->Int{-(~n*n)>k*k*2 ? k+a(n,k+1):max(0,k-(~n)*n/2-k*k)}

And the un-golfed form:

func a(_ n: Int, _ k: Int = 1) -> Int {
    -(~n*n) > k*k*2
        ? k + a(n, k+1)
        : max(0, k - ~n*n/2 - k*k)
}

And here's some sample output.

print((1...10).map { a($0) })
// [1, 2, 3, 6, 9, 11, 15, 21, 24, 28]

It might actually be better to use a loop instead of recursion. Some limitations with closures (i.e. lambdas) in Swift forced me to use a function decl, which takes up a lot of space. :/

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

CJam, 22 bytes

qi),:+{_)mqmo\mqi-}%:+

Uses round(sqrt(n+1)) - floor(sqrt(n)) to calculate the nth position in the bit sequence. (Getting it as a repetition of numbers was smaller to generate, but one byte larger in the end to sum.)

Try it online!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Red, 109 bytes

func[n][b:[[1]]loop n[append/only b head insert next
copy[0 1]last b]sum take/part load form b n + 1 * n / 2]

Try it online!

I know it's very long - I just wanted to see what the K solution (cortesy @coltim) would look like in Red :)

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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