[seqfan] Re: An optimization problem with prime power factorization of integer x_i
Rob Pratt
Rob.Pratt at sas.com
Sun Apr 1 23:55:49 CEST 2012
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/
More information about the SeqFan
mailing list