A Triangular Sequence

August 9, 2019

We build up the rows of the triangle one at a time using `iterate` then `flatten` the rows:

```(define (seq nrows)
(flatten (iterate nrows (lambda (xs) (map add1 (cons 0 xs))) '(1)))```
```> (seq 5)
(1 1 2 1 2 3 1 2 3 4 1 2 3 4 5)```

According to A002260, the nth item of the sequence (counting from 0) is nm*(m+1)/2 + 1, where m = floor((sqrt(8*n+1)-1)/2:

```(define (nth n)
(let ((m (inexact->exact (floor (/ (- (sqrt (+ (* 8 n) 1)) 1) 2)))))
(- n (* m (+ m 1) 1/2) -1)))```
```> (map nth (range 15))
(1 1 2 1 2 3 1 2 3 4 1 2 3 4 5)```

You can run the program at https://ideone.com/hzS2mp.

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;
}
}
}
}
```