Not so triangular numbers

Question

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 code-golf challenge.

Answer 1

Wolfram Language (Mathematica), 41 bytes

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

Try it online!

-2 bytes from @ZippyMagician

Answer 2

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

Answer 3

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

Answer 4

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!

Answer 5

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

Answer 6

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)

Answer 7

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

Answer 8

Charcoal, 24 13 bytes

ＩΣ∕⭆⊕Ｎ⭆10×ιλ²

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

     Ｎ          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)
Ｉ               Cast to string
                Implicitly print

Previous 24-byte more Charoal-y solution:

ＮθＧLθψ¤⭆θ⭆²⭆⊕ιλ≔№ＫＡ0θ⎚Ｉθ

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

Ｎθ

Input n.

ＧLθψ

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.

≔№ＫＡ0θ

Get the number of 0s that were actually printed.

⎚Ｉθ

Clear the canvas and print the result.

Answer 9

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.

Answer 10

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.

Answer 11

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!

Answer 12

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

Answer 13

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!

Answer 14

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

Answer 15

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!

Answer 16

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.

Answer 17

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.

Answer 18

Vyxal s, 8 bytes

ƛdɾ<;fIt

Try it Online!

Answer 19

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.

Answer 20

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

Answer 21

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

Answer 22

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.

Answer 23

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.

Answer 24

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

Answer 25

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)

Answer 26

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.

Answer 27

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

Answer 28

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. :/

Answer 29

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!

Answer 30

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