Programming Praxis

5 Responses to “A Triangular Sequence”

1. chaw said

   August 9, 2019 at 1:23 PM

   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

   August 11, 2019 at 2:34 AM

   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

   August 11, 2019 at 6:16 AM

   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

   August 13, 2019 at 1:19 AM

   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

   August 21, 2019 at 10:53 AM

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