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.
Programming Praxis 
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:
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
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)
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:
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; } } } }