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

# %%

"""

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.

Finding a sub-list within a list, in Python

   

 

Existing?

 As part of a larger project, I thought I might need to search for a sub-list within a given list, and because I am lazy i did a quick google and did not like the answers I found.I started with the thought that the best algorithm for me would be to start searching from the index of the first item in the sublist and so on, but none of the googled answers used list.index.

I decided then to create my own 

My version

Well I want to use list.index. If the item is not in the list then it raises an error, so I'll need a try-except block too.

I look for successive first item from the sub-list in the list and if found, accumulate the index in the answer and move on to search for the next match.

It seemed easy to add flags to:

1. Stop after finding a first index of the sub-list in the list.
2. Allow overlapping matches  or not. [1,0,1] is found twice in [1,0,1,0,1] at indices 0 and 2, but only once if overlapping is not allowed

#!/bin/env python3

#%%

from typing import Any

"""

Find instance of a sub-list in a list

"""

def index_sublist(lst: list[Any],

                  sublst: list[Any],

                  only_first: bool=False,

                  non_overlapping=False,

                  ) -> list[int]:

    "Find instance of a (non-empty), sub-list in a list"

    if not sublst:

        raise ValueError("Empty sub-list")

    if not lst:

        return []

   

    first, ln = sublst[0], len(sublst)

   

    if len(lst) < ln:  # Reddit: check sizes

        return []

   

    ans, i = [], 0

    while True:

        try:

            i = lst.index(first, i)

        except ValueError:

            break

        if lst[i: i+ln] == sublst:

            ans.append(i)

            if only_first:  #Reddit: Only_first calc now fixed

                break

        i += ln if non_overlapping else 1

   

    return ans

#%%

def test():

    assert index_sublist([], [1], only_first=False) == []

    assert index_sublist([1], [1], only_first=False) == [0]

    assert index_sublist([1,0,1], [1], only_first=False) == [0, 2]

    assert index_sublist([2,1,0,1], [1], only_first=True) == [1]

    assert index_sublist([2,1,0,1], [1, 3], only_first=False) == []

   

    assert index_sublist([1,0,1,0,1], [1,0,1],

                         only_first=False,

                         non_overlapping=False) == [0, 2]

    assert index_sublist([1,0,1,0,1], [1,0,1],

                         only_first=False,

                         non_overlapping=True) == [0]

    # Reddit: Extra checks

    assert index_sublist([2,1,0,1,2,1,2], [1, 2],

                         only_first=True) == [3]

    assert index_sublist([2,1,0,1,2,1,2], [1, 2],

                         only_first=False) == [3,5]

#%%

if __name__ == '__main__':

    test()

# %%

STOP PRESS!

A Reddit commenter spotted a bug that I fixed and added a couple of extra tests for.

End.

 

How not to check for a key in a dictionary.

 I skim the Linkedin Python group and sometimes comment.

A few days there was a poll asking for the way to check if a key is in a Python dictionary and as I write, more than half of the 900+ respondents have chosen dict.get rather than key in dict, which is the correct answer!

When pushed, it seems they are relying on dict.get returning None if the key is not in the dict, but fail to see tha if the key being tested is in the dict, but has a value of None then their test fails. 

Here's some code:

# %%

mydict1 = {'a': 1, 'b': 2}

print(mydict1.get('c'))  # -> None

# %%

def key_in_dict1(key_, dict_: dict) -> bool:

    "FAULTY IMPLEMENTATION"

    return dict_.get(key_) != None

# This works

mydict1 = {'a': 1, 'b': 2}

print(key_in_dict1('a', mydict1))  # -> True

print(key_in_dict1('x', mydict1))  # -> False

# %%

# But adding a key of x with value None gives

# the wrong result

mydict2 = {'a': 1, 'b': 2, 'x': None}

print(key_in_dict1('x', mydict2))  # -> False

# %%

# The correct way is to use 'in'

def key_in_dict2(key_, dict_: dict) -> bool:

    "Pythonic IMPLEMENTATION"

    return key_ in dict_

# Tests:

print(key_in_dict2('a', mydict1))  # -> True

print(key_in_dict2('x', mydict1))  # -> False

# %%

# And now for keys with None as a value:

print(key_in_dict2('x', mydict2))  # -> True

Ugly, code-golf solution using dict.get()

You can alter the default value returned from dict.get if a key is not found. This allows one to use two calls of dict.get with different defaults  to be used to give a correct solution:

def key_in_dict3(key_, dict_: dict) -> bool:

    "CODE-GOLF IMPLEMENTATION USING GETs"

    default1 = None

    default2 = ""

    return default1 != default2 \

        and ( dict_.get(key_, default1) != default1

             or dict_.get(key_, default2) != default2)

# Tests:

print(key_in_dict3('a', mydict1))  # -> True

print(key_in_dict3('x', mydict1))  # -> False

print(key_in_dict3('x', mydict2))  # -> True

Of course, don't use  key_in_dict3, use version 2, i.e. key in dict.

END.

Google Bard vs Microsoft Bing Chat: Vanity questions

 I ask two questions about my activities online and compare the outputs from the two AI tools.

Google Bard

 

create a rosettacode.org task in the style of user paddy3118

Sure, here is a Rosetta Code task in the style of user paddy3118:

Task:

Write a program that generates the Godeh series. The Godeh series is an infinite sequence of integers that is defined by the following recursive formula:

godeh(n) = {
  1, if n = 1
  godeh(n // 2), if n is even
  godeh(n // 2) + godeh(n // 2 + 1), if n is odd
}

Input:

An integer n.

Output:

The first n terms of the Godeh series.

Example:

Input: 10

Output:
1
1
2
1
3
2
3
1
4
3

Solution:

Python

def godeh(n):
  if (n == 1):
    return 1
  elif (n % 2 == 0):
    return godeh(n // 2)
  else:
    return godeh(n // 2) + godeh(n // 2 + 1)

n = 10
for i in range(1, n + 1):
  print(godeh(i))

Use code with caution. Learn more

Paddy3118's style:

Paddy3118's programs are typically well-written and easy to understand. They are also often accompanied by clear and concise explanations of the code. In this task, Paddy3118 would likely provide a brief explanation of the Godeh series and the recursive formula used to define it. He would then provide a Python implementation of the program, along with an example of how to use it.

Here is an example of a task that Paddy3118 might write:

Task:

Write a program that generates the prime numbers up to a specified input.

Input:

An integer n.

Output:

A list of all the prime numbers up to n.

Example:

Input: 100

Output:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Solution:

Python

def is_prime(n):
  if (n <= 1):
    return False
  if (n <= 3):
    return True
  if (n % 2 == 0
 
or n % 3 == 0):
    return
 
False
  i = 5

  
while (i * i <= n):
    if (n % i == 0
 
or n % (i + 2) == 0):
      return
 
False
    i += 6

  
return
 
True


def
 
prime_numbers_up_to(n):
  primes = []
  for i in
 
range(2, n + 1):
    if (is_prime(i)):
      primes.append(i)
  return primes

n = 100
primes = prime_numbers_up_to(n)
print(primes)

Use code with caution. Learn more

Sources

1. medium.com/edureka/python-program-prime-number-28001c0d54f2
2. github.com/pratyksha/competitive-programming

 

Microsoft Bing Chat

create a rosettacode.org task in the style of user paddy3118

…

I’m sorry, but I am not able to create a Rosetta Code task for you. However, I can provide you with some information about Paddy3118, a prolific contributor to Rosetta Code who has created many tasks in the past. Paddy3118 is a pseudonym for Donald McCarthy, who works with Electronic Design Automation tools creating design flows, filling in the gaps with novel tools, and generally helping to design and verify integrated circuits¹. He has created 392 new pages on Rosetta Code, of which 148 were not Talk: pages, from approximately 4523 edits¹. You can find more information about Paddy3118 and his contributions to Rosetta Code on his user page ¹. I hope this information helps!

Learn more

1rosettacode.org2rosettacode.org3rosettacode.org4rosettacode.org5en.wikipedia.org

8of30

 

 

 

 

 Bard vs Bing

The actual formatting does not copy-paste well in either case.

• Bard attempts to write a task in my style, and gives some tips on my style.
• Bing cannot create the task, but does extract some info on me.
• Clearly a Bard win.
• Flattery will get them nowhere! (But keep it up mind you).

 

 

Google Bard #2

what does paddy3118 do online?

Paddy3118 is an active participant in the online programming community, particularly in areas related to mathematics and algorithms. They have authored numerous programs and solutions to coding challenges, demonstrating expertise in various programming languages and problem-solving techniques. Paddy3118's contributions can be found across various platforms, including:

GitHub: Paddy3118 has a notable presence on GitHub, where they have authored over 50 programs covering a wide range of topics, including:

• Mathematical algorithms: Implementing various mathematical concepts and algorithms, such as the Godeh series generator, Collatz conjecture tester, and prime number generator.

• Problem-solving challenges: Tackling coding challenges from platforms like Codewars, showcasing their ability to solve complex problems efficiently.

• Data manipulation and analysis: Demonstrating proficiency in handling and analyzing data through programs like the factorial calculator and Fibonacci sequence generator.

Their GitHub repositories often include detailed explanations of the code, making them valuable learning resources for other programmers.

Stack Overflow: Paddy3118 is an active contributor on Stack Overflow, a question-and-answer website for programmers. They have answered over 1,000 questions with an average score of 4.5 out of 5, indicating their deep understanding of programming concepts and their willingness to share their knowledge with others.

Codewars: Paddy3118 is a skilled competitor on Codewars, a coding challenge platform. They have solved over 1,000 coding challenges and currently rank in the top 1% of users. This achievement highlights their ability to think creatively and apply their programming expertise to solve complex problems.

GitHub Discussions: Paddy3118 actively engages in discussions on GitHub Discussions, a forum where users discuss technical topics. They provide helpful advice, share insights, and contribute to the overall knowledge base of the community.

Overall, Paddy3118 is a valuable member of the online programming community, recognized for their contributions to various platforms and their willingness to share their knowledge and expertise with others.

Microsoft Bing Chat #2

what does paddy3118 do online?

…

I’m sorry, but I could not find any information about what Paddy3118 does online. However, I can tell you that Paddy3118 is a pseudonym for Donald McCarthy, who works with Electronic Design Automation tools creating design flows, filling in the gaps with novel tools, and generally helping to design and verify integrated circuits¹. He has created 392 new pages on Rosetta Code, of which 148 were not Talk: pages, from approximately 4523 edits¹. You can find more information about Paddy3118 and his contributions to Rosetta Code on his user page ¹. I hope this information helps!

Learn more

1you.dj2photopea.com3silver.urih.com

10of30

 

Bard vs Bing #2

• Bard has found me on numerous sites and attempted to summarise my contributions to them and comments that I like to help
• Bing states up front that it could not find me but then quotes an extract based on my RosettaCode talk page.
• None mention Python!?!
  
• Another win for Bard.
  

At the moment, just using these easy-access AI tools, Bard seems to give better results.

It's still early days however!

END.