Discussion :

[disedorgue]

Bonjour,

D'après un théorème, démontré par Gauss, tout nombre entier N peut-être représenté par au plus la somme de 3 nombres triangulaire.
Existe-t-il une formule ou une méthode qui permet de trouver ces fameux nombres triangulaire qui une fois additionnés donnent l'entier N ?

Merci par avance pour vos réponses.

[tbc92]

Voici un petit bout de code. C'est en langage Windev, mais je pense que c'est facile à interpréter et à traduire en un autre langage de votre choix :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
t est un tableau dynamique
i, cible, n1 est un entier
 
cible = 1234
i = Saisie("Nbre à atteindre", cible)
SI i <> 1 ALORS 
	Erreur ( " Abandon")
	RENVOYER Vrai
FIN
 
n1 = PartieEntière(Racine(2*cible) + 1)
 
t = allouer un tableau de n1 entiers
POUR i = 1 A n1
	t[i] = i*(i-1) /2
FIN
 
POUR i1 = 1 A n1
	POUR i2 = 1 A n1
		POUR i3 = 1 A n1
			SI t[i1] + t[i2] + t[i3] = cible ALORS 
				Info( t[i1] , t[i2] , t[i3] )
				RENVOYER Vrai
			FIN
		FIN
	FIN
FIN
Erreur ( " !!! pas de solution ")
RENVOYER Faux

Je cherche à décomposer en exactement 3 nombres triangulaires, et je considère que 0 est un nombre triangulaire.

[disedorgue]

Merci, mais là, à ce que j'en ai compris on est sur l'algo force brute: on teste toutes les combinaisons jusqu'à avoir la bonne...
Pour des petits nombres, ça peut le faire, mais comme je risque d'avoir des nombres d'au moins 1024 bits, cela risque d'être long.

Mais cela peut quand même m'être utile pour faire des tests .

[tbc92]

A ma connaissance, il n'y a pas de solution 'automatique'.
Toute solution sera donc par tâtonnements.
Mais effectivement, on peut sensiblement améliorer la première proposition.
Par exemple, en remplaçant la boucle principale par :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
POUR i1 = n1 A 1 PAS -1
	POUR i2 = i1 A 1 PAS -1
		SI t[i2] + t[i1] < cible ALORS 
			POUR i3 = 1 A i2
				SI t[i1] + t[i2] + t[i3] = cible ALORS 
					Info( i1,i2,i3, t[i1] , t[i2] , t[i3] )
					RENVOYER Vrai
				FIN
			FIN
		FIN
	FIN
FIN

[CliffeCSTL]

L'algo peut être améliorer.

- Tu peux précalculer, par exemple, les 1000 premiers nombre triangulaires, ça t'évite une fonction qui recalcule la mm chose.
- pas besoin de commencer a 1 pour les boucles for
- pas besoin de finir la boucle (si on dépasse la cible)

[RemyCave]

Code lisp :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
(* On note tn le énième nombre triangulaire. tn = n*(n+1)/2. *)

(* La fonction plus_grand_nombre_triangulaire_inferieur_ou_egal_a prend en entrée un nombre entier naturel k
   et retourne en sortie le couple (n, tn) où tn est le plus grand entier triangulaire inférieur ou égal à k. *)

let plus_grand_nombre_triangulaire_inferieur_ou_egal_a k =
    let n = ref 0 in
        while !n * (!n + 1) / 2 <= k do
            n := !n + 1
        done;
        (!n - 1,(!n - 1) * !n / 2);;

(* La fonction triangulaire prend en entrée un entier naturel k et retourne en sortie vrai si k est triangulaire,
  faux sinon. *)

let triangulaire k =
    let (a, ta) = plus_grand_nombre_triangulaire_inferieur_ou_egal_a k in
        ta = k;;

(* La fonction nombre_triangulaire précédent prend en entrée un couple (n, tn) et retourne en sortie le
   couple (n-1, tn-n), c'est-à-dire le nombre triangulaire précédent tn. 
   Exemple: 
    # nombre_triangulaire_precedent (100, 5050);;
    - : int * int = (99, 4950)
*)

let nombre_triangulaire_precedent (n, tn) = (n-1, tn-n);;


let deux_termes (a, b, c) = c = 0;;

(* decomp_deux k retourne un triplet (-1, _, _) si k n'est pas décomposable en somme de deux nombres triangulaires.
   Sinon decomp_deux k retourne un triplet (a, ta, tb) dans lequel ta et tb sont deux nombres triangulaires tels que ta + tb = k. *) 

let decomp_deux k =
    let (a, ta) = plus_grand_nombre_triangulaire_inferieur_ou_egal_a k in
    let ra = ref a in
    let rta = ref ta in
        while ((!ra) != -1) && (not (triangulaire (k - !rta))) do
            let (n, tn) = nombre_triangulaire_precedent (!ra, !rta) in begin ra := n; rta := tn end
        done;
        (!ra, !rta, k - !rta);;
        
(* decomp k retourne un triplet (ta, tb, tc) de trois nombres triangulaires dont la somme est égale à k 
  Exemple:
    # decomp 1234567;;
    - : int * int * int = (1233235, 1326, 6)
  On a bien 1 234 567 = 1 233 235 + 1 326 + 6.
*)

let rec decomp k =
    match k with
          0 -> (0, 0, 0)
        | n -> 
            let (a, ta) = plus_grand_nombre_triangulaire_inferieur_ou_egal_a n in
                if ta = n then
                    (ta, 0, 0)
                else 
                        let (f, g, h) = decomp_deux n in
                            if f != -1 then 
                                (g, h, 0)
                            else
                                let ra = ref a in
                                let rta = ref ta in
                                let b = ref (n - !rta) in
                                let (u, v, w) = decomp !b in
                                let ru = ref u in
                                let rv = ref v in
                                let rw = ref w in
                                while not (deux_termes (!ru, !rv, !rw)) do
                                    let (a, ta) = nombre_triangulaire_precedent (!ra, !rta) in begin ra := a; rta := ta end;
                                    b := n - !rta; 
                                    let (u, v, w) = decomp !b in begin ru := u; rv := v; rw := w end
                                done;
                                (!rta, !ru, !rv);;

L'idée c'est qu'on essaie en priorité de décomposer le nombre en une somme de seulement deux nombres triangulaires, et seulement si ça ne marche pas on se lance dans une récursion pour trouver la décomposition en somme de trois nombres triangulaires. C'est toujours pas très rapide mais je pense que c'est déjà plus rapide que ce que j'ai vu précédemment ...

[disedorgue]

Bonjour,
Merci pour ce script lisp, j'ai pas encore tout lu (car ma connaissance du lisp remonte à une bonne quinzaine d'années bien tassée )
Mais déjà, on peut simplifier la boucle de recherche de plus_grand_nombre_triangulaire_inferieur_ou_egal_a, puisque de k, on peut retrouver n en ne prenant que la partie entière de la racine triangulaire de k dont la formule est la suivante (langage bc):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

(-1+sqrt(1+(8*k)))/2

[RemyCave]

Bonjour,
Merci pour ce script lisp, j'ai pas encore tout lu (car ma connaissance du lisp remonte à une bonne quinzaine d'années bien tassée )
Mais déjà, on peut simplifier la boucle de recherche de plus_grand_nombre_triangulaire_inferieur_ou_egal_a, puisque de k, on peut retrouver n en ne prenant que la partie entière de la racine triangulaire de k dont la formule est la suivante (langage bc):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

(-1+sqrt(1+(8*k)))/2

Tout à fait, j'ai fait cette modif pour accélérer mon algo précédent ...et ça va vraiment plus vite, même pour l'interpréteur OCaml sous Windows...

Je remets le code modifié:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
(* On note tn le énième nombre triangulaire. tn = n*(n+1)/2. *)
 
 
 
 
 
(* La fonction nombre_triangulaire précédent prend en entrée un couple (n, tn) et retourne en sortie le
 
   couple (n-1, tn-n), c'est-à-dire le nombre triangulaire précédent tn. 
 
   Exemple: 
 
    # nombre_triangulaire_precedent (100, 5050);;
 
    - : int * int = (99, 4950)
 
*)
 
 
 
let nombre_triangulaire_precedent (n, tn) = (n-1, tn-n);;
 
 
(* La fonction triangulaire prend en entrée un entier naturel k et retourne en sortie vrai si k est triangulaire,
 
  faux sinon. Elle exploite la propriété suivante. Pour tout n, 8*tn + 1 = (2n+1)². *)
 
let triangulaire k = 
    let fk = float_of_int k in
    let n = floor ((sqrt (8.0 *. fk +. 1.0) -. 1.0) /. 2.0) in
    let tn = n *. (n +. 1.0) /. 2.0 in
    tn = fk;;   
 
 
 
(* La fonction plus_grand_nombre_triangulaire_inferieur_ou_egal_a prend en entrée un nombre entier naturel k
 
   et retourne en sortie le couple (n, tn) où tn est le plus grand entier triangulaire inférieur ou égal à k. *)
 
 
 
let plus_grand_nombre_triangulaire_inferieur_ou_egal_a k =
 
    let fk = float_of_int k in
    let n = floor ((sqrt (8.0 *. fk +. 1.0) -. 1.0) /. 2.0) in
    (int_of_float n, int_of_float (n *. (n +. 1.0) /. 2.0));;
 
 
 
(* decomp_deux k retourne un triplet (-1, _, _) si k n'est pas décomposable en somme de deux nombres triangulaires.
 
   Sinon decomp_deux k retourne un triplet (a, ta, tb) dans lequel ta et tb sont deux nombres triangulaires tels que ta + tb = k
   et ou a est l'indice de ta. *) 
 
 
 
let decomp_deux k =
 
    let (a, ta) = plus_grand_nombre_triangulaire_inferieur_ou_egal_a k in
 
    let ra = ref a in
 
    let rta = ref ta in
 
        while ((!ra) != -1) && (not (triangulaire (k - !rta))) do
 
            let (n, tn) = nombre_triangulaire_precedent (!ra, !rta) in begin ra := n; rta := tn end
 
        done;
 
        (!ra, !rta, k - !rta);;
 
 
 
(* decomp k retourne un triplet (ta, tb, tc) de trois nombres triangulaires dont la somme est égale à k 
 
  Exemple:
 
    # max_int;;
    - : int = 1073741823
    # decomp max_int;;
    - : int * int * int = (859445070, 214296753, 0)
    # decomp 1073741821;;
    - : int * int * int = (1073674630, 64980, 2211)
 
*)
 
 
let deux_termes (a, b, c) = c = 0;;
 
 
let rec decomp k =
 
    match k with
 
          0 -> (0, 0, 0)
 
        | n -> 
 
            let (a, ta) = plus_grand_nombre_triangulaire_inferieur_ou_egal_a n in
 
                if ta = n then
 
                    (ta, 0, 0)
 
                else 
 
                        let (f, g, h) = decomp_deux n in
 
                            if f != -1 then 
 
                                (g, h, 0)
 
                            else
 
                                let ra = ref a in
 
                                let rta = ref ta in
 
                                let b = ref (n - !rta) in
 
                                let (u, v, w) = decomp !b in
 
                                let ru = ref u in
 
                                let rv = ref v in
 
                                let rw = ref w in
 
                                while not (deux_termes (!ru, !rv, !rw)) do
 
                                    let (a, ta) = nombre_triangulaire_precedent (!ra, !rta) in begin ra := a; rta := ta end;
 
                                    b := n - !rta; 
 
                                    let (u, v, w) = decomp !b in begin ru := u; rv := v; rw := w end
 
                                done;
 
                                (!rta, !ru, !rv);;