Je me réponds partiellement:
si on a une decomp genre 1^2+2^2
on s'en fout d'avoir 2*1^2+2^2 (puisque de toute façon on garderait 1^2+2^2 vu qu'on veut le plus petit entier)
donc le pb se simplifie en
a = <a_0,...a_k> avec a_i variable booléenne
et
b = <b_0,...b_k> avec b_i = i^n, k le plus grand tq b_k < N
et on cherche a qui contient le max de 1 sous condition a.b <= N (a.b produit scalaire)
si on nomme a_s ce a, alors
on obtient w(n,N) = nbOnes(a_s) et g(n,N) = a_s.b
Comme je suis un peu naïf, voici la version brute
- Code: Tout sélectionner
#!/usr/bin/node
/*
let v=<a_0,...,a_n> with a_i==0 or 1
let b=<0^n,1^n,2^n...>
let s = v.map((x,i)=>b[i]).sum() for every possible v
let m = { Integer => shortest decomposition found}
1. for a given s, if s in m and number of 1 in v < m[s], then m[s] = number of 1 in v
2. get the class of integers needing the most number of 1 in v from m as ints
3. take the smallest int from ints
*/
function decomp(n,N){
var a = 1;
var b = [];
var i = 0;
//build b
while(true){
var b_i = Math.pow(i,n);
if(b_i < N){
b.push(b_i);
i++;
}else{
break;
}
}
var m = {};
//1. iterate all possible s
for(var i = 0; i<Math.pow(2, b.length)-1; ++i){
//get binary representation of i (this is a)
var s = 0;
var a = i.toString(2).split('').reverse();
var numberOfOnes = 0;
//console.log('iterating with a=',a);
a.forEach((x,idx)=>{
if(x=='1'){
numberOfOnes++;
s += b[idx];
}
})
if(s > N){
continue;//not a valid candidate
}
if(!m.hasOwnProperty(s) || numberOfOnes < m[s]){
//console.log('storing ', s, numberOfOnes)
m[s] = numberOfOnes;
}
}
//console.log('current m : ', m)
//2. sort m by descending number of ones
var r = Object.keys(m).sort((a,b)=>{
var onesA = m[a];
var onesB = m[b];
if(onesB>onesA){//onesA first result of the sort if bigger
return 1;
}
if(onesB<onesA){
return -1;
}
return a-b;//3. if onesA==onesB, a first result of the sort if smallest
});
//console.log('sortedM', r)
var gnN = m[r[0]];
var wnN = r[0];
return [gnN, wnN];
}
for(var n = 4; n<10; ++n){
var [g,w] = decomp(n,100000);
console.log('g('+n+',100000):',g,'w('+n+',100000):',w);
}
(ca termine pas pour 2 et 3...)
output:
- Code: Tout sélectionner
g(4,100000): 13 w(4,100000): 89271
g(5,100000): 8 w(5,100000): 61776
g(6,100000): 6 w(6,100000): 67171
g(7,100000): 5 w(7,100000): 96825
g(8,100000): 4 w(8,100000): 72354
g(9,100000): 3 w(9,100000): 20196
Si on est un peu plus smart (parce que décomposer en puissance de 2...ben ca donne un gros b, donc bcp de permutations, donc on attend une éternité),
on peut optimiser la recherche du nombre de 1...
on ajoute autant de 1 que faire se peut dans a(idem tant que a.b <=N) (en partant du début)
au lieu de prendre moroniquement toutes les combinaisons possible de 1 sur le vecteur a
- Code: Tout sélectionner
#!/usr/bin/node
function decomp(n,N){
var a = 1;
var b = [];
var i = 0;
//build b
while(true){
var b_i = Math.pow(i,n);
if(b_i < N){
b.push(b_i);
i++;
}else{
break;
}
}
var s = 0;
var wnN = s;
var gnN = 0;
for(var i = 0; i<b.length; ++i){
s+=b[i];
if(s > N){
break;//adding further 1s wont make us fall below N...
}
wnN = s;
var gnN = i+1;
}
return [gnN,wnN]
}
for(var n = 2; n<10; ++n){
var [g,w] = decomp(n,100000);
console.log('g('+n+',100000):',g,'w('+n+',100000):',w);
}
- Code: Tout sélectionner
g(2,100000): 67 w(2,100000): 98021
g(3,100000): 25 w(3,100000): 90000
g(4,100000): 14 w(4,100000): 89271
g(5,100000): 9 w(5,100000): 61776
g(6,100000): 7 w(6,100000): 67171
g(7,100000): 6 w(7,100000): 96825
g(8,100000): 5 w(8,100000): 72354
g(9,100000): 4 w(9,100000): 20196