|
| |
|
|
A125024
|
|
Minimal Goedel number of endofunctions on k points, by row and sorted within rows (number of points).
|
|
3
|
|
|
|
1, 2, 6, 12, 18, 30, 60, 90, 150, 540, 1500, 2250, 210, 420, 630, 1050, 1890, 2520, 3150, 3780, 7560, 9450, 15750, 18900, 28350, 75600, 113400, 126000, 141750, 216000, 246960, 5402250, 2310, 4620, 6930, 11550
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
If one writes an endofunction over n points (finite n) and numbers the points 1 through n, then each labeled sagittal graph of an endofunction from (1,2,3,..., z) to (a, b, c, ..., z) with a, b, c, ..., z elements of (1,2,3,..., z), is isomorphic to a Goedel number prime(1)^a * prime(2)^b * ... * prime(z)^z. Then, among all the Goedel numbers for different labeled endofunctions of the same (to isomorphism) unlabeled endofunction, there is a unique minimal Goedel number, which is thus the Goedel number for that unlabeled endofunction. Similarly, there is a minimal Goedel number for all the endofunctions on n points, for any n. Iterating the endofunction yields those x for which f^k(n) = x, allowing us to see the cycle index. The length of the n-th row is A001372(n). Each row begins with primorial n# = A002110(n) corresponding to the endofunction (1, 2, 3, ..., n) -> (1, 1, 1, ..., 1) which maps every integer other than 1 to 1 and loops 1 to itself; and ends with the Goedel number of the endofunction consisting only of a cycle of length n labeled (1, 2, 3, ..., n-1, n) -> (n-1, n-2, ..., n, 1). The sequence includes A074736(n) which corresponds to the identity endofunction on n points.
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
EXAMPLE
|
For example, take the endofunction on 4 points which is composed of two 2-cycles. We can write this as: (1, 2, 3, 4) -> (2, 1, 4, 3) which has the Goedel number 2^2 * 3^1 * 5^4 * 7^3 = 2572500. We can also renumber the points (applying the symmetric group S_n: n^n -> n^n) and write it: (1, 2, 3, 4) -> (3, 4, 1, 2) which gives us the Goedel number 2^3 * 3*4 * 5^1 * 7^2 = 158760. But the minimal Goedel number for that endofunction comes from:
(1, 2, 3, 4) -> (4, 3, 2, 1) which gives us 756000. Hence I can enumerate all the minimal Goedel numbers for the 7 endofunctions on 4 points as: 30, 60, 90, 150, 540, 1500, 2250.
Table begins:
n | row(n) of Goedel numbers
0 | 1. (formally defining prime(0) = 1)
1 | 2.
2 | 6, 12, 18.
3 | 30, 60, 90, 150, 540, 1500, 2250.
4 | 210, 420, 630, 1050, 1890, 2520, 3150, 3780, 7560, 9450, 15750, 18900, 28350, 75600, 113400, 126000, 141750, 216000, 246960, 5402250.
5 | 2310, 4620, 6930, 11550, ...
6 | 30030, 60060, 90090, 150150, ...
7 | 510510, 1021020, 1531530, ...
8 | 9699690, 19399380.
|
|
|
CROSSREFS
|
Cf. A001372, A002110, A074736 Goedel encoding of the prime factors of n, in increasing order and repeated according to multiplicity, A076954 Product_{i=1..n} prime(i)^i, A125023 Number of mappings (or mapping patterns) from k =< n points to themselves; number of endofunctions on k <= n points.
|
|
|
KEYWORD
|
easy,nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
