## A Triangular Sequence

### August 9, 2019

Consider the triangle:

```1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
...```

When the triangle is flattened, it produces the sequence (1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 …).

Your task is to write a program to generate the flattened sequence, and a second program to calculate the nth item in the sequence. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 5 Responses to “A Triangular Sequence”

1. chaw said

Here is something hackish I came up with in standard R7RS Scheme and a
few SRFI helpers. It uses only exact math in Scheme (no sqrt, etc.).
No proof yet, so usual caveat applies.

``` (import (scheme base) (scheme write) (only (srfi 1) iota append-map every) (only (srfi 8) receive)) ;; Triangular sequence (flat) for nlevels rows of the underlying triangle. (define (triangular-sequence nlevels) (append-map (lambda (level) (iota level 1)) (iota nlevels 1))) ;; n'th triangular number (define (triangular-number n) (/ (* n (+ n 1)) 2)) ;; rank'th term in the triangular sequence (counting from 1). (define (unrank-triangular-sequence rank) (receive (root rem) (exact-integer-sqrt (* 2 rank)) (/ ((if (<= rem root) + -) rem root) 2))) ;; simple test (define (test nlevels) (every = (map unrank-triangular-sequence (iota (triangular-number nlevels) 1)) (triangular-sequence nlevels))) (display (test 1000)) (newline) ```

Output:

``` #t ```

2. Bill Wood said

Rust version using an iterator to generate the sequence:

```// Author Bill Wood
struct Triangle {
row: usize,
col: usize,
}

impl Iterator for Triangle {
type Item = usize;
fn next(&mut self) -> Option<Self::Item> {
self.col += 1;
if self.col > self.row {
self.row += 1;
self.col = 1;
}
Some(self.col)
}
}

impl Triangle {
fn new() -> Self {
Triangle{ row: 1, col: 0 }
}
fn nth(i: usize) -> usize {
Self::new().nth(i).unwrap()
}
}

fn main() {
for i in 0..10 {
println!("{}", Triangle::nth(i));
}
}
```
3. shakiba said

num = int(input(‘pleas enter rows number:’))
row = 0
while row < num :
n = row + 1
p = 1
while n > 0 :
while p < n :
print (p , end = ”)
p = p + 1
n = n – 1
row = row +1
print()
if row == 9:
plus = 0
for i in range (0 ,10):
plus = plus + i
print (‘The sum of the row 9 is : ‘ , plus)

4. Daniel said

Here’s a solution in Python.

```from itertools import count, islice

def seq():
for n in count(1):
yield from range(1, n + 1)

print(tuple(islice(seq(), 21)))

def get(n):
def isqrt(n):
x = n
while True:
y = (x + (n // x)) // 2
if y - x in (0, 1): return x
x = y
m = (isqrt(8 * n + 1) - 1) // 2
return n - m * (m + 1) // 2 + 1

print(tuple(get(n) for n in range(21)))
```

Output:

```(1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6)
(1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6)
```
5. matthew said

A slightly different unrank function, arithmetic using doubles for maximum range – not sure at what point numeric error spoils things, good up to 10^11 or so at least.

Mathematical, the crucial fact is that if sqrt(2m) = n-1/2, then m = n(n-1)/2 + 1/8, ie. when doing the round(sqrt(2m)), the cutoff point between rows of the triangle are just above the triangular numbers (which is why unrank runs for 1, not 0):

```#include <math.h>
#include <iostream>

double unrank(double m) {
double n = round(sqrt(2*m));
return m - n*(n-1)/2;
}

int main() {
for (double m = 1, i = 0; ; i++) {
for (double j = 1; j <= i; j++, m++) {
if (j != unrank(m)) {
std::cout << m << " " << j << " " << unrank(m) << "\n";
return 1;
}
}
}
}
```