A382747 Greedy partition of the positive integers into arithmetic progressions of length at most 4.

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, 23, 46, 69, 92, 25, 50, 75, 100, 27, 54, 81, 108, 29, 58, 87, 116, 30, 60, 90, 120, 31, 62, 93, 124, 32, 64, 96, 128, 35, 70, 105, 140, 36, 72, 0, 0, 37, 74, 111, 148, 40, 80, 0, 0

Offset: 1

Author

Jan Snellman, Apr 23 2025

Keywords

• nonn
• tabf
• easy

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.

Examples

			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.
		

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.

Crossrefs

First column yields A382748.

A382749(n) = column where n occurs in this matrix.

The case length=2 is A036552, when the latter is interpreted as a matrix with two columns.

Programs

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

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)