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