A239635 Common Sigma, Uncommon Clique Numbers: a(n) is the minimal s for which there exists a set of n pairwise relatively prime integers with a sigma value of s.

1, 12, 24, 72, 240, 360, 1440, 1440, 1440, 8640, 10080, 15120, 34560, 45360, 55440, 60480, 60480, 166320, 181440, 211680, 332640, 332640, 332640, 665280, 665280, 665280, 831600, 907200, 1663200, 2494800, 2661120, 2661120

Offset: 1

Author

Fred Schneider, Mar 22 2014

Keywords

• nonn
• hard

Comments

The meaning of the name just involves a little wordplay.

Common Sigma: Refers to an underlying set with a common sigma.

Uncommon Clique: This set or "clique" (see link below) of numbers is "uncommon" because they are pairwise relatively prime and thus have no common factors.

Graph Theory Description:

Suppose we built an incidence graph for each positive integer s whereby each number which had sigma = s represented a vertex in the graph and the only edges were drawn between relatively prime numbers. For each s, we want to find the maximal clique (aka complete subgraph) size.

a(n) would be the minimum s where the maximal clique = n.

(Note: If a clique of size n exists for s, there exists a clique of any size < n, so any gaps in the series could be filled by S (e.g., 1440: terms 7-9).)

The first 5 terms and their solution sets (plus member factors showing they are all relatively prime to each other):

1 : 1

12 : 6 = 2 * 3, 11 = 11

24 : 14 = 2 * 7, 15 = 3 * 5, 23 = 23

72 : 46 = 2 * 23, 51 = 3 * 17, 55 = 5 * 11, 71 = 71

240 : 135 = 3^3 * 5, 158 = 2 * 79, 203 = 7 * 29, 209 = 11 * 19, 239 = 239

An exhaustive search was performed to show that these are in fact the minimal terms.

Comment with b-file submission:

I found a few useful optimizations:

1) For a sigma's possible solution set, only consider the numbers which have 3 or fewer distinct prime factors.

2) Check if there's a number which is a prime (power). Set that aside. (Call the count c1.)

3) Set aside any numbers with two prime factors (If there are duplicates, say two numbers which are multiples of two, pick the smallest exponent. The larger prime factor has less of chance of being found elsewhere in the solution set). Call this count c2.

4) Then, discard any 3-prime factor numbers which are not relatively prime with the above numbers.

5) Of those remaining numbers, determine the set of distinct primes found amongst their factors. Call this set size pc.

6) If (pc/3) + c1 + c2 > maxCliqueSize found, we have a possibility of adding to this sequence and should try to find a "sub-clique" (among the remaining 3-prime numbers) which is maxCliqueSize-c1-c2.

Links

• Fred Schneider, Table of n, a(n) for n = 1..65
• Fred Schneider, Solution sets for terms 1..65
• Wikipedia, Sigma
• Wikipedia, Clique

Crossrefs

Cf. sigma-related sequences: A000203, A007368.