[VA] Short & Sweet Math Challenge #25 "San Valentin's Special: Weird Math"

[robve]

The weird primes concoction (aka challenge five) depends on the decimal number base. One could argue that a "perfect" property definition should not depend on the number base. The choice of base affects the distribution of base-perfect primes. The prime number theorem sheds some light on the frequency of perfect primes in general.

1. We should observe more primes that meet the definition of base-perfectness when smaller number bases are used than larger number bases.

2. For small primes with k digits such as k=1, k=2, …, k=5 digits there are no perfect primes (in base 10), because primes with k digits are "too close" (as in a Hamming distance kind of way). The prime number theorem tells us that primes are distributed roughly as N/log(N) so that a randomly picked integer not greater than N has a probability of 1/log(N) to be prime. A perfect prime of k digits can be perturbed by its definition to generate 9k distinct composite integers. Roughly, the chance that an integer of k digits is prime is 1/log(10^k)=0.43/k. The chance that the 9k integers are all composite is (1-0.4343/k)^(9k), assuming k is sufficiently large. It turns out that the chance approaches 2% for large k and is half that for small k (though the log constant is somewhat arbitrary). More importantly, there are also far more integers to pick as potential perfect primes for large k. Based on this, it seems reasonable to see perfect primes for large k and there are infinitely many of them.

The first base-perfect primes for base 2 to 19 are (shown is the minimum number of base digits for the perfect prime shown in decimal):


base | digits | first PP   |
2    | 7      | 127        |
3    | 3      | 13         |
4    | 5      | 373        |
5    | 3      | 83         |
6    | 6      | 28151      |
7    | 3      | 223        |
8    | 5      | 6211       |
9    | 4      | 2789       |
10   | 6      | 294001     |
11   | 4      | 3347       |
12   | 7      | 20837899   |
13   | 4      | 4751       |
14   | 6      | 6588721    |
15   | 5      | 484439     |
16   | 5      | 862789     |
17   | 4      | 10513      |
18   | 8      | 2078920243 |
19   | 4      | 10909      |


A very interesting pattern is emerging that has an explanation.

The C "perp" program (note: indent spacing U+00A0):

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(int argc, char **argv)
{
  if (argc > 2)
  {
    long i, j, k;
    const long base = atoi(argv[1]); // perfect prime base
    const long maxd = atoi(argv[2]); // up to primes of maxd digits
    const double lnbase = log(base);
    const long max = pow(base, maxd); // primes up to max (exclusive)
    char *sieve = (char*)malloc(max); // sieve (0 = composite, 1 = prime)

    // init sieve, we should keep only odd values
    for (i = 0; i < max; ++i)
      sieve[i] = (i & 1);

    // seive for primes
    for (i = 3; i < max; i += 2)
    {
      while (i < max && sieve[i] == 0)
        ++i;
      for (j = 2*i; j < max; j += i)
        sieve[j] = 0;
    }

    // sieve for perfect primes
    for (i = 3; i < max; i += 2)
    {
      while (i < max && sieve[i] == 0)
        ++i;
      if (i < max)
      {
        long m = floor(log(i)/lnbase); // m = number of digits of i
        long p = 1; // p = base^j
        char h = 1; // h = 1 if i is perfect
        // for each jth digit in prime i, from least to most significant
        for (j = 0; j <= m; ++j, p *= base)
        {
          // q = prime i with jth digit zero
          long q = i%p + i/p/base*p*base;
          // d = jth digit of prime i
          long d = i/p%base;
          // twiddle jth digit and check for prime
          for (k = 0; k < base; ++k)
            if (k != d && sieve[q+k*p])
              h = 0;
        }
        if (h)
          printf("perfect_%ld %ld\n", base, i);
      }
    }

    free(sieve);
  }
  else
  {
    printf("Usage: perp <BASE> <MAXDIGITS>\n");
  }
}


- Rob