|
| |
|
|
A309250
|
|
a(n) is the index of the binary string of a Post's Correspondence Problem Encoding with index n.
|
|
1
|
|
|
|
1, 2, 3, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23, 24, 24, 24, 24, 25, 25, 25, 25
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
Listing all valid sequences of pairs ((x1, y1), (x2, y2), ...) with binary strings as values (including leading zeros!), so that each value has at least one digit, this sequence gives the index of the base binary string x1y1x2y2...
The binary strings are assumed to be ordered by (1) length and (2) numeric value, starting (for tuple validity) at length 2: 00, 01, 10, 11, 000, 001, ...
The structure of the sequence becomes clearer as you write all numbers having the same number of occurrences in one line:
1, 2, 3, 4,
5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12,
13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, ...,
29, 29, 29, 29, 29, 29, 29, 29, 30, ...
This connection is an empirical observation.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = 2^(b(n)+2) - 4 + ceiling((n - (4/3)*(4^b(n)-1)) / 2^b(n))
where b(n) = floor(log_4((3/4)*n + 1/4)).
|
|
|
EXAMPLE
|
The first 4 PCP encodings consist of two letters only (binary strings 00, 01, 10, 11). Therefore there is only one valid permutation to generate a PCP: [(first letter, second letter)]. Thus the sequence is a bijection between binary strings and PCPs for the first 4 terms, resulting in the numbers 1, 2, 3, 4. From PCP no. 5 on, the length of the binary string leaves room for permutation (e.g., 000 can be converted to PCPs [(0, 00)] or [(00, 0)]). Therefore, multiple PCP indices are mapped to the same binary string, resulting in the same number of occurrences in the sequence. PCPs no. 5 and 6 are mapped to binary index 5, PCPs no. 7 and 8 are mapped to binary index 6 and so on.
As the number of letters in a given PCP reaches 4, there are 4 possible permutations (e.g., [(0, 000)], [(00, 00)], [(000, 0)], [(0, 0), (0, 0)]), and the corresponding binary string indices occur 4 times in the sequence. For 5 letters, there are 8 possible permutations, and so on.
|
|
|
PROG
|
(Java)
public static long b(long index) {
return (long) (Math.log(((float) 3 / 4) * index + 1) / Math.log(4));
}
public static long a(long index) {
index--;
long l = b(index);
long binIndex = (long) Math.pow(2, l + 2) - 4;
binIndex += (index - (long) (((float) 4/3) * ((Math.pow(4, l) - 1)))) / Math.pow(2, l);
return binIndex + 1;
}
(PARI) b(n) = floor(log((3/4) * n + 1)/log(4));
a(n) = 2^(b(n)+2)-4 + floor( (n - 1 - (4/3) * (4^b(n) - 1)) / 2^b(n) ) + 1; \\ Michel Marcus, Jul 20 2019
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
