Détection des nombres de sommes de puissances consécutives

Un entier positif est appelé « nombre de somme de puissances » s'il peut s'écrire comme la somme de puissances d'entiers naturels consécutifs commençant à 1, avec un exposant non nul. Par exemple, 2025 est un tel nombre car 2025 = 1³ + 2³ + 3³ + 4³ + 5³ + 6³ + 7³ + 8³ + 9³.

Il est possible qu'un même nombre admette plusieurs représentations. Par exemple, 91 peut s'écrire :

91 = 1¹ + 2¹ + 3¹ + 4¹ + 5¹ + 6¹ + 7¹ + 8¹ + 9¹ + 10¹ + 11¹ + 12¹ + 13¹
91 = 1² + 2² + 3² + 4² + 5² + 6²

Dans ce cas, il faut privilégier la représentation dont l'exposant est le plus élevé.

Format d'entrée

Un entier positif n (2 < n < 2³¹) sur une seule ligne.

Format de sortie

Si n est un nombre de somme de puissances, affficher la représentation avec le plus grand exposant sous la forme :

1^k+2^k+...+m^k

Si aucune représentation n'existe, afficher Impossible for n. où n est la valeur d'entrée.

Exemples

Entrée 1 :

Sortie 1 :

1^2+2^2+3^2+4^2+5^2+6^2

Entrée 2 :

2147483647

Sortie 2 :

Impossible for 2147483647.

Approche algorithmique

La stratégie consiste à parcourir les exposants possibles du plus grand vers le plus petit. Pour chaque exposant e, on accumule les termes 1ᵉ + 2ᵉ + 3ᵉ + ... jusqu'à atteindre ou dépasser n. Dès qu'une correspondance est trouvée, c'est nécessairement celle avec l'exposant maximal puisqu'on descend depuis les valeurs élevées.

Le calcul de chaque puissance se fait par multiplications successives plutôt que par pow(), afin d'éviter les problèmes de précision et de contrôler les débordements.

#include <iostream>
#include <sstream>

// Calcule base^exposant avec protection contre le débordement
long long puissanceSecurisee(int base, int exposant, long long limite) {
    long long res = 1;
    for (int i = 0; i < exposant; ++i) {
        res *= base;
        if (res > limite) return limite + 1;
    }
    return res;
}

// Tente de trouver m tel que 1^exp + 2^exp + ... + m^exp = cible
int trouverLongueur(int cible, int exp) {
    long long sommeCumulee = 0;
    int compteur = 1;
    while (true) {
        long long terme = puissanceSecurisee(compteur, exp, cible);
        sommeCumulee += terme;
        if (sommeCumulee == cible) return compteur;
        if (sommeCumulee > cible) return 0;
        compteur++;
    }
}

std::string resoudre(int nombre) {
    int meilleurExp = 0;
    int longueurOpt = 0;
    
    // Parcourir les exposants du plus grand au plus petit
    for (int e = 30; e >= 1; --e) {
        int m = trouverLongueur(nombre, e);
        if (m > 0) {
            meilleurExp = e;
            longueurOpt = m;
            break;
        }
    }
    
    if (meilleurExp == 0) {
        return "Impossible for " + std::to_string(nombre) + ".";
    }
    
    std::ostringstream flux;
    for (int i = 1; i <= longueurOpt; ++i) {
        if (i > 1) flux << "+";
        flux << i << "^" << meilleurExp;
    }
    return flux.str();
}

int main() {
    int nombre;
    std::cin >> nombre;
    std::string resultat = resoudre(nombre);
    std::cout << resultat << std::endl;
    return 0;
}

La borne supérieure de l'exposant est fixée à 30 car au-delà, les valeurs dépassent rapidement 2³¹. Le parcuors descendant garantit que la première solution trouvée correspond à l'exposant maximal, éliminant le besoin de comparer plusieurs candidats.

Étiquettes: C++ brute-force arithmétique somme-de-puissances Algorithme

Publié le 5 juillet à 03h21

L'Atelier Monstre

Détection des nombres de sommes de puissances consécutives