# [Clean]
- `1 < n <= 23` in 28 seconds on TIO (17 seconds locally)
- `n = 24 (2311294134347173535961967837989)` in 25 seconds locally
- `n = 25 (23112941343471735359619678378979)` in 134 seconds locally (22 seconds is GC)
This uses a similar approach to Arnauld's JS solution based on recursive permutation rejection, using a specialized tree-set to gain a lot of speed.
For every prime that needs to fit in the number:
1. check if the prime is a sub-string of another prime, and if so, remove it
2. sort the current list of prime sub-strings, join it, and add it to the balanced tree set
3. check if any primes fit on the front of any other ones, and if so, join them
Then, for each pair of sub-strings that we joined, prepend that joined pair to the list of sub-strings and recuse.
Once no more sub-strings can be joined to any other sub-strings on any arm of our recursion, we use the already-ordered tree set to quickly find the lowest number containing the substrings.
*I believe that there is still significant optimization to be made in determining which numbers to attempt merges with using this approach, and that that is probably the best avenue for me to pursue*
*Using Integers instead of Strings (not Ints) may also be a good idea if memory is an issue*
<pre><code>module main
import StdEnv,StdOverloadedList,_SystemEnumStrict
import Data.List,Data.Func,Data.Maybe
import Text
// adapted from Data.Set to work with a single specific type, and persist uniqueness
:: Set a = Tip | Bin !Int !a !.(Set a) !.(Set a)
delta :== 4
ratio :== 2
:: NumberType :== String
makeSetType e = e//{len=size e,str=e}
:: SetType :== NumberType//= {len :: Int, str :: String}
toNumberType = toString
//uSingleton :: !SetType -> Set
uSingleton x :== (Bin 1 x Tip Tip)
// adapted from Data.Set to work with a single specific type, and persist uniqueness
uFindMin :: !.(Set .a) -> .a
uFindMin (Bin _ x Tip _) = x
uFindMin (Bin _ _ l _) = uFindMin l
uSize set :== case set of
	Tip = (0, Tip)
	s=:(Bin sz _ _ _) = (sz, s)
uInsertM :: (a a -> .Bool) -> (a u:(Set a) -> v:(.Bool, w:(Set a))), [v u <= w]
uInsertM cmp = uInsertM`
where
	//uInsertM` :: !.a !.(Set .a) -> .(.Bool, .(Set .a))
	uInsertM` x Tip = (False, uSingleton x)
	uInsertM` x set=:(Bin _ y l r)
		| cmp x y//sx < sy || sx == sy && x < y
			# (t, l) = uInsertM` x l
			= (t, uBalanceL y l r)
			//= (t, if(t)(\y` l` r` = Bin sz y` l` r`) uBalanceL y l r)
		| cmp y x//sx > sy || sx == sy && x > y
			# (t, r) = uInsertM` x r
			= (t, uBalanceR y l r)
			//= (t, if(t)(\y` l` r` = Bin sz y` l` r`) uBalanceR y l r)
		| otherwise = (True, set)
// adapted from Data.Set to work with a single specific type, and persist uniqueness
uBalanceL :: .a u:(Set .a) v:(Set .a) -> w:(Set .a), [v u <= w]
//!a !.(Set a) !.(Set a) -> .(Set a)
uBalanceL x Tip Tip
	= Bin 1 x Tip Tip
uBalanceL x l=:(Bin _ _ Tip Tip) Tip
	= Bin 2 x l Tip
uBalanceL x l=:(Bin _ lx Tip (Bin _ lrx _ _)) Tip
	= Bin 3 lrx (Bin 1 lx Tip Tip) (Bin 1 x Tip Tip)
uBalanceL x l=:(Bin _ lx ll=:(Bin _ _ _ _) Tip) Tip
	= Bin 3 lx ll (Bin 1 x Tip Tip)
uBalanceL x l=:(Bin ls lx ll=:(Bin lls _ _ _) lr=:(Bin lrs lrx lrl lrr)) Tip
	| lrs < ratio*lls
		= Bin (1+ls) lx ll (Bin (1+lrs) x lr Tip)
	# (lrls, lrl) = uSize lrl
	# (lrrs, lrr) = uSize lrr
	| otherwise
		= Bin (1+ls) lrx (Bin (1+lls+lrls) lx ll lrl) (Bin (1+lrrs) x lrr Tip)
uBalanceL x Tip r=:(Bin rs _ _ _)
	= Bin (1+rs) x Tip r
uBalanceL x l=:(Bin ls lx ll lr) r=:(Bin rs _ _ _)
	| ls > delta*rs
		= uBalanceL` ll lr
	| otherwise
		= Bin (1+ls+rs) x l r
where
	uBalanceL` ll=:(Bin lls _ _ _) lr=:(Bin lrs lrx lrl lrr)
		| lrs < ratio*lls
			= Bin (1+ls+rs) lx ll (Bin (1+rs+lrs) x lr r)
		# (lrls, lrl) = uSize lrl
		# (lrrs, lrr) = uSize lrr
		| otherwise
			= Bin (1+ls+rs) lrx (Bin (1+lls+lrls) lx ll lrl) (Bin (1+rs+lrrs) x lrr r)
// adapted from Data.Set to work with a single specific type, and persist uniqueness
uBalanceR :: .a u:(Set .a) v:(Set .a) -> w:(Set .a), [v u <= w]
uBalanceR x Tip Tip
	= Bin 1 x Tip Tip
uBalanceR x Tip r=:(Bin _ _ Tip Tip)
	= Bin 2 x Tip r
uBalanceR x Tip r=:(Bin _ rx Tip rr=:(Bin _ _ _ _))
	= Bin 3 rx (Bin 1 x Tip Tip) rr
uBalanceR x Tip r=:(Bin _ rx (Bin _ rlx _ _) Tip)
	= Bin 3 rlx (Bin 1 x Tip Tip) (Bin 1 rx Tip Tip)
uBalanceR x Tip r=:(Bin rs rx rl=:(Bin rls rlx rll rlr) rr=:(Bin rrs _ _ _))
	| rls < ratio*rrs
		= Bin (1+rs) rx (Bin (1+rls) x Tip rl) rr
	# (rlls, rll) = uSize rll
	# (rlrs, rlr) = uSize rlr
	| otherwise
		= Bin (1+rs) rlx (Bin (1+rlls) x Tip rll) (Bin (1+rrs+rlrs) rx rlr rr)
uBalanceR x l=:(Bin ls _ _ _) Tip
	= Bin (1+ls) x l Tip
uBalanceR x l=:(Bin ls _ _ _) r=:(Bin rs rx rl rr)
	| rs > delta*ls
		= uBalanceR` rl rr
	| otherwise
		= Bin (1+ls+rs) x l r
where
	uBalanceR` rl=:(Bin rls rlx rll rlr) rr=:(Bin rrs _ _ _)
		| rls < ratio*rrs
			= Bin (1+ls+rs) rx (Bin (1+ls+rls) x l rl) rr
		# (rlls, rll) = uSize rll
		# (rlrs, rlr) = uSize rlr
		| otherwise
			= Bin (1+ls+rs) rlx (Bin (1+ls+rlls) x l rll) (Bin (1+rrs+rlrs) rx rlr rr)
			
primes :: [Int]
primes =: [2: [i \\ i <- [3, 5..] | let
		checks :: .[#Int!]
		checks = TakeWhile (\n = i >= n*n) primes
	in All (\n = i rem n <> 0) checks]]
//primePrefixes :: [[NumberType]]
primePrefixes :== Tl (Scan removeOverlap [|] [toNumberType p \\ p <- primes])
removeOverlap :: !.[NumberType] !.NumberType -> [NumberType]
removeOverlap subs nsub = insertSorted subs
where
	insertSorted :: !.[NumberType] -> [NumberType]
	insertSorted [|] = [|nsub]
	insertSorted [|h: t]
		|indexOf h nsub <> -1
			= insertSorted t
		| nsub > h
			= [|h: insertSorted t]
		| otherwise
			= [|nsub, h: Filter (\s = indexOf s nsub == -1) t]
getMergeCandidate :: !.NumberType !.NumberType -> .Maybe NumberType
getMergeCandidate a b
	| a == b = Nothing
	| otherwise
		= last_prefix max_len
where
	sa = size a - 1
	max_len = min sa (size b - 1)
	last_prefix :: !.Int -> .Maybe NumberType
	last_prefix 0 = Nothing
	last_prefix n
		| b%(0,n-1)== a%(n,sa)
			= Just (a%(0,n-1) + b)
		| otherwise
			= last_prefix (dec n)
mergeString :: !.NumberType !.NumberType -> .NumberType
mergeString a b = first_prefix (max (size a - size b) 0)
where
	sa = size a - 1
	first_prefix :: !.Int -> .NumberType
	first_prefix n
		| b%(0,sa-n) == a%(n,sa)
			= a%(0,n-1) +++. b
		| otherwise
			= first_prefix (inc n)
			
//uFilterSt :: !(a -> .b -> .(Bool,.b)) -> .[a] -> .b -> .(.[a],.b)
uFilterSt fn :== uFilterSt`
where
	uFilterSt` :: !.[a] !.b -> .(.[a], .b)
	uFilterSt` [|] s = ([|], s)
	uFilterSt` [|h:t] s
		# (iff, s) = fn h s
		| not iff
			= uFilterSt` t s
		# (t, s) = uFilterSt` t s
		| otherwise
			= ([|h:t], s)
	
	
:: CombType :== NumberType
// todo: keep track of merges that we make independent of the resulting whole number
mapCandidatePermsSt :: !.[.[NumberType]] !u:(Set .NumberType) -> v:(Set NumberType), [u <= v]
mapCandidatePermsSt [ ] returnSet = returnSet
mapCandidatePermsSt [h:t] returnSet
	#! (mem, returnSet) = uInsertM minFinder h` returnSet
	| mem
		= mapCandidatePermsSt t returnSet
	| otherwise
		# merges = [removeOverlap h y \\ x <- h, (Just y) <- Map (getMergeCandidate x) h]
		# returnSet = mapCandidatePermsSt merges returnSet
		= mapCandidatePermsSt t returnSet
		//= mapCandidatePermsSt (merges ++| t) returnSet
where
	h` = foldl mergeString "" h
	dropper e s
		# (mem, s) = uInsertM (<) e s
		= (not mem, s)
	
		
containmentNumbersSt = [ uFindMin (mapCandidatePermsSt [p] Tip) \\ p <- primePrefixes] 
minFinder :== (\a b = let sa = size a; sb = size b in if(sa == sb) (a < b) (sa < sb))
Start = [(i, ' ',n , '\n') \\ i <- [1..] & n <- containmentNumbersSt]
</code></pre>
[Try it online!][TIO-jp7kdwt8]
[Clean]: https://github.com/Ourous/curated-clean-linux
[TIO-jp7kdwt8]: https://tio.run/##tVhtb9u2Fv5s/YqTFWulxrH7svuhvnGA220FOjRbkQTYB8dIaJuOhVCUR9KJ3Xl//eaecyhZlKWm3S6KIq7I88rnHD4SOVVS6IeHLJ@tlIRMpDpKs2VuHJy72c/6rov//XYnjcrFTM4@pNZ1r8431snsZ73Kzp1Jp660@Ek40WMVfnq30lP/dCo2E1lqXci1i6J@H8RMLJ2cwdzkmbc9lw5cDve5uYX71C1AgE31DSZml3KaztMpuM1SdkHoGSylsRgLVjr9YyW1tDYaDIBcCBjCRbqELbxNNRy81w4OBBz0YhYm1VMUzaRyAgbDIfwQGeHSnJ9fReTq11U2keYCA/IkrVXfRFEmbiWa87zESLLf/1NJPbTpJ5zoWmeG8q@oyGVnXTnr94dABoAamFoX0IKevX@0dHkQeYiAlJH7/dU5w@Fytj4oAxydUKwokK45aEzrf4kDQgP/km@E@@pdqmenqU/Kg9tDnDGtnqiEnM1Vkc1VgktbN4RXoEgEKNyJVEQrQ3At@qVlTYX1g3wedcgZrvRF1y@wY4cD9mU/sTuOE9tPCDOufvVeW2ncKSUaC1wmpfg2zxUnizOrQdkkOL4bxCzswn05nSRdGN3BCo6HcD@u/E0zyqIcXkf3C2lk1MGKlVMeG7GPTxlhN4tLqGw8VriAd0JZxD@s8J4i4lGs/Ao2iKJBeWfLia1h0@/bNRyD3cB2C/iIKOLz06dAsxvU7DyBGHtRJeEyUKpINmTZ6q1QQk/lh8p/h5qZZOk8dkl8ubkGdQ3mGp0UNShnkjZzn94G1pzeSWt6J2F6Zj8900zv7P9L7yxML3dYx/vU0j6ML8wKS4A4f7NttEMIe6W3a0ZqlbtB2DX3u1GtG/v9dprzjVZQXhVkRwtRx@MRMEVNTe0a62rHJKHdK9J5xEp5t@XIrHlf1ly85umCr1RFWC0U9tkYKsyTd/5@oq@92lc6VbbmVeG48KtMOWcsJ66Mwj9TrmnLgmPgN8pzNIw6RQbxy0NlkzANmjE4RU4KCsNeR4e2S2654Zn9cFCIDItMKDJR2K2NcCW2NFb2kLyXSXCMKpMyFdPEhcAqF25KLKIqkjdlrUfxRO9Jm6MtaZwAv5KfG4/Zzs@1N3xkmUV83Lsl@9aM/0YVees3K9gIVq@isUEh2ckjdXyskHtLbIb92mpyRlVBzbfmrbN/yFuV/VdR0tleL4a0FFJSvRObVqaYMHu0kVR0UXFSQEnmC07LJ7WuWChwqdp8FjOmhZLOmlsP1UzZ0Fh89mmw@oZ31k5xt7d4c5Fi2dDG1CiJeiRoKu6nIqji9VK7YgBsV/yt2hUHhciwyISiz@9VDqfCeGHAsIGxg40qsjO0rUwdl4BaKsqP6uS3/25qt9tHl0MRahUlqTolnV17tX9ESWz8NyrIrNCsYCNYSA22LKTalfGxOj5WyC9RUlhNjlsF/lI50Vu0NGkmLbHHCE9E43I8xPEr/Evh8hJSOD6C0esu/KvXG@PRDr@C0Xa6kNNbtuyNnqDtwbiaxEMgHtV@X6RIZPGlxnEKJ0PQz3UCPkLUwcT@QxxeiI3MQMPxCbxIwHsZj4k0Wf2jkfN0XeQ5qs5o4yLhSo6frxfo9HwqNLnM7yQfocUSRtsxjGoHvCUtbkmL8zmNkaXrNnxwCOPhMHCAvBoK94ztamJB4y@tj7@bz/EQjvRPgrIra4JmuP0IdX1a0hB/KUhTthiAo5ps8TAn17/NYeGzQYyPXvpWqlk4bjZWOYGFV2Avda1xW0/6HLqA2u9S5aTBulpetw9dAjHE0An5iG6kO5XmRv6Ib7Z0Jpz0qw/Q3Yfa32UEx/kWHwImRAqCIhHuv2KedIBvEIUS1l0tuW0gE@srJXVZEkuXGHylgIdUQKQKOc5mdHQReKgl6YSkuItCV7wGuvVozbem@iJMLxRoBnjyPR6sNaKFKxHfx7prReKx/mWF3wCxKOVwCJOkrSahz3gmp6CxvzPCy99qfBnwIPXQTjC089QE/hGjAhYCzeOT4F7@LKg18xpsIWA1rQAYK46QShrQBKAcHvaoF5qw1PNOtceFuLDfX/nmPXecUewvKSb@EMeXBb1J4s90IzEOhTQmYVR5mGtmo93E7maimik2vCBaCR0BeQr1aKPTdorxga9T6sLFwKHcv0fS@Zw0qEAad7z1mzp3eBCfewACU1daucKmIWvAF/twPgv8h0v4Mc8mLbdt9MXr8lk@gFspl@CMmN5CPgduJQtuIRzc08XnrWSeWEr80XS1hDJ8@0m7Uo767X6R43tEs@MoE8vddv8oTWaLYvVGNeZESMtv4Wq2vFqi6WAWv4j5e/hu3Op9BGNMxq2MJrth9dyuzcWodDpPDnB3yKxbzYU3KUQpdNuGjLm4Ds22iFPGVNUWxdVVwxo9KQFGVq6/kBawoTfemt54iy7ETCSbhIanKI6bdLpOYDFmnyEAbQkVMYOsviZzviVq04oLf4eHW0C8KpNiDy3oImmeq5mCkJm@@45eXDOTL/GsBLLsbobf1mCPj5NCji1N26PQoZ7uRNNcO5HqDNvR9wnlhHhWN6Nxa@2XY3@mqH1XlB8nY0D63VWbL4kvPZXiBxUEBPlvsJNyMMGtQXdoll9pFjkVWemYuJWmjmkG2evcCUMJOtpLr17DKE678AyedTXg/5f6WVJ9x72kj7in9K11BG3rHD88/Hc6V@LGPhy9//Dw00aLLJ36wUcl3Dw32cPR5OFo8fDmzZvsfw "Clean – Try It Online"
Save to `main.icl` and compile with: `clm -fusion -b -IL Dynamics -IL StdEnv -IL Platform main`
This produces a file `a.out` which should be run as `a.out -h <heap_size>M -s <stack_size>M`, where `<heap_size> + <stack_size>` is the memory that will be used by the program in megabytes.
(I generally set the stack to 50MB, but I rarely have programs use even that much)