A003000 -id:A003000 - cp's OEIS frontend

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.

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

Offset: 0

Danny Rorabaugh, Sep 17 2015

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).

			The constant is 0.11944369525286337300011858612688510481590798881680833086306522202891445594210776107239...

Danny Rorabaugh, Table of n, a(n) for n = 0..185
D. Rorabaugh, Toward the Combinatorial Limit Theory of Free Words, University of South Carolina, ProQuest Dissertations Publishing (2015). See section 5.2.
A. I. Zimin, Blokirujushhie mnozhestva termov (Russian), Mat. Sbornik, 119 (1982), 363-375; Blocking sets of terms (English), Math. USSR-Sbornik, 47 (1984), 353-364.

Cf. A003000, A123121, A262312 (aba).

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)).

A094538 Number of ternary words of length n that are not "bifix-free".

Original entry on oeis.org

0, 0, 3, 9, 33, 99, 315, 945, 2883, 8649, 26091, 78273, 235233, 705699, 2118339, 6355017, 19068729, 57206187, 171629595, 514888785, 1544699313, 4634097939, 13902392691, 41707178073, 125121830427, 375365491281

Offset: 0

N. J. A. Sloane, Jun 06 2004

See A019308 and A003000 for much more information. Cf. A094539.

Equals 3^n - A019308(n).

A094539 a(n) = A094538(n)/3.

Original entry on oeis.org

0, 0, 1, 3, 11, 33, 105, 315, 961, 2883, 8697, 26091, 78411, 235233, 706113, 2118339, 6356243, 19068729, 57209865, 171629595, 514899771, 1544699313, 4634130897, 13902392691, 41707276809, 125121830427, 375365787489, 1126097362467

Offset: 0

N. J. A. Sloane, Jun 06 2004

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Cf. A003000, A019308, A094538.

a[0] = 1; a[n_] := a[n] = 3*a[n - 1] - If[EvenQ[n], a[n/2], 0]; Insert[Table[(3^(n) - a[n])/3, {n, 1, 30}], 0, 1] (* Stefan Steinerberger, Mar 24 2006 *)

More terms from Stefan Steinerberger, Mar 24 2006

A216957 a(1)=2; for n > 1, a(n) = 2^(n-2) + (1/(2n-2)) * Sum_{ d divides n-1 } phi(2d)*2^((n-1)/d).

Original entry on oeis.org

2, 2, 4, 6, 12, 20, 40, 74, 148, 286, 568, 1118, 2228, 4412, 8788, 17480, 34836, 69392, 138388, 275942, 550560, 1098516, 2192572, 4376666, 8738324, 17448308, 34845304, 69594398, 139011816, 277691852, 554767744, 1108378658, 2214594580, 4425117884, 8842583584, 17670722600, 35314182976, 70576759892, 141055781836

Offset: 1

N. J. A. Sloane, Sep 26 2012

nonn

N. J. A. Sloane, Table of n, a(n) for n = 1..1000

Different from, but easily confused with, A003000 and A122536.

with(numtheory);
f:=n-> if n=1 then 2 else 2^(n-2) + (1/(2*n-2)) * add(phi(2*d)*2^((n-1)/d), d in divisors(n-1)); fi;

A342239 Table read by upward antidiagonals: T(n,k) is the number of strings of length k over an n-letter alphabet that are bifix free; n >= 1, k >= 1.

Original entry on oeis.org

1, 2, 0, 3, 2, 0, 4, 6, 4, 0, 5, 12, 18, 6, 0, 6, 20, 48, 48, 12, 0, 7, 30, 100, 180, 144, 20, 0, 8, 42, 180, 480, 720, 414, 40, 0, 9, 56, 294, 1050, 2400, 2832, 1242, 74, 0, 10, 72, 448, 2016, 6300, 11900, 11328, 3678, 148, 0, 11, 90, 648, 3528, 14112, 37620, 59500, 45132, 11034, 284, 0

Offset: 1

Peter Kagey, Mar 06 2021

			Table begins:
n\k | 1  2   3    4     5      6       7        8         9
----+------------------------------------------------------
  1 | 1  0   0    0     0      0       0        0         0
  2 | 2  2   4    6    12     20      40       74       148
  3 | 3  6  18   48   144    414    1242     3678     11034
  4 | 4 12  48  180   720   2832   11328    45132    180528
  5 | 5 20 100  480  2400  11900   59500   297020   1485100
  6 | 6 30 180 1050  6300  37620  225720  1353270   8119620
  7 | 7 42 294 2016 14112  98490  689430  4823994  33767958
  8 | 8 56 448 3528 28224 225344 1802752 14418488 115347904

Peter Kagey, Antidiagonals n = 1..100, flattened

Rows: A003000 (n=2), A019308 (n=3), A019309 (n=4).

Columns: A002378 (k=1), A045991 (k=2), A047927 (k=3).

T(n,0)    = n.
T(n,2k)   = n*T(n,2k-1) - T(n,k).
T(n,2k+1) = n*T(n,2k).

A342241 a(n) is the least k > 0 such that the first k bits and the last k bits in the binary expansion of n are the same.

Original entry on oeis.org

1, 1, 2, 1, 3, 1, 3, 1, 4, 1, 2, 1, 4, 1, 4, 1, 5, 1, 2, 1, 5, 1, 2, 1, 5, 1, 5, 1, 5, 1, 5, 1, 6, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 6, 1, 2, 1, 6, 1, 6, 1, 6, 1, 3, 1, 6, 1, 6, 1, 6, 1, 6, 1, 7, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 7, 1, 2

Offset: 0

Rémy Sigrist, Mar 07 2021

This sequence gives the length of the least nonempty prefix that is also a suffix of the binary expansion of a number.

			For n = 42:
- the binary representation of 42 is "101010",
- the first bit ("1") and the last bit ("0") do not match,
- the first 2 bits ("10") and the last 2 bits ("10") match,
- so a(42) = 2.

Rémy Sigrist, Table of n, a(n) for n = 0..8192
Index entries for sequences related to binary expansion of n

Cf. A003000, A070939, A091065, A342242.

a(n) = { my (b=if (n, binary(n), [0])); for (w=1, oo, if (b[1..w]==b[#b+1-w..#b], return (w))) }

def a(n):
  b = bin(n)[2:]
  for i in range(1, len(b)+1):
    if b[:i] == b[-i:]: return i
print([a(n) for n in range(87)]) # Michael S. Branicky, Mar 07 2021

a(n) = 1 iff n = 0 or n is odd.
a(n) <= A070939(n) with equality iff n belongs to A091065.
a(n) = A070939(A342242(n)).

A345530 Triangle T(n,k) read by rows of the number of n-bit words with maximum overlap k.

Original entry on oeis.org

2, 2, 2, 4, 2, 2, 6, 6, 2, 2, 12, 10, 6, 2, 2, 20, 22, 12, 6, 2, 2, 40, 38, 28, 12, 6, 2, 2, 74, 82, 48, 30, 12, 6, 2, 2, 148, 154, 106, 52, 30, 12, 6, 2, 2, 284, 318, 198, 118, 54, 30, 12, 6, 2, 2, 568, 614, 414, 222, 124, 54, 30, 12, 6, 2, 2

Offset: 1

Sean A. Irvine, Jun 20 2021

Here an overlap means some initial part of the binary word matches exactly the end part of the word. More precisely if B = b_1,b_2,...,b_n is the word, and k is the largest value for which b_i=b_n-k+i for 1 <= i <= k, k < n, then B is said to have a maximum overlap of k. The smallest possible overlap is 0 and largest possible overlap is n-1.
The trivial overlap n=k is ignored.
All terms are even, because a word and its bitwise complement have the same maximum overlap.

			For n=3, the maximum overlaps are as follows:
  000 2,
  001 0,
  010 1,
  011 0,
  100 0,
  101 1,
  110 0,
  111 2;
thus row 3 of the triangle is 4, 2, 2 (4 with overlap 0, 2 with overlap 1, 2 with overlap 2).
The triangle begins:
   2;
   2,  2;
   4,  2, 2;
   6,  6, 2, 2;
  12, 10, 6, 2, 2;
  20, 22, 12, 6, 2, 2;
  ...

Sean A. Irvine, Rows n=1..38 flattened
H. Harborth, Endliche 0-1-Folgen mit gleichen Teilblöcken, J. für Reine Angewandte Math. 271 (1974), 139-154.
Sean A. Irvine, Java program (github)

Cf. A003000, A019310, A019311, A345710.

def maxoverlap(n):
    b = bin(n)[2:]
    for k in range(len(b)-1, -1, -1):
        if b.startswith(b[-k:]): return k
def T(n, k): return 2*sum(maxoverlap(i) == k for i in range(2**(n-1), 2**n))
print([T(n, k) for n in range(1, 12) for k in range(n)]) # Michael S. Branicky, Jun 24 2021

# faster version, using maxoverlap above
from collections import Counter
def row(n):
    c = Counter(maxoverlap(i) for i in range(2**(n-1), 2**n))
    return [2*c[k] for k in range(n)]
def table(r): return [i for n in range(1, r+1) for i in row(n)]
print(table(11)) # Michael S. Branicky, Jun 24 2021

Sum_{k=0..n-1} T(n,k) = 2^k.
T(n,0) = A003000(n).
T(n,1) = A019310(n).
T(n,2) = A019311(n).

A099766 Triangle read by rows: T(n,k) = number of unbordered binary words of length n and weight k, n >= 0, 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 0, 2, 0, 0, 2, 2, 0, 0, 2, 2, 2, 0, 0, 2, 4, 4, 2, 0, 0, 2, 4, 8, 4, 2, 0, 0, 2, 6, 12, 12, 6, 2, 0, 0, 2, 6, 18, 22, 18, 6, 2, 0, 0, 2, 8, 24, 40, 40, 24, 8, 2, 0, 0, 2, 8, 32, 60, 80, 60, 32, 8, 2, 0, 0, 2, 10, 40, 92, 140, 140, 92, 40, 10, 2, 0, 0, 2, 10, 50, 128, 232

Offset: 0

N. J. A. Sloane, Nov 11 2004

			Triangle begins:
.1
.1,1
.0,2,0
.0,2,2,0
.0,2,2,2,0
.0,2,4,4,2,0
.0,2,4,8,4,2,0

T. Harju and D. Nowotka, Counting bordered and primitive words with a fixed weight, TUCS Technical Report, No 630, Turku, November 2004. [This is the triangle U(n,k).]
T. Harju and D. Nowotka, Counting bordered and primitive words with a fixed weight, Theoret. Comput. Sci. 340 (2005), no. 2, 273-279. [This is the triangle U(n,k).]

Row sums give A003000. Cf. A099768, A102416.

U:=proc(n,k) option remember; if n < 1 then RETURN(0); fi; if n = 1 then RETURN(1); fi; if n > 1 and k = 0 then RETURN(0); fi; if k > 1 and k >= n then RETURN(0); fi; U(n-1,k)+U(n-1,k-1)-E(n,k); end;
E:=proc(n,k) option remember; if n mod 2 = 0 and k mod 2 = 0 then U(n/2,k/2) else 0; fi; end;

See Maple code.

A308528 Number of length-n binary words having no nontrivial prefix that is a palindrome of odd length.

Original entry on oeis.org

2, 4, 4, 8, 12, 24, 40, 80, 148, 296, 568, 1136, 2232, 4464, 8848, 17696, 35244, 70488, 140680, 281360, 562152, 1124304, 2247472, 4494944, 8987656, 17975312, 35946160, 71892320, 143775792, 287551584, 575085472, 1150170944, 2300306644, 4600613288, 9201156088

Offset: 1

Jeffrey Shallit, Jun 06 2019

nonn

A nontrivial palindrome is one that is of length at least 2.

For n even we have a(n) = 2a(n-1), and for n odd, a(n) = A003000(n).

			For n = 5, the only words counted are 00101, 00110, 00111, 01100, 01101, 01111 and their binary complements.

Daniel Gabric, Jeffrey Shallit, Borders, Palindrome Prefixes, and Square Prefixes, arXiv:1906.03689 [cs.DM], 2019.

Cf. A003000, A308529.

A330651 a(n) = n^4 + 3n^3 + 2n^2 - 2*n.

Original entry on oeis.org

0, 4, 44, 174, 472, 1040, 2004, 3514, 5744, 8892, 13180, 18854, 26184, 35464, 47012, 61170, 78304, 98804, 123084, 151582, 184760, 223104, 267124, 317354, 374352, 438700, 511004, 591894, 682024, 782072, 892740, 1014754, 1148864, 1295844

Offset: 0

Ed Pegg Jr, Jan 15 2020

a(n)/A269657(n) gives unforgeable word approximations (A003000) with increasing accuracy, as follows: 4/15, 44/79, 174/253, ... ~ 0.26 (A242430), 0.5569 (A019308), 0.68774 (A019309), 0.8055770, 0.83674321, 0.85937882, 0.87654509, 0.89000100, 0.9008270111, ....

Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Cf. A269657, A242430, A003000, A019308, A019309.

A330651 := n -> (((n+3)*n+2)*n-2)*n; # M. F. Hasler, Feb 29 2020

Numerator/@Table[(-2 n+2 n^2+3 n^3+n^4)/(1+3 n+6 n^2+4 n^3+n^4),{n,0,33}] (* Ed Pegg Jr, Jan 15 2020 *)

Vec(2*x*(2 + 12*x - 3*x^2 + x^3) / (1 - x)^5 + O(x^40),-40) \\ Colin Barker, Jan 15 2020

apply( {A330651(n)=(((n+3)*n+2)*n-2)*n}, [0..44]) \\ M. F. Hasler, Feb 29 2020

From Colin Barker, Jan 15 2020: (Start)
G.f.: 2*x*(2 + 12*x - 3*x^2 + x^3) / (1 - x)^5.
a(n) = 5*a(n-1) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + a(n-5) for n>5.
(End)
E.g.f.: exp(x)*x*(4 + 18*x + 9*x^2 + x^3). - Stefano Spezia, Feb 03 2020

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A094538 Number of ternary words of length n that are not "bifix-free".

Views

Author

Keywords

Crossrefs

Formula

A094539 a(n) = A094538(n)/3.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A216957 a(1)=2; for n > 1, a(n) = 2^(n-2) + (1/(2n-2)) * Sum_{ d divides n-1 } phi(2d)*2^((n-1)/d).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A342239 Table read by upward antidiagonals: T(n,k) is the number of strings of length k over an n-letter alphabet that are bifix free; n >= 1, k >= 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A342241 a(n) is the least k > 0 such that the first k bits and the last k bits in the binary expansion of n are the same.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Formula

A345530 Triangle T(n,k) read by rows of the number of n-bit words with maximum overlap k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Python

Formula

A099766 Triangle read by rows: T(n,k) = number of unbordered binary words of length n and weight k, n >= 0, 0 <= k <= n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A308528 Number of length-n binary words having no nontrivial prefix that is a palindrome of odd length.

Views

Author

Keywords

Comments

A330651 a(n) = n^4 + 3n^3 + 2n^2 - 2*n.