A286262 -id:A286262 - cp's OEIS frontend

A028445 Number of cubefree words of length n on two letters.

1, 2, 4, 6, 10, 16, 24, 36, 56, 80, 118, 174, 254, 378, 554, 802, 1168, 1716, 2502, 3650, 5324, 7754, 11320, 16502, 24054, 35058, 51144, 74540, 108664, 158372, 230800, 336480, 490458, 714856, 1041910, 1518840, 2213868, 3226896, 4703372, 6855388, 9992596

Offset: 0

Anne Edlin (anne(AT)euclid.math.temple.edu)

nonn

It appears that the number of maximal cubefree words A282133(n) ~ a(n-11). - M. F. Hasler, May 05 2017

S. R. Finch, Mathematical Constants, Cambridge, 2003, see page 368 for cubefree words.

Michael S. Branicky, Table of n, a(n) for n = 0..60 (terms 0..47 entered by Charles R Greathouse IV from Edlin paper)
Anne E. Edlin, Cubefree words [Broken link]
Anne E. Edlin, Cubefree words [Cached copy, pdf version, with permission]
Anne E. Edlin, The number of binary cubefree words of length up to 47 and their numerical analysis [Cached copy, with permission]
Anne E. Edlin, Maple package "Cubefree" [Cached copy, with permission]
Anne E. Edlin, Maple package "GJseries" [Cached copy, with permission]
Mari Huova, Combinatorics on Words. New Aspects on Avoidability, Defect Effect, Equations and Palindromes, Turku Centre for Computer Science, TUCS Dissertations No 172, April 2014.
K. Jarhumaki and J. Shallit, Polynomial vs Exponential Growth in Repetition-Free Binary Words, arXiv:math/0304095 [math.CO], 2003.
R. Kolpakov, Efficient Lower Bounds on the Number of Repetition-free Words, J. Integer Sequences, Vol. 10 (2007), Article 07.3.2.
A. M. Shur, Growth properties of power-free languages, Computer Science Review, Vol. 6 (2012), 187-208.
A. M. Shur, Numerical values of the growth rates of power-free languages, arXiv:1009.4415 [cs.FL], 2010.
Eric Weisstein's World of Mathematics, Cubefree Word.

Cf. A007777, A082379, A082380, A286262.

A282133 gives the maximally cubefree words.

isCubeFree:=proc(v) local n,L;
for n from 3 to nops(v) do for L to n/3 do
if v[n-L*2+1 .. n] = v[n-L*3+1 .. n-L] then RETURN(false) fi od od; true end;
A028445:=proc(n) local s,m;
if n=0 then 1 else add( `if`(isCubeFree(convert(m,base,2)),2,0), m = 2^(n-1)..2^n-1) fi end;
[seq(A028445(n),n=0..10)];  # M. F. Hasler, May 04 2017

Length/@NestList[DeleteCases[Flatten[Outer[Append, #, {0, 1}, 1], 1], {_, x__, x__, x__, _}] &, {{}}, 20] (* Vladimir Reshetnikov, May 16 2016 *)

(isCubeFree(v)=!for(n=3,#v,for(L=1,n\3,v[n-L*2+1..n]==v[n-L*3+1..n-L]&&return))); A028445(n)=sum(m=1<<(n-1)+1<<(n-4),1<M. F. Hasler, May 04 2017

from itertools import product
def cf(s):
    for l in range(1, len(s)//3 + 1):
      for i in range(len(s) - 3*l + 1):
          if s[i:i+l] == s[i+l:i+2*l] == s[i+2*l:i+3*l]: return False
    return True
def a(n):
    if n == 0: return 1
    return 2*sum(1 for w in product("01", repeat=n-1) if cf("0"+"".join(w)))
print([a(n) for n in range(21)]) # Michael S. Branicky, Mar 13 2022

# faster, but > memory, version for initial segment of sequence
def icf(s): # incrementally cubefree
    for l in range(1, len(s)//3 + 1):
        if s[-3*l:-2*l] == s[-2*l:-l] == s[-l:]: return False
    return True
def aupton(nn, verbose=False):
    alst, cfs = [1], set("0")
    for n in range(1, nn+1):
        an = 2*len(cfs)
        cfsnew = set(c+i for c in cfs for i in "01" if icf(c+i))
        alst, cfs = alst+[an], cfsnew
        if verbose: print(n, an)
    return alst
print(aupton(30)) # Michael S. Branicky, Mar 13 2022

Let L = lim a(n)^(1/n); then L exists since a(n) is submultiplicative, and 1.4575732 < L < 1.4575772869240 (Shur 2010). Empirical: L=1.4575772869237..., i.e. the upper bound is very precise. - Arseny Shur, Apr 27 2015

a(29)-a(36) from Lars Blomberg, Aug 22 2013

A063037 Numbers without 3 consecutive equal binary digits.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 9, 10, 11, 12, 13, 18, 19, 20, 21, 22, 25, 26, 27, 36, 37, 38, 41, 42, 43, 44, 45, 50, 51, 52, 53, 54, 73, 74, 75, 76, 77, 82, 83, 84, 85, 86, 89, 90, 91, 100, 101, 102, 105, 106, 107, 108, 109, 146, 147, 148, 149, 150, 153, 154, 155, 164, 165, 166

Offset: 1

Lior Manor, Jul 05 2001

Complement of A136037; intersection of A003796 and A003726. - Reinhard Zumkeller, Dec 11 2007
From Emeric Deutsch, Jan 27 2018: (Start)
Also 0 together with the indices of the compositions that have no parts larger than 2. For the definition of the index of a composition see A298644.
For example, 105 is in the sequence since its binary form is 1101001 and the composition [2,1,1,2,1] has no parts larger than 2.
On the other hand, 132 is not in the sequence since its binary form is 10000100 and the composition [1,4,1,2] has a part larger than 2.
The command c(n) from the Maple program yields the composition having index n. (End)
The sequence contains A000045(n+1) positive terms with binary length n. - Rémy Sigrist, Sep 30 2022

			The binary representation of 9 (1001) has no 3 consecutive equal digits.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A000045, A000975, A166535, A286262.

isA063037 := proc(n)
    local bdgs,rep,d,i ;
    if n = 0 then
        return true;
    end if;
    bdgs := convert(n,base,2) ;
    rep := 1;
    d := op(1,bdgs) ;
    for i from 2 to nops(bdgs) do
        if op(i,bdgs) = op(i-1,bdgs) then
            rep := rep+1 ;
        else
            rep :=1 ;
        end if ;
        if rep > 2 then
            return false;
        end if;
    end do:
    return true ;
end proc:
for n from 0 to 50 do
    if isA063037(n) then
        printf("%d,",n) ;
    end if;
end do: # R. J. Mathar, Dec 18 2013
# Second Maple program:
Runs := proc (L) local j, r, i, k: j := 1: r[j] := L[1]: for i from 2 to nops(L) do if L[i] = L[i-1] then r[j] := r[j], L[i] else j := j+1: r[j] := L[i] end if end do: [seq([r[k]], k = 1 .. j)] end proc: RunLengths := proc (L) map(nops, Runs(L)) end proc: c := proc (n) ListTools:-Reverse(convert(n, base, 2)): RunLengths(%) end proc: A := {0}: for n to 250 do if `subset`(convert(c(n), set), {1, 2}) then A := `union`(A, {n}) else end if end do: A; # most of this Maple program is due to W. Edwin Clark. - Emeric Deutsch, Jan 27 2018

Select[Range[0, 168], AllTrue[Length /@ Split@ IntegerDigits[#, 2], # < 3 &] &] (* Michael De Vlieger, Aug 20 2017 *)

{ n=0; for (m=0, 10^9, x=m; t=1; b=2; while (x>0, d=x-2*(x\2); x\=2; if (d==b, c++; if (c==3, t=x=0), b=d; c=1)); if (t, write("b063037.txt", n++, " ", m); if (n==1000, break)) ) } \\ Harry J. Smith, Aug 16 2009

a(n) = { n--; if (n<=1, return (n), my (s=1); for (i=1, oo, my (f=fibonacci(i+1)); if (nRémy Sigrist, Sep 30 2022

from itertools import count, islice
def A063037_gen(startvalue=0): # generator of terms >= startvalue
    return filter(lambda n: not ('000' in (s:=bin(n)[2:]) or '111' in s), count(max(0,startvalue)))
A063037_list = list(islice(A063037_gen(),20)) # Chai Wah Wu, Oct 04 2022

It appears (but has not yet been proved) that the terms of {a(n)} can be computed recursively as follows. Let {c(i)} be defined for i >= 4 by c(i) = 2c(i-1) + 1, if i is a multiple of 3, else c(i) = 2c(i-1) - 1, with c(4) = 1. I.e., {c(i)} = {1,1,3,5,9,19,37,73,147,...}, for i=4,5,6,... . Let a(1)=1, a(2)=2, a(3)=3. For n > 3, choose k so that F(k)-2 < n <= F(k+1)-2, where F(k) denotes the k-th Fibonacci number (A000045). Then a(n) = c(k) + 2a(F(k)-2) - a(2F(k)-n-3). This has been verified for n up to 1100. - John W. Layman, May 26 2009

Missing "less than" sign supplied in the conjectured recurrence (thanks to Franklin T. Adams-Watters for pointing this out) by John W. Layman, Nov 09 2009

A282133 Number of maximal cubefree binary words of length n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 2, 2, 4, 10, 12, 14, 28, 38, 56, 84, 124, 184, 264, 374, 544, 836, 1190, 1746, 2544, 3712, 5410, 7890, 11470, 16666, 24436, 35574, 51892, 75552, 110124, 160624, 234162, 341178, 497058, 725026, 1056630, 1540158, 2244566, 3271600

Offset: 1

Jeffrey Shallit, Feb 06 2017

nonn

A word is cubefree if it has no block within it of the form xxx, where x is any nonempty block. A cubefree word w is maximal if it cannot be extended to the right (i.e., both w0 and w1 end in cubes).

It appears that a(n) ~ A028445(n-11). - M. F. Hasler, May 05 2017

			For n = 8, the two maximal cubefree words of length 8 are 00100100 and its complement 11011011.
The first few maximal cubefree words beginning with 1 are:
[1, 1, 0, 1, 1, 0, 1, 1],
[1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0],
[1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1],
[1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0],
[1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1],
[1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0],
[1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0],
[1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1],
[1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1],
[1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0].
For those beginning with 0, take the complements. - _N. J. A. Sloane_, May 05 2017

Lars Blomberg, Table of n, a(n) for n = 1..59

Cf. A028445, A282317.

For these numbers halved, see A286270.

# Maple code adapted from that in A286262 by N. J. A. Sloane, May 05 2017
isCubeFree:=proc(v) local n,L;
for n from 3 to nops(v) do for L to n/3 do
if v[n-L*2+1 .. n] = v[n-L*3+1 .. n-L] then RETURN(false) fi od od; true end;
A282133:=proc(n) local s,m;
s:=0;
for m from 2^(n-1) to 2^n-1 do
if isCubeFree(convert(m,base,2)) then
   if (not isCubeFree(convert(2*m,base,2))) and
   (not isCubeFree(convert(2*m+1,base,2))) then
   s:=s+2; fi;
fi;
od; s; end;
[seq(A282133(n),n=0..18)];

CubeFreeQ[v_List] := Module[{n, L}, For[n = 3, n <= Length[v], n++, For[L = 1, L <= n/3, L++, If[v[[n - L*2 + 1 ;; n]] == v[[n - L*3 + 1 ;; n - L]], Return[False]]]]; True];
a[n_] := a[n] = Module[{s, m}, s = 0; For[m = 2^(n - 1), m <= 2^n - 1, m++, If[CubeFreeQ[IntegerDigits[m, 2]], If[!CubeFreeQ[IntegerDigits[2*m, 2]] && !CubeFreeQ[IntegerDigits[2*m + 1, 2]], s += 2]]]; s];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 25}] (* Jean-François Alcover, Mar 08 2023, after Maple code *)

def icf(s): # incrementally cubefree
    for l in range(1, len(s)//3 + 1):
        if s[-3*l:-2*l] == s[-2*l:-l] == s[-l:]: return False
    return True
def aupton(nn, verbose=False):
    alst, cfs = [], set("0")
    for n in range(1, nn+1):
        cfsnew = set()
        an = 0
        for c in cfs:
            maximal = True
            for i in "01":
                if icf(c+i):
                    cfsnew.add(c+i)
                    maximal = False
            if maximal: an += 2
        alst, cfs = alst+[an], cfsnew
        if verbose: print(n, an)
    return alst
print(aupton(30)) # Michael S. Branicky, Mar 18 2022

a(36)-a(48) from Lars Blomberg, Feb 09 2019

A293843 Split the infinite binary word A030302, from left to right, into the largest possible cubefree chunks; a(n) = length of n-th cubefree chunk.

Original entry on oeis.org

5, 7, 4, 4, 10, 3, 9, 5, 2, 3, 5, 12, 9, 10, 2, 3, 7, 9, 2, 5, 4, 2, 4, 2, 4, 2, 4, 6, 6, 3, 8, 15, 6, 12, 5, 2, 14, 2, 6, 2, 4, 6, 3, 11, 13, 8, 2, 2, 4, 3, 5, 7, 4, 2, 6, 5, 2, 5, 2, 2, 3, 2, 5, 2, 5, 7, 4, 3, 7, 7, 7, 3, 7, 15, 7, 19, 7, 2, 5, 7, 11, 5, 5

Offset: 1

Rémy Sigrist, Oct 17 2017

Using A030190 instead of A030302 leads to the same sequence except for the first term (that would equal 6).
The word A030302 contains infinitely many consecutive triples of 0's (corresponding for example to the last binary digits of multiples of 8), hence A030302 has no infinite cubefree suffix, and this sequence is well defined for any n > 0.
a(n) >= 2 for any n > 0.
This sequence is unbounded: for any n > 0:
- A028445(2*n) > 0,
- hence we can choose a number in A286262, say c, with 2*n digits in binary,
- and the subword of A030302 corresponding to c will participate in no more than two cubefree chunks,
- and one of those chunks will have at least length n, QED.
The first records of the sequence are (see also A293867 and A293868):
a(n)  n
----  --
5     1
7     2
10    5
12    12
15    32
19    76
21    212
25    412
35    418
36    2305
39    5118
47    5516
59    49014
63    104902
67    261530
71    478638
75    1016483
79    2148745
83    4532050
87    9534639
91    20011894
95    41896466

			The following table shows the first terms of the sequence, alongside the corresponding cubefree chunks:
n   a(n)  n-th chunk
--  ----  ----------
1   5     11011
2   7          1001011
3   4                 1011
4   4                     1100
5   10                        0100110101
6   3                                   011
7   9                                      110011011
8   5                                               11011
9   2                                                    11
10  3                                                      100

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Rémy Sigrist, PERL program for A293843

Cf. A028445, A030190, A030302, A286262, A293867, A293868.

A337223 a(n) is the least number that can be obtained by replacing some cube XXX in the binary expansion of n by X.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 1, 2, 9, 10, 11, 12, 13, 2, 3, 4, 5, 18, 19, 20, 21, 22, 5, 6, 25, 26, 27, 4, 5, 6, 7, 8, 9, 10, 11, 36, 37, 38, 9, 10, 41, 2, 43, 44, 45, 10, 11, 12, 13, 50, 51, 52, 53, 54, 13, 8, 9, 10, 11, 12, 13, 14, 3, 4, 17, 18, 19, 20, 21, 22, 17

Offset: 0

Rémy Sigrist, Aug 19 2020

Leading zeros in binary expansions are ignored.

Fixed points correspond to A286262.

			The first terms, in decimal and in binary, are:
  n   a(n)  bin(n)  bin(a(n))
  --  ----  ------  ---------
   0     0       0          0
   1     1       1          1
   2     2      10         10
   3     3      11         11
   4     4     100        100
   5     5     101        101
   6     6     110        110
   7     1     111          1
   8     2    1000         10
   9     9    1001       1001
  10    10    1010       1010
  11    11    1011       1011
  12    12    1100       1100
  13    13    1101       1101
  14     2    1110         10
  15     3    1111         11
  16     4   10000        100

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

Cf. A286262, A297405, A337222, A337224.

PARI
```
See Links section.
```

a(A297405(n)) = n for any n > 0.

A286261 Numbers whose binary expansion is not a cubefree string.

Original entry on oeis.org

7, 8, 14, 15, 16, 17, 23, 24, 28, 29, 30, 31, 32, 33, 34, 35, 39, 40, 42, 46, 47, 48, 49, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 78, 79, 80, 81, 84, 85, 87, 88, 92, 93, 94, 95, 96, 97, 98, 99, 103, 104, 106, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130

Offset: 1

M. F. Hasler, May 05 2017

Cubefree means that there is no substring which is the repetition of three identical nonempty strings, see examples.

If n is in the sequence, any number of the form n*2^k + m with 0 <= m < 2^k is in the sequence, and also any number of the form m*2^k + n with 2^k > n, m >= 0.

			7 is in the sequence, because 7 = 111[2] contains three consecutive "1"s.
8 is in the sequence, because 8 = 1000[2] contains three consecutive "0"s.
42 is in the sequence, because 42 = 101010[2] contains three consecutive "10"s.
From the comment follows that all numbers of the form 7*2^k, 8*2^k or 42*2^k are in the sequence, for any k >= 0.
All numbers congruent to 7 or congruent to 0 (mod 8) are in the sequence.
All numbers of the form m*2^(k+3) +- n with n < 2^k are in the sequence.

Chai Wah Wu, Table of n, a(n) for n = 1..10000

Cf. A028445, A286262 (complement of this sequence).

from _future_ import division
def is_cubefree(s):
    l = len(s)
    for i in range(l-2):
        for j in range(1,(l-i)//3+1):
            if s[i:i+2*j] == s[i+j:i+3*j]:
                return False
    return True
A286261_list = [n for n in range(10**4) if not is_cubefree(bin(n)[2:])] # Chai Wah Wu, May 06 2017

a(n) ~ n: the sequence has asymptotic density one.

A349955 Numbers whose representation in any base b >= 2 is a cubefree word.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 9, 10, 11, 12, 18, 19, 20, 22, 25, 36, 37, 38, 44, 45, 50, 51, 52, 74, 75, 76, 77, 89, 90, 100, 101, 102, 105, 109, 147, 150, 153, 154, 165, 166, 173, 178, 179, 180, 181, 204, 205, 210, 214, 217, 293, 294, 300, 301, 306, 308, 309, 329, 330

Offset: 1

Vladimir Reshetnikov, Mar 20 2022

A subsequence of A178905. A subsequence of A286262.

Michael S. Branicky, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Cubefree Word.

Cf. A178905, A286262.

Prepend[Cases[Range[330], n_ /; NoneTrue[Range[2, (Sqrt[4 n - 3] - 1)/2], MatchQ[IntegerDigits[n, #], {_, d__, d__, d__, _}] &]], 0]

from sympy.ntheory.digits import digits
def hascube(s):
    for l in range(1, len(s)//3 + 1):
      for i in range(len(s) - 3*l + 1):
          if s[i:i+l] == s[i+l:i+2*l] == s[i+2*l:i+3*l]: return True
    return False
def ok(n):
    if n < 7: return True
    b = 2
    d = digits(n, b)[1:]
    while len(d) >= 3:
        if hascube(d):
            return False
        b += 1
        d = digits(n, b)[1:]
    return True
print([k for k in range(331) if ok(k)]) # Michael S. Branicky, Mar 27 2022

A352335 Numbers whose representation in the Fibonacci base is a cubefree word.

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 7, 10, 11, 12, 16, 17, 19, 27, 28, 31, 44, 45, 50, 51, 72, 74, 82, 83, 117, 120, 134, 189, 194, 195, 218, 307, 315, 316, 353, 497, 511, 571, 572, 804, 805, 828, 925, 926, 1302, 1303, 2108

Offset: 1

Vladimir Reshetnikov, Mar 19 2022

This is a finite sequence with 47 terms. The largest term is 2108, whose representation in the Fibonacci base is 1001001010010100, because 2108 = 1597 + 377 + 89 + 34 + 8 + 3.

			17 can be expressed as a sum of distinct, non-consecutive Fibonacci numbers 13 + 3 + 1, so the representation of 17 in the Fibonacci base is 100101, which is a cubefree word, so 17 is in this sequence.

Eric Weisstein's World of Mathematics, Cubefree Word.
Eric Weisstein's World of Mathematics, Zeckendorf Representation.
Wikipedia, Zeckendorf's theorem.

Cf. A003714, A014417, A028445, A286262.

Cases[NestList[Function[n, {n[[1]] + 1, NestWhile[# + 1 &, n[[2]] + 1, BitAnd[#, 2 #] > 0 &]}], {0, 0}, 2108], {k_, z_} /; !MatchQ[IntegerDigits[z, 2], {_, w__, w__, w__, _}] :> k]

cp's OEIS Frontend

A028445 Number of cubefree words of length n on two letters.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Python

Formula

Extensions

A063037 Numbers without 3 consecutive equal binary digits.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A282133 Number of maximal cubefree binary words of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Extensions

A293843 Split the infinite binary word A030302, from left to right, into the largest possible cubefree chunks; a(n) = length of n-th cubefree chunk.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A337223 a(n) is the least number that can be obtained by replacing some cube XXX in the binary expansion of n by X.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A286261 Numbers whose binary expansion is not a cubefree string.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

A349955 Numbers whose representation in any base b >= 2 is a cubefree word.

Views

Author

Keywords