Fonction de Sudan
En calculabilité, la fonction de Sudan est un exemple de fonction récursive mais non récursive primitive (de même que la fonction d'Ackermann, plus connue).
Elle fut conçue en 1927 par le mathématicien roumain Gabriel Sudan, élève de David Hilbert.
Définition modifier
- ,
- ,
- .
Tableaux de valeurs modifier
y\x | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
0 | 0 | 1 | 2 | 3 | 4 | 5 |
1 | 1 | 2 | 3 | 4 | 5 | 6 |
2 | 2 | 3 | 4 | 5 | 6 | 7 |
3 | 3 | 4 | 5 | 6 | 7 | 8 |
4 | 4 | 5 | 6 | 7 | 8 | 9 |
5 | 5 | 6 | 7 | 8 | 9 | 10 |
6 | 6 | 7 | 8 | 9 | 10 | 11 |
y\x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
1 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | 29 |
2 | 4 | 8 | 12 | 16 | 20 | 24 | 28 | 32 | 36 | 40 | 44 | 48 | 52 | 56 | 60 |
3 | 11 | 19 | 27 | 35 | 43 | 51 | 59 | 67 | 75 | 83 | 91 | 99 | 107 | 115 | 123 |
4 | 26 | 42 | 58 | 74 | 90 | 106 | 122 | 138 | 154 | 170 | 186 | 202 | 218 | 234 | 250 |
5 | 57 | 89 | 121 | 153 | 185 | 217 | 249 | 281 | 313 | 345 | 377 | 409 | 441 | 473 | 505 |
6 | 120 | 184 | 248 | 312 | 376 | 440 | 504 | 568 | 632 | 696 | 760 | 824 | 888 | 952 | 1016 |
7 | 247 | 375 | 503 | 631 | 759 | 887 | 1015 | 1143 | 1271 | 1399 | 1527 | 1655 | 1783 | 1911 | 2039 |
8 | 502 | 758 | 1014 | 1270 | 1526 | 1782 | 2038 | 2294 | 2550 | 2806 | 3062 | 3318 | 3574 | 3830 | 4086 |
9 | 1013 | 1525 | 2037 | 2549 | 3061 | 3573 | 4085 | 4597 | 5109 | 5621 | 6133 | 6645 | 7157 | 7669 | 8181 |
10 | 2036 | 3060 | 4084 | 5108 | 6132 | 7156 | 8180 | 9204 | 10228 | 11252 | 12276 | 13300 | 14324 | 15348 | 16372 |
11 | 4083 | 6131 | 8179 | 10227 | 12275 | 14323 | 16371 | 18419 | 20467 | 22515 | 24563 | 26611 | 28659 | 30707 | 32755 |
12 | 8178 | 12274 | 16370 | 20466 | 24562 | 28658 | 32754 | 36850 | 40946 | 45042 | 49138 | 53234 | 57330 | 61426 | 65522 |
13 | 16369 | 24561 | 32753 | 40945 | 49137 | 57329 | 65521 | 73713 | 81905 | 90097 | 98289 | 106481 | 114673 | 122865 | 131057 |
14 | 32752 | 49136 | 65520 | 81904 | 98288 | 114672 | 131056 | 147440 | 163824 | 180208 | 196592 | 212976 | 229360 | 245744 | 262128 |
On peut démontrer que F1(x, y) = F1(0, y) + 2y x.
y\x | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
0 | 0 | 1 | 2 | 3 | 4 | 5 |
1 | 1 | 8 | 27 | 74 | 185 | 440 |
2 | 19 | F1(8, 10) = 10 228 | F1(27, 29) = 15 569 256 417 ≈ 1,55.1010 | F1(74, 76) ≈ 5,74.1024 | F1(185, 187) ≈ 3,67.1058 | F1(440, 442) ≈ 5,02.10135 |
Voir aussi modifier
Article connexe modifier
Liens externes modifier
Suites A260003 et A260004 de l'OEIS
Crédit d'auteurs modifier
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Sudan function » (voir la liste des auteurs).