A393585 - OEIS

OFFSET

1,2

COMMENTS

Conjectured values:

a(13) = 116: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15}, {1, 7, 9, 10, 11, 13, 16, 17, 19, 23, 29, 31, 37}.

a(14) = 134: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15}, {1, 7, 9, 10, 11, 13, 16, 17, 19, 23, 25, 29, 31, 37}.

a(15) = 154: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 20}, {1, 7, 11, 13, 15, 16, 17, 18, 19, 23, 25, 29, 31, 37, 41}.

There appears to always be one prime-heavy set and one composite-heavy set. For example, in one of the set pairs for n = 10, the first set is composite heavy (4, 6, 9, 10, 12) and the second is prime-heavy (5, 7, 11, 13, 17, 19, 23). The proportions of the primes/composites seem to be just over half of the set.

Are first differences nondecreasing?

From David A. Corneth, Mar 30 2026: (Start)

For any ceiling(n^2/2) <= p < q < n^2 where p and q are prime, if q in one of two sets achieving a(n) then p is also in such pair of sets.

a(2) = 3. Proof: a(2) >= 3 via {1, 2}, {1, 2} giving {1, 2, 4} as distinct products.

As there can be at most 2^2 = 4 products we have a(2) <= 4. Suppose a(2) = 4. Then there exist two sets A, B such that product of two elements, one from A, one from B is {1, 2, 3, 4}. As 1 is in the product both A and B contain 1. There are two places left in total of A and B. As 2 and 3 are both prime they must both be in A or B. So then we must have {A, B} = {{1, 2}, {1, 3}}. This way we do not get product 4 which is a contradiction. Therefore a(2) < 4. Combining with a(2) >= 3 we have a(2) = 3.

a(3) = 7. Proof: a(n) <= 3^2 = 9. Suppose a(n) = 9. Then the distinct products are {1, 2, 3, 4, 5, 6, 7, 8, 9}. This set has four primes. As there are 4 spots left in the two sets the primes take all the spots. Then no product of two elements multiply to 4. A contradiction. So we don't have 7, the largest prime >= ceil(3^2/2) = 5. Therefore the product of numbers <= 9 is a subset of {1, 2, 3, 4, 5, 6, 8, 9} and a(3) <= 8. Suppose a(3) = 8. Then, without loss of generality, there are 3 options for A and B where # denotes a number and two # may represent distinct numbers. The options are:

{A, B} = {{1, 2, #}, {1, 3, 5}}, {A, B} = {{1, 3, #}, {1, 2, 5}}, {A, B} = {{1, 5, #}, {1, 2, 3}} (Cf. A001222). We need to get 4 or 8 which have Omega(4) = 2 and Omega(8) = 3 respectively. So we need to include a number k with Omega(k) <= 2 to get 4. The only number this can be is 4 itself. In all cases there will be at least two numbers in the product that are > 9. a(3) >= 8 implies that at most 1 number can be more than 9 which is a contradiction. Therefore a(3) >= 7.

We can trim the search in some cases. For example in a search for a(6) we cannot have the sets start with {1, 2, 3} and {1, 2, 9} respectively, knowing a(6) >= 25. The products are 1, 2, 9, 2, 4, 18, 3, 6, 27. The two is double so from here we can get at most 6^2 - 1 = 35. If we extend the sets with the smallest numbers possible we get {1, 2, 3, 4, 5, 6}, {1, 2, 9, 10, 11, 12}. This gives the products (sorted, listed with multiplicity) of {1, 2, 2, 3, 4, 4, 5, 6, 6, 8, 9, 10, 10, 11, 12, 12, 18, 20, 22, 24, 27, 30, 33, 36, 36, 40, 44, 45, 48, 50, 54, 55, 60, 60, 66, 72}. Of these there are 11 numbers > 36. So now we can get at most 36-1-11 = 24. Furthermore we cannot get any number < k*m where k and m are the smallest number in the respective sets. In this case this removes 0 numbers. So when the sets start with {1, 2, 3} and {1, 2, 9} we have a(6) <= 24 which contradicts a(6) >= 25. (End)

a(16) >= 172: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 20}, {1, 7, 11, 13, 15, 16, 17, 18, 19, 23, 25, 29, 31, 37, 41, 47}. - Pontus von Brömssen, Apr 06 2026

LINKS

Table of n, a(n) for n=1..12.

David A. Corneth, PARI program.

Rhys Feltman, a(11) solutions.

Rhys Feltman, a(12) solutions.

EXAMPLE

a(1) = 1: {1}, {1}.

a(2) = 3: {1, 2}, {1, 2}.

a(3) = 7: {1, 2, 3}, {1, 3, 4}.

a(4) = 12: {1, 2, 3, 4}, {1, 3, 4, 5}.

a(5) = 18: {1, 2, 3, 4, 5}, {1, 3, 5, 7, 8}.

a(6) = 27: {1, 2, 3, 4, 5, 6}, {1, 5, 7, 8, 9, 11}.