Skip to content

Instantly share code, notes, and snippets.

@prozacgod
Last active October 13, 2016 13:13
Show Gist options
  • Save prozacgod/8ac05c926f13007332b37489238abd52 to your computer and use it in GitHub Desktop.
Save prozacgod/8ac05c926f13007332b37489238abd52 to your computer and use it in GitHub Desktop.
A reddit thread interested me while I wound up my day for work, so I wrote this.
# inspired by this post, an a general curiousity...
# https://www.reddit.com/r/math/comments/578drx/i_believe_ive_found_something_very_interesting/
# it seems that reverse binary primes actually get rarer the further you get
# http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n/3035188#3035188
def primes(n):
""" Returns a list of primes < n """
sieve = [True] * (n/2)
for i in xrange(3,int(n**0.5)+1,2):
if sieve[i/2]:
sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]
# http://stackoverflow.com/questions/15285534/isprime-function-for-python-language
def is_prime(n):
if n == 2 or n == 3: return True
if n < 2 or n%2 == 0: return False
if n < 9: return True
if n%3 == 0: return False
r = int(n**0.5)
f = 5
while f <= r:
#print '\t',f
if n%f == 0: return False
if n%(f+2) == 0: return False
f +=6
return True
def binary(n):
return bin(n)[2:]
def reverseBinary(n):
return binary(n)[::-1]
def revPrimeRun(primeMax, quiet=True):
allPrimes = primes(primeMax)
revPrimes = []
for prime in allPrimes:
rb = reverseBinary(prime)
value = int(rb, 2)
isPrime = is_prime(value)
if isPrime:
revPrimes += [(prime, value)]
if not quiet:
print "%d, %s, %s, %d, %s" % (prime, binary(prime), rb, value, str(isPrime))
if not quiet:
print "Number of Primes < primeMax:", len(allPrimes)
print "Number of RevePrimes:", len(revPrimes)
print "rev/all", len(revPrimes)/float(len(allPrimes))
return (len(revPrimes), len(allPrimes))
revPrimeRun(1000, False)
v = []
for a in range(100, 100000, 1000):
revPrimes, allPrimes = revPrimeRun(a)
v += [float(revPrimes) / allPrimes]
print v
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment