[exercice] Nombre hexagonal

Inspiré de l'exercice Euler 44

16 juillet 2010 à 5:50:01

Bonjour

Un nombre hexagonal est de la forme

où n est un entier à partir de 1.

Voici un code Python qui donne la liste des 10 premiers nombres hexagonaux :

>>> for n in range(1,11):print n*(2*n-1),
... 
1 6 15 28 45 66 91 120 153 190
>>>

Il est possible de trouver deux nombres hexagonaux dont la somme et la différence soient encore hexagonaux :

par exemple, <math>\(H_{1876}\)</math> et <math>\(H_{1593}\)</math> puisque je vous laisse vérifier que

<math>\(H_{1876}+H_{1593}=H_{2461}\)</math> et <math>\(H_{1876}-H_{1593}=H_{991}\)</math>.

Votre mission : Ecrire un programme Python qui permette de trouver un autre couple d'entiers hexagonaux dont la somme et la différence soient encore hexagonaux.

Vhann

16 juillet 2010 à 6:44:05

Citation : candide

Un nombre heptagonal est de la forme
<math>\(H_n=n(3n-5)/2\)</math>

où n est un entier à partir de 2.

Parle-t-on des mêmes nombres heptagonaux ici: http://en.wikipedia.org/wiki/Heptagonal_number ?

L'équation est légèrement différente (de même que les listes des premiers nombres de la suite)

(Wikipedia donne <math>\(\frac{5n^2 - 3n}{2} = \frac{n(5n - 3)}{2}\)</math>)

Cordialement,
Vhann

candide

16 juillet 2010 à 12:08:02

Citation : Vhann

Parle-t-on des mêmes nombres heptagonaux ici: http://en.wikipedia.org/wiki/Heptagonal_number ?

L'équation est légèrement différente (de même que les listes des premiers nombres de la suite)

En effet j'ai inversé les coefficients et j'ai l'impression que cela ne marche pas pour des nombres heptagonaux "vrais". Par contre ça marche pour des nombres hexagonaux. Je corrige l'énoncé en conséquence.

Merci d'avoir vérifié.

iNaKoll

16 juillet 2010 à 16:35:33

TRES Drôle ce petit exercice!

Bon, je dois vraiment être mauvais sur ce coup, j'ai eu un peu de mal.
En fait, je me suis rapidement rendu compte que l'algorithme naïf de recherche exhaustive était lent comme pas permis. J'ai d'abord essayé quelque chose comme ça :

start = clock()
hexa = [n*(2*n-1) for n in range(2,2600)]
maxi = max(hexa)
print [ [x,y] for x in hexa for y in hexa[:hexa.index(x)] if x+y < maxi and x+y in hexa and x-y in hexa ]
stop = clock()
print 'Execution time :', stop-start, 's'

[[7036876, 5073705]]
Execution time : 299.618980374 s

Il s'agit bien de <math>\(H_{1876}\)</math> et de <math>\(H_{1593}\)</math> (ouf).

L'algorithme m'a tout l'air d'être de complexité cubique (si ce n'est plus). Autant dire que j'ai assez vite oublié ce code! Il m'aurait fallut une éternité pour déterminer le couple d'hexagonaux suivants.
Je ne m'en suis pas "sorti" sans faire un petit peu de maths avant d'attaquer le code.

On cherche 4 nombres entiers x, y, w et z tels que :

<math>\(H_{x}+H_{y}=H_{z}\)</math>
et
<math>\(H_{x}-H_{y}=H_{w}\)</math>
On pose :
<math>\(s=H_{x}+H_{y}\)</math>
<math>\(d=H_{x}-H_{y}\)</math>
On cherche x et y tels que la somme s et la différence d vérifient :
<math>\(2z^2-z-s=0\)</math>
<math>\(2w^2-w-d=0\)</math>
d'où :
<math>\(z=\frac{1}{4}+\frac{\sqrt{1+8s}}{4}\)</math>

<math>\(w=\frac{1}{4}+\frac{\sqrt{1+8d}}{4}\)</math>
On comprend alors que pour que z et w existent, la somme s et la différence d doivent vérifier :
<math>\(\sqrt{1+8s}\)</math> est entier
<math>\(\sqrt{1+8d}\)</math> est entier

Finalement j'ai pu retourner au code python :

from time import clock
from math import sqrt
from math import modf

def hexaf(n):
    return n*(2*n-1)

start = clock()
lim = 10000
epsilon = 0.01
hexa = [hexaf(n) for n in xrange(2,lim)]
candidats = [ [x,y] for x in xrange(2,lim) for y in xrange(2,x) if (modf(sqrt(1+8*(hexaf(x)+hexaf(y))))[0]  < epsilon) and (modf(sqrt(1+8*(hexaf(x)-hexaf(y))))[0]  < epsilon) ]
valides = [z for z in candidats if hexaf(z[0])+hexaf(z[1]) in hexa and hexaf(z[0])-hexaf(z[1]) in hexa]
print valides
stop = clock()
print 'Execution time :', stop-start, 's'

Edit: Je précise que le z dans le code n'a rien à voir avec le z de la petite démonstration de math au dessus.

[[1876, 1593], [3979, 3875], [8444, 4263]]
Execution time : 146.530580414 s

(Ouf!)

Vu que c'est un des problèmes du projet Euler, j'imagine qu'il doit y avoir une méthode bien plus rapide. Je suis pas trop performant sur ce coup. :honte:

Edit: J'ai légèrement modifié mon code ce qui lui permet d'être 2 fois plus rapide.. :-°

Inkamath on GitHub - Interpréteur d'expressions mathématiques. Reprise du développement en cours.

candide

16 juillet 2010 à 17:03:00

Citation : iNaKoll

Je ne m'en suis pas "sorti" sans faire un petit peu de maths avant d'attaquer le code.

J'ai pas du tout fait comme ça mais le code que j'obtiens reste assez long à donner le résultat (une quinzaine de secondes).

GurneyH

17 juillet 2010 à 12:23:02

Moins matheux qu'iNnaKoll.

Je précalcule les nombre hexagonaux, sous une limite prise à la louche. :-°

import time

def hexagonal(n) :
        return n * (2 * n - 1)
    
def findCouple(limit):
    hh = [ hexagonal(n) for n in range(limit * 2) ]
    res, h = [], dict.fromkeys( hh, 1 )
    
    for i in xrange(1, limit) :
        for j in xrange(i + 1, limit) :
            if h.has_key(hh[i] + hh[j]) and h.has_key(hh[j] - hh[i]):
                res.append((i, j))
    return res

             
start = time.clock()
print findCouple(5000)
print time.clock() - start

[(1593, 1876), (3875, 3979)]
10.7992211301

edit :coquille dans le code :-°

3 coquilles
normalement c'est bon.

Zeste de Savoir, le site qui en a dans le citron !

candide

17 juillet 2010 à 12:45:01

Il reste des coquilles (h au lieu de p). Sinon, ton code marche très bien et est moins brute force que le mien.

GurneyH

17 juillet 2010 à 12:53:24

Citation : candide

Il reste des coquilles (h au lieu de p).

j'ai édité de nouveau, donc c'est bien hh pour la liste, et h pour le dictionnaire.

Ca m'apprendra à modifier mes variables au dernier moment. :-°

Zeste de Savoir, le site qui en a dans le citron !

yoch

9 mai 2011 à 21:31:18

Citation : candide

Votre mission : Ecrire un programme Python qui permette de trouver un autre couple d'entiers hexagonaux dont la somme et la différence soient encore hexagonaux.

Bonjour,

Je me permets ce petit deterrage pour proposer un algo que j'ai conçu pour l'exo 44 du project euler. Pour commencer, une remarque, l'exo du project Euler comprend une contraite en plus (sur laquelle mon algo est en défaut) :

Citation : Project Euler - 44

Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference is pentagonal and D = |Pk − Pj| is minimised;

Pour trouver rapidement des couples d'entiers, on procède comme suit :
- générer les termes de la fonctions un après l'autre
- a partir du troisième terme, on recherche dans l'ensemble des termes précédents d’éventuelles paires dont la somme vaut le présent terme (voir algo ci-après)
- pour chaque paire trouvée, on teste si la différence est aussi un terme (existe dans l'ensemble des termes générés)

Voici l'équivalent en C d'un algo pour trouver très rapidement les paires de valeurs d'un ensemble S (valeurs uniques ordonnées) ayant pour somme n:

#include <stdio.h>

#define NB  36
int main()
{
    unsigned ensemble[] = { 4,9,11,15,17,21,24,25,29,32,45,46,49,52,53,55,61 };
    unsigned sz = sizeof ensemble / sizeof *ensemble;

    unsigned start=0, stop=sz-1;
    while (start != stop)
    {
        unsigned sum = ensemble[start] + ensemble[stop];
        if ( sum < NB )
            start++;
        else if ( sum > NB )
            stop--;
        else
        {
            printf("%u + %u = %u\n", ensemble[start], ensemble[stop], NB);
            start++;  //ou stop--;
        }
    }

    return 0;
}

C'est tout !

EDIT :
Il faut préciser que cette technique ne garantit pas de trouver toutes les paires de nombres hexagonaux dans l'ensemble obtenu.

Et voici un code python inspiré de celui de GurneyH pour l'exo (je ne suis pas très à l'aise avec python) :

def findCouple (limit):
    hexagonal = lambda n: n * (2 * n - 1)
    liste = list()
    ensemble = set()

    for i in range(1,limit):
        n = hexagonal(i)
        liste.append(n)
        ensemble.add(n)

        if i > 2:
            start = 0
            stop = i-2
            while start < stop:
                sum = liste[start]+liste[stop]
                if (sum < n):
                    start+=1
                elif (sum > n):
                    stop-=1
                else:
                    diff = liste[stop]-liste[start]
                    if diff in ensemble:
                        print("H[", start, "] + H[", stop, "] = H[", i, "] = ", n)
                    start+=1
                    stop-=1

findCouple (6000)

Les perfs sont plutôt décevantes (6.7s contre 0.35s pour un code ressemblant en C++)

Fort en pommes

10 mai 2011 à 11:26:11

Salut,

Est-ce un exercice niveau débutant, intermédiaire ou avancé?

yoch

10 mai 2011 à 14:30:20

Citation : Fort en pommes

Salut,

Est-ce un exercice niveau débutant, intermédiaire ou avancé?

Bonjour,

Perso, je trouve que cet exo ne requiert pas précisément d'avoir un bon niveau en python, mais plutôt un niveau intermédiaire en algorithmique.