|
|
A137744
|
|
Number of different strings of length n obtained from "abcd" by iteratively duplicating any substring.
|
|
12
|
|
|
0, 0, 0, 0, 1, 4, 13, 40, 119, 348, 1014, 2966, 8726, 25820, 76823, 229814, 691186, 2089850, 6351448, 19398726, 59525641, 183462778, 567794458, 1764118964
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,6
|
|
COMMENTS
|
|
|
LINKS
|
|
|
EXAMPLE
|
a(4) = # { abcd },
a(5) = # { aabcd, abbcd, abccd, abcdd },
a(6) = # { aaabcd, aabbcd, aabccd, aabcdd, ababcd, abbbcd, abbccd, abbcdd, abcbcd, abcccd, abccdd, abcdcd, abcddd }
|
|
PROG
|
(Python)
def process(s, n, catalog, cache):
....l=len(s)
....if l==n:
........catalog.add(s)
........return
....if s in cache:
........return
....cache.add(s)
....for x in range(l):
........for y in range(x+1, min(x+n-l, l)+1):
............process(s[:y]+s[x:], n, catalog, cache)
....catalog=set()
....cache=set()
....process("abcd", n, catalog, cache)
....return len(catalog)
|
|
CROSSREFS
|
|
|
KEYWORD
|
more,nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|