Build a drug testing scheduler

Question

In this problem on Puzzling.SE, I ask a question about determining the amounts of drug to use in a clinical test to minimize total drug usage and fulfill the requirements of the testing procedure.

The problem is as follows, for those of you who currently don't have access to the private beta:

A medical researcher is trying to test the effect of a certain drug on mice. He is supposed to collect data for all doses from 1 to 2N units, but only has the data collection resources for N tests. He has decided to only test dose amounts that are not multiples or factors of each other (for example, if he decided to use a dose of 15 units for a specific test, that would preclude tests for 1, 3, 5, 30, 45, etc. units). Moreover, because the drug is relatively expensive, he wants to use as little of the drug as he can manage to run these tests.

How can he arrange the dosage amounts so that he ends up using all N test packages, and the total units of dosage used in the tests are as low as possible?

The original problem states N = 25. Your task is to build a program than can answer this question for any number of tests up to N = 2500.

Your program will take a number N from 1 to 2500 as input, and return a set of N integers between 1 and 2N inclusive such that none of the N numbers are multiples of each other, each number from 1 to 2N is a factor or multiple of at least one of the numbers in the set, and the sum of all the numbers in the set is as low as you can manage.

Your program must return a valid result for each value of N to be valid.

Your program will be scored by the sum of all the returned numbers for each scenario from N = 1 to N = 2500. In the event of a tie, the shorter solution will win.

Answer 1

Javascript 5,955,958,211

I'm not sure if it is the optimal solution.
I used a brute-force method.

function f(n) {
  var o=[];
  for(var i=n;i--;) o.push(2*n-i); //init array from n+1 to 2*n

  for(i=n;i>0;i--) { //bruteforce on number from n to 1
    var index=0;
    var nbFactor=0;
    for(j=0;j<n;j++) {
      if((o[j]/i)%1==0) {
        index=j;
        nbFactor++;
      }
    }
    if(nbFactor==1) { //if there is only 1 factor, replace it by the new number
      o[index]=i;
    }
  }
  return o.sort(function(a,b){return a-b;});
}

Golfed (130) :

function f(n){o=[];for(i=n;i++<2*n;)o.push(i);for(i=n;i;i--){for(d=c=j=0;j<n;j++)if((o[j]/i)%1==0)d=j,c++;if(c==1)o[d]=i}return o}

Here is the result found by my algorithm for 25 :

[8, 12, 14, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 29, 30, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49]

Little piece of code to compute the score (takes approx. 200 seconds on Chrome) :

var result=0;
var t = Date.now();
for(var j=1;j<2501;j++) {
  result += f(j).reduce(function(r,e){return r+e;});
}
console.log("Score : " + result + "\nCompute time : " + ((Date.now()-t)/1000) + " seconds");

Answer 2

JavaScript - 5,955,958,211

A tiny bit of pre-processing to generate the factors of 1 ... 5000

var factors = [];

for( var i = 1; i <= 5000; i++ )
{
    factors[i] = [];
    for( var j = 1; j <= i; j++ )
    {
        if ( i % j == 0 )
            factors[i].push(j);
    }
}

The main function:

function find_min_doses( N, DEBUG )
{
    var output = [];
    var factorCount = [];
    for( var i = 1; i <= 2*N; i++ )
    {
        factorCount[i]=0;
        for( var j = 0; j < factors[i].length; j++ )
        {
            factorCount[factors[i][j]]++;
        }
    }
    var changed = false;
    do
    {
        if ( DEBUG && changed )
        {
            console.log( output.sort( function(a,b){ return a-b; } ).toString()
                         + " = "
                         + output.reduce( function(p,c){ return p+c; } )
                       );
        }
        changed = false;

        var count = 0;
        for( var i = 1; i <= 2*N; i++ )
        {
            if ( factorCount[i] == 1 )
            {
                if ( count < N )
                {
                    output[count++] = i;
                }
                else
                {
                    for( var j = 0; j < factors[i].length; j++ )
                        factorCount[factors[i][j]]--;
                }
            }
        }

        for( var i = 0; i < N; i++ )
        {
            var o = output[i];
            var f = factors[o];
            for( var j = 0; j < f.length; j++ )
            {
                var v = f[j];
                if ( factorCount[v] == 2 )
                {
                    output[i]=v;
                    for( var k = 0; k < f.length; k++ )
                    {
                        factorCount[f[k]]--;
                    }
                    changed = true;
                    break;
                }
            }
        }
    }
    while( changed );

    return output.reduce( function(p,c){ return p+c; } );
}

A test harness:

var total = 0;
var time = new Date();
for ( var i = 1; i <= 2500; i++ )
{
    total += find_min_doses( i );
}
console.log( "Score: " + total + "\nTime: " + ((new Date()-time)/1000) + " seconds." );

Output (Chrome)

Score: 5955958211
Time: 1.438 seconds.

Output (FireFox)

Score: 5955958211
Time: 66.107 seconds.

Answer 3

Prolog - 5,955,958,211 (?)

Its far too slow to run all 2500 test cases but it will find the optimal solution(s) in every case.

Golfed - 370 Characters

a([]).
a([_]).
a([H,N|T]):-H<N,a([N|T]).
s([],0).
s([H|T],S):-s(T,X),S is X+H.
e(_,[]).
e(V,[H|T]):-H mod V>0,e(V,T).
d([]).
d([H|T]):-e(H,T),d(T).
b(N,L):-T is 2*N,between(1,T,L).
l([H|T],M):-l(T,H,M).
l([],M,M).
l([H|T],C,M):-X is min(H,C),l(T,X,M).
m(R,M):-findall(T,s(R,T),L),l(L,M).
f(N):-length(R,N),maplist(b(N),R),a(R),d(R),m(R,M),s(R,M),write(R),nl,write(M),nl.

Ungolfed

ensure_sorted([]).                    % Ensures that the values of
ensure_sorted([_]).                   % a list are in ascending order.
ensure_sorted([Head,Next|Tail]):-
    Head<Next,
    ensure_sorted([Next|Tail]).

sum([Head|Tail],Total):-              % Calculate the sum of
    sum(Tail,Temp),                   % a list
    Total is Temp+Head.

ensure_not_divisor(_,[]).             % Ensure that the value
ensure_not_divisor(Val,[Head|Tail]):- % is not a divisor of 
    Head mod Val > 0,                 % any numbers of the list.
    ensure_not_divisor(Val,Tail).

ensure_no_divisors([]).
ensure_no_divisors([Head|Tail]):-     % For each value of the list
    ensure_not_divisor(Head,Tail),    % ensure that it is not a divisor
    ensure_no_divisors(Tail).         % of the succeeding values.

btwn(N,List):-                        % Restrict the values to be
    Temp is 2*N,                      % between 1 and 2N
    between(1,Temp,List).

list_min([Head|Tail],Min):-           % Find the minimum value of
    list_min(Tail,Head,Min).          % the list.
list_min([],Min,Min).
list_min([Head|Tail],Current_Min,Min):-
    Temp is min(Head,Current_Min),
    list_min(Tail,Temp,Min).

min_sum(R,Min):-                      % For all the valid answers
    findall(Temp,sum(R,Temp),List),   % find the minimum sum.
    list_min(List,Min).

func(N):-
    length(R,N),                      % A list of N unknown values
    maplist(btwn(N),R),               % Restrict each value to integers 1..2N
    ensure_sorted(R),                 % Ensure the list is sorted.
    ensure_no_divisors(R),            % Ensure that each value is not a divisor of a higher value.
    min_sum(R,Min),                   % Find the minimum sum of all answers
    sum(R,Min),                       % Restrict the answer to have the minimum sum.
    write(R),nl,                      % Output the doses (and a newline).
    write(Min),nl.                    % Output the score (and a newline).

Answer 4

Python – 7,818,751,250

As a last-place reference answer, consider the following:

def f(n):
    return range(n+1, n*2+1)

For any N, choosing unit sizes from N+1 to 2N will ensure that no number is a multiple or factor of any other, simply by virtue of the fact that they're too close together. The smallest nontrivial multiple of N+1 is 2N+2, and the largest nontrivial factor of 2N is N, and no nontrivial multiple or factor of any number will fall between those two.

However, there will always be solutions that do much better than this – simply replacing 2N-2 with N-1 already will always yield a better solution.