Sudan function
In the theory of computation, the Sudan function is an example of a function that is recursive, but not primitive recursive. This is also true of the better-known Ackermann function. The Sudan function was the first function having this property to be published.
It was discovered in 1927 by Gabriel Sudan, a Romanian mathematician who was a student of David Hilbert.Definition
| 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 |
In general, F1 is equal to F1 + 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 = 10228 | F1 ≈ 1.55 | F1 ≈ 5.74 | F1 ≈ 3.67 | F1 ≈ 5.02 |
