OFFSET
1,2
COMMENTS
Table by rows, rows have length 4.
Elements are a permutation of positive integers, intermixed with zeros.
Expanded description: Partition the positive integers into arithmetic progressions of the form k, 2k, 3k, 4k, putting every positive integer into the first progressions where it fits, allowing shortened progressions (which are padded with zeros):
k, 0, 0, 0;
k, 2k, 0, 0;
k, 2k, 3k, 0.
Construction:
1. Start by matrix M with rows indexed by positive integers, columns by 1,2,3,4.
2. M_ij = i*j.
3. Proceeding row by row, then column by column, if M_ij = M_rk with r < i, set M_is = 0 for i <= s <= 4; if j=0, remove entire row.
4. Call the resulting matrix A.
So starting with
M = [ 1 2 3 4]
[ 2 4 6 8]
[ 3 6 9 12]
[ 4 8 12 16]
[ 5 10 15 20]
[ 6 12 18 24]
[ 7 14 21 28]
[ 8 16 24 32]
[ 9 18 27 36]
[10 20 30 40]
[11 22 33 44]
[12 24 36 48]
[13 26 39 52]
[14 28 42 56]
[15 30 45 60]
[16 32 48 64]
[17 34 51 68]
[18 36 54 72]
[19 38 57 76]
[20 40 60 80]
we arrive at
A = [ 1 2 3 4]
[ 5 10 15 20]
[ 6 12 18 24]
[ 7 14 21 28]
[ 8 16 0 0]
[ 9 0 0 0]
[ 11 22 33 44]
[ 13 26 39 52]
[ 17 34 51 68]
[ 19 38 57 76]
Every row in A is an arithmetic progression (even when 0 is adjoined), and every positive integer occurs at precisely one position.
Thus we get a partition of the positive integers into parts which are arithmetic progressions; using this partition for every prime number p yields a regular (in the sense of Narkiewicz) convolution product on the vector space of arithmetic functions.
The first column of A contains those b such that p^b is primitive.
Alternative construction:
Form an infinite rooted tree T on the nonnegative integers in the following way.
1. 0 is the root.
2. Form a branch 0 - 1 - 2 -3 - 4.
3. Proceed inductively. Add n to end of an existing branch as either
0 - k=n
0 - k - 2k=n
0 - k - 2k - 3k=n
0 - k - 2k - 3k - 4k=n
with a preference for smaller k.
4. After infinitely many steps you have constructed T.
5. Read the positive integers branch by branch.
LINKS
Jan Snellman, Table of n, a(n) for n = 1..20788
W. Narkiewicz, On a class of arithmetical convolutions, Colloq. Math. 10, 1963, pp 81-94.
Jan Snellman, Greedy Regular Convolutions, arXiv:2504.02795 [math.NT], 2025.
EXAMPLE
Up to n=15 the branches of the aforementioned tree looks like
0 - 1 - 2 - 3 - 4,
0 - 5 - 10 - 15,
0 - 6 - 12,
0 - 7 - 14,
0 - 8,
0 - 9,
0 - 11,
0 - 13;
but since 20=5*4 the second branch may not be complete, so at this stage we only know the first row of the matrix A. Adding 16, 17, 18, 19, 20 we get
0 - 1 - 2 - 3 - 4,
0 - 5 - 10 - 15 - 20,
0 - 6 - 12 - 18,
0 - 7 - 14,
0 - 8 - 16,
0 - 9,
0 - 11,
0 - 13,
0 - 17,
0 - 19;
and now we know the first two rows of A.
PROG
(SageMath)
def greedy_matrix(blocklength=2, initial_cols=20):
m, n = blocklength, initial_cols
A = matrix(ZZ, m, n, lambda i, j: (i+1)*(j+1))
for c in range(2, n+1):
for r in range(1, m+1):
prev = set(flatten([list(_) for _ in A.columns()[:(c-1)]]))
v = A[r-1, c-1]
if v in prev:
for j in range(r, m+1):
A[j-1, c-1] = 0
break
return A
def pruned_greedy_matrix(blocklength=2, initial_cols=20):
A = greedy_matrix(blocklength=blocklength, initial_cols=initial_cols)
return matrix([_ for _ in A.columns() if add(_) > 0]).transpose()
pruned_greedy_matrix(blocklength=4, initial_cols=20)
(Python)
def A382747_generator(blocklength=4):
a_set = set()
a0 = 1
while 1:
while a0 in a_set:
a_set.remove(a0)
a0 += 1
for i in range(1, blocklength+1):
a = i*a0
if i != 1 and a in a_set:
for j in range(blocklength-i+1): yield 0
break
yield a
a_set.add(a) # Pontus von Brömssen, Apr 30 2025
CROSSREFS
KEYWORD
nonn,tabf,easy
AUTHOR
Jan Snellman, Apr 23 2025
STATUS
approved