Collatz Primes

May 1, 2015

Today’s exercise comes from the world of recreational mathematics; I found it at Stack Overflow:

The Collatz sequence starting at n continues with n / 2, if n is even, and 3 n + 1 if n is odd. For instance, the Collatz sequence that starts from 19 is 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. It is conjectured that all Collatz sequences eventually end at 1, but has never been proven. The Collatz sequence that starts from 19 contains 7 prime numbers: 19, 29, 11, 17, 13, 5 and 2. Find the smallest starting number for a Collatz sequence that contains 65 or more primes.

Your task is to find the requested Collatz sequence. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

3 Responses to “Collatz Primes”

  1. Rutger said

    In Python..

    Solution performance can be increased by creating a cached collatz(n) function. For example, if we have previously computed collatz(6) already, a consecutive call for collatz(12) would obtain the result from cache.

    def is_prime(number):
        if number == 2:
            return True
        if not (number % 2):
            return False
        i = 3
        while i <= number**0.5:
            if not (number % i):
                return False
            i += 2
        return True
    
    
    def collatz(n):
    	yield n
    	if n == 1:
    		return
    	if n % 2:
    		for c in collatz(3*n+1):
    			yield c
    	else:
    		for c in collatz(n/2):
    			yield c
    
    
    
    for i in range(1,3000000):
    	c = collatz(i)
    	count = 0
    	for v in c:
    		if (is_prime(v)):
    			count +=1
    	if count > 65:
    		print i, count
    

    Result:
    1805311 68
    1993215 71
    2139627 69
    2407081 68
    2707967 68
    2989823 71

  2. Lucas A. Brown said

    In the following Python code, I import an isprime() function from my personal library. This uses BPSW for numbers above 3825123056546413051, Miller-Rabin in various increments for numbers below that, and has a few prefilters including trial division, Fermat’s test, and Euler’s test.

    Brute force:

    from itertools import count
    from labmath import isprime
    def collatz(n):
        yield n
        while n != 1:
            n = 3*n+1 if n%2 else n/2
            yield n
    for n in count(1):
        if sum(map(isprime, list(collatz(n)))) >= 65: break
    print n
    

    On my machine, this finishes in about 15 minutes.

    Caching:

    from itertools import count
    from labmath import isprime
    cache = {1:0}
    for x in count(1):
        n, l = x, []
        while not (n in cache):
            l.append(n)
            n = 3*n+1 if n%2 else n/2
        for m in reversed(l):
            cache[m] = cache[n] + isprime(m)
            n = m
        if cache[x] >= 65: break
    print x
    

    This finishes in 27 seconds.

    (The answer is 1805311, which initiates a sequence of length 402 containing 67 primes.)

  3. Ernie G. said

    I use a sieve to determine if a number, n, is prime where n < 2×10**9. If n is greater than that then I use an isprime method. Since most of the numbers in the Collatz sequence are
    < 2×10**9, the program executes much faster, about 2 sec.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: