7
\$\begingroup\$

The set of ten numbers below:

223092870
17237308840522
1075474925835771
12574206406402195
79458974087499419
265057843710517649
466012798920390527
926434345611831877
1390237791335182649
2336970054109245767

has the property that no two pairs of numbers have the same greatest common factor. (In this case, the greatest common factor of each pair of numbers is actually a distinct prime.)

Your task is to find the set of 10 positive integers with the smallest sum that satisfy this property.

For reference, the sum of the above ten numbers is 5 477 838 726 638 839 246 (≈5.48×1018).

\$\endgroup\$
  • \$\begingroup\$ What's the score? The sum, then post time? \$\endgroup\$ – John Dvorak Aug 26 '13 at 19:34
  • \$\begingroup\$ The lowest currently posted sum wins, and if there is an exact tie, then earliest posted time is the tiebreaker. \$\endgroup\$ – Joe Z. Aug 26 '13 at 19:35
  • 1
    \$\begingroup\$ recently posted? The oldest one with a given sum should be the winner. \$\endgroup\$ – John Dvorak Aug 26 '13 at 19:36
  • \$\begingroup\$ I corrected that. Sorry for the confusion :\ \$\endgroup\$ – Joe Z. Aug 26 '13 at 19:37
  • 1
    \$\begingroup\$ I suppose I intended it to be something more like a Project Euler puzzle, which often requires the use of a computer to calculate. \$\endgroup\$ – Joe Z. Aug 26 '13 at 23:06
8
\$\begingroup\$

Sum: 11835

[1920, 1792, 1440, 1344, 1280, 1080, 1008, 810, 756, 405]

To verify, a table of the gcd values for each pair:

     | 1920 | 1792 | 1440 | 1344 | 1280 | 1080 | 1008 |  810 |  756
-----+------+------+------+------+------+------+------+------+-----          
 405 |   15 |    1 |   45 |    3 |    5 |  135 |    9 |  405 |   27
 756 |   12 |   28 |   36 |   84 |    4 |  108 |  252 |   54 |
 810 |   30 |    2 |   90 |    6 |   10 |  270 |   18 |
1008 |   48 |  112 |  144 |  336 |   16 |   72 |
1080 |  120 |    8 |  360 |   24 |   40 |
1280 |  640 |  256 |  160 |   64 |
1344 |  192 |  448 |   96 |
1440 |  480 |   32 |
1792 |  128 |

Implementation Details

Update: Massive performance gain c/o @PeterTaylor, as is so often the case.

  • For a set S of length n matching the problem description, each element of S must have at least n-1 divisors (including 1 and the value itself), as each must participate in exactly n-1 unique gcd. Only values with this property are considered.
  • The algorithm for the number of divisors takes the following form:
    If i is a positive integer with the prime factorization p0e0·p1e1…pnen, then the number of divisors of i is equal to (e0+1)·(e1+1)…(en+1). When counting divisors, only primes of the set [2, 3, 5, 7] are used; i.e. only those divisors which are 7-smooth are counted.
  • The search algorithm begins with the largest value of the set, and then searches recursively for each next smaller value. When the current search space has been exhausted, the next larger value with enough divisors is added to the list.
    Note: while this is guaranteed to find the set with the smallest maximum value, it is not necessarily the optimal solution to this problem. A counter-example for n=6:
    [120, 112, 90, 84, 80, 45] (531) vs. [162, 108, 81, 72, 48, 16] (487).
  • The memoization of the gcd function results in a significant performance gain. By the time the third or fourth term is reached, most of the gcds have already been calculated, and need only to be looked up. Additionally, the first iteration is performed outside of the gcd function itself, which increases look-up collision.
  • for ... else is something of a Python oddity. The else block will only be evaluated if the for loop terminates properly, i.e. not by break. I use this for short-circuiting upon duplicate gcds.
  • The length of the set, n, is provided as input via stdin.

Implementation

from time import time

num_vals = input()

def memoize(func):
  class memodict(dict):
    def __call__(self, *args):
      return self[args]
    def __missing__(self, key):
      ret = self[key] = func(*key)
      return ret
  return memodict()

@memoize
def gcd(a, b):
  while b:
    a, b = b, a%b
  return a

def divisors(n):
  divs = 1
  for i in 2,3,5,7:
    exp = 1
    while n%i == 0:
      n /= i
      exp += 1
    divs *= exp
  return divs

def next_val(n):
  while True:
    n += 1
    d = divisors(n)
    if d >= num_vals-1: return n

vals = []

def f(n, end, nums, factors):
  if n<1:
    return nums
  index = n-1
  for i in vals[n-1:end]:
    index += 1
    new_factors = set()
    for j in nums:
      v = gcd(i, j%i)
      if v in factors or v in new_factors:
        break
      new_factors.add(v)
    else:
      ret = f(n-1, index, nums + [i], factors | new_factors)
      if ret: return ret

def g(n):
  global vals
  val = 0
  while len(vals) < n:
    val = next_val(val)
    vals += [val]
  index = n-1
  while True:
    ret = f(n-1, index, [val], set())
    if ret: return ret
    val = next_val(val)
    vals += [val]
    index += 1

t1 = time()
v = g(num_vals)
print sum(v), v
print time() - t1

Solutions and approximate runtime for n ∈ [2, 10]:

3 [2, 1]
0.00s

11 [6, 3, 2]
0.00s

43 [18, 12, 9, 4]
0.00s

149 [54, 36, 27, 24, 8]
0.05s

531 [120, 112, 90, 84, 80, 45]
0.07s

1143 [240, 224, 180, 168, 160, 126, 45]
0.34s

2601 [480, 448, 360, 336, 320, 270, 252, 135]
2.32s

5445 [960, 896, 720, 672, 640, 540, 504, 378, 135]
2m 2.4s

11835 [1920, 1792, 1440, 1344, 1280, 1080, 1008, 810, 756, 405]
36m 6s
|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ The optimal solution up to n=6 uses only the primes 2 and 3. (You find all of them except n=6: {16, 48, 72, 81, 108, 162} scores 487). Your sets for n=7 and n=8 are also optimal, and your sets for n=9 and n=10 are those which I calculated manually for four-prime sets, but which I haven't proven optimal. It's a big jump from 7 to 11, so four-prime sets probably hold the crown for a while more. \$\endgroup\$ – Peter Taylor Aug 29 '13 at 22:42
  • 1
    \$\begingroup\$ If you change the return to yield in g(n), you can have it keep searching for possible solutions past the first one. So far I've tried it up to 8 (can't keep my computer running long enough before going to bed to try the others), but besides the 487 solution for n=6, so far no other "sub-minimal" solutions have popped up. \$\endgroup\$ – Joe Z. Aug 31 '13 at 4:02
9
\$\begingroup\$

Sum: 58025

(ruby)

(0..9).map{|i|(2**i)*(3**(9-i))}

Gives

[19683, 13122, 8748, 5832, 3888, 2592, 1728, 1152, 768, 512]
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Don't think it can get much better than that. \$\endgroup\$ – Joe Z. Aug 26 '13 at 22:17
  • \$\begingroup\$ @JoeZ. In fact, I think this may be provably optimal. \$\endgroup\$ – primo Aug 27 '13 at 9:28
  • \$\begingroup\$ @primo I promise you an upvote if you post a proof of optimality. \$\endgroup\$ – John Dvorak Aug 27 '13 at 12:54
  • 2
    \$\begingroup\$ @JanDvorak happily, I seem to have been mistaken. The pattern breaks as early as n = 4. Compare [27, 18, 12, 8] with [30, 15, 10, 6]. \$\endgroup\$ – primo Aug 28 '13 at 14:55
  • 2
    \$\begingroup\$ FWIW, this is almost optimal for the problem when limited to two primes. It can be improved by special-casing the extrema: (0..n-1).map{|i|(2**(i==n-1?n-2:i))*(3**(i==0?n-2:n-1-i))} \$\endgroup\$ – Peter Taylor Aug 30 '13 at 13:08
1
\$\begingroup\$

Sum: 132251618166478572 (≈1.32×1017)

As a reference last-place answer, I will post the Python code I used to generate the initial set of numbers in the question:

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
          67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137,
          139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197]

numbers = [1] * 10

primefactor = 0

for a in range(10):
    for b in range(a+1, 10):
        numbers[a] *= primes[primefactor]
        numbers[b] *= primes[primefactor]
        primefactor = primefactor + 1

# can't use "sum" because it produces weird values.
numbertotal = 0
for i in numbers:
    numbertotal += i

print numbers, numbertotal

Essentially what this does is take every prime number from 2 to 197 (the first 10C2 = 45 primes), and multiplies them to a unique pair of numbers. That way, any pair of numbers will only have that one prime that was assigned to it as a common factor.

This was done mostly as a proof that there do exist sets of numbers with the property required in the question - as you can see, the value it generated is far from optimal.

Modifying this code to shuffle the primes around randomly before multiplying them results in smaller numbers being created. With multiple trials, I found the following set of numbers:

1268193027813141
2224904691135063
4714631150921614
7005966291691742
9288794198034215
9315429894689005
12630588322608113
13006064536029667
23545741081119313
49251304972436699

whose sum is 132251618166478572, as above.

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.