A003000 -id:A003000 - cp's OEIS frontend

A242430 Decimal expansion of the unforgeable pattern-free binary word constant, a constant mentioned in A003000.

2, 6, 7, 7, 8, 6, 8, 4, 0, 2, 1, 7, 8, 8, 9, 1, 1, 2, 3, 7, 6, 6, 7, 1, 4, 0, 3, 5, 8, 4, 3, 0, 2, 5, 5, 2, 5, 5, 5, 0, 5, 9, 8, 9, 7, 9, 9, 3, 4, 8, 4, 5, 3, 2, 0, 7, 6, 3, 1, 1, 8, 8, 8, 5, 1, 1, 2, 1, 4, 9, 3, 7, 7, 8, 5, 2, 3, 2, 7, 6, 2, 8, 5, 3, 5, 4, 4, 7, 6, 2, 2, 3, 8, 5, 6, 1, 3, 6, 8, 4

Offset: 0

Jean-François Alcover, May 14 2014

A binary word (a word over a 2-letter alphabet) is said "unforgeable" if it never matches a left or right shift of itself. The limit lower bound of the number of unforgeable words of length n is (0.26778684...)*2^n.

			0.267786840217889112376671403584302552555...

Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, p. 369.
See more references and links in A003000, which is the main entry for this subject.

Cf. A003000, A006156, A007777, A028445, A045690.

digits = 100; k0 = 5; dk = 5; Clear[r]; r[k_] := r[k] = Sum[(-1)^(n-1)*2/(2^(2^(n+1)-1)-1) * Product[2^(2^m-1)/(2^(2^m-1)-1), {m, 2, n}], {n, 1, k}] // N[#, digits+10]&; r[k0]; r[k = k0 + dk]; While[RealDigits[r[k], 10, digits+10] !=  RealDigits[r[k - dk], 10, digits+10], Print["k = ", k]; k = k + dk]; RealDigits[r[k], 10, digits] // First

A218874 (A122536(n)-A003000(n))/2.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 4, 8, 18, 36, 73, 146, 295, 590, 1182, 2364, 4732, 9464, 18929, 37858, 75721, 151442, 302878, 605756, 1211504, 2423008, 4845968, 9691936, 19383784, 38767568, 77534894, 155069788, 310139104, 620278208, 1240555349

Offset: 1

N. J. A. Sloane, Nov 09 2012

nonn

If a formula or recurrence were known it would explain the mysterious sequence A122536.

200 terms are known from the b-files for A122536 and A003000.

B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, arXiv:1212.6102, Dec 25 2012.
B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, Journal of Integer Sequences, Vol. 16 (2013), Article 13.4.3.
Index entries for sequences related to curling numbers

Cf. A122536, A003000.

A045690 Number of binary words of length n (beginning with 0) whose autocorrelation function is the indicator of a singleton.

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 20, 37, 74, 142, 284, 558, 1116, 2212, 4424, 8811, 17622, 35170, 70340, 140538, 281076, 561868, 1123736, 2246914, 4493828, 8986540, 17973080, 35943948, 71887896, 143771368, 287542736, 575076661, 1150153322, 2300289022, 4600578044, 9201120918

Offset: 1

Torsten.Sillke(AT)uni-bielefeld.de

The number of binary strings sharing the same autocorrelations.
Appears to be row sums of A155092, beginning from a(2). - Mats Granvik, Jan 20 2009
The number of binary words of length n (beginning with 0) which do not start with an even palindrome (i.e. which are not of the form ss*t where s is a (nonempty) word, s* is its reverse, and t is any (possibly empty) word). - Mamuka Jibladze, Sep 30 2014
From Gus Wiseman, Mar 08 2021: (Start)
This sequence counts each of the following essentially equivalent things:
1. Sets of distinct positive integers with maximum n in which all adjacent elements have quotients > 1/2. For example, the a(1) = 1 through a(6) = 10 sets are:
  {1}  {2}  {3}    {4}      {5}        {6}
            {2,3}  {3,4}    {3,5}      {4,6}
                   {2,3,4}  {4,5}      {5,6}
                            {2,3,5}    {3,4,6}
                            {3,4,5}    {3,5,6}
                            {2,3,4,5}  {4,5,6}
                                       {2,3,4,6}
                                       {2,3,5,6}
                                       {3,4,5,6}
                                       {2,3,4,5,6}
2. For n > 1, sets of distinct positive integers with maximum n - 1 whose first-differences are term-wise less than their decapitation (remove the maximum). For example, the set q = {2,4,5} has first-differences (2,1), which are not less than (2,4), so q is not counted under a(5). On the other hand, r = {2,3,5,6} has first-differences {1,2,1}, which are less than {2,3,5}, so r is counted under a(6).
3. Compositions of n where each part after the first is less than the sum of all preceding parts. For example, the a(1) = 1 through a(6) = 10 compositions are:
  (1)  (2)  (3)   (4)    (5)     (6)
            (21)  (31)   (41)    (51)
                  (211)  (32)    (42)
                         (311)   (411)
                         (212)   (321)
                         (2111)  (312)
                                 (3111)
                                 (2121)
                                 (2112)
                                 (21111)
(End)

Alois P. Heinz, Table of n, a(n) for n = 1..3324 (first 500 terms from T. D. Noe)
E. H. Rivals, Autocorrelation of Strings.
E. H. Rivals, S. Rahmann Combinatorics of Periods in Strings
E. H. Rivals, S. Rahmann, Combinatorics of Periods in Strings, Journal of Combinatorial Theory - Series A, Vol. 104(1) (2003), pp. 95-113.
T. Sillke, How many words have the same autocorrelation value?

Cf. A002083, A005434. A003000 = 2*a(n) for n > 0.
Different from, but easily confused with, A007148 and A093371.
The version with quotients <= 1/2 is A018819.
The version with quotients < 1/2 is A040039.
Multiplicative versions are A337135, A342083, A342084, A342085.
A000045 counts sets containing n with all differences > 2.
A000929 counts partitions with no adjacent parts having quotient < 2.
A342094 counts partitions with no adjacent parts having quotient > 2.
Cf. A003242, A038548, A056924, A154402, A167606, A342096, A342097, A342098, A342191.

a:= proc(n) option remember; `if`(n=0, 1/2,
       2*a(n-1)-`if`(n::odd, 0, a(n/2)))
    end:
seq(a(n), n=1..40);  # Alois P. Heinz, Jun 24 2021

a[1] = 1; a[n_] := a[n] = If[EvenQ[n], 2*a[n-1] - a[n/2], 2*a[n-1]]; Array[a, 40] (* Jean-François Alcover, Jul 17 2015 *)
Table[Length[Select[Subsets[Range[n]],MemberQ[#,n]&&Min@@Divide@@@Partition[#,2,1]>1/2&]],{n,8}] (* Gus Wiseman, Mar 08 2021 *)

a(n)=if(n<2,n>0,2*a(n-1)-(1-n%2)*a(n\2))

a(2n) = 2*a(2n-1) - a(n) for n >= 1; a(2n+1) = 2*a(2n) for n >= 1.

a(n) = A342085(2^n). - Gus Wiseman, Mar 08 2021

More terms from James Sellers.

Additional comments from Michael Somos, Jun 09 2000

A122536 Number of binary sequences of length n with no initial repeats (or, with no final repeats).

Original entry on oeis.org

2, 2, 4, 6, 12, 20, 40, 74, 148, 286, 572, 1124, 2248, 4460, 8920, 17768, 35536, 70930, 141860, 283440, 566880, 1133200, 2266400, 4531686, 9063372, 18124522, 36249044, 72493652, 144987304, 289965744

Offset: 1

Sarah Nibs, Sep 18 2006

nonn

An initial repeat of a string S is a number k>=1 such that S(i)=S(i+k) for i=0..k-1. In other words, the first k symbols are the same as the next k symbols, e.g., ABCDABCDZQQ has an initial repeat of size 4.

Equivalently, this is the number of binary sequences of length n with curling number 1. See A216955. - N. J. A. Sloane, Sep 26 2012

			a(4)=6: 0100, 0110, 0111, 1000, 1001 and 1011. (But not 00**, 11**, 0101, 1010.)

Allan Wilks, Table of n, a(n) for n = 1..200 (The first 71 terms were computed by _N. J. A. Sloane_.)
B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, arXiv:1212.6102 [math.CO], 2012-2013.
B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, Journal of Integer Sequences, Vol. 16 (2013), Article 13.4.3.
Daniel Gabric, Jeffrey Shallit, Borders, Palindrome Prefixes, and Square Prefixes, arXiv:1906.03689 [cs.DM], 2019.
Sarah Nibs, Java program for this sequence and A003000
Index entries for sequences related to curling numbers

Twice A093371. Leading column of each of the triangles A216955, A217209, A218869, A218870. Different from, but easily confused with, A003000 and A216957. - N. J. A. Sloane, Sep 26 2012

See A121880 for difference from 2^n.

Conjecture:  a_n ~ C * 2^n where C is 0.27004339525895354325... [Chaffin, Linderman, Sloane, Wilks, 2012]
a(2n+1)=2*a(2n) = A211965(n+1), a(2n)=2*a(2n-1)-A216958(n) = A211966(n). - N. J. A. Sloane, Sep 28 2012
a(1) = 2; a(2n) = 2*[a(2n-1) - A216959(n)], n >= 1. - Daniel Forgues, Feb 25 2015

a(31)-a(71) computed from recurrence and the first 30 terms of A216958 by N. J. A. Sloane, Sep 28 2012, Oct 25 2012

A052944 a(n) = 2^n + n - 1.

Original entry on oeis.org

0, 2, 5, 10, 19, 36, 69, 134, 263, 520, 1033, 2058, 4107, 8204, 16397, 32782, 65551, 131088, 262161, 524306, 1048595, 2097172, 4194325, 8388630, 16777239, 33554456, 67108889, 134217754, 268435483, 536870940, 1073741853, 2147483678

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Shortest length of bit-string containing all bit-strings of given length n. - Rainer Rosenthal, Apr 30 2003
Such a bitstring can be obtained by taking a length-2^n binary de Bruijn sequence and repeating the n-1 initial symbols at the end. - Joerg Arndt, Mar 16 2015
Bit string definition is equivalent to minimum number of tosses of a coin to achieve all possible outcomes of n tosses. - Maurizio De Leo, Mar 01 2015
Also the indices of Fermat numbers that can be represented as cyclotomic numbers. Specifically, F(a(n)) = cyclotomic(2^2^n,2^2^n). - T. D. Noe, Oct 17 2003
a(n) = A006127(n) - 1. - Reinhard Zumkeller, Apr 13 2011
Randomly select (with uniform distribution) a length n binary word w. a(n) is apparently the expected wait time for the first occurrence of w over all infinite binary sequences. For example: a(4)=19. We consider A005434(4)=4 distinct classes of length 4 binary words that share the same autocorrelation. There are A003000(4)=6 words that have waiting time = 16; 2 words with waiting time =20; 6 words with waiting time = 18; and 2 words with waiting time =30. 1/16*(6*16 + 2*20 + 6*18 + 2*30) = 19. - Geoffrey Critzer, Feb 27 2014

			a(3) = 10 because "0001110100" has length 10 and contains all possible patterns of 3 bits:
  0001110100
  ----------
  000.......
  .001......
  ......010.
  ..011.....
  .......100
  .....101..
  ....110...
  ...111....

Discussed in newsgroup de.rec.denksport in Apr 2003
N. G. de Bruijn: A combinatorial problem. Indagationes Math. 8 (1946), pp. 461-467.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Adam M. Goyt and Lara K. Pudwell, Avoiding colored partitions of two elements in the pattern sense, arXiv preprint arXiv:1203.3786 [math.CO], 2012; J. Int. Seq. 15 (2012) # 12.6.2.
A. M. Hinz, S. Klavžar, U. Milutinović, C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 178. Book's website
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1001
Viktor Lopatkin, Pasha Zusmanovich, Commutative Lie algebras and commutative cohomology in characteristic 2, arXiv:1907.03690 [math.KT], 2019.
T. Manneville, V. Pilaud, Compatibility fans for graphical nested complexes, arXiv preprint arXiv:1501.07152 [math.CO], 2015-2016.
E. H. Rivals, Autocorrelation of Strings.
Eric Weisstein's World of Mathematics, Cyclotomic Polynomial
Eric Weisstein's World of Mathematics, Coin Tossing
Index entries for linear recurrences with constant coefficients, signature (4,-5,2).

Cf. A000051, A000215, A160692.

List([0..40], n-> 2^n +n-1); # G. C. Greubel, Oct 18 2019

[2^n + n - 1: n in [0..40]]; // Vincenzo Librandi, Jun 20 2011

spec:= [S,{S=Prod(Union(Sequence(Union(Z,Z)),Sequence(Z)),Sequence(Z))}, unlabeled ]: seq(combstruct[count ](spec,size=n), n=0..20);
seq(2^n + n-1, n=0..40); # G. C. Greubel, Oct 18 2019

Table[2^n+n-1, {n,0,40}] (* Vladimir Joseph Stephan Orlovsky, Oct 25 2008 *)

a(n)=2^n+n-1 \\ Charles R Greathouse IV, Nov 20 2011

[2^n +n-1 for n in (0..40)] # G. C. Greubel, Oct 18 2019

G.f.: (2-3*x)/((1-2*x)*(1-x)^2).
a(n+1) = 2*a(n) - n + 2 with a(0)=0. - Pieter Moree, Mar 06 2004
For n>=1: partial sums of A000051. - Emeric Deutsch, Mar 04 2004
a(0)=0, a(1)=2, a(2)=5, a(n+3) = 4*a(n+2) - 5*a(n+1) + 2*a(n). - Hermann Kremer (Hermann.Kremer(AT)online.de), Mar 16 2004
a(n) = A000225(n) + n. - Zerinvary Lajos, May 29 2009
E.g.f.: U(0), where U(k) = 1 + x/(2^k + 2^k/(x - 1 - x^2*2^(k+1)/(x*2^(k+1) - (k+1)/U(k+1) )));(continued fraction, 3rd kind, 4-step ). - Sergei N. Gladkovskii, Dec 01 2012
G.f.: G(0)*x/(1-x) where G(k) = 1 + 2^k/(1 - x/(x + 2^k/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, May 24 2013
G.f.: Q(0)*x/(1-x), where Q(k)= 1 + 1/(2^k - 2*x*4^k/(2*x*2^k + 1/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 24 2013
E.g.f.: exp(2*x) - (1-x)*exp(x). - G. C. Greubel, Oct 18 2019

A350844 Number of strict integer partitions of n with no difference -2.

Original entry on oeis.org

1, 1, 1, 2, 1, 3, 3, 4, 4, 7, 7, 8, 11, 12, 15, 18, 21, 23, 31, 32, 40, 45, 54, 59, 73, 78, 94, 106, 122, 136, 161, 177, 203, 231, 259, 293, 334, 372, 417, 476, 525, 592, 663, 742, 821, 931, 1020, 1147, 1271, 1416, 1558, 1752, 1916, 2137, 2357, 2613, 2867

Offset: 0

Gus Wiseman, Jan 21 2022

nonn

			The a(1) = 1 through a(12) = 11 partitions (A..C = 10..12):
  1   2   3    4   5    6     7    8     9     A      B     C
          21       32   51    43   62    54    73     65    84
                   41   321   52   71    63    82     74    93
                              61   521   72    91     83    A2
                                         81    541    92    B1
                                         432   721    A1    543
                                         621   4321   632   651
                                                      821   732
                                                            741
                                                            921
                                                            6321

Gus Wiseman, Sequences counting and ranking partitions and compositions by their differences and quotients.

The version for no difference 0 is A000009.
The version for no difference > -2 is A001227, non-strict A034296.
The version for no difference -1 is A003114 (A325160).
The version for subsets of prescribed maximum is A005314.
The version for all differences < -2 is A025157, non-strict A116932.
The opposite version is A072670.
The multiplicative version is A350840, non-strict A350837 (A350838).
The non-strict version is A350842.
A000041 counts integer partitions.
A027187 counts partitions of even length.
A027193 counts partitions of odd length (A026424).
A116931 counts partitions with no difference -1 (A319630).
A323092 counts double-free integer partitions (A320340) strict A120641.
A325534 counts separable partitions (A335433).
A325535 counts inseparable partitions (A335448).
Cf. A000929, A003000, A018819, A040039, A045690, A045691, A154402, A303362, A323094, A342095, A342097.

Table[Length[Select[IntegerPartitions[n],FreeQ[Differences[#],0|-2]&]],{n,0,30}]

A350837 Number of integer partitions of n with no adjacent parts of quotient 2.

Original entry on oeis.org

1, 1, 2, 2, 4, 5, 7, 10, 14, 18, 24, 31, 41, 53, 70, 87, 112, 140, 178, 221, 277, 344, 428, 526, 648, 792, 971, 1180, 1436, 1738, 2103, 2533, 3049, 3660, 4387, 5242, 6259, 7450, 8860, 10511, 12453, 14723, 17387, 20489, 24121, 28343, 33269, 38982, 45632, 53327

Offset: 0

Gus Wiseman, Jan 18 2022

nonn

The first of these partitions that is not double-free (see A323092 for definition) is (4,3,2).

			The a(1) = 1 through a(7) = 10 partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)
       (11)  (111)  (22)    (32)     (33)      (43)
                    (31)    (41)     (51)      (52)
                    (1111)  (311)    (222)     (61)
                            (11111)  (411)     (322)
                                     (3111)    (331)
                                     (111111)  (511)
                                               (4111)
                                               (31111)
                                               (1111111)

Gus Wiseman, Sequences counting and ranking partitions and compositions by their differences and quotients.

The version with quotients >= 2 is A000929, sets A018819.
                           <= 2 is A342094, ranked by A342191.
                           < 2 is A342096, sets A045690, strict A342097.
                           > 2 is A342098, sets A040039.
The sets version (subsets of prescribed maximum) is A045691.
These partitions are ranked by A350838.
The strict case is A350840.
A version for differences is A350842, strict A350844.
The complement is counted by A350846, ranked by A350845.
A000041 = integer partitions.
A116931 = partitions with no successions, ranked by A319630.
A116932 = partitions with differences != 1 or 2, strict A025157.
A323092 = double-free partitions, ranked by A320340.
Cf. A000070, A003000, A003114, `A003242, A051424, `A101417, A120641, A154402, A305148, A323093, A323094, A342095, A350839.

Table[Length[Select[IntegerPartitions[n], FreeQ[Divide@@@Partition[#,2,1],2]&]],{n,0,15}]

A350838 Heinz numbers of partitions with no adjacent parts of quotient 2.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 22, 23, 25, 26, 27, 28, 29, 31, 32, 33, 34, 35, 37, 38, 39, 40, 41, 43, 44, 45, 46, 47, 49, 50, 51, 52, 53, 55, 56, 57, 58, 59, 61, 62, 64, 67, 68, 69, 70, 71, 73, 74, 75, 76, 77, 79, 80, 81, 82, 83

Offset: 1

Gus Wiseman, Jan 18 2022

nonn

Differs from A320340 in having 105: (4,3,2), 315: (4,3,2,2), 455: (6,4,3), etc.

The Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k), so these are numbers with no adjacent prime indices of quotient 1/2.

			The terms and their prime indices begin:
      1: {}            19: {8}             38: {1,8}
      2: {1}           20: {1,1,3}         39: {2,6}
      3: {2}           22: {1,5}           40: {1,1,1,3}
      4: {1,1}         23: {9}             41: {13}
      5: {3}           25: {3,3}           43: {14}
      7: {4}           26: {1,6}           44: {1,1,5}
      8: {1,1,1}       27: {2,2,2}         45: {2,2,3}
      9: {2,2}         28: {1,1,4}         46: {1,9}
     10: {1,3}         29: {10}            47: {15}
     11: {5}           31: {11}            49: {4,4}
     13: {6}           32: {1,1,1,1,1}     50: {1,3,3}
     14: {1,4}         33: {2,5}           51: {2,7}
     15: {2,3}         34: {1,7}           52: {1,1,6}
     16: {1,1,1,1}     35: {3,4}           53: {16}
     17: {7}           37: {12}            55: {3,5}

The version with quotients >= 2 is counted by A000929, sets A018819.
                           <= 2 is A342191, counted by A342094.
                           < 2 is counted by A342096, sets A045690.
                           > 2 is counted by A342098, sets A040039.
The sets version (subsets of prescribed maximum) is counted by A045691.
These partitions are counted by A350837.
The strict case is counted by A350840.
For differences instead of quotients we have A350842, strict A350844.
The complement is A350845, counted by A350846.
A000041 = integer partitions.
A000045 = sets containing n with all differences > 2.
A003114 = strict partitions with no successions, ranked by A325160.
A056239 adds up prime indices, row sums of A112798, counted by A001222.
A116931 = partitions with no successions, ranked by A319630.
A116932 = partitions with differences != 1 or 2, strict A025157.
A323092 = double-free integer partitions, ranked by A320340.
A350839 = partitions with gaps and conjugate gaps, ranked by A350841.
Cf. A000302, A001105, A003000, A018819, A094537, A120641, A154402, A319613, A323093, A337135, A342097, A342095.

primeptn[n_]:=If[n==1,{},Reverse[Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]]];
Select[Range[100],And@@Table[FreeQ[Divide@@@Partition[primeptn[#],2,1],2],{i,2,PrimeOmega[#]}]&]

A019308 Number of "bifix-free" words of length n over a three-letter alphabet.

Original entry on oeis.org

1, 3, 6, 18, 48, 144, 414, 1242, 3678, 11034, 32958, 98874, 296208, 888624, 2664630, 7993890, 23977992, 71933976, 215790894, 647372682, 1942085088, 5826255264, 17478666918, 52436000754, 157307706054, 471923118162

Offset: 0

Jeffrey Shallit

nonn

E. Barcucci, A. Bernini, S. Bilotta, R. Pinzani, Cross-bifix-free sets in two dimensions, arXiv preprint arXiv:1502.05275 [cs.DM], 2015.
S. Bilotta, E. Pergola and R. Pinzani, A new approach to cross-bifix-free sets, arXiv preprint arXiv:1112.3168 [cs.FL], 2011.
Joshua Cooper and Danny Rorabaugh, Asymptotic Density of Zimin Words, arXiv preprint arXiv:1510.03917
T. Harju and D. Nowotka, Border correlation of binary words.
P. Tolstrup Nielsen, A note on bifix-free sequences, IEEE Trans. Info. Theory IT-19 (1973), 704-706.
D Rorabaugh, Toward the Combinatorial Limit Theory of Free Words, arXiv preprint arXiv:1509.04372, 2015

Equals 3*A045694(n) for n>0. Cf. A003000, A019309.

a[0]=1; a[n_]:=a[n]=3*a[n-1]-If[EvenQ[n], a[n/2], 0] (* Ed Pegg Jr, Jan 05 2005 *)

a(2n+1) = 3a(2n); a(2n) = 3a(2n-1) - a(n).

A094536 Number of binary words of length n that are not "bifix-free".

Original entry on oeis.org

0, 0, 2, 4, 10, 20, 44, 88, 182, 364, 740, 1480, 2980, 5960, 11960, 23920, 47914, 95828, 191804, 383608, 767500, 1535000, 3070568, 6141136, 12283388, 24566776, 49135784, 98271568, 196547560, 393095120, 786199088, 1572398176, 3144813974

Offset: 0

N. J. A. Sloane, Jun 06 2004

Also the number of binary strings of length n that begin with an even length palindrome. (E.g., f(4) = 10 with strings 0000 0001 0010 0011 0110 1001 1100 1101 1110 1111.) - Peter Kagey, Jan 11 2015

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

Peter Kagey, Table of n, a(n) for n = 0..1000

See A003000 for much more information.
Cf. A094537.
A254128(n) gives the number of binary strings of length n that begin with an odd-length palindrome.

a[0]:= 0:
for n from 1 to 100 do
if n::odd then a[n]:= 2*a[n-1]
else a[n]:= 2*a[n-1] + 2^(n/2) - a[n/2]
fi
od:
seq(a[i],i=0..100); # Robert Israel, Jan 12 2015

b[0]=1;b[n_]:=b[n]=2*b[n-1]-(1+(-1)^n)/2*b[Floor[n/2]]; a[n_]:=2^n-b[n];Table[a[n], {n, 0, 34}]

s = [0,0]
(2..N).each { |n| s << 2 * s[-1] + (n.odd? ? 0 : 2**(n/2) - s[n/2]) }

a(n) = 2^n - A003000(n).
Let b(0)=1; b(n) = 2*b(n-1) - 1/2*(1+(-1)^n)*b([n/2]); a(n) = 2^n - b(n). - Farideh Firoozbakht, Jun 10 2004
a(0) = 0; a(1) = 0; a(2*n+1) = 2*a(2*n); a(2*n) = 2*a(2*n-1) + 2^n - a(n). - Peter Kagey, Jan 11 2015
G.f. g(x) satisfies (1-2*x)*g(x) = 2*x^2/(1-2*x^2) - g(x^2). - Robert Israel, Jan 12 2015

More terms from Farideh Firoozbakht, Jun 10 2004

Corrected by Don Rogers (donrogers42(AT)aol.com), Feb 15 2005

cp's OEIS Frontend

A242430 Decimal expansion of the unforgeable pattern-free binary word constant, a constant mentioned in A003000.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Mathematica

A218874 (A122536(n)-A003000(n))/2.

Views

Author

Keywords

Comments

Links

Crossrefs

A045690 Number of binary words of length n (beginning with 0) whose autocorrelation function is the indicator of a singleton.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A122536 Number of binary sequences of length n with no initial repeats (or, with no final repeats).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A052944 a(n) = 2^n + n - 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A350844 Number of strict integer partitions of n with no difference -2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A350837 Number of integer partitions of n with no adjacent parts of quotient 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A350838 Heinz numbers of partitions with no adjacent parts of quotient 2.

Views

Author