Programming Praxis

3 Responses to “Collatz Primes”

1. Rutger said

   May 1, 2015 at 11:09 AM

   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

   May 1, 2015 at 3:41 PM

   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

   May 5, 2015 at 11:04 AM

   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.