Mainly Tech projects on Python and Electronic Design Automation.

Sunday, April 21, 2024

Searching OEIS tables

  a Jamaican showing how to search a table by row in the Jamaican hills. Image 4 of 4

 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 -*-
# %%
"""
adia_to_table.py file

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


Created on Thu Apr  4 18:16:07 2024

@author: paddy3118
"""

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
    """
Read B-file bfname

## 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")
    ad = read_bfile(fname)
    ans = antidiag_to_table(ad[1][:m])
    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

@author: paddy

"""
# %% 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.

Followers

Subscribe Now: google

Add to Google Reader or Homepage

Go deh too!

whos.amung.us

Blog Archive