[seqfan] Re: [math-fun] prime ladders

[Edwin Clark]

On Sat, 14 Mar 2009, N. J. A. Sloane wrote:

> I've seen two different versions of how you can move from one prime to another:
>
> Version 1: change a single digit
> Version 2: change a single digit and then permute the digits
>
> subject in both cases to the restriction that the new prime cannot
> begin with 0; the number of digits must remain constant.
>
> Call two primes equivalent if you can go from one to the other in this way.
>
> For each version of equivalence, there are four obvious sequences:
>
> a(n) = number of equivalence classes of primes with n digits.
>
> Arrange the equivalence classes by the size of the smallest member.
>
> b(k) = size of the k-th equivalence class
> c(k) = smallest member of the k-th equivalence class
> d(k) = largest member of the k-th equivalence class
>
> Presumably the two a-sequences will begin with a bunch of 1's,
> the two b-sequences will start like A006879,
> the two c-sequences will start like A003617,
> and the two d-sequences will start like A003618.
>
> There are potentially eight (new?) sequences here - could someone compute them?
>

Neil, I thought base sequences in the OEIS were frowned upon. But...

Doing this in base b: Let H(n,b) be the Hamming graph whose vertices 
are the sequences of length n over the alphabet {0,1,...,b-1} with 
adjacency being defined by having Hamming distance 1. Let P(n,b) be the 
subgraph of H(n,b) induced by the set of vertices which are base b 
representations of primes with n digits (not allowing leading 0 digits).

For fixed base b the version 1 sequences you asked for, are (I think):

a(n) = number of components of the graph P(n,b)

Let S be the sequence of all components of the graphs P(n,b), n>0, sorted 
by the smallest prime in a component. Then

b(k) = size of the k-th term in S
c(k) = smallest member of the k-th term in S (in decimal notation)
d(k) = largest member of the k-th term in S (in decimal notaton)

I have a Maple program that will compute these sequences for small values 
of b, but it crashes for b = 10 and n = 6. Prior to that P(n,10) is 
connected(as has been noted). We do know that P(6,10) has several 
components since as has been pointed out there are five isolated vertices 
(= weak primes. See http://www.research.att.com/~njas/sequences/A050249)
Perhaps someone with more computer power or a better program can find the 
components of P(n,10) for a few n greater than 5.

Here are parts of the sequences for bases 2 and 3. I will 
submit these to the OEIS. But I am too lazy to put in the sequences for 
bases 4,...,9.

The rapid growth of the sequences a is I believe due to 
the abundance of weak primes for base b as n increases. But there are a 
fair number of components with 2 and 3 elements as well.

base = 2:
a = 0, 1, 1, 2, 1, 2, 4, 11, 13, 19, 29, 43, 107, 169, 350, 603, 1134,
b = 2, 2, 1, 1, 5, 3, 4, 9, 2, 1, 1, 7, 4, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 
12, 1, 20, 1, 1, 1, 1,
c = 2, 5, 11, 13, 17, 37, 41, 67, 73, 107, 127, 131, 149, 173, 191, 193, 
211, 223, 233, 239, 241, 251, 257, 263, 277, 281, 337, 349, 353, 373,
d = 3, 7, 11, 13, 31, 61, 59, 113, 89, 107, 127, 227, 181, 173, 191, 229, 
211, 223, 233, 239, 241, 251, 257, 479, 277, 503, 337, 349, 353, 373,

base = 3:
a = 1, 2, 4, 8, 15, 32, 88, 209, 539, 1403,
b = 1, 2, 1, 2, 1, 1, 1, 3, 1, 2, 1, 1, 3, 1, 1, 5, 2, 3, 2, 2, 1, 2, 1, 
4, 2, 2, 1, 2, 1, 1,
c = 2, 3, 7, 11, 13, 19, 23, 29, 31, 37, 41, 59, 61, 67, 71, 83, 97, 103, 
109, 113, 149, 163, 167, 173, 191, 193, 199, 223, 229, 239,
d = 2, 5, 7, 17, 13, 19, 23, 53, 31, 43, 41, 59, 79, 67, 71, 137, 151, 
157, 127, 131, 149, 181, 167, 233, 197, 211, 199, 241, 229, 239,

Checks on these sequences would be appreciated.

--Edwin