0
$\begingroup$

I am trying to find a formula or algorithm to calculate the nth pair of numbers in this infinite sequence, starting at 0. That is, for each number on the left, a method to calculate the corresponding pair of numbers on the right:

0: (0, 0)

1: (1, 0)
2: (0, 1)

3: (2, 0)
4: (1, 1)
5: (0, 2)

6: (3, 0)
7: (2, 1)
8: (1, 2)
9: (0, 3)

10: (4, 0)
11: (3, 1)
12: (2, 2)
13: (1, 3)
14: (0, 4)
...

Each pair of numbers represents a coordinate in an infinite 2 dimensional matrix. The ordering of the coordinates traces a path along each diagonal:

14
9 13
5 8 12
2 4 7 11
0 1 3 6 10

I have gotten as far as finding a Python function to generate a finite number of terms of the sequence:

def generate_seq(m):
  k = 0
  for i in range(m):
    for j in range(i):
      print(f'{k}: {(i - j - 1, j)}')
      k += 1

I also think that the last printed value of k can be calculated as k = (n * (n - 1) / 2) - 1.

$\endgroup$
2
  • $\begingroup$ Where is this problem from? $\endgroup$
    – Sal
    Commented Mar 20 at 19:36
  • $\begingroup$ @Sal The automated generation of a font for an alphabet based on binary numbers. The nth letter in the alphabet will correspond to a grid of black and white pixels encoding the nth binary number. By iterating the zeros and ones along the diagonals, arbitrarily many additional letters can be added without changing any of the previous ones, except to pad them as needed with additional white space to keep their sizes the same. $\endgroup$
    – user695931
    Commented Mar 21 at 4:53

1 Answer 1

0
$\begingroup$

I took the sequence of the first value in each pair 0 1 0 2 1 0 3 2 1 0 4 3 2 1 0 5 4 3 2 1 0 6 5 4 3 2 1 0 and entered it into the On-Line Encyclopedia of Integer Sequences. It identified the sequence as https://oeis.org/A025581. This led me to https://oeis.org/A073189/a073189.txt. From this I was able to define a Python function that appears to generate it:

import math

def binomial(n, k):
  return math.factorial(n) / (math.factorial(k) * math.factorial(n - k))

for n in range(0, 15):
  if n == 0:
    t1 = 0
    t2 = 0
  else:
    t1 = binomial(math.floor(3/2 + math.sqrt(2 + 2 * n)), 2) - (n + 1)
    t2 = n - binomial(math.floor(1/2 + math.sqrt(2 + 2 * n)), 2) 

  print(f'{n}: {(t1, t2)}')

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .