A125024 Minimal Goedel number of endofunctions on k points, by row and sorted within rows (number of points).

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

Offset: 0

Author

Jonathan Vos Post, Nov 15 2006

Keywords

• easy
• nonn
• tabf

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.

Examples

			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.

Formula

a(A125023(n)) = A002110(n).