Working Javascript solution:
function sum(A) { var s = 0; for (var i = 0; i < A.length; ++i) { s += A[i] } return s } function powerSumSet(A) { sums = [] maxes = [] mins = [] for (var i = 0; i < A.length; ++i) { maxes.push(0); mins.push(Infinity) } for (var i = 0; i < (1 << A.length); ++i) { nextSet = getSubSet(i, A) nextSum = sum(nextSet) if (sums.indexOf(nextSum) < 0) { sums.push(nextSum) } maxes[nextSet.length] = Math.max(maxes[nextSet.length], nextSum) mins[nextSet.length] = Math.min(mins[nextSet.length], nextSum) } return [sums, maxes, mins] } function getSubSet(s, set) { a = [] k = 0 while (s != 0) { if ((s & 1) == 1) a.push(set[k]) k += 1 s >>= 1 } return a } function hasProp(s) { data = powerSumSet(s.slice(0, s.length - 1)) sumset = data[0] maxes = data[1] mins = data[2] for (var i = 0; i < maxes.length; ++i) { if (mins[i] <= s[s.length - 1] + maxes[i - 2]) { return false } } for (var i = 0; i < sumset.length; ++i) { if (sumset.indexOf(sumset[i] + s[s.length -1 ]) >= 0) { return false } } return true } // Returns the optimal set of size K, subject to compatibility with rest var minsum = 256 function opt(K, rest) { if (K == 0) return rest var nextElem = (rest.length > 0 ? (rest[rest.length -1] + 1) : 1) var optimum = [] while (minsum > sum(rest) + K * nextElem) { var nextSet = rest.slice(0, rest.length) nextSet.push(nextElem) if (hasProp(nextSet)) { var test = opt(K - 1, nextSet) if (test.length > 0 && sum(test) <= minsum) { minsum = sum(test) optimum = test } } nextElem += 1 } return optimum } console.log(opt(7, []).join(""));Python solution to 60, in order to offset things:
def isPrime(x): if x < 2: return False elif x % 2 == 0: return x == 2 i = 3 while i * i <= x: if x % i == 0: return False i += 1 return True def mag(x): return 10 if x < 10 else 10 * mag(x // 10) def concat(x, y): return x * mag(y) + y def getPrimes(N): return [x for x in range(N+1) if isPrime(x)] def satisfies(p,s): return all(isPrime(concat(e, p)) and isPrime(concat(p, e)) for e in s) primes = getPrimes(10000) def finishSet(s, target, start): if len(s) == 5: test = sum(s) return test if test < target else target else: for i in range(start, len(primes)): p = primes[i] if satisfies(p,s): cset = s[:] cset.append(p) test = finishSet(cset,target,i) if test < target: target = test break return target print(finishSet([],10000000,0))
No comments:
Post a Comment