Gandhar Joshi - cp's OEIS frontend

A380593 Starting position of the first occurrence of the longest monochromatic arithmetic progression of difference n in the Rudin-Shapiro sequence (A020987).

7, 14, 28, 28, 31, 43, 95, 56, 43, 62, 453, 86, 99, 190, 39, 112, 495, 86, 366, 124, 81, 321, 203, 172, 1006, 81, 233, 380, 2019, 78, 993, 224, 980, 990, 888, 172, 1084, 732, 4057, 248, 2007, 162, 164, 642, 1215, 406, 1729, 344, 1398, 2012, 1988, 162, 1765

Offset: 1

Gandhar Joshi, Jan 27 2025

nonn

The length of this longest monochromatic progression is A364995(n).

			For n = 3, the longest length of the monochromatic arithmetic progression in the Rudin-Shapiro sequence is given by A364995(3)=5. Let r(i) be the i-th term of the Rudin-Shapiro sequence (A020985). We have r(28) = r(31) = r(34) = r(37) = r(40), and no j<i exists such that r(j) = r(j+3) = r(j+2*3) = r(j+3*3) = r(j+4*3). So a(3)=28.

B. Sobolewski, On monochromatic arithmetic progressions in binary words associated with pattern sequences, Theoretical Computer Science 1018 (2024), 114815.

Gandhar Joshi, Table of n, a(n) for n = 1..1022
Bartosz Sobolewski, On monochromatic arithmetic progressions in binary words associated with pattern sequences, arXiv:2204.05287 [math.CO], 2023.

Cf. A020987, A020985, A364995 (progression length).

# Replace in the code below: every n with the desired constant difference, and every q with the longest MAP length for difference n given by A364995(n).
def rs_n_map "Ak (k RS[i]=RS[i+n*k] & Aj (j ~(Ak (k RS[j]=RS[j+n*k])";
# While using Walnut to find values above and including a(1022), one has to run the code with constant value estimates and through trial and error hone in onto the smallest value that returns TRUE.

A370756 a(n) is the van der Waerden number W_t(2,n) of the Thue-Morse word (A010060).

Original entry on oeis.org

1, 3, 7, 10, 13, 16, 19, 57, 73, 136, 151, 166, 181, 196, 211, 226, 241, 256, 271, 621, 652, 683, 714, 745, 776, 807, 838, 869, 900, 931, 962, 993, 1057, 2080, 2143, 2206, 2269, 2332, 2395, 2458, 2521, 2584, 2647, 2710, 2773, 2836, 2899, 2962, 3025, 3088, 3151

Offset: 1

Gandhar Joshi, Feb 29 2024

nonn

a(n) is an extremely naive lower bound of the Waerden numbers A005346(n).

			For n=3, at least a(3)=7 terms of the prefix of the Thue-Morse word are required to find a monochromatic arithmetic progression of length 3:
  Thue-Morse word: 0 1 1 0 1 0 0 ...
                   ^     ^     ^
The 3 terms have equal values and are at locations which are a constant step apart (3 in this case).

B. L. van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw. Arch. Wisk. (in German), 15 (1927), 212-216.

Kevin Ryde, Table of n, a(n) for n = 1..8194
Kevin Ryde, C Code

Cf. A010060, A005346, A342818 (longest progression lengths), A342827 (first positions of longest progressions of length A342818(n)).

C
```
/* See links. */
```

// The program is written for a fixed value of progression length, so it is run to find each a(n) separately. Following is an example to find a(5).
def tmw5map "T[i]=T[i+d] & T[i]=T[i+2*d] & T[i]=T[i+3*d] & T[i]=T[i+4*d]";
// This asserts that there is a progression of length 5 for difference d and first position i taken in pair.
def tmw5mapnew "$tmw5map(d,i) & d>0 & i+4*dA342818.
test tmw5mapnew 5;
// This enumerates the first 5 accepted pairs (d,i) in binary listed in lexicographic order. The first or second in the list is our improved bound to be replaced for N in line number 2.
def tmw5mapfin "Ed,i ($tmw5map(d,i) & d>0 & i+4*d

a(13) onward from Kevin Ryde, Mar 31 2024

A370755 a(n) is the van der Waerden number W_f(2,n) of the Fibonacci word (A003849).

Original entry on oeis.org

1, 3, 8, 12, 21, 29, 42, 59, 67, 80, 88, 144, 160, 173, 186, 199, 220, 254, 377, 394, 423, 444, 465, 491, 512, 533, 554, 588, 609, 987, 1024, 1058, 1092, 1126, 1160, 1194, 1228, 1262, 1296, 1330, 1364, 1406, 1440, 1474, 1508, 1563, 1652, 2588, 2643, 2698, 2753

Offset: 1

Gandhar Joshi, Feb 29 2024

nonn

a(n) is an extremely naive lower bound of the Waerden numbers A005346(n).

			For n=3, at least a(3)=8 terms of the prefix of the Fibonacci word are required to find a monochromatic arithmetic progression of length 3:
  Fibonacci word: 0 1 0 0 1 0 1 0 ...
                        ^   ^   ^
The 3 terms have equal values and are at locations which are a constant step apart (2 in this case).

B. L. van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw. Arch. Wisk. (in German), 15 (1927), 212-216.

Kevin Ryde, Table of n, a(n) for n = 1..7500
Kevin Ryde, C Code

Cf. A003849, A005346, A339949 (longest progression lengths), A364648 (first positions of longest progressions of length A339949(n)).

C
```
/* See links. */
```

// The program is written for a fixed value of progression length, so it is run to find each a(n) separately. Following is an example to find a(5).
def fibw5map "?msd_fib F[i]=F[i+d] & F[i]=F[i+2*d] & F[i]=F[i+3*d] & F[i]=F[i+4*d]";
// This asserts that there is a progression of length 5 for difference d and first position i taken in pair.
def fibw5mapnew "?msd_fib $fibw5map(d,i) & d>0 & i+4*dA339949.
test fibw5mapnew 5;
// This enumerates the first 5 accepted pairs (d,i) in Zeckendorf representation listed in lexicographic order. The first or second in the list is our improved bound to be replaced for N in line number 2.
def fibw5mapfin "?msd_fib Ed,i ($fibw5map(d,i) & d>0 & i+4*d

A367184 Starting index in the Period doubling sequence (A096268) of the first maximum length word in which every subword of length n is distinct.

Original entry on oeis.org

0, 0, 1, 0, 5, 2, 1, 0, 11, 10, 9, 4, 3, 2, 1, 0, 23, 22, 21, 20, 19, 18, 17, 8, 7, 6, 5, 4, 3, 2, 1, 0, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84, 83, 82, 81, 80

Offset: 1

Gandhar Joshi, Nov 08 2023

nonn

a(2^m)=0; i.e. for all nonnegative integers m, the longest words w with no length-(2^m) subwords of w repeated are the prefixes of length A366462(2^m) of the Period doubling sequence.

			For n=3, the first instance of one of the longest words w in A096268 with no repeated subwords of length 3 is w=1000101 which begins at index 1, so a(3)=1. The length of w is A366462(3) = 7.

Kevin Ryde, Table of n, a(n) for n = 1..8192
Kevin Ryde, PARI/GP Code

Cf. A096268, A366462 (length of the longest word), A275202 (subword complexity).

PARI
```
\\ See links.
```

def pdfaceq "At (t PD[i+t]=PD[j+t]"; % Check if two length-n factors of Period doubling sequence at positions i and j are equal; PD is predefined in Walnut as the DFA that recognises the Period doubling sequence. %
def pd_w_len_N_unique_factors "Aj, k (i<=j & j<(i+n-N) & j ~$pdfaceq(j, k, N)": % Find lengths and positions of words with length-N unique factors; must replace N with a constant %
def pd_longest_len_N "$pd_w_len_N_unique_factors(i,n) & Am (m>n) => ~$pd_w_len_N_unique_factors(i,m)"; % Check the longest of the lengths of words defined in the line above; must replace N with the same constant %
def pd_longest_len_N_fpos "$pd_longest_len_N(i,M) & Aj (j ~$pd_longest_len_N(j,M)"; % This finds the first positions of the longest words required; must replace M with A366462(N).%

A366462 a(n) is the length of the longest word w in the Period-doubling sequence (A096268) in which every length-n factor of w is unique.

Original entry on oeis.org

2, 4, 7, 9, 11, 15, 17, 19, 21, 23, 25, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 127, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149, 151, 153, 155, 157, 159, 161

Offset: 1

Gandhar Joshi, Oct 24 2023

nonn

So far, all the values in the list except the first two are odd numbers.

			For n=3, the length of the longest word in the Period-doubling sequence that admits only unique length-3 factors is a(3) = 7 (attained by word 1000101 and its reversal).

Kevin Ryde, Table of n, a(n) for n = 1..8192
Kevin Ryde, PARI/GP Code

Cf. A096268, A275202 (subword complexity).

PARI
```
\\ See links.
```

def pdfactoreq "At (t PD[i+t]=PD[j+t]"; % Check if two length-n factors of Period-doubling sequence at positions i and j are equal; PD is predefined in Walnut as the DFA that recognises the Period-doubling sequence. %
def PD_w_len_N_unique_factors "Ei (Aj, k (i<=j & j<(i+n-N) & j ~$pdfactoreq(j, k, N))": % Find lengths of words with length-N unique factors; must replace N with a constant %
def longest_len_N "$PD_w_len_N_unique_factors(n) & Am (m>n) => ~$PD_w_len_N_unique_factors(m)"; % Check the longest of the lengths found in previous line; must replace N with the same constant %

A364995 Length of the longest monochromatic arithmetic progressions of difference n in the Rudin-Shapiro sequence (A020985).

Original entry on oeis.org

4, 4, 5, 4, 6, 5, 9, 4, 9, 6, 15, 5, 6, 9, 10, 4, 10, 9, 12, 6, 10, 15, 13, 5, 12, 6, 12, 9, 12, 10, 19, 4, 18, 10, 13, 9, 15, 12, 22, 6, 12, 10, 15, 15, 12, 13, 9, 5, 12, 12, 15, 6, 13, 12, 13, 9, 10, 12, 9, 10, 18, 19, 33, 4, 34, 18, 10, 10, 10, 13, 12, 9

Offset: 1

Gandhar Joshi, Aug 15 2023

nonn

Also applies to the other versions of Rudin-Shapiro sequence (e.g., A020987).

For n < 2^k the inequality a(n) <= 2^(k+1) holds, and a monochromatic arithmetic progression of length a(n) and difference n appears within 10*4^k initial terms of the Rudin-Shapiro sequence (A020985). More generally, if a(n) <= 2^m, then such a progression appears within 5*2^(k+m) initial terms. Conversely, if the maximal length of a progression within 5*2^(k+m) initial terms is <= 2^m, then also a(n) <= 2^m. These properties follow from the referenced paper by Sobolewski. - Bartosz Sobolewski, Jun 17 2024

			For n = 3, let r(i) be the i-th term of the Rudin-Shapiro sequence (A020985). We have r(28) = r(31) = r(34) = r(37) = r(40), and no k and m > 5 exist such that r(k) = r(k+3) = r(k+2*3) = ... = r(k+(m-1)*3). So a(3)=5.

Bartosz Sobolewski, Table of n, a(n) for n = 1..10000
Ibai Aedo, Uwe Grimm, Yasushi Nagai, and Petra Staynova, Monochromatic arithmetic progressions in binary Thue-Morse-like words, Theor. Comput. Sci., 934 (2022), 65-80; preprint: On long arithmetic progressions in binary Morse-like words, arXiv:2101.02056 [math.CO], 2021.
Bartosz Sobolewski, On monochromatic arithmetic progressions in binary words associated with pattern sequences, arXiv:2204.05287 [math.CO], 2023.

Cf. A020985, A020987, A380593 (first starting index).

Cf. A342818 (analog for the Thue-Morse sequence).

a[n_] := a[n] = If[EvenQ[n], a[n/2], Max[Map[Length, Split /@ Table[RudinShapiro[m n + j], {j, 1, n}, {m, 0, 10*4^(Floor[Log2[n]] + 1)/n}], {2}]]];
Table[a[n], {n, 1, 72}] (* Bartosz Sobolewski, Jun 17 2024 *)

a(33)-a(34) from Sobolewski added by Gandhar Joshi, Apr 30 2024

Corrected and extended by Bartosz Sobolewski, Jun 17 2024

A364648 Starting position of the first occurrence of the longest monochromatic arithmetic progression of difference n in the Fibonacci infinite word (A003849).

Original entry on oeis.org

2, 3, 20, 16, 11, 20, 0, 143, 2, 11, 54, 8, 32, 2, 11, 7, 70, 3, 7, 0, 986, 10, 3, 7, 16, 11, 2, 87, 376, 2, 3, 2, 21, 87, 2, 3, 7, 16, 3, 7, 0, 20, 23, 11, 20, 8, 11, 2, 11, 20, 36, 11, 7, 0, 6764, 31, 3, 376, 84, 11, 54, 0, 20, 2, 3, 2, 42, 87, 2, 3, 54, 304

Offset: 1

Gandhar Joshi, Jul 31 2023

nonn

From Gandhar Joshi, Jan 25 2025: (Start)
F(n) is the n-th Fibonacci number.
Conjecture: for n>0,
1. a(F(2n))=F(4n)-1; a(F(2n+1))=F(2n+3)-2.
2. a(F(6n)/2)=F(6n+3)/2-1; a(F(6n-3)/2)=F(6n)/2-2. (End)

			For the difference n = 3, the longest monochromatic progression has length A339949(3) = 5 and thus defined by f(i)=f(i+3)=f(i+6)=f(i+9)=f(i+12), where f(i) is the i-th term of the Fibonacci word (A003849); the smallest i for which that holds is i=20, so a(3) = 20.

Gandhar Joshi, Table of n, a(n) for n = 1..1973
Ibai Aedo, U. Grimm, Y. Nagai, and P. Staynova, Monochromatic arithmetic progressions in binary Thue-Morse-like words, Theor. Comput. Sci., 934 (2022), 65-80.
Gandhar Joshi and D. Rust, Monochromatic arithmetic progressions in the Fibonacci word, arXiv:2501.05830 [math.DS], 2025. See p.12.

Cf. A003849, A339949 (length of the longest monochromatic arithmetic progression).

# In the following line, replace every n with the desired constant difference, and every q with the longest MAP length for difference n given by A339949(n).
def f_n_map "?msd_fib Ak (k F[i]=F[i+n*k] & Aj (j ~(Ak (k F[j]=F[j+n*k])";
# Gandhar Joshi, Jan 25 2025

A365624 a(n) is the length of the longest word w in the Thue-Morse sequence (A010060) in which every length-n factor of w is unique.

Original entry on oeis.org

2, 5, 8, 12, 16, 18, 24, 26, 32, 34, 36, 38, 48, 50, 52, 54, 64, 66, 68, 70, 72, 74, 76, 78, 96, 98, 100, 102, 104, 106, 108, 110, 128, 130, 132, 134, 136, 138, 140, 142, 144, 146, 148, 150, 152, 154, 156, 158, 192, 194, 196, 198, 200, 202, 204, 206

Offset: 1

Gandhar Joshi, Sep 13 2023

nonn

Interestingly, 5 is the only odd number in the list so far.

			The length of the longest word in Thue-Morse sequence that admits only unique length-2 factors is 5. For example, 11001 (which is not the only one). Hence a(2)=5.

Kevin Ryde, Table of n, a(n) for n = 1..8192
Kevin Ryde, PARI/GP Code

Cf. A010060, A005942 (subword complexity), A366408 (first location).

PARI
```
\\ See links.
```

def tmfaceq "At (t T[i+t]=T[j+t]"; % Check if two length-n factors of Thue-Morse at positions i and j are equal; T is predefined in Walnut as the DFA that recognises Thue-Morse sequence. %
def tm_w_len_N_unique_factors "Ei (Aj,k (i<=j & j<(i+n-N) & j ~$tmfaceq(j,k,N))": % Find lengths of words with length-N unique factors; must replace N with a constant %
def longest_len_N "$tm_w_len_N_unique_factors(n) & Am (m>n) => ~$tm_w_len_N_unique_factors(m)"; % Check the longest of the lengths found in previous line; must replace N with the same constant %

A363070 Take the terms 0..n of the infinite Fibonacci word A003849, regard them as a number in Fibonacci base.

Original entry on oeis.org

0, 1, 2, 3, 6, 10, 17, 28, 45, 74, 120, 194, 315, 510, 826, 1337, 2163, 3501, 5665, 9167, 14833, 24000, 38834, 62835, 101669, 164505, 266175, 430681, 696857, 1127538, 1824396, 2951935, 4776331, 7728267, 12504599, 20232867, 32737467, 52970334, 85707802, 138678137, 224385940, 363064078

Offset: 0

Gandhar Joshi, May 16 2023

			0 ->                            0 -> a(0) = 0,
0,1 ->                         01 -> a(1) = 1,
0,1,0 ->                      010 -> a(2) = 2,
0,1,0,0 ->                   0100 -> a(3) = 3,
0,1,0,0,1 ->                01001 -> a(4) = 6,
0,1,0,0,1,0 ->             010010 -> a(5) = 10,
0,1,0,0,1,0,1 ->          0100101 -> a(6) = 17,
0,1,0,0,1,0,1,0 ->       01001010 -> a(7) = 28,
0,1,0,0,1,0,1,0,0 ->    010010100 -> a(8) = 45,
0,1,0,0,1,0,1,0,0,1 -> 0100101001 -> a(9) = 74.

Gandhar Joshi, Table of n, a(n) for n = 0..1000
Agnibha Banerjee, Python Program, May 16 2023.

Cf. A003849 (Fibonacci word), A005713, A189920 (Zeckendorf digits).

Cf. A182028.

Python
```
# see linked program
```

def aupto(n): # produces n terms, indices 0..n-1
    F1, F, a = [0], [0, 1], [0, 1]
    while len(F) < n:
        F1, F = F, F+F1
    [a.append(a[-2]+a[-1]+F[i]+F[i-1]) for i in range(2, n)]
    return a
print(aupto(42)) # Michael S. Branicky, May 17 2023

a(n) = Sum_{i=0..n} A003849(i)*Fibonacci(n-i+2).
a(n) = a(n-1) + a(n-2) + A003849(n) + A003849(n-1).
a(n) = a(n-1) + a(n-2) + A005713(n-1). - Kevin Ryde, May 20 2023

cp's OEIS Frontend

User: Gandhar Joshi

A380593 Starting position of the first occurrence of the longest monochromatic arithmetic progression of difference n in the Rudin-Shapiro sequence (A020987).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Walnut

A370756 a(n) is the van der Waerden number W_t(2,n) of the Thue-Morse word (A010060).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

C

Walnut

Extensions

A370755 a(n) is the van der Waerden number W_f(2,n) of the Fibonacci word (A003849).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

C

Walnut

A367184 Starting index in the Period doubling sequence (A096268) of the first maximum length word in which every subword of length n is distinct.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Walnut

A366462 a(n) is the length of the longest word w in the Period-doubling sequence (A096268) in which every length-n factor of w is unique.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Walnut

A364995 Length of the longest monochromatic arithmetic progressions of difference n in the Rudin-Shapiro sequence (A020985).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A364648 Starting position of the first occurrence of the longest monochromatic arithmetic progression of difference n in the Fibonacci infinite word (A003849).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs