Arithmétique et info

Olympiades mathématiques, énigmes et défis
Sharkk
Membre Naturel
Messages: 23
Enregistré le: 30 Oct 2016, 11:55

Arithmétique et info

par Sharkk » 26 Mai 2017, 20:31

Bonjour,
voila j'ai un petit soucis avec un problème en python qui est le suivant:
Deux entiers n,N > 1 étant donnés, écrire un programme python déterminant le plus petit
entier w(n,N) entre 1 et N nécessitant le plus de puissances n-ièmes dans sa décomposition
de longueur minimale en somme de puissances n-ièmes (non nulles) (ce nombre de
puissances étant noté g(n,N)).
Par exemple, g(2, 6) = 3 car tous les entiers entre 1 et 6 peuvent s’écrire comme somme de
3 carrés, et w(2,6) = 3 car 3 est le premier entier à nécessiter 3 carrés pour être décomposé.
Dresser la liste des w(n,100 000) et g(n, 100 000) pour n entre 2 et 10.
Le principe consiste à générer la liste nombres entre 1 et n qui sont sommes de k puissances
n-ièmes (en les générant, et non en cherchant à décomposer chaque nombre), et de
déterminer le premier k pour lequel cette liste est complète (cela donne g(n,N)). Ensuite, le
plus petit élément manquant dans la liste précédente donne w(n,N).

Voila, cependant je ne vois vraiment pas comment générer les listes de nombres entre 1 et n qui sont sommes de k puissance n-ième.
il faudrait faire une boucle while (tant que ma liste n'a pas n éléments on continue à en rajouter) puis il faudrait en meme temps un compteur k qui augmente pour faire varier les puissances n-ièmes,
Je suis un peu embrouillé,

Merci d'avance ,
bonne soirée



Sharkk
Membre Naturel
Messages: 23
Enregistré le: 30 Oct 2016, 11:55

Re: Arithmétique et info

par Sharkk » 26 Mai 2017, 20:35

Je pense deja qu'il y a une erreur d'énoncé ici
Sharkk a écrit:Le principe consiste à générer la liste nombres entre 1 et n qui sont sommes de k puissances
n-ièmes

Ce serait plus rechercher à générer les nombres de 1 à N

Matt_01
Habitué(e)
Messages: 609
Enregistré le: 30 Avr 2008, 19:25

Re: Arithmétique et info

par Matt_01 » 27 Mai 2017, 03:25

Un algo qui prend en entrée deux ensembles A et B et qui ressort l'ensemble A+B \[|N+1 , + inf[ te permettrait de calculer itérativement l'ensemble des entiers inférieurs à N qui sont somme de k puissance n ème. Bon à priori il y aurait beaucoup de calculs inutiles, mais je ne pense pas qu'on puisse s'en détourner. (On partirait de A = {1^n,2^n, ..., a^n} tel que a^n <= N < (a+1)^n et on calcule A+A \ [|N+1 ; +inf [ etc ...).

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: Arithmétique et info

par fatal_error » 28 Mai 2017, 21:00

bonsoir,

pas sur de comprendre l'énoncé:
Par exemple, g(2, 6) = 3 car tous les entiers entre 1 et 6 peuvent s’écrire comme somme de
3 carrés,

1 peut il s'écrire comme somme de 3 carrés?
idem 2, idem 3.
genre 5 == 2^2 + 1^2 ?

quid de g(3,10)
peut on ecrire 10 = 2^3 + 2*1^3?
la vie est une fête :)

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: Arithmétique et info

par fatal_error » 28 Mai 2017, 21:52

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
la vie est une fête :)

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 3 invités

cron

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite