login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 0

%I #7 Nov 29 2021 12:15:27

%S 2,4,10,40,460,53590,718052410,128899816953780640,

%T 4313494300416744426870901874924164733839903365825579313972159982440

%N 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 The ideal substring length is related to A007501. It can be shown these are equivalent problems.

%C For n = 1, the ideal substring length is 2.

%C For n > 1:

%C n = 2, term 0 of A007501, substring length = 2

%C n = 3, term 1 of A007501, substring length = 3

%C n = 4, term 2 of A007501, substring length = 6

%C etc.

%C 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 Given substring length p as indicated in A007501, sequence is p(p+1)-2.

%F a(n) = a(n - 1)(a(n - 1) + 6)/4 [From _N. Sato_, Feb 01 2010]

%e To illustrate, suppose we have a string of repeating Xs.

%e n = 1: replace(string, "XX", "X"), the longest string which will reduce to "X" is "XX"

%e n = 2: replace(replace(string, "XX", "X"), "XX", "X") will reduce up to 4 Xs to "X"

%e n = 3: replace(replace(replace(string, "XXX", "X"), "XX", "X"), "XX", "X") up to 10 Xs

%e n = 4: replace(replace(replace(replace(string, "XXXXXX", "X"), "XXX", "X"), "XX", "X"), "XX", "X") up to 40 Xs

%e etc.

%o (Other) // q is this sequence, p is A007501

%o set q = 2

%o output q

%o repeat

%o set p = q / 2 + 1

%o set q = p * (p + 1) - 2

%o output q

%o end repeat

%Y 2, followed by A007501

%K easy,nonn

%O 1,1

%A Russell Harper (russell.harper(AT)springboardnetworks.com), Apr 24 2009

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 5 03:37 EDT 2024. Contains 372257 sequences. (Running on oeis4.)