Geek asks and answers

Finding maximal subsets

For a given n, we find a subset S {1,2, ..., n} such that

  • all elements of S are coprime.
  • sum of elements S as large as possible

The brute force search takes too long and I cannot find the template. I know that I can just take all primes from 1 to n, but this is probably not the right answer. Thank.

+3
source share
5 answers

I would see this as a dynamic programming problem . Let me go through 20 minutes. First, take primes in reverse order.

19, 17, 13, 11, 7, 5, 3, 2

, . , , (, , ). size: {set} = (total, next_number). ( , .) . ( .)

, , , .

Step 0
0: {} => (1, 1)

Step 1
1: {19} => (20, 19)

Step 2
2: {19, 17} => (37, 17)

Step 3
3: {19, 17, 13} => (50, 13)

Step 4
4: {19, 17, 13, 11} => (61, 11)

Step 5
5: {19, 17, 13, 11, 7} => (68, 7)

6: {19, 17, 13, 11, 7, 2} => (75, 14)

Step 6
6: {19, 17, 13, 11, 7, 5} => (73, 5)
   {19, 17, 13, 11, 7, 2} => (75, 14)

7: {19, 17, 13, 11, 7, 5, 2} => (88, 20)
   {19, 17, 13, 11, 7, 5, 3} => (83, 15)

Step 7
7: {19, 17, 13, 11, 7, 5, 2} => (88, 20)
   {19, 17, 13, 11, 7, 5, 3} => (83, 15)

8: {19, 17, 13, 11, 7, 5, 3, 2} => (91, 18)

Step 8
8: {19, 17, 13, 11, 7, 5, 3, 2} => (99, 16)

, 16, 15, 7, 11, 13, 17, 19, 1, , 1, 7, 11, 13, 15, 16, 17, 19.

( , , . !)

+4

, , , . , , n = 30.

1, 16, 27, 25, 7, 11, 13, 17, 19, 23, 29

, . , - , n/2: 17, 19, 23, 29 (?). , 3 ^ 3 5 ^ 2 30, , , (?).

2 ^ 4, 7, 11 13? 2 7, 11 13. :

2 * 13 = 26 replaces 16 + 13 = 29 BAD
2 * 11 = 22 replaces 16 + 11 = 27 BAD
2^2 * 7 = 28 replaces 16 + 7 = 23 GOOD

, , ( ):

1, 11, 13, 17, 19, 23, 25, 27, 28, 29

, , .

!

+3

.

N = {1, 2, 3,..., n}. p1 < p2 < p3 <... < pk - N. Ti - N, pi, , pi. Ti.

. S = {1}. , pi , S. , Ti. xi Ti , S, S. i.

k + 1, S. , S.

.

n = 30. - 2, 3, 5, 7, 11, 13, 17, 19, 23 29.

T1 = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30}
T2 = {3, 9, 15, 21, 27}
T3 = {5, 25}
T4 = {7}
T5 = {11}
T6 = {13}
T7 = {17}
T8 = {19}
T9 = {23}
T10 = {29}

, 15 * 5 * 2 = 150 .

n = 100.

1 17 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 88 89 91 95 97 99
Sum = 1374


1 17 23 29 31 37 41 43 47 53 59 61 67 71 73 79 81 83 88 89 91 95 97
Sum = 1356

2 n = 150. 9 n = 200.

+1

, , NP-Complete.

( 1 n, ).

, , .

.

0

Prolog, . Toshiba SWI-Prolog N < 90. N = 100-150 :

  N         Sum       Time(s)
-----    ---------    -------
 100        1356         1.9
 110        1778         2.4
 120        1962         4.2
 130        2273        11.8
 140        2692        16.3
 150        2841        30.5

The timings reflect an implementation that starts from zero for each value of N. Most of the calculation for N + 1 can be skipped if the result for N is previously known, so if it is necessary to calculate the range of N values, it would be advisable to use this.

The following is the Prolog source code.

/*
   Check if two positive integers are coprime
   recursively via Euclid division algorithm
*/
coprime(0,Z) :- !, Z = 1.
coprime(A,B) :-
    C is B mod A,
    coprime(C,A).

/*
   Find the sublist of first argument that are
   integers coprime to the second argument
*/
listCoprime([ ],_,[ ]).
listCoprime([H|T],X,L) :-
    (   coprime(H,X)
     -> L = [H|M]
     ;  L = M
    ),
    listCoprime(T,X,M).

/*
   Find the sublist of first argument of coprime
   integers having the maximum possible sum
*/
sublistCoprimeMaxSum([ ],S,[ ],S).
sublistCoprimeMaxSum([H|T],A,L,S) :-
    listCoprime(T,H,R),
    B is A+H,
    sublistCoprimeMaxSum(R,B,U,Z),
    (   T = R
     -> ( L = [H|U], S = Z )
     ;  ( sublistCoprimeMaxSum(T,A,V,W),
          (   W < Z
           -> ( L = [H|U], S = Z )
           ;  ( L = V, S = W )
          )
        )
    ).

/*    Test utility to generate list N,..,1   */
list1toN(1,[1]).
list1toN(N,[N|L]) :-
    N > 1,
    M is N-1,
    list1toN(M,L).

/*    Test calling sublistCoprimeMaxSum/4   */
testCoprimeMaxSum(N,CoList,Sum) :-
    list1toN(N,L),
    sublistCoprimeMaxSum(L,0,CoList,Sum).
0
source

More articles:


All Articles