Sudan Function

### A function of two positive integers x and y, defined by the recurrence relation

F0(x,y) = x + y,

Fn+1(x,0) = x, for n ≥ 0,

Fn+1(x,y+1) = Fn( Fn+1(x,y), Fn+1(x,y)+y+1), for n ≥ 0.

## Tables of Values of F0(x,y)

 ╔    y    x 0 1 2 3 4 5 6 7 8 0 0 1 2 3 4 5 6 7 8 1 1 2 3 4 5 6 7 8 9 2 2 3 4 5 6 7 8 9 10 3 3 4 5 6 7 8 9 10 11 4 4 5 6 7 8 9 10 11 12 5 5 6 7 8 9 10 11 12 13 6 6 7 8 9 10 11 12 13 14

## Properties of F0(x,y)

F0(x,0) = x

F0(0,y) = y

F0(x,x) = 2x,

e.g F0(4,4) = 2.4 = 8 ü

## Tables of Values of F1(x,y)

 ╔    y  x 0 1 2 3 4 5 6 7 8 9 10 0 0 1 4 11 26 57 120 247 502 1013 2036 1 1 3 8 19 42 89 184 375 758 1525 3060 2 2 5 12 27 58 121 248 503 1014 2037 4084 3 3 7 16 35 74 153 312 631 1270 2549 5108 4 4 9 20 43 90 185 376 759 1526 3061 6132 5 5 11 24 51 106 217 440 887 1782 3573 7156 6 6 13 28 59 122 249 504 1015 2038 4085 8180 7 7 15 32 67 138 281 568 1143 2294 4597 9204 8 8 17 36 75 154 313 632 1271 2550 5109 10228 9 9 19 40 83 170 345 696 1399 2806 5621 11252 10 10 21 44 91 186 377 760 1527 3062 6133 12276

Properties of F1(x,y)

F1(x,0) = x,

F1(0,y) = (x + 2)(2x - 1),

F1(x,y) = F1(0,y) + x.2y,

e.g. F1(3,4) = F1(0,4) + 3.24 = 26 + 48 = 74 ü

F1(x,y) = (x + 2).2y - (y + 2), (explicit solution)

e.g. F1(8,8) = (x+2).2y - (y+2) = 10.2 - 10 = 2560 - 10 = 2550 ü

Graphical Representation of F1(x,y) ## Tables of Values of F2(x,y)

 ╔      y   x 0 1 2 0 0 F1(0,1) = 1 F1(1,3) = 19 ≈ 101 1 1 F1(1,2) = 8 F1(8,10) = 10228 ≈ 104 2 2 F1(2,3) = 27 F1(27,29) ≈ 1010 3 3 F1(3,4) = 74 F1(74,76) ≈ 1025 4 4 F1(4,5) = 185 F1(185,187) ≈ 1058 5 5 F1(5,6) = 440 F1(440,442) ≈ 10136

Properties of F2(x,y)

F2(x,0) = x,

F2(x,y+1) = F1( F2(x,y), F2(x,y)+y+1).

History of Fn(x,y)

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 but 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.

Applications of Fn(x,y)

Higher order Sudan functions with n ≥ 2 can be used to test the ability of computers to handle recursion efficiently.