cp's OEIS Frontend

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

%I A125024 #10 Dec 23 2015 21:24:55
%S A125024 1,2,6,12,18,30,60,90,150,540,1500,2250,210,420,630,1050,1890,2520,
%T A125024 3150,3780,7560,9450,15750,18900,28350,75600,113400,126000,141750,
%U A125024 216000,246960,5402250,2310,4620,6930,11550
%N A125024 Minimal Goedel number of endofunctions on k points, by row and sorted within rows (number of points).
%C A125024 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.
%F A125024 a(A125023(n)) = A002110(n).
%e A125024 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:
%e A125024 (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.
%e A125024 Table begins:
%e A125024 n | row(n) of Goedel numbers
%e A125024 0 | 1. (formally defining prime(0) = 1)
%e A125024 1 | 2.
%e A125024 2 | 6, 12, 18.
%e A125024 3 | 30, 60, 90, 150, 540, 1500, 2250.
%e A125024 4 | 210, 420, 630, 1050, 1890, 2520, 3150, 3780, 7560, 9450, 15750, 18900, 28350, 75600, 113400, 126000, 141750, 216000, 246960, 5402250.
%e A125024 5 | 2310, 4620, 6930, 11550, ...
%e A125024 6 | 30030, 60060, 90090, 150150, ...
%e A125024 7 | 510510, 1021020, 1531530, ...
%e A125024 8 | 9699690, 19399380.
%Y A125024 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.
%K A125024 easy,nonn,tabf
%O A125024 0,2
%A A125024 _Jonathan Vos Post_, Nov 15 2006