[[ From MaxP ]]

WARNING for SW: Don’t forget to install the paclet: PacletInstall[“path_to_combinator_evolve_paclet”] (on all machines)
HINT for SW: GeneralUtilities are only needed at definition time, so there is no need to evaluate them on parallel machines.
In[]:=
<< CombinatorEvolve`;​​ParallelEvaluate[<< CombinatorEvolve`];​​<< GeneralUtilities`;
WARNING: I have to set some step limit because some of the inits don’t terminate. I don’t see any way to avoid that because of undecidability. So the results below might not be correct. I do check however that they all terminate at a fixed point.
In[]:=
$maxStepCount = 2000;​​combinatorInOutLeafCounts[expr_] := ModuleScope[​​ {First[#], Last[#]} & @ SKCombinatorLeftmostOutermostLeafCounts[expr, $maxStepCount]​​]
In[]:=
takeRangeForKernel[list_] := ModuleScope[​​ length = Length[list];​​ first = Floor[($KernelID - 1) / $KernelCount length] + 1;​​ last = Floor[$KernelID / $KernelCount length];​​ list[[first ;; last]]​​]
In[]:=
Catenate[ParallelEvaluate[#&/@takeRangeForKernel[#]]]===#&@Range[Prime[30]]
Out[]=
True

S and K

In[]:=
enumeration=Catenate[EnumerateCombinators/@Range[11]];
In[]:=
Length[enumeration]
Out[]=
40239014
In[]:=
leafCountsData=ResourceFunction["MonitorProgress"][#->combinatorInOutLeafCounts[#]&/@enumeration];
In[]:=
results=KeySelect[#≤100&][First/@KeySort[First[MinimalBy[#,#〚2,1〛&]]&/@GroupBy[leafCountsData,#〚2,2〛&]]]
Out[]=
In[]:=
Export["~/Downloads/results.wxf",results];
In[]:=
Counts[KeyValueMap[#1===#2&][Last[SKCombinatorLeftmostOutermostLeafCounts[#,10000]]&/@results]]
Out[]=
True100

S

In[]:=
enumerationS=Catenate[EnumerateCombinators[#,{s}]&/@Range[13]];
In[]:=
Length[enumerationS]
Out[]=
290512
In[]:=
leafCountsDataS=ResourceFunction["MonitorProgress"][#->combinatorInOutLeafCounts[#]&/@enumerationS];
In[]:=
resultsS=KeySelect[#≤100&][First/@KeySort[First[MinimalBy[#,#〚2,1〛&]]&/@GroupBy[leafCountsDataS,#〚2,2〛&]]]
Out[]=
In[]:=
Export["~/Downloads/resultsS.wxf",resultsS];
In[]:=
Counts[KeyValueMap[#1===#2&][Last[SKCombinatorLeftmostOutermostLeafCounts[#,10000]]&/@resultsS]]
Out[]=
True100

Investigation

In[]:=
In[]:=
ListStepPlot[LeafCount/@skresults]
Out[]=
20
40
60
80
100
2
4
6
8
10
In[]:=
FindFit[List@@@Normal[LeafCount/@skresults],aLog[x]+b,{a,b},x]
Out[]=
{a1.89389,b1.83119}
1.89Log[x]+1.83
In[]:=
Log[b,x]
Out[]=
Log[x]
Log[b]
In[]:=
Exp[1/1.89]
Out[]=
1.6974
In[]:=
Plot[Log[1.7x],{x,1,100}]
Out[]=
20
40
60
80
100
1
2
3
4
5
In[]:=
Plot[1.89Log[x]+1.83,{x,1,100}]
Out[]=
20
40
60
80
100
2
4
6
8
10
In[]:=
Show[%213,%]
Out[]=
20
40
60
80
100
2
4
6
8
10
In[]:=
FindFit[List@@@Normal[LeafCount/@skresults],Log[1+a,x],{a},x]
Out[]=
{a0.525778}
In[]:=
Show[ListStepPlot[LeafCount/@Values[skresults]],Plot[Log[1.525,x],{x,1,100}]]
Out[]=
20
40
60
80
100
2
4
6
8
10

S results