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.

2, 4, 10, 40, 460, 53590, 718052410, 128899816953780640, 4153790702679538920955222740373360, 4313494300416744426870901874924164733839903365825579313972159982440

Offset: 1

Author

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

Keywords

• easy
• nonn

Comments

The ideal substring length is related to A007501. It can be shown these are equivalent problems.

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

For n > 1:

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

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

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

etc.

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.

Examples

			To illustrate, suppose we have a string of repeating Xs.
n = 1: replace(string, "XX", "X"), the longest string which will reduce to "X" is "XX"
n = 2: replace(replace(string, "XX", "X"), "XX", "X") will reduce up to 4 Xs to "X"
n = 3: replace(replace(replace(string, "XXX", "X"), "XX", "X"), "XX", "X") up to 10 Xs
n = 4: replace(replace(replace(replace(string, "XXXXXX", "X"), "XXX", "X"), "XX", "X"), "XX", "X") up to 40 Xs
etc.
		

Crossrefs

2, followed by A007501

Programs

Maple

a:= proc(n) option remember; a(n-1)*(a(n-1)+6)/4 end: a(1):=2:
seq(a(n), n=1..10);  # Alois P. Heinz, Oct 11 2024

Mathematica

NestList[-Floor[(#+3)/2]^2+(#+3)*Floor[(#+3)/2]-2&,2,9] (* Shenghui Yang, Oct 11 2024 *)

Other

// q is this sequence, p is A007501
set q = 2
output q
repeat
set p = q / 2 + 1
set q = p * (p + 1) - 2
output q
end repeat

Formula

Given substring length p as indicated in A007501, sequence is p(p+1)-2.

a(n) = a(n-1)*(a(n-1) + 6)/4. - N. Sato, Feb 01 2010

Extensions

Missing a(9) inserted by Alois P. Heinz, Oct 11 2024