cp's OEIS Frontend

A159860 The maximum length of a string of identical characters which can be reduced to one character in "n" nested substitution operations, e.g. replace(string, substring, character) such that all shorter strings will also reduce to one character.

%I A159860 #21 Oct 12 2024 09:03:29
%S A159860 2,4,10,40,460,53590,718052410,128899816953780640,
%T A159860 4153790702679538920955222740373360,
%U A159860 4313494300416744426870901874924164733839903365825579313972159982440
%N A159860 The maximum length of a string of identical characters which can be reduced to one character in "n" nested substitution operations, e.g. replace(string, substring, character) such that all shorter strings will also reduce to one character.
%C A159860 The ideal substring length is related to A007501. It can be shown these are equivalent problems.
%C A159860 For n = 1, the ideal substring length is 2.
%C A159860 For n > 1:
%C A159860 n = 2, term 0 of A007501, substring length = 2
%C A159860 n = 3, term 1 of A007501, substring length = 3
%C A159860 n = 4, term 2 of A007501, substring length = 6
%C A159860 etc.
%C A159860 This has applications in text processing operations in computer languages where recursions or loops may not be possible (e.g. standard SQL). To remove extra spaces, one might be tempted to nest several replace operations but use the same substring length, or perhaps double or halve at each step, both of which will not clear as effectively as using substring lengths as indicated in A007501.
%F A159860 Given substring length p as indicated in A007501, sequence is p(p+1)-2.
%F A159860 a(n) = a(n-1)*(a(n-1) + 6)/4. - _N. Sato_, Feb 01 2010
%e A159860 To illustrate, suppose we have a string of repeating Xs.
%e A159860 n = 1: replace(string, "XX", "X"), the longest string which will reduce to "X" is "XX"
%e A159860 n = 2: replace(replace(string, "XX", "X"), "XX", "X") will reduce up to 4 Xs to "X"
%e A159860 n = 3: replace(replace(replace(string, "XXX", "X"), "XX", "X"), "XX", "X") up to 10 Xs
%e A159860 n = 4: replace(replace(replace(replace(string, "XXXXXX", "X"), "XXX", "X"), "XX", "X"), "XX", "X") up to 40 Xs
%e A159860 etc.
%p A159860 a:= proc(n) option remember; a(n-1)*(a(n-1)+6)/4 end: a(1):=2:
%p A159860 seq(a(n), n=1..10);  # _Alois P. Heinz_, Oct 11 2024
%t A159860 NestList[-Floor[(#+3)/2]^2+(#+3)*Floor[(#+3)/2]-2&,2,9] (* _Shenghui Yang_, Oct 11 2024 *)
%o A159860 (Other) // q is this sequence, p is A007501
%o A159860 set q = 2
%o A159860 output q
%o A159860 repeat
%o A159860 set p = q / 2 + 1
%o A159860 set q = p * (p + 1) - 2
%o A159860 output q
%o A159860 end repeat
%Y A159860 2, followed by A007501
%K A159860 easy,nonn
%O A159860 1,1
%A A159860 Russell Harper (russell.harper(AT)springboardnetworks.com), Apr 24 2009
%E A159860 Missing a(9) inserted by _Alois P. Heinz_, Oct 11 2024