## 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 *n*th item of the sequence (counting from 0) is *n* – *m**(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

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.

Output:

Rust version using an iterator to generate the sequence:

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.

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):