Dal sito Project Euler, che propone un numero elevato di challenge di programmazione, di varia difficoltà (da risolvere con il linguaggio di programmazione che si preferisce), ho trovato un problema interessante, il numero 45. Il problema definisce:
- T[ ] = numeri triangolari (triangle): generati da N(N+1)/2
- P[ ] = numeri pentagonali (pentagonal): generati da N(3N-1)/2
- H[ ] = numeri esagonali (hexagonal): generati da N(N+1)/2
Un esempio è il numero 285, abbiamo T(285)=P(165)=H(143)=40755.
La consegna chiede di trovare il prossimo numero (quindi, la terna) che soddisfa la condizione T(x1)=P(x2)=H(x3).
Premessa: in generale Project Euler ha la filosofia <<One Minute Rule>> ovvero far girare il codice in un tempo inferiore al minuto (altrimenti il codice va sistemato dal punto di vista dell'efficienza): certo dipende dalla macchina specifica e dal linguaggio di programmazione scelto, questa comunque è una linea generale.
Più in generale, dal sito ufficiale Project Euler viene definito in questo modo:
Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.
Ho scelto di risolvere il problema col linguaggio C, potendo memorizzare le variabili all'interno dei registri della CPU anziché nella RAM (su questo magari faremo un approfondimento a parte) in modo da avere la massima efficienza possibile. Riporto il codice e in seguito i risultati.
/*Project Euler n.45*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
int main(){
register long int i;
register float xp,xh;
i=286;
clock_t start = clock();
while(1){
xp=(1+pow((1+12*i*(i+1)),0.5))/6.0;
if(((int)(xp)==xp)&&(0.5*i*(i+1)==0.5*xp*(3*xp-1))){
xh=(1+pow((1+4*i*(i+1)),0.5))/4.0;
if((int)(xh)==xh){break;}
}
i++;
}
clock_t end = clock();
printf("xT=%ld\nxP=%.0f\nxH=%.0f\n",i,xp,xh);
printf("%f s\n",(float)(end-start)/CLOCKS_PER_SEC);
return 0;
}
Risultati:
il prossimo numero, successivo a 285 è piuttosto grande, 55385, quindi:
- T(55385)
- P(31977)
- H(27693)
- infatti: T(55385) = P(31977) = H(27693) = 1.533.776.805
- tempo di esecuzione del codice: 0,00312s (direi buono, se il limite era un minuto! 😅 )
Conoscevate Project Euler? L'idea mi sembra carina. Cosa ne pensate?
