Cody

Problem 42355. Minimum Set (A+A)U(A*A) OEIS A263996

Created by Richard Zapor in Community

This Challenge is to find an integer vector A that creates the minimum set size for (A+A) U (A*A) for a given vector length, OEIS A263996. The length, best value, Prime_max, and Value_max will be provided.

The OEIS A263996 gives the minimum set sizes thru length 50. Length 7 has best value 26 with Prime_max 5 and Value_max 8. A=[1 2 3 4 5 6 8] yields [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 20 24 25 30 32 36 40 48 64]. The Al Zimmermann Sums Contest Final Report extends A263996 for lengths 40:40:1000 with complete vector solutions. The contest winner, Rokicki, noted his method used P-smooth sets, hill climbing, and random swaps. The contest was a little tougher with only L given.

Example Input/Output: L=9;Best=36;pmax=5;vmax=12; v = SP(L,Best,pmax,vmax); Yields v=[1 2 3 4 5 6 8 10 12]

Theory/Hints: The V superset is found using psmooth(pmax,vmax) . One observation is that for every v element the set v contains prod of all v element factor permutations. The time eater will be score evaluation. Residual evaluation suggested. A history screen, prior to score evaluation, of prior processed vectors is essential. A quick history pre-screen is vector sum. Replace testing of only values that are not factors of other numbers (eg 2,3 no replace) enables a reasonable time rolling score solution without random for the small test case values.

Solution Stats

100.0% Correct | 0.0% Incorrect
Last solution submitted on Aug 30, 2017