A130769 Injection of the sequence of positive integers used in recursive calls (including initial call) in the execution of the Collatz (3n+1) function into the positive integers using the standard power-of-primes encoding (`Goedel-coding').
2, 12, 1649253940128607650037732224082865475000, 720, 2032221170141662500000, 7372155480163603867228249918067794802791875000000
Offset: 1
Keywords
Examples
G(3) = 1649253940128607650037732224082865475000 because given F as described above, F(3) = (3, 10, 5, 16, 8, 4, 2, 1) and thus G(3) = 2^3 * 3^10 * 5^5 * 7^16 * 11^8 * 13^4 * 17^2 * 19 = 1649253940128607650037732224082865475000.
References
- J. Shallit and D. Wilson, The "3x+1" Problem and Finite Automata, Bulletin of the EATCS #46 (1992) pp. 182-185.
- R. K. Guy, Unsolved Problems in Number Theory, E16.
Links
- R. K. Guy, Unsolved Problems in Number Theory, E16.
Programs
-
Lisp
;; (main function to call is f-code with n and a list of primes): ; Generate F sequence for the Collatz (3n+1) function (defun F (n) (cond ((= n 1)) (list n)) ((evenp n) (cons n (F (/ n 2)))) (t (cons n (F (1+ (* 3 n))))))) ; The Goedel-coding function. Takes a list of integers and a list of primes and performs the standard powers-of-primes encoding. (defun goedel-code (l p) (cond ((endp l) 1) (t (* (expt (car p) (car l)) (goedel-code (cdr l) (cdr p)))))) ; Encode intermediate values of Collatz function, using a given list of primes (defun G (n) (goedel-code (F n) *list-of-primes*))
Formula
Let f(n) be the Collatz (3n+1) function. Let F(n) be the sequence of positive integers m s.t. f(m) is called during the execution of f(n). (So F(1) = (1); F(2) = (2, 1); F(3) = (3, 10, 5, 15, 8, 4, 2, 1); and so on.) Assume that F(n) has k terms. Then, each instance of the sequence, G(n), is generated by encoding the sequence F(n) as a positive integer as follows: G(n) = 2^F(n)0 * 3^F(n)_1 * 5^F(n)_2 * ... * p(k-1)^F(n){k-1} where F(n)_i is the i-th member of the sequence F(n) and p(i) is the i-th prime.