(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) )
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
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.
No comments:
Post a Comment