Search: a123121 -id:a123121
|
| |
|
|
A262312
|
|
The limit, as word-length approaches infinity, of the probability that a random binary word is an instance of the Zimin pattern "aba"; also the probability that a random infinite binary word begins with an even-length palindrome.
|
|
+10
4
|
|
|
|
7, 3, 2, 2, 1, 3, 1, 5, 9, 7, 8, 2, 1, 1, 0, 8, 8, 7, 6, 2, 3, 3, 2, 8, 5, 9, 6, 4, 1, 5, 6, 9, 7, 4, 4, 7, 4, 4, 4, 9, 4, 0, 1, 0, 2, 0, 0, 6, 5, 1, 5, 4, 6, 7, 9, 2, 3, 6, 8, 8, 1, 1, 1, 4, 8, 8, 7, 8, 5, 0, 6, 2, 2, 1, 4, 7, 6, 7, 2, 3, 7
(list;
constant;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,1
|
|
|
COMMENTS
|
Word W over alphabet L is an instance of "aba" provided there exists a nonerasing monoid homomorphism f:{a,b}*->L* such that f(W)=aba. For example "oompaloompa" is an instance of "aba" via the homomorphism defined by f(a)=oompa, f(b)=l. For a proof of the formula or more information on Zimin words, see Rorabaugh (2015).
The second definition comes from a Comment in A094536: "The probability that a random, infinite binary string begins with an even-length palindrome is: lim n -> infinity a(n)/2^n ~ 0.7322131597821108... . - Peter Kagey, Jan 26 2015"
Also, the limit, as word-length approaches infinity, of the probability that a random binary word has a bifix; that is, 1-x where x is the constant from A242430. - Danny Rorabaugh, Feb 13 2016
|
|
|
LINKS
|
|
|
|
FORMULA
|
The constant is Sum_{n>=0} A003000(n)*(1/4)^n.
Using the recursive definition of A003000, one can derive the series Sum_{j>=0} 2*(-1)^j*(1/4)^(2^j)/(Product_{k=0..j} 1-2*(1/4)^(2^k)), which converges more quickly to the same limit and without having to calculate terms of A003000.
For ternary words, the constant is Sum_{n>=0} A019308(n)*(1/9)^n.
For quaternary words, the constant is Sum_{n>=0} A019309(n)*(1/16)^n.
|
|
|
EXAMPLE
|
0.7322131597821108876233285964156974474449401020065154679236881114887...
|
|
|
PROG
|
(Sage) N(sum([2*(1/4)^(2^j)*(-1)^j/prod([1-2*(1/4)^(2^k) for k in range(j+1)]) for j in range(8)]), digits=81) #For more than 152 digits of accuracy, increase the j-range.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A018238
|
|
Add 1 to leading digit and put in front.
|
|
+10
3
|
| |
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
The concatenation of first n terms (if n is small) yields a palindrome: 1, 121, 1213121, etc. - Amarnath Murthy, Apr 08 2003
This is not the case from n=10 on: According to the formula in A123121 A082215(10) has an even number of digits, the middle digits being "10". (In a strict sense, e.g. Def. 3 of the first reference there, A082215(9) is the last Zimin word on the alphabet {1,...,9}, though.)
While there is less ambiguity about the definition of A018238(10), it is not clear if A018238(11) should start with "11..." or with "10..." (the largest digit of all subsequent terms being "9"). According to the formula in A123121, a(100) has 3 digits more than a(99), so the first choice seems appropriate and has been adopted for the given PARI code.
However, it corresponds to a modified definition, "a(n) = concatenation of n and all preceding terms". a(3) is the only prime term up to a(14) included. The sequence is (1,0,1,0,1,0,...) (mod 3), at least up to a(20). (End)
|
|
|
LINKS
|
|
|
|
PROG
|
(PARI) A018238(n, t="")=for(k=2, n, t=Str(t, k-1, t)); eval(Str(n, t)) \\ M. F. Hasler, May 05 2008
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,base
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A262313
|
|
Decimal expansion of the limit of the probability that a random binary word is an instance of the Zimin pattern "abacaba" as word length approaches infinity.
|
|
+10
3
|
|
|
|
1, 1, 9, 4, 4, 3, 6, 9, 5, 2, 5, 2, 8, 6, 3, 3, 7, 3, 0, 0, 0, 1, 1, 8, 5, 8, 6, 1, 2, 6, 8, 8, 5, 1, 0, 4, 8, 1, 5, 9, 0, 7, 9, 8, 8, 8, 1, 6, 8, 0, 8, 3, 3, 0, 8, 6, 3, 0, 6, 5, 2, 2, 2, 0, 2, 8, 9, 1, 4, 4, 5, 5, 9, 4, 2, 1, 0, 7, 7, 6, 1, 0, 7, 2
(list;
constant;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
Word W over alphabet L is an instance of "abacaba" provided there exists a nonerasing monoid homomorphism f:{a,b,c}*->L* such that f(W)=abacaba. For example "01011010001011010" is an instance of "abacaba" via the homomorphism defined by f(a)=010, f(b)=11, f(c)=0. For a proof of the formula or more information on Zimin words, see Rorabaugh (2015).
|
|
|
LINKS
|
|
|
|
FORMULA
|
The constant is Sum_{n=1..infinity} A003000(n)*(Sum_{i=0..infinity} G_n(i)+H_n(i)), with:
G_n(i) = (-1)^i * r_n((1/2)^(2*2^i)) * (Product_{j=0..i-1} s_n((1/2)^(2*2^j))) / (Product_{k=0..i} 1-2*(1/2)^(2*2^k)),
r_n(x) = 2*x^(2n+1) - x^(4n) + x^(5n) - 2*x^(5n+1) + x^(6n),
s_n(x) = 1 - 2*x^(1-n) + x^(-n);
H_n(i) = (-1)^i * u_n((1/2)^(2*2^i)) * (Product_{j=0..i-1} v_n((1/2)^(2*2^j))) / (Product_{k=0..i} 1-2*(1/2)^(2*2^k)),
u_n(x) = 2*x^(4n+1) - x^(5n) + 2*x^(5n+1) + x^(6n),
v_n(x) = 1 - 2*x^(1-n) + x^(-n) - 2*x^(1-2n) + x^(-2n).
The inside sum is an alternating series and the outside sum has positive terms and a simple tail bound. Consequentially, we have the following bounds with any positive integers N and K:
Lower bound, Sum_{n=1..N} A003000(n)*(Sum_{i=0..2K-1} G_n(i)+H_n(i));
Upper bound, (1/2)^N + Sum_{n=1..N} A003000(n)*(Sum_{i=0..2K} G_n(i)+H_n(i)).
|
|
|
EXAMPLE
|
The constant is 0.11944369525286337300011858612688510481590798881680833086306522202891445594210776107239...
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
| |
|
|
|
1, 121, 1213121, 121312141213121, 1213121412131215121312141213121, 121312141213121512131214121312161213121412131215121312141213121, 1213121412131215121312141213121612131214121312151213121412131217121312141213121512131214121312161213121412131215121312141213121
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
Also called Zimin words.
a(n) is a palindrome for n<10; it is debatable whether a(n) can be called a Zimin word for n>=10 (see the Comments in A018238). - Danny Rorabaugh, Sep 26 2015
|
|
|
LINKS
|
|
|
|
FORMULA
|
The Zimin words are defined here by Z_1 = 1, Z_n = Z_{n-1}nZ_{n-1}. - Dmitry Kamenetsky, Sep 30 2006
|
|
|
MATHEMATICA
|
a = {1}; Do[w = IntegerDigits@ a[[n - 1]]; AppendTo[a, FromDigits@ Join[w, IntegerDigits@ n, w]], {n, 2, 7}]; a (* Michael De Vlieger, Sep 26 2015 *)
|
|
|
CROSSREFS
|
See A001511 for another representation of this sequence of digits.
|
|
|
KEYWORD
|
base,nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
"Palindromes" replaced with "Numbers" in sequence name by Danny Rorabaugh, Sep 26 2015
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A262500
|
|
Number of binary, minimal instances of Zimin word Z_n that begin with 0.
|
|
+10
1
|
| |
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
Zimin words are defined recursively by Z_1 = x_1, Z_{n+1} = Z_nx_{n+1}Z_n. Using a different alphabet: Z_1 = a, Z_2 = aba, Z_3 = abacaba, ... .
Word W over alphabet L is an instance of Z_n provided there exists a nonerasing monoid homomorphism f:{x_1,...,x_n}*->L* such that f(W)=Z_n. For example "abracadabra" is an instance of Z_2 via the homomorphism defined by f(x_1)=abra, f(x_2)=cad.
An instance W is minimal if no proper substring of W is also an instance.
The total number of minimal Z_n-instances over the alphabet {0,1} is 2*a(n).
The minimal, binary Z_3-instances have lengths ranging from 7 to 25. There exist minimal, binary Z_4-instances over 10000 letters long.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
The a(1)=1 instance of Z_1 is '0'.
The a(2)=3 instances of Z_2 are '000', '010', and '0110'. '01110' is not a minimal instance because it contains Z_2-instance '111' as a proper subword.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,bref,hard,more
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
Search completed in 0.010 seconds
|
