cp's OEIS Frontend

A336913 Image of n under the 3^x+1 map, which is a variation of the 3x+1 (Collatz) map.

%I A336913 #21 Jun 27 2021 03:40:38
%S A336913 4,1,28,2,244,2,2188,3,19684,3,177148,3,1594324,3,14348908,4,
%T A336913 129140164,4,1162261468,4,10460353204,4,94143178828,4,847288609444,4,
%U A336913 7625597484988,4,68630377364884,4,617673396283948,5,5559060566555524,5,50031545098999708,5
%N A336913 Image of n under the 3^x+1 map, which is a variation of the 3x+1 (Collatz) map.
%C A336913 It seems that all 3^x+1 trajectories reach 1; this has been verified up to 10^9. Once a 3^x+1 trajectory reaches 1, it repeats the following cycle: 1, 4, 2, 1, 4, 2, 1, ...
%H A336913 Wikipedia, <a href="http://en.wikipedia.org/wiki/Collatz_conjecture">Collatz conjecture</a>
%F A336913 a(n) = floor(log_2(n)) if n is even, 3^n+1 if n is odd.
%e A336913 For n = 5, a(5) = 3^5+1 = 244, because 5 is odd.
%e A336913 For n = 6, a(6) = floor(log_2(6)) = 2, because 6 is even.
%o A336913 (Python)
%o A336913 from math import floor, log
%o A336913 def a(n): return 3**n + 1 if n % 2 else int(floor(log(n, 2)))
%o A336913 print([a(n) for n in range(1, 51)])
%o A336913 (Python)
%o A336913 '''
%o A336913 Program that confirms that 3^x+1 trajectories end with 1.
%o A336913 We avoid the expensive 3^n+1 calculation based on the following:
%o A336913 - 3^n is not a power of two (for n >= 1).
%o A336913 - 3^n+1 is not a power of two (for n > 1) because of the Catalan Conjecture, which was proven in 2002.
%o A336913 - Thus, floor(log2(3^n+1)) == floor(log2(3^n)) == floor(n*log2(3)) for n > 1.
%o A336913 Thanks to Clark R. Lyons for this optimization.
%o A336913 '''
%o A336913 from math import floor, log
%o A336913 log2_of_3 = log(3, 2) # 16 digits after the decimal point.
%o A336913 max_n = 10**15 / 2    # Larger values multiplied by log2_of_3 may have rounding errors.
%o A336913 def check_trajectory(n):
%o A336913     while n > 1:
%o A336913         if n % 2 == 0:
%o A336913             n = int(floor(log(n, 2)))
%o A336913         else:
%o A336913             if n > max_n:
%o A336913                 raise ValueError(str(n) + " is too large to be multiplied by log2_of_3")
%o A336913             n = int(floor(n * log2_of_3))
%o A336913 n = 1
%o A336913 while n <= 1000000000:
%o A336913     check_trajectory(n)
%o A336913     n += 1
%Y A336913 Cf. A006370 (image of n under the 3x+1 map).
%Y A336913 Cf. A336914 (gives number of steps to reach 1).
%Y A336913 See also A199561.
%K A336913 nonn
%O A336913 1,1
%A A336913 _Robert C. Lyons_, Aug 08 2020