

A090822


Gijswijt's sequence: a(1) = 1; for n>1, a(n) = largest integer k such that the word a(1)a(2)...a(n1) is of the form xy^k for words x and y (where y has positive length), i.e., the maximal number of repeating blocks at the end of the sequence so far.


84



1, 1, 2, 1, 1, 2, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 2, 3, 2, 1, 1, 2, 1, 1, 2, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 3, 3, 2, 1, 1, 2, 1, 1, 2, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 2, 3, 2, 1, 1, 2, 1, 1, 2, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 3, 3, 2, 2, 2, 3, 2, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

Here xy^k means the concatenation of the words x and k copies of y.
Fix n and suppose a(n) = k. Let len_y(n) = length of shortest y for this k and let len_x = n1  k*len_y(n) = corresponding length of x. A091407 and A091408 give len_y and len_x. For the subsequence when len_x = 0 see A091410 and A091411.
The first 4 occurs at a(220) (see A091409).
The first 5 appears around term 10^(10^23).
We believe that for all N >= 6, the first time N appears is at about position 2^(2^(3^(4^(5^...^(N1))))).  N. J. A. Sloane and Allan Wilks, Mar 14 2004
For a similar formula, see p. 6 of Levi van de Pol article.  Levi van de Pol, Feb 06 2023
In the first 100000 terms the fraction of [1's, 2's, 3's, 4's] seems to converge, to about [.287, .530, .179, .005] respectively.  Allan Wilks, Mar 04 2004
When k=12 is reached, say, it is treated as the number 12, not as 1,2. This is not a basedependent sequence.
Answer: Given that "...the fraction of [1's, 2's, 3's, 4's] seems to converge, to about [.287, .530, .179, .005]..." that average should be the dot product of these vectors, i.e., about 1.904.  M. F. Hasler, Jan 24 2008
Second answer: The asymptotic densities of the numbers exist, and the average is the dot product. See pp. 5659 of Levi van de Pol article.  Levi van de Pol, Feb 06 2023
Which is the first step with two consecutive 4's? Or the shortest run found so far between two 4's?  Sergio Pimentel, Oct 10 2016
Answer: The first x such that the xth and (x+1)th element are 4, is 255895648634818208370064452304769558261700170817472823... ...398081655524438021806620809813295008281436789493636144. See p. 55 of Levi van de Pol article.  Levi van de Pol, Feb 06 2023


REFERENCES

N. J. A. Sloane, Seven Staggering Sequences, in Homage to a Pied Puzzler, E. Pegg Jr., A. H. Schoen and T. Rodgers (editors), A. K. Peters, Wellesley, MA, 2009, pp. 93110.


LINKS

D. C. Gijswijt, Krulgetallen, Pythagoras, 55ste Jaargang, Nummer 3, Jan 2016, (Article in Dutch about this sequence, see pages 1013, cover and back cover).


MAPLE

K:= proc(L)
local n, m, k, i, b;
m:= 0;
n:= nops(L);
for k from 1 do
if k*(m+1) > n then return(m) fi;
b:= L[k..1];
for i from 1 while i*k <= n and L[i*k .. (i1)*k1] = b do od:
m:= max(m, i1);
od:
end proc:
A[1]:= 1:
for i from 2 to 220 do
A[i]:= K([seq(A[j], j=1..i1)])
od:


MATHEMATICA

ClearAll[a]; reversed = {a[2]=1, a[1]=1}; blocs[len_] := Module[{bloc1, par, pos}, bloc1 = Take[reversed, len]; par = Partition[ reversed, len]; pos = Position[par, bloc_ /; bloc != bloc1, 1, 1]; If[pos == {}, Length[par], pos[[1, 1]]  1]]; a[n_] := a[n] = Module[{an}, an = Table[{blocs[len], len}, {len, 1, Quotient[n1, 2]}] // Sort // Last // First; PrependTo[ reversed, an]; an]; A090822 = Table[a[n], {n, 1, 99}] (* JeanFrançois Alcover, Aug 13 2012 *)


PROG

(Haskell) see link.
(PARI) A090822(n, A=[])={while(#A<n, my(k=1, L=0, m=k); while((k+1)*(L+1)<=#A, for(N=L+1, #A/(m+1), A[m*N..1]==A[(m+1)*N..N1]&&(m+=1)&&break); m>kbreak; k=m); A=concat(A, k)); A} \\ M. F. Hasler, Aug 08 2018
(Python)
def k(s):
maxk = 1
for m in range(1, len(s)+1):
i, y, kk = 1, s[m:], len(s)//m
if kk <= maxk: return maxk
while s[(i+1)*m:i*m] == y: i += 1
maxk = max(maxk, i)
def aupton(terms):
alst = [1]
for n in range(2, terms+1):
alst.append(k(alst))
return alst


CROSSREFS



KEYWORD

nonn,nice


AUTHOR



STATUS

approved



