# Not so triangular numbers

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.

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

# 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

• Ah, this means I can drop the v from my Gaia answer. Neat observation! – Giuseppe Nov 3 '20 at 1:30

# Wolfram Language (Mathematica), 41 bytes

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


Try it online!

-2 bytes from @ZippyMagician

# Husk, 8 bytes

Σ↑ṁṘḋ2NΣ


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


f n=sum$sum[1..n]takedo 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! # 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 # 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.) 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)  • LTs×€{íS2äнO is the same length but outputs $a(n)$ given $n$. – ovs Nov 2 '20 at 14:47 • @ovs Thanks, I've added it as well. :) – Kevin Cruijssen Nov 2 '20 at 14:59 # 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


# 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 1s)
Ｉ               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.

• +1 for literally drawing a triangle. – Razetime Nov 2 '20 at 13:59
• @Razetime Shame I don't have to do that any more though. – Neil Nov 2 '20 at 14:39

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

# K (oK), 3025 24 bytes

-6 bytes thanks to coltim

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


Try it online!

Returns the n-th term 1-indexed.

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

# JavaScript (Node.js), 100898584 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!

• 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. – xnor Nov 2 '20 at 23:28
• You can put c=... directly inside Math.ceil(c=Math...) and omit the f= (I think) – user Nov 2 '20 at 23:42
• I realized the 0.5 I wrote can be .5. – xnor Nov 2 '20 at 23:43
• 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 – Samathingamajig Nov 3 '20 at 0:10
• Down to 77 by removing unnecessary ( and ), and changing how sqrt is done... Try it online! – Samathingamajig Nov 3 '20 at 0:26

# 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

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

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

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

• Nice answer! You can also use 48<, I think. Also, I think 1 to n should work instead of the stream. – user Nov 2 '20 at 14:17
• Thanks for the tips! I initially wanted to return the stream and later realized I needed the n. – corvus_192 Nov 2 '20 at 14:25
• I think take(n*n+n>>1) works for -1 byte. – ovs Nov 2 '20 at 16:27
• 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. – user Nov 2 '20 at 16:35

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! # C (gcc), 8482 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. # 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. # 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. # 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


# MATL, 15 14 bytes

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


Input is 1-based.

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


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

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

# Gaia, 1211 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


# MathGolf, 19 12 bytes

╒♂░*mzyh½<iΣ


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

Try it online.

╒♂░*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)

• @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. – Kevin Cruijssen Nov 3 '20 at 9:51

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

# 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
)
:v(0.5+:/ Round :/_, ending implied
} End map


# Swift, 80 bytes

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

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

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