# Go deh!

Mainly Tech projects on Python and Electronic Design Automation.

## Sunday, April 21, 2024

### Searching OEIS tables

A few months ago I submitted a series to OEIS* that was accepted; yes, but OEIS does not seem to leave my series searchable!

*OEIS is the Online Encyclopedia of  Integer Series. I guess table is not in the name, but...

(best viewed on larger than a portrait phone)

### Let me explain.

The documentation for OEIS, explains that if you have a 2D triangle or table of values rather than a one dimensional strict series, then one should antidiagonalise the data and submit the series produced.

They give as an example A003987 . This gives this table:

Table begins
0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, ...
1,  0,  3,  2,  5,  4,  7,  6,  9,  8, 11, 10, ...
2,  3,  0,  1,  6,  7,  4,  5, 10, 11,  8, ...
3,  2,  1,  0,  7,  6,  5,  4, 11, 10, ...
4,  5,  6,  7,  0,  1,  2,  3, 12, ...
5,  4,  7,  6,  1,  0,  3,  2, ...
6,  7,  4,  5,  2,  3,  0, ...
7,  6,  5,  4,  3,  2, ...
8,  9, 10, 11, 12, ...
9,  8, 11, 10, ...
10, 11,  8, ...
11, 10, ...
12, ...
...

The above gets antidiagonalised to the series beginning:

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

#### Searching...

If we search for a sub-sequence of the antidiagonalised table, we can find the correct entry.

If, however, we search for a row of the values from the table,  A003987 is not found!
The values chosen: to search for: 5,4,7,6,1,0,3 appear near the end of the table which shows that that row of numbers should be followed by a 2.
The table shows 13*13 / 2 ~ 85 values. OEIS has a list of 104 values, so it has the data to search through.

### No intuitive search of OEIS tables

It seems to me that the most intuitive way to search a table of values is by row, left to right. There are other ways to search a table, (assuming an origin at top left and the table extends to the right and down):

• By row, L2R. , R2L
• By Column Top2Bottom, , B2T
• By 45 degree diagonals, ↘, ↖, ↙, ↗

OEIS doesn't seem to do these searches on tabular data.

### Regenerating a 2D table from antidiagonalised data.

I did play around and created some code to recreate a table as a list of row-lists, in Python, given an OEIS B-file. The options handling is a work in progress, but the main part was being able to generate the table.

# -*- coding: utf-8 -*-
# %%
"""

Generate 2D table from OEIS type anti-diagonalised sequence held in file

Created on Thu Apr  4 18:16:07 2024

"""

from itertools import zip_longest
import math
# from pprint import pp
from antidiagonals import antidiag_triangle_indices

def read_bfile(bfname: str) -> tuple[int | None,  # first index
list[int]]:   # anti-diag values
"""

## B-File format:
* Ref: https://oeis.org/SubmitB.html
* Blank lines ignored
* Lines beginning  with # ignored
* Lines of two, space-separated integers <index> <indexed-value>

It is assumed the index increments by one on subsequent lines.
"""
first_index, values = None, []
with open(bfname) as bfile:
for line in bfile:
ln = line.strip()
if not ln or ln.startswith('#'):
continue
index, value = [int(field) for field in ln.split()[:2]]
if first_index is None:
first_index = index
values.append(value)

return first_index, values

def antidiag_to_table(sequence: list[int]) -> list[list[int]]:
"""
Convert anti-diagonalised sequence back to infinite 2D table.

Parameters
----------
sequence : list[int]
Anti-diagonalised values from table.

Returns
-------
list[list[int]]
Table of rows of ints.

Table rows will fill in from successive sequence values like this:

1  2  4  7 11 16 ...
3  5  8 12 17
6  9 13 18
10 14 19
15 20
21
.
.
.
"""

# 1, 3, 6, 10, 15, 21, ... rows*(rows+1) / 2

# min columns in triangular table generation. ~= min rows
size = len(sequence)                                  # = rows*(rows+1)/2
rows = math.ceil((-1 + math.sqrt(4 * 2 * size)) / 2)  # solve for rows
# cols = rows  # last row may be deleted if last anti-diag is part filled.
# print(f"{(size, cols) = }")

# Empty (triangular) table of None's
table = [[None] * (rows - i)
for i in range(rows)]

indices = antidiag_triangle_indices()
col = 0  # for if sequence is empty
for val, (row, col) in zip(sequence, indices):
table[row][col] = val

# Remove unfilled part of last anti-diag of table
while col > 0:
row, col = next(indices)
table[row].pop(-1)
# remove last row if present and empty
if table and not table[-1]:
table.pop(-1)

return table

def pp_table(table: list[list[int]]) -> None:
"Pretty-print table of differring row lengths"
if not table:
return
col_width = max(max(len(str(val)) for val in row) for row in table)
for row in table:
print(''.join(f"{val:{col_width}}" for val in row))

def transpose(table: list[list[int]]) -> list[list[int]]:
"Table of rows to x<>y transposed table of new rows"
fv = math.nan
tr = [list(new_row)
for new_row in zip_longest(*table, fillvalue=fv)]
# remove fillvalues in triangular transposition
for row in tr:
try:
row[row.index(fv):] = []
except ValueError:
continue

return tr

if __name__ == "__main__":
print("# TEST FILL BY ANTI-DIAGONAL\n")
for n in range(0, 8):
print(f"{n = }:\n")
ans = antidiag_to_table(list(range(1, n+1)))
pp_table(ans)
print()

fname, m = 'b365096.txt', 505
print(f"\n\n# Data from {fname}, first {m} values:\n")
pp_table(ans)
print("\n## Transposed:\n")
pp_table((tr:=transpose(ans)))

And antidiagonals.py is this:

# -*- coding: utf-8 -*-
"""
Anti-diagonals:

0,0 0,1 0,2 0,3
1,0 1,1 1,2 1,3
2,0 2,1 2,2 2,3
3,0 3,1 3,2 3,3

Of Square:
0,0  0,1 1,0  0,2 1,1 2,0  0,3 1,2 2,1 3,0   1,3 2,2 3,1  2,3 3,2  3,3

of Infinite table:
0,0  0,1 1,0  0,2 1,1 2,0  0,3 1,2 2,1 3,0   0,4 1,3 2,2 3,1 4,0 ...

Created on Mon Aug 21 13:36:31 2023

"""
# %% Triangles

from itertools import islice

def antidiag_triangle_indices() -> tuple[int, int]:
x = y = 0
while True:
yield (x, y)
x, y = (x+1, y-1) if y else (0, x+1)

list(islice(antidiag_triangle_indices(), 15))

# %% Rectangles

from itertools import islice

def antidiag_rectangle_indices(sizex: int=4, sizey: int=4) -> tuple[int, int]:
x = y = 0
while True:
yield (x, y)
if (x, y) == (sizex - 1, sizey - 1):
break
x, y = (x+1, y-1)
if x == sizex or y < 0:
u = x + y + 1
x, y = (0, u) if u < sizey else (u - sizey + 1, sizey - 1)

list(antidiag_rectangle_indices(3, 4))

END.