login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A336913 Image of n under the 3^x+1 map, which is a variation of the 3x+1 (Collatz) map. 1
4, 1, 28, 2, 244, 2, 2188, 3, 19684, 3, 177148, 3, 1594324, 3, 14348908, 4, 129140164, 4, 1162261468, 4, 10460353204, 4, 94143178828, 4, 847288609444, 4, 7625597484988, 4, 68630377364884, 4, 617673396283948, 5, 5559060566555524, 5, 50031545098999708, 5 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

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, ...

LINKS

Table of n, a(n) for n=1..36.

Wikipedia, Collatz conjecture

FORMULA

a(n) = floor(log_2(n)) if n is even, 3^n+1 if n is odd.

EXAMPLE

For n = 5, a(5) = 3^5+1 = 244, because 5 is odd.

For n = 6, a(6) = floor(log_2(6)) = 2, because 6 is even.

PROG

(Python)

from math import floor, log

def a(n): return 3**n + 1 if n % 2 else int(floor(log(n, 2)))

print([a(n) for n in range(1, 51)])

(Python)

'''

Program that confirms that 3^x+1 trajectories end with 1.

We avoid the expensive 3^n+1 calculation based on the following:

- 3^n is not a power of two (for n >= 1).

- 3^n+1 is not a power of two (for n > 1) because of the Catalan Conjecture, which was proven in 2002.

- Thus, floor(log2(3^n+1)) == floor(log2(3^n)) == floor(n*log2(3)) for n > 1.

Thanks to Clark R. Lyons for this optimization.

'''

from math import floor, log

log2_of_3 = log(3, 2) # 16 digits after the decimal point.

max_n = 10**15 / 2    # Larger values multiplied by log2_of_3 may have rounding errors.

def check_trajectory(n):

    while n > 1:

        if n % 2 == 0:

            n = int(floor(log(n, 2)))

        else:

            if n > max_n:

                raise ValueError(str(n) + " is too large to be multiplied by log2_of_3")

            n = int(floor(n * log2_of_3))

n = 1

while n <= 1000000000:

    check_trajectory(n)

    n += 1

CROSSREFS

Cf. A006370 (image of n under the 3x+1 map).

Cf. A336914 (gives number of steps to reach 1).

See also A199561.

Sequence in context: A139051 A061692 A096206 * A134150 A134151 A264773

Adjacent sequences:  A336910 A336911 A336912 * A336914 A336915 A336916

KEYWORD

nonn

AUTHOR

Robert C. Lyons, Aug 08 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 31 02:33 EDT 2021. Contains 346367 sequences. (Running on oeis4.)