cp's OEIS Frontend

A090822 Gijswijt's sequence: a(1) = 1; for n>1, a(n) = largest integer k such that the word a(1)a(2)...a(n-1) 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.

%I A090822 #125 Aug 19 2025 09:36:59
%S A090822 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,
%T A090822 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,
%U A090822 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
%N A090822 Gijswijt's sequence: a(1) = 1; for n>1, a(n) = largest integer k such that the word a(1)a(2)...a(n-1) 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.
%C A090822 Here xy^k means the concatenation of the words x and k copies of y.
%C A090822 The name "Gijswijt's sequence" is due to _N. J. A. Sloane_, not the author!
%C A090822 Fix n and suppose a(n) = k. Let len_y(n) = length of shortest y for this k and let len_x = n-1 - 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.
%C A090822 The first 4 occurs at a(220) (see A091409).
%C A090822 The first 5 appears around term 10^(10^23).
%C A090822 We believe that for all N >= 6, the first time N appears is at about position 2^(2^(3^(4^(5^...^(N-1))))). - _N. J. A. Sloane_ and _Allan Wilks_, Mar 14 2004
%C A090822 For a similar formula, see p. 6 of Levi van de Pol article. - _Levi van de Pol_, Feb 06 2023
%C A090822 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
%C A090822 When k=12 is reached, say, it is treated as the number 12, not as 1,2. This is not a base-dependent sequence.
%C A090822 Does this sequence have a finite average? Does anyone know the exact value? - _Franklin T. Adams-Watters_, Jan 23 2008
%C A090822 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
%C A090822 Second answer: The asymptotic densities of the numbers exist, and the average is the dot product. See pp. 56-59 of Levi van de Pol article. - _Levi van de Pol_, Feb 06 2023
%C A090822 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
%C A090822 Answer: The first x such that the x-th 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
%D A090822 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. 93-110.
%H A090822 N. J. A. Sloane, <a href="/A090822/b090822.txt">Table of n, a(n) for n = 1..24000</a>
%H A090822 Andreas Abel and Andres Loeh, <a href="/A090822/a090822.hs.txt">Haskell program</a>
%H A090822 Fokko J. van de Bult, Dion C. Gijswijt, John P. Linderman, N. J. A. Sloane and Allan R. Wilks, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL10/Sloane/sloane55.html">A Slow-Growing Sequence Defined by an Unusual Recurrence</a>, J. Integer Sequences, Vol. 10 (2007), #07.1.2.
%H A090822 Benjamin Chaffin, John P. Linderman, N. J. A. Sloane, and Allan R. Wilks, <a href="http://arxiv.org/abs/1212.6102">On Curling Numbers of Integer Sequences</a>, arXiv:1212.6102 [math.CO], Dec 25 2012.
%H A090822 Benjamin Chaffin, John P. Linderman, N. J. A. Sloane, and Allan R. Wilks, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Sloane/sloane3.html">On Curling Numbers of Integer Sequences</a>, Journal of Integer Sequences, Vol. 16 (2013), Article 13.4.3.
%H A090822 Benjamin Chaffin and N. J. A. Sloane, <a href="http://neilsloane.com/doc/CNC.pdf">The Curling Number Conjecture</a>, preprint.
%H A090822 Dion C. Gijswijt, <a href="https://pyth.eu/uploads/user/ArchiefPDF/Pyth55-3.pdf">Krulgetallen</a>, Pythagoras, 55ste Jaargang, Nummer 3, Jan 2016, (Article in Dutch about this sequence, see pages 10-13, cover and back cover).
%H A090822 Levi van de Pol, <a href="https://arxiv.org/abs/2209.04657">The first occurrence of a number in Gijswijt's sequence</a>, arXiv:2209.04657 [math.CO], 2022.
%H A090822 Levi van de Pol, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL28/Vandepol/vandepol5.html">The Growth Rate of Gijswijt's Sequence</a>, J. Int. Seq. (2025) Vol. 28, Art. No. 25.4.6. See p. 2.
%H A090822 N. J. A. Sloane, <a href="http://neilsloane.com/doc/g4g7.pdf">Seven Staggering Sequences</a>.
%H A090822 N. J. A. Sloane, <a href="/A195264/a195264.pdf">Confessions of a Sequence Addict (AofA2017)</a>, slides of invited talk given at AofA 2017, Jun 19 2017, Princeton. Mentions this sequence.
%H A090822 <a href="/index/Ge#Gijswijt">Index entries for sequences related to Gijswijt's sequence</a>
%H A090822 <a href="/index/Cu#curling_numbers">Index entries for sequences related to curling numbers</a>
%p A090822 K:= proc(L)
%p A090822 local n,m,k,i,b;
%p A090822 m:= 0;
%p A090822 n:= nops(L);
%p A090822 for k from 1 do
%p A090822   if k*(m+1) > n then return(m) fi;
%p A090822   b:= L[-k..-1];
%p A090822   for i from 1 while i*k <= n and L[-i*k .. -(i-1)*k-1] = b do od:
%p A090822   m:= max(m, i-1);
%p A090822 od:
%p A090822 end proc:
%p A090822 A[1]:= 1:
%p A090822 for i from 2 to 220 do
%p A090822   A[i]:= K([seq(A[j],j=1..i-1)])
%p A090822 od:
%p A090822 seq(A[i],i=1..220); # _Robert Israel_, Jul 02 2015
%t A090822 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[n-1, 2]}] // Sort // Last // First; PrependTo[ reversed, an]; an]; A090822 = Table[a[n], {n, 1, 99}] (* _Jean-François Alcover_, Aug 13 2012 *)
%o A090822 (Haskell) -- See link.
%o A090822 (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..-N-1]&&(m+=1)&&break);m>k||break; k=m);A=concat(A,k));A} \\ _M. F. Hasler_, Aug 08 2018
%o A090822 (Python)
%o A090822 def k(s):
%o A090822     maxk = 1
%o A090822     for m in range(1, len(s)+1):
%o A090822         i, y, kk = 1, s[-m:], len(s)//m
%o A090822         if kk <= maxk: return maxk
%o A090822         while s[-(i+1)*m:-i*m] == y: i += 1
%o A090822         maxk = max(maxk, i)
%o A090822 def aupton(terms):
%o A090822     alst = [1]
%o A090822     for n in range(2, terms+1):
%o A090822         alst.append(k(alst))
%o A090822     return alst
%o A090822 print(aupton(99)) # _Michael S. Branicky_, Mar 28 2022
%Y A090822 Cf. A091407, A091408, A091409 (records), A091410, A091411, A091579, A091586, A091970, A093955-A093958.
%Y A090822 A091412 gives lengths of runs. A091413 gives partial sums.
%Y A090822 Cf. also A094004, A160766, A217206, A217207.
%Y A090822 Generalizations: A094781, A091975, A091976, A092331-A092335.
%K A090822 nonn,nice
%O A090822 1,3
%A A090822 _Dion Gijswijt_, Feb 27 2004