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.

Advertisements

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

    Link to playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=6e91a92e70d95cd7f0aa9294194095d0

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: