[seqfan] Re: An optimization problem with prime power factorization of integer x_i

[Rob Pratt]

You can solve it with integer linear programming as follows:

Binary variables:
        is_x[i,v], with the interpretation that is_x[i,v] = 1 if x[i] = v and is_x[i,v] = 0 otherwise
        is_prod[v], with the interpretation that is_prod[v] = 1 if prod {i in 1..k} x[i] = v and is_prod[v] = 0 otherwise

Constraints:
        sum {v} is_x[i,v] = 1 for i in 1..k
        x[i] = sum {v} v * is_x[i,v] for i in 1..k
        x[i] + 1 <= x[i+1] for i in 1..k-1
        sum {v} is_prod[v] = 1
        sum {v} log(v) * is_prod[v] = sum {i, v} log(v) * is_x[i,v]
        sum {v} A064547[v] * is_prod[v] >= k

Objective:
        minimize sum {i, v} log(v) * is_x[i,v]

-----Original Message-----
From: seqfan-bounces at list.seqfan.eu [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of Vladimir Shevelev
Sent: Sunday, April 01, 2012 1:16 PM
To: Sequence Fanatics Discussion list
Subject: [seqfan] Re: An optimization problem with prime power factorization of integer x_i

Thanks Rob, I  meant  A064547(prod{i=1,...,k}x_i)>=k  and carelessly took the "logarithm" which, generally speaking,  gives an error. In case  x = (2,3,4,5,6), the right restriction is not satisfied (A064547(720)=3<5).

Regards,
Vladimir

----- Original Message -----
From: Rob Pratt <Rob.Pratt at sas.com>
Date: Sunday, April 1, 2012 18:25
Subject: [seqfan] Re: An optimization problem with prime power factorization of integer x_i
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>

> Seems to fail first for k = 5, since x = (2,3,4,5,6) satisfies the
> constraints and has a smaller product than (2,3,4,5,7).
>
> -----Original Message-----
> From: seqfan-bounces at list.seqfan.eu [mailto:seqfan-
> bounces at list.seqfan.eu] On Behalf Of Vladimir Shevelev
> Sent: Sunday, April 01, 2012 8:36 AM
> To: seqfan at list.seqfan.eu
> Subject: [seqfan] An optimization problem with prime power
> factorization of integer x_i
>
> Dear SeqFans,
>
>
> Let x_1, x_2,..., x_k be integers with the restrictions:
> 2<=x_1<x_2<...<x_k, sum{i=1,...,k}A064547(x_i)>=k.  Let the goal function be Prod{i=1,...,k}x_i-->min.
> It is easy to see that the unique solution is {(x_1)^*,..., (x_k)^*},
> where {x_i}^* are the first k terms of A050376. If any expert could
> verify how to get formally the solution or its approximation, using
> the methods of integer programming?
>
> Regards,
> Vladimir
>
>
>  Shevelev Vladimir‎
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>

 Shevelev Vladimir‎

_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/