A365315 Number of unordered pairs of distinct positive integers <= n that can be linearly combined using positive coefficients to obtain n.

0, 0, 0, 1, 2, 4, 5, 8, 10, 12, 15, 18, 20, 24, 28, 28, 35, 37, 42, 44, 49, 49, 60, 59, 66, 65, 79, 74, 85, 84, 93, 93, 107, 100, 120, 104, 126, 121, 142, 129, 145, 140, 160, 150, 173, 154, 189, 170, 196, 176, 208, 193, 223, 202, 238, 203, 241, 227, 267, 235

Offset

0,5

Comments

We consider (for example) that 2x + y + 3z is a positive linear combination of (x,y,z), but 2x + y is not, as the coefficient of z is 0.

Links

Chai Wah Wu, Table of n, a(n) for n = 0..10000

Example

We have 19 = 4*3 + 1*7, so the pair (3,7) is counted under a(19).
For the pair p = (2,3), we have 4 = 2*2 + 0*3, so p is counted under A365314(4), but it is not possible to write 4 as a positive linear combination of 2 and 3, so p is not counted under a(4).
The a(3) = 1 through a(10) = 15 pairs:
  (1,2)  (1,2)  (1,2)  (1,2)  (1,2)  (1,2)  (1,2)  (1,2)
         (1,3)  (1,3)  (1,3)  (1,3)  (1,3)  (1,3)  (1,3)
                (1,4)  (1,4)  (1,4)  (1,4)  (1,4)  (1,4)
                (2,3)  (1,5)  (1,5)  (1,5)  (1,5)  (1,5)
                       (2,4)  (1,6)  (1,6)  (1,6)  (1,6)
                              (2,3)  (1,7)  (1,7)  (1,7)
                              (2,5)  (2,3)  (1,8)  (1,8)
                              (3,4)  (2,4)  (2,3)  (1,9)
                                     (2,6)  (2,5)  (2,3)
                                     (3,5)  (2,7)  (2,4)
                                            (3,6)  (2,6)
                                            (4,5)  (2,8)
                                                   (3,4)
                                                   (3,7)
                                                   (4,6)

Mathematica

combp[n_, y_]:=With[{s=Table[{k, i}, {k, y}, {i, 1, Floor[n/k]}]}, Select[Tuples[s], Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n], {2}], combp[n, #]!={}&]], {n, 0, 30}]

Prog

(Python)
from itertools import count
from sympy import divisors
def A365315(n):
    a = set()
    for i in range(1, n+1):
        for j in count(i, i):
            if j >= n:
                break
            for d in divisors(n-j):
                if d>=i:
                    break
                a.add((d, i))
    return len(a) # Chai Wah Wu, Sep 13 2023

Crossrefs

The unrestricted version is A000217, ranks A001358.

For all subsets instead of just pairs we have A088314, complement A365322.

For strict partitions we have A088571, complement A088528.

The case of nonnegative coefficients is A365314, for all subsets A365073.

The (binary) complement is A365321, nonnegative A365320.

A004526 counts partitions of length 2, shift right for strict.

A007865 counts sum-free subsets, complement A093971.

A179822 and A326080 count sum-closed subsets.

A326083 and A124506 appear to count combination-free subsets.

A364350 counts combination-free strict partitions.

A364914 and A365046 count combination-full subsets.

Cf. A070880, A088809, A326020, A364534, A365043, A365311, A365312, A365378, A365379, A365380, A365383.

Sequence in context: A188975 A115392 A342541 * A179509 A157007 A173509

Adjacent sequences: A365312 A365313 A365314 * A365316 A365317 A365318

Keyword

nonn

Author

Gus Wiseman, Sep 06 2023

Status

approved