Saturday, August 26, 2023

"Staring at assorted perms and Python", or "The Ranking and Unranking of Lexical Permutations"

 

I have been playing with encryptions and then series that involved permutations. Submitting my Godeh series to the OEIS made me look closer at the permutations that Python produces, and at maybe reducing those permutations to a single integer.

(p.s. Post is best read on a larger than portrait phone screen)

Here are the start of the permutations used in the Godeh series rows:

(0,)
(0, 1)
(1, 0)
(0, 1, 2)
(0, 2, 1)
(1, 0, 2)
(1, 2, 0)
(2, 0, 1)
(2, 1, 0)
(0, 1, 2, 3)
(0, 1, 3, 2)
(0, 2, 1, 3)
(0, 2, 3, 1)
(0, 3, 1, 2)
(0, 3, 2, 1)
(1, 0, 2, 3)
(1, 0, 3, 2)
(1, 2, 0, 3)
(1, 2, 3, 0)
(1, 3, 0, 2)
(1, 3, 2, 0)
(2, 0, 1, 3)
(2, 0, 3, 1)
(2, 1, 0, 3)
(2, 1, 3, 0)
(2, 3, 0, 1)
(2, 3, 1, 0)
(3, 0, 1, 2)
(3, 0, 2, 1)
(3, 1, 0, 2)
(3, 1, 2, 0)
(3, 2, 0, 1)
(3, 2, 1, 0)

It can be generated by this:

from itertools import permutations, chain
from math import factorial
from typing import Sequence
from pprint import pp

# %% perms in Python generation order
generation_order = []
for width in range(1, 5):
    for perm in permutations(range(width)):
        print(perm)
        generation_order.append(perm)

I truncate at all the perms for four items, but you get the idea - it could extend in this way without limit.

Ordered by...

Successive groups of permutations are for incrementing items permuted. Within each group, of permutations of the same amount of items, the order is lexicographical, i.e. the Python sorted order, 

I stared at, and messed around with the ordered perms of four items above, looking for patterns. But lets just confirm the order is sort by width then lexicographical:

wtl = sorted(set(generation_order),
             key=lambda x:(len(x), x))
if generation_order == wtl:
    print(' == width_then_lexicographical ordering')
else:
    print(' != width_then_lexicographical ordering of:')
    pp(wtl)

# Prints:  == width_then_lexicographical ordering


Ranks

I remembered that I had created a Rank of a permutation task some time ago, (2012), and that there was something "off" with the ranking. 

Sure enough the issue was that a rank number gets transformed into a unique permutation, and vice-versa, knowing the start configuration and given any permutation of it then yoy can generate its rank number - But the order of permutations for increasing rank number does not have to be that lexical sort used by Python, and indeed the Myrvold & Ruskey or Trottor & Johnson algorithms I converted to Python are not in lexical order.

So now I know I needed some way to rank and un-rank a lexically ordered set of permutations, as generated by Python.

Something to look at and talk about

Lets assign ranks to Python perms and column headings to make it easier to talk about:

from string import ascii_uppercase

n = 4  # large enough to hopefully show patterns, but not too large
print(' # :  ' + '  '.join(char for char in ascii_uppercase[:n]))
for rank, perm in enumerate(permutations(range(n))):
    print(f"{rank:>2} : {perm}")
"""
Outputs:

 # :  A  B  C  D
 0 : (0, 1, 2, 3)
 1 : (0, 1, 3, 2)
 2 : (0, 2, 1, 3)
 3 : (0, 2, 3, 1)
 4 : (0, 3, 1, 2)
 5 : (0, 3, 2, 1)
 6 : (1, 0, 2, 3)
 7 : (1, 0, 3, 2)
 8 : (1, 2, 0, 3)
 9 : (1, 2, 3, 0)
10 : (1, 3, 0, 2)
11 : (1, 3, 2, 0)
12 : (2, 0, 1, 3)
13 : (2, 0, 3, 1)
14 : (2, 1, 0, 3)
15 : (2, 1, 3, 0)
16 : (2, 3, 0, 1)
17 : (2, 3, 1, 0)
18 : (3, 0, 1, 2)
19 : (3, 0, 2, 1)
20 : (3, 1, 0, 2)
21 : (3, 1, 2, 0)
22 : (3, 2, 0, 1)
23 : (3, 2, 1, 0)
"""


Patterns

I can't go through the many false trails I had in coming to my result, (there were several), but I finally noticed that The digits in column A stayed the same for 6 successive rows and six is three factorial. Column B stays the same for 2 successive rows i.e. 2! , I guessed 1! for column C and D is what's left.

A lot of deleted code later I found that, kinda, after you  pop the first digit out of the starting perm at rank 0, which would be rank // (4 - 1)!; you could take the second digit out using indices using decreasing factorials, but also modulo the decreasing numbers left to index.

Hard to write a textual description of, but I was very chuffed to work out the following on my own:

def nth_perm(initial: Sequence[int], n: int) -> tuple[int]:
    init = list(initial)
    a = len(initial)
    fac_divs = tuple((n // factorial(a - j)) % (a - j + 1)
                     for j in range(1, a))

    return tuple([init.pop(indx) for indx in fac_divs]
                 + init)

nth_perm(range(4), 11)

And indeed the nth perm of (0, 1, 2 ,3) produced for n = 11 was (1, 3, 2, 0).

Check

I decided to check my perm-from-rank generator against the Python permutations:

start = range(4)
for i, perm in enumerate(permutations(range(4))):
    assert perm == nth_perm(start, i)


Generate ranking from arbitrary perm

This had its own aha moments, and eventually I created the following code generating the rank of the sorted perm:

def s_perm_rank(p: Sequence[int]) -> int:
    """
    Ranking of perm p in the sorted sequence of perms of the ints 0 .. len(p)-1
    p must be a permutation of the integers 0 .. (len(p)-1)
    """
    this = list(p)
    a = len(this)
    init = list(range(a))  # Perm of rank 0
    assert set(this) == set(init), "p must be perm of the ints 0 .. (len(p)-1)"

    n, f = 0, a
    while this:
        f -= 1
        n += init.index(this[0]) * factorial(f)
        init.remove(this.pop(0))

    return n


Roundtrip Check

To check I roundtrip from rank to perm to rank, and also check against the Python permutations ranking

n = 4
init = range(n)
for i, py_perm in enumerate(permutations(range(n))):
    s_perm = nth_perm(init, i)
    print(f"{i:>2}: {py_perm=} {py_perm==s_perm=} {i==s_perm_rank(s_perm)=}")


Output:

 0: py_perm=(0, 1, 2, 3) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
 1: py_perm=(0, 1, 3, 2) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
 2: py_perm=(0, 2, 1, 3) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
 3: py_perm=(0, 2, 3, 1) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
 4: py_perm=(0, 3, 1, 2) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
 5: py_perm=(0, 3, 2, 1) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
 6: py_perm=(1, 0, 2, 3) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
 7: py_perm=(1, 0, 3, 2) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
 8: py_perm=(1, 2, 0, 3) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
 9: py_perm=(1, 2, 3, 0) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
10: py_perm=(1, 3, 0, 2) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
11: py_perm=(1, 3, 2, 0) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
12: py_perm=(2, 0, 1, 3) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
13: py_perm=(2, 0, 3, 1) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
14: py_perm=(2, 1, 0, 3) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
15: py_perm=(2, 1, 3, 0) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
16: py_perm=(2, 3, 0, 1) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
17: py_perm=(2, 3, 1, 0) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
18: py_perm=(3, 0, 1, 2) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
19: py_perm=(3, 0, 2, 1) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
20: py_perm=(3, 1, 0, 2) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
21: py_perm=(3, 1, 2, 0) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
22: py_perm=(3, 2, 0, 1) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
23: py_perm=(3, 2, 1, 0) py_perm==s_perm=True i==s_perm_rank(s_perm)=True

It works!

Tidy

I searched online, read more mathematical articles in and around the subject of permutations and decided to tidy things up with renamings and changes to function arguments. For example, I found that lex is used as a short replacement for lexicographic ordering, and that a perm is usually generated from the integer width of the perm and the rank required, rather than giving the perm of rank 0 and the rank

The final, (?), version is:


#%% Tidy
def lex_perm_unrank(width: int, rank: int) -> tuple[int]:
    """
    Generate the lexicographic-permutation of ints 0 .. width-1 of given rank.
   
    Author: Donald S. McCarthy "Paddy3118"
    Date: August 2023
    """    
    initial = list(range(width))
    indices = [(rank // factorial(width - j)) % (width - j + 1)
               for j in range(1, width+1)]

    return tuple(initial.pop(index) for index in indices)


# %% Check
for w in range(7):
    for py_rank, py_perm in enumerate(permutations(range(w))):
        lex_perm = lex_perm_unrank(w, py_rank)
        assert lex_perm == py_perm
print("lex_perm_unrank consistent with Python permutations order.")


# %% Tidier
def lex_perm_rank(p: Sequence[int]) -> int:
    """
    Rank of perm p in the lexicographic ordered perms of ints 0 .. len(p)-1
    p must be a permutation of the integers 0 .. (len(p)-1)
   
    Author: Donald S. McCarthy "Paddy3118"
    Date: August 2023
    """
    perm = list(p)
    width = len(perm)
    initial = list(range(width))  # Perm of rank 0
    assert set(perm) == set(initial), \
           "p must be a permutation of the integers 0 .. (len(p)-1)"

    rank, f = 0, width
    while perm:
        f -= 1
        rank += initial.index(perm[0]) * factorial(f)
        initial.remove(perm.pop(0))

    return rank

# %% Check both
for w in range(7):
    for py_rank, py_perm in enumerate(permutations(range(w))):
        lex_perm = lex_perm_unrank(w, py_rank)
        lex_rank = lex_perm_rank(lex_perm)
        assert lex_perm == py_perm and lex_rank == py_rank
print("lex_perm_rank/unrank consistent with Python permutations order.")

 

END.


Monday, August 21, 2023

The Godeh Series, Python, and OEIS

(Best viewed on screens larger than a portrait phone)

 

In my previous post I generalised a form of encryption to do this:

 
Task Encrypt grouping chars by mod M, N times:
    Given an input string S; Some order of the K integers 0..K-1 called
    M, where K <= length_of(S); and an integer N > 0

    First form groups:
        Form group G[0] by concatenating every K'th item of S starting from index 0
        Form group G[1] by concatenating every K'th item of S starting from index 1
        ...
        Form group G[K-1] by concatenating every K'th item of S starting from index K-1

    Group Concatenation:
        Concatenate all the groups G in the order given M to form the partial result P
        P(1) = concatenate_left_to_right(G[i] for i in M)
    Repetition:
        Substituting P for S, repeat the above process N times to form the final
        encrypted string P(N)

    Corner cases:
        If S is empty or N is 0 then return S.
        If M is empty return the empty version of sequence S (empty string).

Examples:
    encrypt6('012345', [1, 0], 0) => '012345'
    encrypt6('012345', [1, 0], 1)          => '135024'
    encrypt6('012345', [1, 0], 2)                   => '304152'
    encrypt6('012345', [1, 0], 3)                            => '012345'
    encrypt6('012345', [1, 0], 4)                                     => '135024'

    encrypt6('01234567', [2, 1, 0], 0) => '01234567'
    encrypt6('01234567', [2, 1, 0], 1)          => '25147036'
    encrypt6('01234567', [2, 1, 0], 2)                   => '10576243'
    encrypt6('01234567', [2, 1, 0], 3)                            => '52063174'
    encrypt6('01234567', [2, 1, 0], 4)                                     => '01234567'

Created from Sun Aug  6 09:10:10 2023

@author: paddy3118


Repetitions

In the example of we see that for n = 3, the output of  encrypt6('012345', [1, 0], 3) starts repeating for higher n.

I have found, but have not proved, that 
encrypt6(S, M, n) == encrypt6(S, M, (n modulo x) )
for some x.
I.e. outputs will eventually equal the input to form a repettitive cycle of outputs.

The length of the cycle, x before repetition does not seem to be simple.

The Godeh series

This series calculates the length of the cycles of encrypt6 untill the input is produced again.
 
 
Godeh series - Original definition by Author
    1. Given:
    * An ordered list of S distinct items, S >= 1.
    * Some permutation of the K integers 0..K-1 called M, where 1 <= K <= S.

    2. Form groups:
    * Form group G[0] by concatenating every K'th item of S starting from index 0
    * Form group G[1] by concatenating every K'th item of S starting from index 1
      ...
    * Form group G[K-1] by concatenating every K'th item of S starting from index K-1

    3. Concatenate groups:
    * Concatenate all the groups G in the order given by M to form the first partial
      result P(1)
        P(1) = concatenate_left_to_right(G[i] for i in M)

    4. Repetition:
        Substituting P for S, repeat the above process until the order of items in P
        equals the initial order, S.

    5. Result
    * Godeh(S, M) = the number of repetitions needed of steps 1-through-4

Created on Thu Aug 17 19:40:32 2023

@author: paddy3118

 

Python code to generate one term

from collections.abc import Sequence
from collections import defaultdict
from itertools import zip_longest, permutations, chain, islice
from functools import cache, lru_cache
from pprint import pp
from string import ascii_letters, digits
from time import sleep
from typing import Callable, Any, overload
import sys
sys.path.append(r'C:\Users\paddy\Google Drive\Code\oeisify')
from oeis_request import oeis_request
from antidiagonals import antidiag_triangle_indices


def godeh(s: int, m: Sequence[int]) -> int:
    "Godeh function Godeh(s, m)"
    k = len(m)
    assert s >= k
    assert set(range(k)) == set(m), \
           f"Sequence m of length {k} should contain a permutation of all the " \
           f"numbers 0..{k-1} inclusive."

    s_init = list(range(s))
    n, s = 0, None
    while s != s_init:
        if n == 0:
            s = s_init
        n += 1
        s = sum((s[offset::k] for offset in m),
                start=[])

    return n



Table of values

 Each row should represent M as "successive permutations" - i.e perms of (0,) then perms of (0,1), perms of (0,1,2) ...
Successive values in each row are then godeh(S,M) where S = len(M), len(M)+1, len(M+2), ...

Code:
 
GodehTableType = dict[tuple[int], list[int]]

def godeh_table(max_s: int=15, max_permed_ints: int=3) -> GodehTableType:
    """
    Create a table of Godeh series values

    Parameters
    ----------
    max_s : int, optional
        Godeh(s, m) for s=len(m) to len(m) + max_s, for all m. The default is 10.
    max_permed_ints : int, optional
        All perms of (0), (0, 1), (0, 1, 2), ... (0, 1, ..max_permed_ints).
        The default is 3.

    Returns
    -------
    dict[
         tuple[int],    # M
         list[int]]     # Godeh(S, M) for S = len(M), len(M)+1, ...
        Tablulated Godeh values.

    """
    table = defaultdict(list)
    for m in chain(*(permutations(range(i)) for i in range(1, max_permed_ints+1))):
        for s in range((k:=len(m)), max_s + k):
            table[(m)].append(godeh(s, m))
    return dict(table)

godeh_series = godeh_table(20, 3)
# %%
pp(godeh_series, width=222)
 
 Output:
 
 
{(0,): [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 (0, 1): [1, 2, 2, 4, 4, 3, 3, 6, 6, 10, 10, 12, 12, 4, 4, 8, 8, 18, 18, 6],
 (1, 0): [2, 2, 4, 4, 3, 3, 6, 6, 10, 10, 12, 12, 4, 4, 8, 8, 18, 18, 6, 6],
 (0, 1, 2): [1, 3, 4, 4, 6, 2, 2, 6, 5, 5, 11, 6, 6, 15, 16, 16, 52, 4, 4, 38],
 (0, 2, 1): [2, 2, 2, 4, 6, 6, 4, 4, 4, 21, 3, 3, 30, 4, 4, 90, 18, 18, 24, 5],
 (1, 0, 2): [2, 2, 4, 4, 6, 4, 4, 4, 21, 21, 3, 30, 30, 8, 90, 90, 18, 24, 24, 10],
 (1, 2, 0): [3, 3, 4, 6, 6, 4, 6, 6, 5, 11, 11, 6, 15, 15, 16, 52, 52, 4, 38, 38],
 (2, 0, 1): [3, 4, 4, 6, 2, 2, 6, 5, 5, 11, 6, 6, 15, 16, 16, 52, 4, 4, 38, 11],
 (2, 1, 0): [2, 2, 4, 6, 6, 4, 4, 4, 21, 3, 3, 30, 4, 4, 90, 18, 18, 24, 5, 5]}

 
 

Duplicate rows?

I suspect that there are duplicate rows of values so generate a larger table and search for row duplication, (I use text searches but it gets the job done).

Code:

def find_reps_in_godeh(g: GodehTableType,
                       _slice_start: int=10,
                       _slice_end: int=18) -> None:
    """
    Prints information on duplicated Godeh table rows.

    Parameters
    ----------
    g : GodehTableType
        Table of Godeh(S,M) values.
    _slice_start : int, optional
        Defines slice of a rows values to search for in other rows of g.
        The default is 10.
    _slice_end : int, optional
        Defines slice of a rows values to search for in other rows of g.
        The default is 18.

    Returns
    -------
    None
    """
    # Uses a string search on stringified row values between commas
    searchable = {m: ',' + str(values)[1:-1].replace(' ','') + ','
                  for m, values in g.items()}
    keys, rows = list(searchable), list(searchable.values())
    # Search for every row in all "higher" rows
    maxrows = len(rows)
    for i in range(maxrows - 1):
        isearch = ',' + str(g[keys[i]][10:17])[1:-1].replace(' ','') + ','
        for k in range(i+1, maxrows):
            if isearch in (rowk:=rows[k]):
                offset = _slice_start - rowk[:rowk.index(isearch)].count(',')
                print(f"Found {keys[i]} in {keys[k]} at {offset = }")


godeh_series = godeh_table(40, 5)  # more values
find_reps_in_godeh(godeh_series, 10, 20)


Output:
 
Found (0, 1) in (1, 0) at offset = 1
Found (0, 1, 2) in (2, 0, 1) at offset = 1
Found (0, 2, 1) in (2, 1, 0) at offset = 1
Found (0, 1, 2, 3) in (3, 0, 1, 2) at offset = 1
Found (0, 1, 3, 2) in (3, 0, 2, 1) at offset = 1
Found (0, 2, 1, 3) in (3, 1, 0, 2) at offset = 1
Found (0, 2, 3, 1) in (3, 1, 2, 0) at offset = 1
Found (0, 3, 1, 2) in (3, 2, 0, 1) at offset = 1
Found (0, 3, 2, 1) in (3, 2, 1, 0) at offset = 1
Found (0, 1, 2, 3, 4) in (4, 0, 1, 2, 3) at offset = 1
Found (0, 1, 2, 4, 3) in (4, 0, 1, 3, 2) at offset = 1
Found (0, 1, 3, 2, 4) in (4, 0, 2, 1, 3) at offset = 1
Found (0, 1, 3, 4, 2) in (4, 0, 2, 3, 1) at offset = 1
Found (0, 1, 4, 2, 3) in (4, 0, 3, 1, 2) at offset = 1
Found (0, 1, 4, 3, 2) in (4, 0, 3, 2, 1) at offset = 1
Found (0, 2, 1, 3, 4) in (4, 1, 0, 2, 3) at offset = 1
Found (0, 2, 1, 4, 3) in (4, 1, 0, 3, 2) at offset = 1
Found (0, 2, 3, 1, 4) in (4, 1, 2, 0, 3) at offset = 1
Found (0, 2, 3, 4, 1) in (4, 1, 2, 3, 0) at offset = 1
Found (0, 2, 4, 1, 3) in (4, 1, 3, 0, 2) at offset = 1
Found (0, 2, 4, 3, 1) in (4, 1, 3, 2, 0) at offset = 1
Found (0, 3, 1, 2, 4) in (4, 2, 0, 1, 3) at offset = 1
Found (0, 3, 1, 4, 2) in (4, 2, 0, 3, 1) at offset = 1
Found (0, 3, 2, 1, 4) in (4, 2, 1, 0, 3) at offset = 1
Found (0, 3, 2, 4, 1) in (4, 2, 1, 3, 0) at offset = 1
Found (0, 3, 4, 1, 2) in (4, 2, 3, 0, 1) at offset = 1
Found (0, 3, 4, 2, 1) in (4, 2, 3, 1, 0) at offset = 1
Found (0, 4, 1, 2, 3) in (4, 3, 0, 1, 2) at offset = 1
Found (0, 4, 1, 3, 2) in (4, 3, 0, 2, 1) at offset = 1
Found (0, 4, 2, 1, 3) in (4, 3, 1, 0, 2) at offset = 1
Found (0, 4, 2, 3, 1) in (4, 3, 1, 2, 0) at offset = 1
Found (0, 4, 3, 1, 2) in (4, 3, 2, 0, 1) at offset = 1
Found (0, 4, 3, 2, 1) in (4, 3, 2, 1, 0) at offset = 1

 Observation, Duals!

 The first line is saying that M = (1, 0) values are the same as those for M = (0, 1); just with an offset of being one term over.
 
  • There are only row duals found. no rows data is replicated in more than one other row.
  •  All the offsets are one.
  • Duals are between rows of the same size perms in M; with the Leftmost value of M being max(M) paired with an M where the leftmost value of M is min(M).

OEIS Searching by hand: Abulsme

I put a few selections of the table rows into OEIS by hand and found that, (but not proved), I can generate all the Abulsme function values from my Godeh function!
 

def a105272_table(max_s: int=10, max_permed_ints: int=40):
    """
    Abulsme function by different means: http://www.abulsme.com/function.html
    == Godeh(S, M) where All M's are ints sorted high to low
    """
    table = defaultdict(list)
    for m in (range(i)[::-1] for i in range(1, max_permed_ints+1)):
        for s in range(k:=len(m), max_s + k):
            table[k].append(godeh(s, m))
    return dict(table)

a105272 = a105272_table(20, 15)
# %%
pp(a105272, width=222)


Table of Abulsme values produced

 
{1: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 2: [2, 2, 4, 4, 3, 3, 6, 6, 10, 10, 12, 12, 4, 4, 8, 8, 18, 18, 6, 6],
 3: [2, 2, 4, 6, 6, 4, 4, 4, 21, 3, 3, 30, 4, 4, 90, 18, 18, 24, 5, 5],
 4: [2, 2, 4, 7, 3, 3, 8, 10, 6, 6, 20, 4, 4, 4, 132, 30, 3, 3, 24, 252],
 5: [2, 2, 4, 7, 15, 5, 5, 12, 40, 45, 4, 4, 12, 8, 16, 6, 6, 16, 28, 4],
 6: [2, 2, 4, 14, 6, 10, 12, 12, 7, 15, 56, 90, 9, 9, 51, 21, 105, 23, 5, 5],
 7: [2, 2, 4, 14, 6, 12, 30, 4, 4, 20, 15, 70, 30, 18, 10, 10, 48, 72, 24, 25],
 8: [2, 2, 4, 14, 6, 13, 13, 24, 8, 8, 40, 70, 91, 18, 18, 22, 20, 20, 44, 312],
 9: [2, 2, 4, 14, 6, 13, 15, 15, 63, 9, 9, 20, 18, 85, 30, 24, 60, 44, 3, 3],
 10: [2, 2, 4, 14, 6, 26, 16, 10, 18, 12, 6, 6, 42, 21, 22, 42, 68, 165, 182, 30],
 11: [2, 2, 4, 14, 6, 26, 16, 60, 78, 48, 20, 22, 22, 12, 25, 390, 90, 21, 360, 42],
 12: [2, 2, 4, 14, 6, 26, 16, 65, 120, 84, 21, 36, 20, 20, 44, 132, 120, 24, 100, 108],
 13: [2, 2, 4, 14, 6, 26, 16, 65, 168, 168, 120, 20, 25, 9, 9, 60, 24, 187, 616, 84],
 14: [2, 2, 4, 14, 6, 26, 16, 130, 24, 60, 130, 144, 20, 26, 28, 28, 15, 60, 84, 84],
 15: [2, 2, 4, 14, 6, 26, 16, 130, 24, 204, 24, 144, 170, 170, 40, 10, 10, 30, 510, 34]}

 

Auto-check OEIS

I hooked in my oeis search routine and searched for each row of the Godeh table of values.

Code:


def oeis_check_values(table: dict[Any, list[int]],
                      _slice_start: int=4,
                      _slice_end: int=12,
                      _secs_between_searches: int=5,
                      _show_not_found=False
                      ) -> None:
    "Search for each row of table in OEIS"
   
    for key, vals in table.items():
        oeis = oeis_request(str(vals[_slice_start:_slice_end])[1:-1])
        found = [k for k in oeis if k[0] == 'A']
        if found:
            print(f"{key}: is found in OEIS {', '.join(found)}")
        elif _show_not_found:
            print(f"{key}: Not found in oeis.")
           
        sleep(_secs_between_searches)

godeh_series = godeh_table(40, 5)  # more values
oeis_check_values(godeh_series, _secs_between_searches=2)

It takes some time to run, but eventually I get these results:

Output:

(0,): is found in OEIS A000012, A055642, A135010, A057427, A138121, A000030, A047999, A071625, A079944, A228351
(0, 1): is found in OEIS A024222
(1, 0): is found in OEIS A024222
(0, 2, 1): is found in OEIS A118960
(2, 1, 0): is found in OEIS A118960
(0, 3, 2, 1): is found in OEIS A120280
(3, 2, 1, 0): is found in OEIS A120280
(0, 4, 3, 2, 1): is found in OEIS A120363
(4, 3, 2, 1, 0): is found in OEIS A120363
(0, 5, 4, 3, 2, 1): is found in OEIS A120654
(5, 4, 3, 2, 1, 0): is found in OEIS A120654

Ignoring (0,) which is just all the ones; All the other matches are selections from the Abulsme function,
a105272, when M is either reverse sorted, or its dual.
 

OEIS ENTRY?

It seems that the  Godeh Series is more general than a105272 so I thought I'd submit it to OEIS. It's submitted and allocated as A365096. Fingers crossed!

Antidiagonalisation

When you submit a table of values the DATA entry must be in antidiagonalisation format. I did a quick module to provide that functionality:

Module antidiagonals.py:

# -*- 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))


 

Antidiagonalisation test

 
def antidiagonalise(table: dict[Any, list[int]]) -> int:
    maxx = len(xkeys:=list(table))
    maxy = min(len(row) for row in table.values())
    antigen = antidiag_triangle_indices().__next__
    x, y = antigen()
    while x < maxx and y < maxy:
        yield table[xkeys[x]][y]
        x, y = antigen()

t = {f"{x = }": [(x, y) for y in range(7)] for x in range(3)}

print('# Sample table')
pp(t, width=100, sort_dicts=False)

print("\nAntidiagonalised\n", list(antidiagonalise(t)))

 
 Test output:
 
# Sample table
{'x = 0': [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6)],
 'x = 1': [(1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6)],
 'x = 2': [(2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6)]}

Antidiagonalised
 [(0, 0), (0, 1), (1, 0), (0, 2), (1, 1), (2, 0), (0, 3), (1, 2), (2, 1)]

 
 

 Better formatted table for comments

godeh_series2 = godeh_table(20, 3)

for M, v in godeh_series2.items():
    m = f"{M = }"
    print(f"{m:>13s}: {str(v)[1:-1].replace(' ', '')},...")
 
 Output:
 
     M = (0,): 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,...
   M = (0, 1): 1,2,2,4,4,3,3,6,6,10,10,12,12,4,4,8,8,18,18,6,...
   M = (1, 0): 2,2,4,4,3,3,6,6,10,10,12,12,4,4,8,8,18,18,6,6,...
M = (0, 1, 2): 1,3,4,4,6,2,2,6,5,5,11,6,6,15,16,16,52,4,4,38,...
M = (0, 2, 1): 2,2,2,4,6,6,4,4,4,21,3,3,30,4,4,90,18,18,24,5,...
M = (1, 0, 2): 2,2,4,4,6,4,4,4,21,21,3,30,30,8,90,90,18,24,24,10,...
M = (1, 2, 0): 3,3,4,6,6,4,6,6,5,11,11,6,15,15,16,52,52,4,38,38,...
M = (2, 0, 1): 3,4,4,6,2,2,6,5,5,11,6,6,15,16,16,52,4,4,38,11,...
M = (2, 1, 0): 2,2,4,6,6,4,4,4,21,3,3,30,4,4,90,18,18,24,5,5,...
 
 
 
 END.