OT-Governor General binary

[D. Hugh Redelmeier]

| 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?

================ counting-palindromes.c ================
/*
  gcc -g -Wall counting-palindromes.c -lgmp
*/

#include <stdio.h>
#include <gmp.h>

int
main()
{

    unsigned long i;
    int pal_count = 0;
    int pri_count = 0;

    for (i = 0; i < 1ul<<16; i++) {
	unsigned long ri = i;
	mpz_t p;

	ri = ((ri & 0x00FF)<<8)  | ((ri >> 8) & 0x00FF);
	ri = ((ri & 0x0F0F)<<4)  | ((ri >> 4) & 0x0F0F);
	ri = ((ri & 0x3333)<<2)  | ((ri >> 2) & 0x3333);
	ri = ((ri & 0x5555)<<1)  | ((ri >> 1) & 0x5555);

	mpz_init_set_ui(p, (1ul << 32) | 1ul | (i << 1) | (ri << 16));

	pal_count++;
	pri_count += mpz_probab_prime_p(p, 10);

	mpz_clear(p);
    }

    printf("33-bit palindromes: %d\nprimes %d\n", pal_count, pri_count);

    return 0;
}
================ counting-palindromes-2.c ================
/*
  gcc -g -Wall counting-palindromes-2.c -lgmp
*/

#include <stdio.h>
#include <gmp.h>

int
main()
{

    unsigned long i;
    int pal_count = 0;
    int pri_count = 0;

    for (i = 1ul<<16; i < 1ul<<17; i++) {
	mpz_t p;

	unsigned long pal = i;
	unsigned long x;

	for (x = i>>1; x != 0; x >>= 1) {
	    pal = (pal << 1) | (x & 1);
	}

	mpz_init_set_ui(p, pal);

	pal_count++;
	pri_count += mpz_probab_prime_p(p, 10);

	mpz_clear(p);
    }

    printf("33-bit palindromes: %d\nprimes %d\n", pal_count, pri_count);

    return 0;
}
================ end ================
--
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