A130769 - OEIS

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').

%I #3 Feb 27 2009 03:00:00

%S 2,12,1649253940128607650037732224082865475000,720,

%T 2032221170141662500000,

%U 7372155480163603867228249918067794802791875000000

%N 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').

%D J. Shallit and D. Wilson, The "3x+1" Problem and Finite Automata, Bulletin of the EATCS #46 (1992) pp. 182-185.

%D R. K. Guy, Unsolved Problems in Number Theory, E16.

%H R. K. Guy, <a href="http://www.cecm.sfu.ca/organics/papers/lagarias/paper/html/paper.html">Unsolved Problems in Number Theory</a>, E16.

%F 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.

%e G(3) = 1649253940128607650037732224082865475000

%e because given F as described above,

%e F(3) = (3, 10, 5, 16, 8, 4, 2, 1)

%e and thus

%e G(3) = 2^3 * 3^10 * 5^5 * 7^16 * 11^8 * 13^4 * 17^2 * 19

%e = 1649253940128607650037732224082865475000.

%o 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*))

%Y Cf. A001281, A001281.

%K nonn

%O 1,1

%A Grant Olney Passmore (grant(AT)math.utexas.edu), Jul 13 2007