OT-Governor General binary

[Mel Wilson]

On 10-10-05 11:58 PM, D. Hugh Redelmeier wrote:
> | From: Mel Wilson<mwilson-4YeSL8/OYKRWk0Htik3J/w at public.gmane.org>
>
> | There seem to be 2972 33-bit palindromic primes.
>
> Out of how many 33-bit palindromes?
>
> Top and bottom bit are 1.
> That leaves 31 bits to be determined.
> The top-but-1 16 bit can be anything
> This determines the remaining 15 bits.
> So there are 64K 33-bit palindromes.
>
> So 4.5% are primes.
>
> The density of primes around N is about 1 / ln(N).
>
> 2^16 / ln(2^33.5) == 2822.34...
>
> Not too far off 2972.
>
> But note: all primes in this area are odd, and so are palindromes so
> the density in palindromes of 33 bits ought to be double.  So
> something seems wrong.
>
> I wrote two variants of a program to count 33-bit binary palindromic
> primes.  They both count 5572.  They both might be buggy.
>
> Mel: were did you get your number?
>
> Did I make a mistake?

Ah my!  I got my number from a buggy program that ignored palindromes 
with '0' in the middle.  According to my program after corrections, 
your result is spot on.

Sorry for the confusion.
	Mel.

P.S.  I appreciate the herald's point now.  Out of the palindromic 
primes, the chosen bit string is one of the nicest-looking ones.
MPW

# primetest.py
#=======================
import random

def radexp2 (n):
	q, k = n, 0
	while not q & 1:
		k += 1
		q /= 2
	return q, k

def prime_test (n):
	'''Knuth's Algorithm P'''
	x = random.randint (1, n)
	q, k = radexp2 (n-1)
	y = pow (x, q, n)
	for j in xrange (k):
		if (j == 0 and y == 1) or (y == n-1):
			return True
		if j > 0 and y == 1:
			return False
		if j >= k:
			return False
		y = pow (y, 2, n)
	return False
			
def is_prime (n, count=25):
	for times in xrange (count):
		if not prime_test (n):
			return False
	return True


# palprimes_33.py
#=======================
import primetest

def bitstr (n):
	'''Represent a binary number as a string of '1' and '0'.'''
	s = []
	while n:
		n, r = divmod (n, 2)
		s.append (str (r))
	return ''.join (s[::-1])
	
for n in xrange (0x10001, 0x20000, 2):
	s = bitstr (n)
	t = s[-1:0:-1] + s	# make a palindrome
	m = int (t, 2)
	if primetest.is_prime (m):
		print m, t, len (t)
	t = t[:16] + '0' + t[17:]	# same again with middle '0'
	m = int (t, 2)
	if primetest.is_prime (m):
		print m, t, len (t)
--
The Toronto Linux Users Group.      Meetings: http://gtalug.org/
TLUG requests: Linux topics, No HTML, wrap text below 80 columns
How to UNSUBSCRIBE: http://gtalug.org/wiki/Mailing_lists