%I #18 Jun 11 2024 12:04:11
%S 0,0,0,0,1,4,13,40,119,348,1014,2966,8726,25820,76823,229814,691186,
%T 2089850,6351448,19398726,59525641,183462778,567794458,1764118964
%N Number of different strings of length n obtained from "abcd" by iteratively duplicating any substring.
%C See A137743 for more comments.
%H <a href="/index/Do#repeat">Index entries for doubling substrings</a>
%e a(4) = # { abcd },
%e a(5) = # { aabcd, abbcd, abccd, abcdd },
%e a(6) = # { aaabcd, aabbcd, aabccd, aabcdd, ababcd, abbbcd, abbccd, abbcdd, abcbcd, abcccd, abccdd, abcdcd, abcddd }
%o (PARI) A135473(12,4)
%o (Python)
%o def process(s,n,catalog,cache):
%o ....l=len(s)
%o ....if l==n:
%o ........catalog.add(s)
%o ........return
%o ....if s in cache:
%o ........return
%o ....cache.add(s)
%o ....for x in range(l):
%o ........for y in range(x+1,min(x+n-l,l)+1):
%o ............process(s[:y]+s[x:],n,catalog,cache)
%o def A137744(n):
%o ....catalog=set()
%o ....cache=set()
%o ....process("abcd",n,catalog,cache)
%o ....return len(catalog)
%o # _Bert Dobbelaere_, Nov 01 2018
%Y Cf. A137740-A137743, A135473, A137745-A137748.
%K more,nonn
%O 0,6
%A _M. F. Hasler_, Feb 10 2008
%E a(13)-a(19) from _Lars Blomberg_, Jan 12 2013
%E a(20)-a(21) from _Bert Dobbelaere_, Nov 01 2018
%E a(22)-a(23) from _Bert Dobbelaere_, Jun 10 2024