[Question]
  [
## Background
[SKI combinator calculus](https://en.wikipedia.org/wiki/SKI_combinator_calculus), or simply SKI calculus, is a system similar to lambda calculus, except that SKI calculus uses a small set of *combinators*, namely `S`, `K`, and `I` instead of lambda abstraction. Unlike lambda calculus, beta reduction is possible only when a combinator is given enough arguments to reduce.
The three combinators in SKI calculus are defined as follows:
$$
\begin{aligned}
S\;x\;y\;z & \overset{S}{\implies} x\;z\;(y\;z) \\
K\;x\;y & \overset{K}{\implies} x \\
I\;x & \overset{I}{\implies} x
\end{aligned}
$$
For example, the SKI expression \$ e=S(K(S\;I))K \$ is equivalent to the lambda expression \$ λx.λy.y\;x \$, as applying two arguments to \$ e \$ reduces to the desired result:
$$
\begin{aligned}
S(K(S\;I))K\;x\;y & \overset{S}{\implies} (K(S\;I)x)(K\;x)y \\
& \overset{K}{\implies} S\;I(K\;x)y \\
& \overset{S}{\implies} (I\;y)(K\;x\;y) \\
& \overset{I,K}{\implies} y\;x
\end{aligned}
$$
It is known that [any lambda expression can be converted to a SKI expression](https://en.wikipedia.org/wiki/Combinatory_logic#Completeness_of_the_S-K_basis).
A [Church numeral](https://en.wikipedia.org/wiki/Church_encoding#Church_numerals) is an encoding of natural numbers (including zero) as a lambda expression. The Church encoding of a natural number \$ n \$ is \$ λf. λx. f^n\;x \$ - given a function \$ f \$ and an argument \$ x \$, \$ f \$ repeatedly applied to \$ x \$ \$ n \$ times.
It is possible to construct a lambda expression (and therefore a SKI expression) that performs various arithmetic (e.g. addition, multiplication) in Church encoding. Here are a few examples of Church numerals and Church arithmetic functions: (The given SKI expressions are possibly not minimal.)
$$
\begin{array}{r|r|r}
\text{Expr} & \text{Lambda} & \text{SKI} \\ \hline
0 & λf. λx. x & K\;I \\
1 & λf. λx. f\;x & I \\
2 & λf. λx. f(f\;x) & S (S (K\;S) K) I \\
\text{Succ} \; n & λn. λf. λx. f(n\;f\;x) & S (S (K\;S) K) \\
m+n & λm. λn. λf. λx. m\;f(n\;f\;x) & S (K S) (S (K (S (K\;S) K)))
\end{array}
$$
## Challenge
Write an SKI expression that accepts a Church numeral of \$ n \$ and evaluates to the Church numeral of \$ \lfloor n/2 \rfloor \$.
## Scoring and winning criterion
The score is the total number of `S`, `K`, and `I` combinators used. The submission with the lowest score wins.
[Here is a Python script](https://tio.run/##hVLLTsMwELznK1bi4F1RoC23oJ44RT3miFDkJA6NSJ3ITlHKz5dNnGcL4mLZuzPjmbWrc30o9fMlhB0U8hinEhp/2J3H3bcPDX4Tnnkhb/8HuPGCRafxvFRlUEljVWQ/c7TkewC2lsknA9@Cdz5lpYEEcg227QHkmTuKcB8I34HfHjbvTBj3qL5kgQlbaRmq6Di7HQgcGI@yqpROMbiBEEPiQeyxKiukF5DXhYWIxLi7yqj6ZPRkw8WzSWnGeCPmdMQpxiwkOVJdRgnqbhzsTI@8fniZPxtjhg79sCHMCJu5l9/wTXdDZsrjeEeP1jhD3bPcmu3cAVsE1VRGWZuX2kKZwevhZJIDrFewWcHWu6tMrmvsNacHFRyO2M@f/X/aIYa4D2lPDnfjpRtc70WmaV5zzWNmxAd@soUS67RqgyKRIDdqZeuo56BcQTy9koT79i/shmENqG7eksht4lkEWRR4K9jZlO37Gqk/FG7WrhQvSm3AlnaQxZeK2pAcQQhxCS68Tq1FsCXhKlHXYKOzQE9PsL1K5FBDJvJ@STIIXQfZrieCCNuP7ovV/Mcv3dHlBw "Python 3 – Try It Online") to check the correctness and score of your SKI expression. For the record, I have a (relatively naïve) solution of score 126.
  
[Answer]
# 40 combinators
```
S(S(SI(K(S(S(KS)K)(K(S(S(KS)(S(KK)S))(K(S(KK)(S(S(KS)K)))))))))(K(S(SI(K(KI)))(K(KI)))))(KK)
```
[Try it online!](https://tio.run/##hVNNb6NADL3zKyz1MLaatkl6Y5XTnhBHjlWFBhg2qAQQQyrSP596ZvhMWm0OxGO/Zz@/gebSHevq9RrBAUp5SjIJvT9Glyn68qHHL8ILP8gLfwH3XrCq9J6XqRwa2WoV648CNfkegO5k@sHAt@CdT3ndQgpFBdrUAIrcHUUUBsJ34Len3TsTphjVpywxZSmGoUrLORxA4Mh4lk2jqgyDOwgxJBmbPTd1g/QH5G1i1URiYke1qju31SzDrafTup3WmzDnE85rLJYkR@rqOMXK2sHKqok3mJf7CxtzdOinHWFO2C@1/ITv7YS8rU/TjAFd4QL1yO22LOcBWCKovmmV1kVdaahz@Hs8t@kRthvYbWDvPTRtUXU49JwvVPByxHp@rf@nHGGEYUQhOdydFmvcoEVmWdFxzmNmzAe@slUn7mO6jR2JBDmrle7igYNyA8l8SxIezbtwGM0aUdZvSeSCZLGCLEu8b2hlSnO/raz@KdxtXSpZpcyChnaU5aeKzZK8ghDialyIAit9ED/H5hlSRC7F4Qwafw5s@GHgjvbfRCFdecA8deXZWsuNWbbAHiy8enmB/Y1ZDjXaRd4PJo2Nbj3ab2eCiMw35IvN8mNaq6PrNw)
Generated with a little help from a slightly modified version of [my answer to Combinatory Conundrum](https://codegolf.stackexchange.com/a/128136/39242):
$$\begin{align\*}
\textit{zero} &= λf. λx. x = KI \\
\textit{succ} &= λn. λf. λx. f\,(n\,f\,x) = S(S(KS)K) \\
\textit{zero-pair} &= λf. f\,\textit{zero}\,\textit{zero} = S(SI(K\,\textit{zero}))(K\,\textit{zero}) \\
\textit{next-pair-helper} &= λf. λm. λn. f\,n\,(\textit{succ}\,m) \\ &= S(S(KS)(S(KK)S))(K(S(KK)\,\textit{succ})) \\
\textit{next-pair} &= λp. λf. p\,(\textit{next-pair-helper}\,f) \\ &= S(S(KS)K)(K\,\textit{next-pair-helper}) \\
\textit{half} &= λn. n\,\textit{next-pair}\,\textit{zero-pair}\,K \\ &= S(S(SI(K\,\textit{next-pair}))(K\,\textit{zero-pair}))(KK)
\end{align\*}$$
[Answer]
# 31 combinators
```
S(S(S(SI(K(S(S(KS)(S(KK)S))(K(S(KK)(S(S(KS)K)))))))(KK))(K(KI)))(K(KI))
```
[Try it online!](https://tio.run/##hVNNb6swELzzK1bqwbtq2ibpjaec3glx5FhVyIB5QSWAbFKR/vl0jflMWr1EStbe2fHMGJpLe6yr12sEByjlKckkdP5YXabqy4cOvwgv/ENe@Au484JVp/O8TOXQSG1UbD4KNOR7AKaV6QcD34J3XuW1hhSKCoztARS5W4ooDITvwG9Pu3cemGpUn7LElKXYCVX2M4cDCBwnnmXTqCrD4A5CDElGsuembpD@gLzdWJFITPqjtGrPupplOHsmrfVkb8KcTzjbWJgkN9TWcYpVHwcrq6a5IbzcX8SYo0M/7Qhzwm6p5Sd815@Q6/o0nTGgK1ygHpluy3IegCWC6hqtjCnqykCdw9/jWadH2G5gt4G999Doompx4JwvVLA5Yj2/9v/TjjDCMKKQHO5OSx/coEVmWdHynseTMS/4ylZMzGPZRkYiQS5qZdp4mEG5gWS@JQmP9lk4jGGNqD5vSeSKZGFBliXeE/Yypb1fLat/Cndbt5WstqxBO3aU5aeKrUm2IIS42hT4G/TiJyMhRawgdCVGsy/7sXu2GQY0/V@Zaz5gFc/62Jtc@gbbXcTy8gL7m1wcakyGvB/yGIlu49hv5wER2dfFF5vle7NWR9dv "Python 3 – Try It Online")
$$\begin{align\*}
\textit{zero} &= λf. λx. x = KI \\
\textit{succ} &= λn. λf. λx. f\,(n\,\,f\,\,x) = S(S(KS)K) \\
\textit{fst} &= λm. λn. m = K \\
\textit{next} &= λg. λm. λn. g\,\,n\,(\textit{succ}\,\,m) = S(S(KS)(S(KK)S))(K(S(KK)\,\textit{succ})) \\
\textit{half} &= λn. n\,\,\textit{next}\,\,\textit{fst}\,\,\textit{zero}\,\,\textit{zero} = S(S(S(SI(K\,\textit{next}))(K\,\textit{fst}))(K\,\textit{zero}))(K\,\textit{zero})
\end{align\*}$$
[Answer]
# 56 combinators
```
S(K(SI(KK)))(S(SI(K(S(S(K(S(K(S(S(K(S(KS)K))S)(KK)))(S(K(SI))K)))(SI(K(KI))))(S(K(S(S(KS)K)))(SI(KK))))))(K(S(SI(K(KI)))(K(KI)))))
```
[Try it online!](https://tio.run/##hVNNb6swELzzK1bqwbtq2ibpjaec3glx5FhVyIB5QSWAgFSkfz5d25iPpNW7RGt7ZjwzDs2lP9bV6zWCA5TylGQSBt9Nl2n68mHAL8IL/5AX/gIevGB1MnhepnJoZNupuPsosCPfA@h6mX4w8C1451Vet5BCUUGnzwCK3C5FFAbCt@C3p907E6YZ1acsMWUrmqFKwzkcQKBjPMumUVWGwR2EGJI4seembpD@gLzdWIlITMxVrerPbTXbsPG6tG6neBPmfMI5xiIkWVJfxylWpg52Vk28sbzcX9SYo0U/7QhzwmHp5Sf8YG7I2/o03TGiK1ygHlluy3YegC2CGppWdV1RVx3UOfw9ntv0CNsN7Daw9x6atqh6HDXnBxUcjtjPr@f/OY4wwjCikCzuzospbvQis6zoec9jZswLfrKVEutoNadIJMhWrbo@HjkoN5DMryThUf8XDq4shzJ9SyI7JIsIsizxXtDYlPp9W1n9U7jb2q1ktaUDatpRlp8q1iE5ghDialwHGGrTbF@PGLks82RScUiH0yQiu9CUkFfuYG5hUtZz6OQNduLQlW3M3lbNrh3fVGoOuKlFoy8vsL@p1KJcqeT9UKUTum1yv50JItJfmi82y09u7Y6u3w "Python 3 – Try It Online")
This is the hand-optimized version of my own solution (originally of score 126). I also used the "pair" construct, but in rather basic way.
$$
\begin{align\*}
\textit{zero} &= λf. λx. x = KI \\
\textit{succ} &= λn. λf. λx. f\,(n\,f\,x) = S(S(KS)K) \\
\textit{pair} &= λx. λy. λf. f\,x\,y \\
\textit{zero-pair} &= \textit{pair}\,\textit{zero}\,\textit{zero} \\
\textit{fst} &= λp. p\,(λx. λy. x) \\
\textit{snd} &= λp. p\,(λx. λy. y) \\
\textit{next-pair} &= λp. \textit{pair}\,(\textit{snd}\,p)\,(\textit{succ}\,(\textit{fst}\,p))\\
\textit{half} &= λn. \textit{fst}\,(n\,\textit{next-pair}\,\textit{zero-pair})
\end{align\*}
$$
Then I used [\$SKIBC\$-conversion](https://en.wikipedia.org/wiki/Combinatory_logic#Combinators_B,_C). Those reverse-applications generated lots of \$C\$s (\$C = (S (S (K (S (K S) K)) S) (K K))\$), which turned out to be very heavy even after reduction.
[Answer]
# 45 combinators
```
S(K(SI(KK)))(S(SI(K(SI(K(S(K(S(S(KS)(S(K(SI))K))))(S(KK)(S(KK)(S(S(KS)K)))))))))(K(S(SI(K(KI)))(K(KI)))))
```
From `\n.(\p.p(\xy.x))(n(\p.p(\xyf.fy(\fz.f(xfz))))(\f.f00))`.
]