7
$\begingroup$

Do or do not, there is no try.     — Yoda

Here is another MathJax puzzle. The Starring MathJax puzzle involved handling numbers in MathJax, even though there are no count registers or numeric operations implemented in MathJax. This puzzle continues with that theme.

Goal: find the minimal replacement for (replace this line) in the following MathJax code

$$\require{begingroup}\begingroup
(replace this line)
\binary{19}
\endgroup$$

so that the output is the number 19, but displayed in binary:

$$10011$$

The Catch? Your code should produce the proper binary number no matter what non-negative integer is given in place of 19.

When counting the length of your solution, control sequences count as 1 character, as do macro parameters #1 (and ## if needed, and even ##1 if used in a nested macro definition), and pairs of braces ({ with a paired } count as one). So \stars and \s each count as 1. All other non-white-space characters count as 1, but please do use spaces and line breaks for clarity.

Example: \def \x #1:#2\x {#1#1\stop} has a character count of 10.

To make this easier, I've made a code snippet that counts the tokens for you. (Unfortunately, there are no code snippets on this site, so I had to use the SE sandbox for it.) Run the snippet, then paste your MathJax code into the resulting text area and press "Count Tokens". Only paste in the replacement lines, not the \require{begingroup}\begingroup or the \binary{19} or \endgroup lines, or they will be counted against you!

Do not use any additional \require{...} macros, or defeat the final call to \endgroup. Admittedly, the audience for this puzzle is small. Please share any answer that even almost works. A solution is known, and will be posted after a suitable period, if no other solution is offered.

It is not necessary to display your solution in a spoiler. Explanations, especially including self-tracing code is a plus, but not a requirement. A solution is known, but it is likely not optimal.

NOTE ☆ Before posting an answer, be sure to test it on a freshly loaded browser page ☆ Might also need to reload the page while editing, as inadvertent indiscretions in one edit can pervert MathJax results during later edits ☆

$\endgroup$
  • $\begingroup$ Initial solution in this camp has 148 tokens but hits MathJax's buffersize guardrail at a measly $\small\texttt{\binary{121}}$. Not yet worth posting. Goes through unary via $\small\texttt{\stars{}}$ plagiarized from Davide Cervone's solution at puzzling.stackexchange.com/a/38110/18129 $\endgroup$ – humn Aug 4 '16 at 12:47
  • $\begingroup$ My initial solution was around 185 tokens, but I have it under 100 at the moment (with only three static definitions and one dynamic one). $\endgroup$ – Davide Cervone Aug 4 '16 at 13:07
  • $\begingroup$ Amazing! fewer $\small\texttt{\def}$s than in $\small\texttt{\stars{}}$, and fewer than half of my present total. Please don't hurry to post, though I'm sure to enjoy the lesson when the time comes. Nice and puzzling to ponder in the meanwhile. $\endgroup$ – humn Aug 4 '16 at 13:30
  • $\begingroup$ I'm not going to post anything until you have had a chance to work out your own solution to your satisfaction, @humn, (unless you or someone else asks for a hint). I think I've finished my work on the problem for now, and will await your solution to see if there is anything I can crib... $\endgroup$ – Davide Cervone Aug 4 '16 at 14:14
  • $\begingroup$ @humn, your comment above made me look again at the stars problem, and I was able to restructure it (following my approach here) to use only 4 definitions, saving 7 tokens. I've posted the new solution. $\endgroup$ – Davide Cervone Aug 5 '16 at 12:49
5
+100
$\begingroup$

The Framework

One approach to this problem is to consider the binary number as follows:

\begin{align} 10011 &= 1\times 2^4 + 0\times 2^3 + 0\times 2^2 + 1\times 2^1 + 1\times 2^0\\ &= 2\cdot2\cdot2\cdot2\cdot1+2\cdot2\cdot2\cdot0+2\cdot2\cdot0+2\cdot1+1\\ &= 2\cdot(2\cdot2\cdot2\cdot1+2\cdot2\cdot0+2\cdot0+1)+1\\ &= 2\cdot(2\cdot(2\cdot2\cdot1+2\cdot0+0)+1)+1\\ &= 2\cdot(2\cdot(2\cdot(2\cdot1+0)+0)+1)+1\\ \end{align} (This is again Horner's Method, that we have seen before.) It means that the binary number is recursively formed as 2 times something plus either 1 or 0. So we can get the lowest digit by taking the number and dividing it by two; the remainder will be the lowest digit. Repeating that process on the result of the division will yield the next digit, and so on.

Another way to think of it is that 10011 divided by 2 is 1001.1, or 1001 with a remainder of 1. (That is, 19 divided by 2 is 9 with a remainder 1.) Continuing this process, 1001 divided by 2 is 100 with remainder 1 (9 divided by 2 is 4 with remainder 1), then 100 becomes 10 with remainder 0 (4 divided by 2 is 2 with remainder 0), 10 becomes 1 with remainder 0 (2 divided by 2 is 1 with remainder 0), and 1 becomes 0 with remainder 1 (1 divided by 2 is 0 with remainder 1). Any further division yields 0 with remainder 0.

So one way to proceed is to take our original number and divide by 2; the remainder is our lower digit and our result of the division is the next number to divide. Continue dividing by 2 until we get 0 as the result, collecting together the remainders as the digits in binary.

Of course, this approach works for any base (recursively divide by the base and take the remainder as the next lowest digit). [As an aside, one can handle "decimals" by multiplying by the base and taking the integer part as the next highest "decimal" number in the base, but that is not required by this puzzle.]


Current Solution

My current solution is 91 tokens, using 3 static definitions and 1 dynamic one, presented below.

$$\require{begingroup}\begingroup \def\binary#1{\n#1 \d % {}{}} \def\n#1 #2{#2#1} \def\d#1#2 #3 #4#5{\def\D##1#1##2 ##3##4 #5 ##5#1##6 ##7##8 {\n#2 \d % \binary {#4##7} ##3} \D 02468 0 #1 1 1 {} 0 01 0 23 1 45 2 67 3 89 4 1 98 9 76 8 54 7 32 6 10 5 } \binary{19} \endgroup$$

This uses the following code:

$$\require{begingroup}\begingroup
\def\binary#1{\n#1 \d % {}{}}
\def\n#1 #2{#2#1}
\def\d#1#2 #3 #4#5{\def\D##1#1##2 ##3##4  #5  ##5#1##6 ##7##8
{\n#2 \d %
\binary {#4##7}
##3}
\D 02468 0 #1 1    1 {}  0  01 0 23 1 45 2 67 3 89 4  1  98 9 76 8 54 7 32 6 10 5
}
\binary{19}
\endgroup$$

The \binary macro is called recursively with the current number (19, 9, 4, 2, 1, empty) as its parameter, divides it by 2, calling itself with the result and placing the remainder on the line below (just before the \endgroup). When it is called with an empty parameter, it stops, leaving the binary number on the lines below, ready to be output.

The process uses two static macros. The first is \n, which is used to terminate the loop when the parameter is empty (it uses the % technique to comment out the looping macro when the parameter is empty, as we have seen before).

The main loop is performed by the \d macro, which does the division by two. It does this by "long division". It divides the first digit of the number by 2, saving that as the first digit of the result, and "brings down" the remainder, along with the next digit, divides that by 2 as the next digit of the result, brings down the remainder, and so on. When we run out of digits, the final remainder is the binary digit we need, and it calls \binary again with the new number, saving the binary digit on the next line.

The parameters to \d are as follows:

#1  The first digit of the number being divided
#2  The remaining digits
#3  skip "%" or "% \binary"
#4  The result of the division so far
#5  The remainder being "brought down" from the last digit (initially blank)

Using #1 and #5, \d creates a macro \D that determines the result of dividing #5#1 by 2 and its remainder (these are the ##7 and ##3 parameters of \D). Then \D sets up the recursion by calling \n with the remaining digits, but set up so that when the loop terminates, \binary is called with the result of the division by 2 (so far), and the remainder on the next line (followed by any previous remainders, i.e., the digits of the binary number). If the looping \d doesn't terminate, then #3 eats up the % and \binary, and #4 gets the result so far, and #5 the remainder, and the loop repeats.

So how does \D work to get the division and remainder? It uses a data table that looks up the results as follows. The remainder comes first in the table, and uses the fact that in base 10, the final digit being 0, 2, 4, 6, or 8 means the remainder is 0 and anything else means it is 1. So the 02468 0 #1 1 encodes that and \D uses ##1#1##2 ##3 to find the digit (#1) either in 02468 or as #1 itself, and skips to the next space to find the remainder (##3). [We could have used 02468 0 13579 1 as the lookup table, but we save 4 tokens by using #1 in place of 13579, since if it is not in the first set, it must be in the second set.]

The result of the division is found in a similar way, but using both #5 and #1. First, #5 is used to locate either the 01 0 23 1 45 2 67 3 89 4 or the 98 9 76 8 54 7 32 6 10 5 sequence (using ##4 #5 to look for the #5 digit with two spaces on either side), and then the #1 digit is found within that; then the digit after the next space is the result of dividing #5#1 by 2. For example, if #5 is 1 and #1 is 5, we use the second sequence above, locate the 5 (in 54 7...) and take the 7 as the result, meaning 15 divided by 2 is 7 (with remainder 1).

So the sequence 01 0 23 1 45 2 67 3 89 4 means 00 and 01 divided by 2 are both 0, 02 and 03 divided by 2 are both 1, 04 and 05 divided by 2 are both 2, and so on. Similarly, 98 9 76 8 54 7 32 6 10 5 means 19 and 18 divided by 2 are both 9, 17 and 16 divided by 2 are both 8, and so on. One has to be careful to make sure that the first time any number appears in the list, it is as the digit, not the result, so that is why the second list is reversed. Had we done it in the other order (as 01 5 23 6 45 7 67 8 89 9), then when #1 was 5, for example, it would match the 5 at 5 23... rather than the one at 45 7... as desired. [One could use multiple spaces (or returns) to make it possible to use the increasing order, but it wasn't necessary, here).

The 1 {} between the remainder table and the division table has not yet been explained, and may be puzzling at first. This is there to handle the case of an initial 1 in the division. In order to have 19 divided by 2 become 9 (and not 09) we need the special case that an initial 1 produce nothing (just a remainder), not a 0. So the \binary macro sets up the initial remainder to be blank (so that \d gets #5 as a blank, not a 0 or 1 in that case). When that is true, the #5 will be three blanks in a row, and so the division table is actually 1 {} 0 01 0 23 1 45 2 67 3 89 4, meaning that 1 will produce a blank result for ##7 rather than the 0 it does when #5 is 0. Any other leading digit falls into the rest of the table and the blank #5 acts as a 0. [Technically, we should really have 01 {} in order to handle a leading 0 as well, so that \binary{019} could be processed, but we'd need to do better with the remainder table to handle this case properly, and it was not required by this puzzle in any case.]

In summary, the parameters for \D are

##1  skip to digit #1
##2  skip to space
##3  remainder of #5#1 divided by 2
##4  skip to double space followed by #5 followed by double space
     (i.e., find correct division subtable)
##5  skip to digit #1
##6  skip to space
##7  integer part of #5#1 divided by 2
##8  skip rest of table

The code above produces the final binary number with each digit on a separate line. This produces the proper output, but is not very aesthetically pleasing, and semantically incorrect. It is easy to get all the digits on a single line by replacing \binary with

\def\binary#1#2
{\n#1 \d % {}{}
#2}

and removing the line break before the ##3 in the definition of \D, at a cost of two tokens (the to new #2). This puts the remainder temporarily directly after the parameter to \binary, and \binary then moves it to the beginning of the following line.

Here is a live trace of this slightly longer code in action.

$$\require{begingroup}\begingroup \def\>#1#2 #3%;{\texttt{#1 #2}& \longrightarrow & \break{#3}#3%;} \def\<#1#2#3#4#5{\texttt{\d [#1][#2][#3][#4][#5]}& \longrightarrow & \break{\def\D##1#1##2 ##3##4 #5 ##5#1##6 ##7##8 {\n#2 \d % \binary {#4##7} ##3} \D 02468 0 #1 1 1 {} 0 ... }} \def\break#1{\def\&{}\=.#1\endbreak\+ \endbreak\.} \def\=#1 #2\endbreak#3{#3#1 #2\endbreak#3} \def\+.#1 {\&\def\&{&&}\texttt{#1}\\\=.} \def\..#1\endbreak#2\.{\&\texttt{#1}\\} % \def\binary#1#2 {\>\binary{[#1][#2]} \n#1 \d % {}{} #2} \def\n#1 #2{\>\n{[#1][#2]} #2#1} \def\d#1#2 #3 #4#5{\<{#1}{#2}{#3}{#4}{#5} \def\D##1#1##2 ##3##4 #5 ##5#1##6 ##7##8 {\>\D{..[##3]..[##7]..} \n#2 \d % \binary {#4##7}##3} \D 02468 0 #1 1 1 {} 0 01 0 23 1 45 2 67 3 89 4 1 98 9 76 8 54 7 32 6 10 5 } \begin{array}{lcl} \binary{19} %; \end{array} \endgroup$$

To really see \d in action, you need to use a larger number like \binary{195} so that \d produces multi-digit results: it will go through \binary{97}, \binary{48}, etc.


Possible reductions

Note that \n plays double duty, here, as it checks for the termination of both the \binary macro and the \d macro. But it may be possible to use the techniques of @humn in the Starring MathJax puzzle to eliminate it, saving 7 tokens.

Two more tokens can be saved in the lookup table by using #1 for the final pair of digits (as we did for the 13579 in the remainder table), but I left it as is to make the algorithm clearer.

One might also be able to do better than add the extra #2 to \binary as a means of eliminating the unwanted line breaks.


Generalization

It is possible to extend this binary version to work in other bases, but note that the separation of the lookup table into separate remainder and division tables relies on the fact that 2 divides 10 so that the remainders are independent of the previous remainder (#5). That is not the case in general, so for other bases, the remainders depend on #5, and need to be included in the data that is selected by the value of #5. Also, it is not always possible to order the division table so that the digits always appear before the first time that value is the result of the division. In that case, you can use braces to "hide" the result so that it will not be matched in the lookup process, at the cost of an extra token for the braces.

$\endgroup$
  • $\begingroup$ Hurray, Davide C, we approached from different angles again. (Perhaps you already passed through mine; my venture into with direct calculation was a magnitude less efficient than your solution.) I'm already having fun experimenting with your solution and am getting an idea of how much fun you had with its sub-puzzles. For different bases, my initial version asymptotically requires 1+ token per input-base increment and, ooof, 3 per output-base increment. And, of course, I'll be adding references to explanations in your solution(s), again. $\endgroup$ – humn Sep 7 '16 at 12:08
  • $\begingroup$ The comment about #2 refers to the change discussed just above the live trace (which presents the final number as one unit rather than one digit per line), @humn. I was impressed at how small your solution was. You had mentioned that you were using a unary representation in the middle, so I didn't work on that approach myself (I already had an earlier decimal version, and just worked on sliming that down). The unary approach worked better for you than I thought it would, but (of course), it limits the size of the number you can convert (it will be on the order on 5120). $\endgroup$ – Davide Cervone Sep 7 '16 at 18:03
  • $\begingroup$ While my version can handler larger numbers, yours converts to other bases more easily, and with fewer extra tokens. Making the remainder and division tables for larger bases in mine is much harder, and takes a lot more space. $\endgroup$ – Davide Cervone Sep 7 '16 at 18:04
  • $\begingroup$ The efficiency of long divison in this solution is almost heretical within the non-numerical semantics of MathJax. The trace also creates a wonderfully episodic story. Did you by any chance along the way consider anything like this other non-unary calculation that I found uneconomical all around (but almost intriguing enough to complete)?: i) Have a fractal tree of "bit buckets"; ii) put digits' bits into nearby corresponding buckets; iii) multiply by 10 ($\small 1010_2$) by moving copies of existing $\to$ 3 buckets over and 1 bucket over; finally, iv) comb through the redundant buckets. $\endgroup$ – humn Sep 7 '16 at 18:55
  • 1
    $\begingroup$ You asked for it, Davide C, you got it: 7 fewer tokens but not where you speculated (so another 7 might still be possible!). This is in \D, where you mentioned that 2 tokens could be saved by muddying the clarity with #1s. Turns out that one of my ideas from flailing at long division had lasting value: to order the doubling and halving digits like cascades, so that, e.g, where 89 points to 4, that 4 is also part of the 45 that points to 2. Here's a printout, with 83 tokens after deleting the now-unnecessary {}. $\endgroup$ – humn Sep 10 '16 at 11:22
3
$\begingroup$

A $\texttt{\binary}$ Klein bottle

These 72 replacement code tokens form 2 static macros and 1 dynamic macro, while blurring the distinction between inside and outside, reminiscent of a Klein bottle, with data that are not just produced by recursive calls but are explicitly those calls themselves.

$$\require{begingroup}\begingroup \def\safe{\text{\endgroup error}} \def \@ #1\endgroup{ #1\@ \endgroup0} \def \binary #1#2 #3\endgroup{ \def \N ##1#1 ##2 ##3 ##4 ##5 ##6 ##7 ##8 ##9 { ##8 ##3#2 #3##6\endgroup##2} \N \binary \binary \@ 1 #3 \@ 9 {} 8 7 6 5 4 3 2 1 0 % \binary {} \binary #3 #2 \@ 0 #3#3#3#3 #3 #1 #1 {} \binary {} } \binary{19} \endgroup$$ $\kern29em\safe$

This should actually count as 68 tokens because 4 tokens are nonfunctional empty $\small\texttt{\{}\,\texttt{\}}$ braces that ensure spaces at ends of lines. If those spaces haven’t been lost, here goes 68 without the empties:

$$\require{begingroup}\begingroup \def\safe{\text{\endgroup error}} \def \@ #1\endgroup{ #1\@ \endgroup0} \def \binary #1#2 #3\endgroup{ \def \N ##1#1 ##2 ##3 ##4 ##5 ##6 ##7 ##8 ##9 { ##8 ##3#2 #3##6\endgroup##2} \N \binary \binary \@ 1 #3 \@ 9 8 7 6 5 4 3 2 1 0 % \binary \binary #3 #2 \@ 0 #3#3#3#3 #3 #1 #1 \binary } \binary{19} \endgroup$$ $\kern29em\safe$

(If $\small\bbox[mistyrose]{\color{red}{\text{\safe}}} \raise-.8ex\strut$ follows those results, $\small\texttt{\endgroup}$ successfully practiced safe MathJax.)

The solution resides almost entirely within $\small\texttt{\binary{}}$, if within means anything anymore.

  • $\small\texttt{\binary{}}$ performs two different stages: cumulative conversion to unary and recursive halving to binary. Conversion to unary adapts the $\small\texttt{\stars{}}$ macro from Starring MathJax. Conversion to binary follows Davide Cervone’s framework.

  • Each unary digit is an instance of $\small\texttt{\binary}$ itself, called as a macro in the unary-to-binary stage.

  • Leading digit 0 acts as a wheelhouse and uses two dynamic skip parameters, $\small\texttt{##4}$ and $\small\texttt{##5}$, to decide how to handle i) a mere $\small\texttt{\binary{0}}$ call, ii) completion of a non-final decimal digit's unary accumulation, and iii) stage transition from unary accumulation to binary halving.

  • Being mandatory and otherwise confining, $\small\texttt{\endgroup}$ is commandeered as a delimiter, to terminate an initially-empty intermediate result and to precede the ultimate 0s and 1s. This does not defeat $\small\texttt{\endgroup}$ because it is faithfully rewritten and no macros follow it.

More explanation and proofreading to come as time allows, but for now just a fractal trace, a listing, and worksheets. In the live trace of $\small\texttt{\binary{25}}$, $\small\texttt{\b}$ represents $\small\texttt{\binary}$. Superfluous line breaks at the end are side effects of avoiding blank lines and of distinguishing between input 1s and output 1s.

$$\require{begingroup}\begingroup \def \Par #1{ \, \rlap{ \kern2mu\texttt {#1} } \G{\raise-.2ex\underline{\hphantom{ \texttt{#1}\, }}} } \def \G { \color{#888} } \def \Eol {{ \, \large \raise-.3ex\G{\unicode{8629}} \, }} \def \TSUB #1#2#3{ %1=[from] %2=[to] %3={fill2[from]fill1[from]fill0} \def \TSUC % ##1#1##2#1%\TSUC##3{\texttt{##1}##3\TSUC % ##2#1%\TSUC{##3}} \TSUC % #3#1%\TSUC{#2}#1%\TSUC% } \def \TYPE #1{{ \TSUB { } \Eol {#1} }} \def \RETURN #1~{ \small \TYPE{#1} \\[-1ex] #1~ } % \def \@ #1\endgroup{ \RETURN #1\@ \endgroup0} % \def \b #1#2 #3\endgroup{ \def \N ##1#1 ##2 ##3 ##4 ##5 ##6 ##7 ##8 ##9 { \RETURN ##8 ##3#2 #3##6\endgroup##2} \N \b \b \@ 1 #3 \@ 9 {} 8 7 6 5 4 3 2 1 0 % \b {} \b #3 #2 \@ 0 #3#3#3#3 #3 #1 #1 {} \b {} } % \begin{array}{r} \RETURN \b{25} \endgroup~ \end{array}$$

Empty $\small\texttt{\{}\,\texttt{\}}$ braces may be disregarded as they are nonfunctional and only highlight trailing spaces.

.                                 - - - WRUNG OUT - - -
$$\require{begingroup}\begingroup
\def\@#1\endgroup{#1\@
\endgroup0}
\def\binary#1#2
#3\endgroup{\def\N##1#1 ##2 ##3  ##4   ##5   ##6 ##7
 ##8 ##9
          {##8 ##3#2
#3##6\endgroup##2}
\N \binary          \binary \@ 1
       #3   \@
  9 {}
  8  7  6  5  4  3  2  1  0  %      \binary {}
 \binary #3 #2  \@
 0
   #3#3#3#3   #3  #1  #1         {}
 \binary {}
          }
\binary{19}
\endgroup$$
.
.                                 - - - AIRED OUT - - -
$$\require{begingroup}\begingroup
%
%
%     \@{}  prepends 0, as a remainder while halving,
%                       to the result that follows \endgroup
%
\def  \@  #1\endgroup{
#1\@
\endgroup0}
%
%
%     \binary{}  has a decimal-to-unary accumulation stage
%                and a unary-to-binary  halving stage
%
 \def  \binary  #1#2
#3\endgroup{
   \def  \N  ##1#1 ##2 ##3  ##4   ##5   ##6 ##7
 ##8 ##9
          {
##8 ##3#2
#3##6\endgroup##2}
\N \binary          \binary \@ 1
       #3   \@
  9 {}
  8  7  6  5  4  3  2  1  0  %      \binary {}
 \binary #3 #2  \@
 0
   #3#3#3#3   #3  #1  #1         {}
 \binary {}
          }
%
%
\binary{19}
\endgroup$$
.                             - - - PARAMETERS - - -
.
.    leading "digit's" current value    #1    1 - 9    (to be decremented)
.                                             0        (for quintupling or transition to halving)
.                                             %        (for doubling)
.                                             \binary  (to be halved for being consecutive)
.                                             \@       (when remainder=1)
.                subsequent "digits"    #2    remaining digits to accumulate
.                                                    OR instances of \binary to be halved
. resulting \binary\binary...\binary    #3    (being accumulated  OR  being halved)
.                                       ##1   (skip to current leading digit  OR  \binary  OR  \@)
.        additional 1 for the result    ##2   when leading-digit \@ signals that remainder=1 after halving
.         leading digit's next value    ##3   decrement  OR  %  OR  blank
.                                   ##4,##5   (skip to ##6)
.   append to #3 (\binary...\binary)    ##6   \binary  (as increment or as half of \binary\binary)
.                                             #3#3#3#3 (quintuple)
.                                             #3       (double)
.                                             \@       (when beginning a new round of halving)
.                                       ##7   (skip to ##8)
.                          next call    ##8   \binary  (while accumulating)
.                                             empty    (while halving)
.                                             0        (abort for \binary{0})
.                                       ##9   (leftovers)

If the following worksheets don’t make sense, join the club. They make less sense by the minute to me too, and any portion may be out of date.

.                        call  #1  #2...  |  #3...                         \e  ...
.                              --  -----     ----------------------------      ----
.   \binary{0}|\endgroup   \b   0   -     |   -                            \e
.                           0   %   -     |   -                            \e
.
.
.                        call  #1  #2...  |  #3...                         \e  ...
.                        ----  --  -----     ----------------------------      ----
.  \binary{12}|\endgroup   \b  12   -     |   -                            \e
.  \binary 12 |\endgroup   \b   1   2     |   -                            \e
.                          \b   0   2     |  \b                            \e
.                          \b   %   2     |  \b\b\b\b\b                    \e
.                          \b   -   2     |  \b\b\b\b\b\b\b\b\b\b          \e
.                                ...:
.                               :
.                          \b   2   -     |  \b\b\b\b\b\b\b\b\b\b          \e
.                          \b   1   -     |  \b\b\b\b\b\b\b\b\b\b\b        \e
.                          \b   0   -     |  \b\b\b\b\b\b\b\b\b\b\b\b      \e
.                           -   %   -     |  \b\b\b\b\b\b\b\b\b\b\b\b \@|  \e
.     ..........................:                                       :
.    : call  #1   #2...                    .............................:
.    : ----  --  -----------------------  :
.    % | \b  \b  \b\b\b\b\b\b\b\b\b\b \@  |   -                            \e
.      - \b   \b     \b\b\b\b\b\b\b\b \@  |  \b                            \e
.      - \b    \b        \b\b\b\b\b\b \@  |  \b\b                          \e
.      - \b     \b           \b\b\b\b \@  |  \b\b\b                        \e
.      - \b      \b              \b\b \@  |  \b\b\b\b                      \e
.      - \b       \b                  \@  |  \b\b\b\b\b                    \e
.      - \@                            -  |  \b\b\b\b\b\b                  \e
.                                            \b\b\b\b\b\b \@|              \e     0
.         ...................................:              :
.        :                                 .................:
.        :                                :
.        \b        \b        \b\b\b\b \@  |   -                            \e     0
.      - \b         \b           \b\b \@  |  \b                            \e     0
.      - \b          \b               \@  |  \b\b                          \e     0
.      - \@                            -  |  \b\b\b                        \e     0
.                                            \b\b\b \@|                    \e    00
.         ...................................:        :
.        :                                 ...........:
.        :                                :
.        \b           \b           \b \@  |   -                            \e    00
.      - \b            \@              -  |  \b                            \e    00
.                       -              -  |  \b \@|                        \e   100
.       ..................................:       :
.      :                                   .......:
.      :                                  :
.      | \b             \@             -  |   -                            \e   100
.         -              -             -  |   -                            \e  1100
.
.
.                                  d:   c   n   #2       #3    a           b
.
.                                 #1:  \b  #1   (-)  |   (-)   -       \e  -
.                                  2:  \b   1 (#2/-) | (#3/-) \b       \e  -
.                                  1:  \b   0 (#2/-) | (#3/-) \b       \e  -
.                                  0:  \b   %  (#2)  | (#3/-) #3#3#3#3 \e  -
.                                  %:  \b   -  (#2)  | (#3/-) #3       \e  -
.
.      (instant 0, blank #2,#3)    0:   0   %    -   |    -    -       \e  -
.     (begin halving, blank #2)    0:   -   %    -   |  (#3)  \@|      \e  -
.
.                                 \b:   -   -  (#2)  | (#3/-) \b       \e  -
.                                 \@:   -   -   (-)  |  (#3)  \@|      \e  1
.          (all done, blank #3)   \@:   -   -   (-)  |    -    -       \e  1
.
.
.    Un-encapsulate  \stars{19}                                                                                     #1,,#1,,,,,,,,,{}|,\b,{}|,,,,,,,,,,}
.             to be  \stars 19 .                                                                                    ''db__nnsssttta..|f__c
.
.    Decrement a leading-digit 9.           9,{}|,.8,,7 . . . 1..0..%,,,,,,\b,{}|,\b,#3.#2..\@|.0|...#3#3#3#3...#3..#1..#1.........{}|.\b.{}|,,,,,,,,,,}
.                                           'd___b__nn...............sssttt__a..|f__c.......................................................|zzzzzzzzzz
.
.    Decrement a leading-digit 1                              1,,0,,%,,,,,,\b,{}|,\b,#3.#2..\@|.0|...#3#3#3#3...#3..#1..#1.........{}|.\b.{}|,,,,,,,,,,}
.                                                             'db_nn.sssttt__a..|f__c.......................................................|zzzzzzzzzz
.
.    More decimals, quintuple                                      0,,%,,,,,.\b.{}|.\b..#2..\@|.0|,,,#3#3#3#3,..#3..#1..#1.........{}|,\b,{}|,,,,,,,,,,}
.    (nonempty #2, maybe empty #3).                                'db_nnsss......................ttt________a.......................|f__c..|zzzzzzzzzz
.
.    More bits                                                     0,,%,,,,,.\b.{}|.\b.#3,,,\@|,0|,,.#3#3#3#3...#3..#1..#1.........{}|,\b,{}|,,,,,,,,,,}
.    (empty #2, nonempty #3).                                      'db_nnsss.............ttt___a.|fc........................................|zzzzzzzzzz
.
.    All done  (empty #2,#3).                                        0,,%,,,,,.\b.{}|.\b,,,,\@|.0|,,.#3#3#3#3...#3..#1..#1.........{}|,\b,{}|,,,,,,,,,,}
.                                                                    'db_nnsss..........ttta..|f__c.........................................|zzzzzzzzzz
.
.    Double (nonempty #2, maybe empty #3).                            %,,,,..\b.{}|.\b..#2..\@|.0|,,,#3#3#3#3...#3..#1..#1.........{}|,\b,{}|,,,,,,,,,,}
.                                                                     'dbnn.......................sss........ttt__a..................|f__c..|zzzzzzzzzz}
.
.   \N \b.,,,,,,,,,\b,\@.1|,,.....#3...\@|  9 {}|  8  7 . . . 1  0  %      \b {}| \b #3 #2  \@| 0|   #3#3#3#3   #3  #1  #1         {}| \b {}|,,,,,,,,,,}
.      ''dbnnsssttt__a....|fc...............................................................................................................|zzzzzzzzzz
.
.    New round of     \@,1|,,,,,,.#3,,,\@|,.9.{}|,,8  7 . . . 1  0  %      \b {}| \b #3 #2  \@| 0|   #3#3#3#3   #3  #1  #1         {}| \b {}|,,,,,,,,,,}
.    halving.         ''d__bnnsss...ttt___a.....|fc.........................................................................................|zzzzzzzzzz
.
.    All done           \@,1|,,,,,,,,,,\@|,,9 {}|  8  7 . . . 1  0  %      \b {}| \b #3 #2  \@| 0|   #3#3#3#3   #3  #1  #1         {}| \b {}|,,,,,,,,,,}
.    (empty #3).        ''d__bnnsssttta..|fc................................................................................................|zzzzzzzzzz
.
.
.    ##1,                    'd  digit      = 1      d+b,n,a,f,c+x LT s            -->  3 LE s
.    ##2,                    _b  bit        = 1
.    ##3,,                  _nn  next digit = 2            a,f,c+x LT t LT d+b+n   -->  3 LE t
.    ##4,,,                 sss  skip1      = 3
.    ##5,,,                 ttt  skip2      = 3                       t LE x+y LT t+a LE c+x+y
.    ##6,                   __a  append     = 1
.    ##7|,                   |f  further    = eol+1       a LT f+c LT t+a,b+n
.    ##8,                   __c  call       = 1
.    ##9|,,,,,,,,,, |zzzzzzzzzz  cleanup    = eol+10      b LE f+c
.             . conditional spacer for 0  x = 1
.            .. conditional spacer for 0  y = 2            n+s+t+a LT z
.
.                                                                                                                                    #1d b #1n s t a -{}|-->f \b c {}|z
.                 9d {}| b 8n -7--6- - -2----1----0-----%-->s t  \b a -{}|-->f \b c -#3---#2---\@|------0|--------#3#3#3#3-----#3----#1----#1---------{}|-->f \b c {}|z
.                                       2d b 1n --0-----%-->s t  \b a -{}|-->f \b c -#3---#2---\@|------0|--------#3#3#3#3-----#3----#1----#1---------{}|-->f \b c {}|z
.                                                 0d b -%n -->s -\b----{}|-----\b----#3---->t  \@| a ---0|-->f c -#3#3#3#3-----#3----#1----#1---------{}|-->f \b c {}|z
.                                            1d b 0n ---%-->s t  \b a -{}|-->f \b c -#3-x-#2-y-\@|------0|--------#3#3#3#3-----#3----#1----#1---------{}|-->f \b c {}|z
.                                                 0d b -%n -->s -\b----{}|-----\b---------#2-y-\@|------0|---->t  #3#3#3#3 a --#3----#1----#1---------{}|-->f \b c {}|z
.                                                 0d b -%n -->s -\b----{}|-----\b-------->t a -\@|--> f 0| c -----#3#3#3#3-----#3----#1----#1---------{}|-->f \b c {}|z
.                                                       %d b n --\b----{}|-----\b---------#2-y-\@|------0|---->s -#3#3#3#3-->t #3 a -#1----#1---------{}|-->f \b c {}|z
.    \bd b n s t \b a -\@--1|-->f c -----#3-----\@|-->f c -9-(d)-{}|--------8--7- - -#3---#2---\@|------0|--------#3#3#3#3-----#3----#1----#1---------{}|-->f \b c {}|z
.                      \@  1| b n s -(a)-#3-->t \@| a -----9-(d)-{}|-->f c -8--7- - -#3---#2---\@|------0|--------#3#3#3#3-----#3----#1----#1---------{}|-->f \b c {}|z
.                      \@d 1| b n s t a --------\@|-->f c -9-(d)-{}|--------8--7- - -#3---#2---\@|------0|--------#3#3#3#3-----#3----#1----#1---------{}|-->f \b c {}|z
.
.                       b LE f+c LT b+n      a LT t      d+b,n LT s               a,f,c+x LT s,t                a LT f+c LT t+a
.                                                            a LT t LT d+b+n          x+y LT t+a LE c+x+y        n+s+t+a LT z
.                                                                                              t LE x+y


Initial solution:   This road to $\texttt{\binary}$ goes through $\texttt{\unary}$   (cleaned up)

The stripped down version would have 84 81 code tokens in 3 static macros and 2 dynamic macros, In the spirit of plagiarism solidarity, Davide Cervone’s solution’s thrifty and nifty use of $\small\texttt{#1}$ as a self-serving default digit-match, as adapted to $\small\texttt{#2}$ here, saved 3 code tokens for $\small\texttt{\binary{}}$ and reduced from 4 to 3 the number of additional tokens needed for each increment of output base.

$$\require{begingroup}\begingroup \def \binary #1{ \unary #1 10 } \def \unary #1#2 #3 { \def \U ##1#1 ##2 ##3 ##4 ##5 ##6 ##7 { ##3 \unary ##4#2 ##6#3 } \U 9 8 7 6 5 4 3 2 1 0 #2 % * \halvesies #3#3#3#3 #3 } \def \halvesies #1#2#3 #4 { \def \H ##1#2 ##2 ##3 ##4 ##5 { ##3 \halvesies ##4#2 } \H * #3 #4 #2 #4 % #410 } \binary{19} \endgroup$$

Traced:

$$\require{begingroup}\begingroup \def \G { \color{#888} } \def \Eol {{ \large \kern1mu \raise-.3ex\G{\unicode{8629}}\kern2mu }} \def \Par #1{ \rlap{ \kern2mu\texttt {#1} } \G{\raise-.2ex\underline{\hphantom{ \texttt{#1}\, }}} } \def \RETURN #1 #2\strut{ \texttt{#1} \Eol \texttt{#2} \\[-.5ex] \normalsize #1 #2\strut } % % \def \binary #1{ \small \texttt{\binary{#1}} & & \longrightarrow & \RETURN \unary #1 10 } \def \unary #1#2 #3 { \def \U ##1#1 ##2 ##3 ##4 ##5 ##6 ##7 { \scriptsize \texttt{\unary} \, \Par {#1} \, \Par {#2} \Eol \Par {#3} \kern-3.8em & & \longrightarrow & \RETURN ##3 \unary ##4#2 ##6#3 } \U 9 8 7 6 5 4 3 2 1 0 #2 % * \halvesies #3#3#3#3 #3 } % \def \halvesies #1#2#3 #4 { \def \H ##1#2 ##2 ##3 ##4 ##5 { \scriptsize \texttt{\halvesies} \, \Par {#1} \, \Par {#2} \, \Par {#3} \kern-3.8em & \Par{#4} & \longrightarrow & \RETURN ##3 \halvesies ##4#2 } \H * #3 #4 #2 #4 % #410 } % \scriptsize\begin{array}{lrl} \binary{19} \strut \end{array} \endgroup$$


Septenary

MathJax allows ready extension of this earlier version up to output base 7, where $\small\texttt{\septenary{19}} = \texttt{25}$, using 96 (99 with empty $\small\texttt{\{}\,\texttt{\}}$ braces) replacement code tokens.

$$\require{begingroup}\begingroup \def \septenary #1{ \unary #1 6543210 } \def \unary #1#2 #3 { \def \U ##1#1 ##2 ##3 ##4 ##5 ##6 ##7 { ##3 \unary ##4#2 ##6#3 } \U 9 8 7 6 5 4 3 2 1 0 #2 % * \seventhsies #3#3#3#3 #3 } \def \seventhsies #1#2#3#4#5#6#7#8 #9 { \def \H ##1#7 ##2 ##3 ##4 ##5 { ##3 \seventhsies ##4#7 } \H * #8 #9 #7 #9 % #96543210 } \septenary{19} \endgroup$$

Traced:

$$\require{begingroup}\begingroup \def \G { \color{#888} } \def \Eol {{ \large \kern1mu \raise-.3ex\G{\unicode{8629}}\kern2mu }} \def \Par #1{ \rlap{ \kern2mu\texttt {#1} } \G{\raise-.2ex\underline{\hphantom{ \texttt{#1}\, }}} } \def \RETURN #1 #2\strut{ \texttt{#1} \Eol \texttt{#2} \\[-.5ex] \normalsize #1 #2\strut } % % \def \septenary #1{ \small \texttt{\septenary{#1}} & & \longrightarrow & \RETURN \unary #1 6543210 } \def \unary #1#2 #3 { \def \U ##1#1 ##2 ##3 ##4 ##5 ##6 ##7 { \scriptsize \texttt{\unary} \, \Par {#1} \, \Par {#2} \Eol \Par {#3} \kern4.5em & & \longrightarrow & \RETURN ##3 \unary ##4#2 ##6#3 } \U 9 8 7 6 5 4 3 2 1 0 #2 % * \seventhsies #3#3#3#3 #3 } % \def \seventhsies #1#2#3#4#5#6#7#8 #9 { \def \H ##1#7 ##2 ##3 ##4 ##5 { \scriptsize \texttt{\seventhsies} \, \Par {#1} \, \Par {#2} \, \Par {#3} \, \Par {#4} \, \Par {#5} \, \Par {#6} \, \Par {#7} \, \Par {#8} \kern-4em & \Par{#9} & \longrightarrow & \RETURN ##3 \seventhsies ##4#7 } \H * #8 #9 #7 #9 % #96543210 } % \scriptsize\begin{array}{lrl} \septenary{19} \strut \end{array} \endgroup$$

$\endgroup$
  • $\begingroup$ Your solution is a nice one, and I do see the influence of our other puzzles on your answer (nice). I agree that the trace is a pretty one. I wish the end result didn't have all the extra spaces in it, however (just my OCD acting up). This is similar to a solution I have for one of the puzzles I have yet to post (I have two more in the wings, for when you are done with this one). $\endgroup$ – Davide Cervone Sep 7 '16 at 19:50
  • $\begingroup$ Yeh, I hope to get the naughty bits (tee hee, 0s and 1s) to behave better in an imagined revision that uses fewer $\small\texttt{%}$s as well. Inspired by the clarity of your works, it already took a revision, and one of the empty braces, to get the stars to be as neat as they are. Also trying to to piece together/apart another jigsaw-like puzzle that, if it works out, you deserve an unrestrained crack at. In the meanwhile, more power to you and your students, @Davide C! Many thanks again for MathJax in the first place, for making it so much fun recently, and in advance for future puzzles. $\endgroup$ – humn Sep 7 '16 at 20:20
  • $\begingroup$ You are welcome. I have really enjoyed working on these puzzles, and seeing the clever, but very different, approaches that you have taken. Thanks for starting the MathJax theme, here. I didn't realize just how flexibly MathJax could be used. $\endgroup$ – Davide Cervone Sep 7 '16 at 20:52
  • $\begingroup$ MathJax can be used flexibly, @Davide C? And how! Then there's (didn't fit into previous comment) the whole area of beauty and mathematical exposition where you took the Dragons, worlds beyond solving the puzzle and admirable in any medium. Your MathJax sonar probably already pinged off the new puzzle, a relatively easy possible local optimum along experiments toward a real devious concept that might not even pan out. $\endgroup$ – humn Sep 8 '16 at 17:01
  • $\begingroup$ I didn't get the chance to work on it before it was solved by others. It does seem like an interesting mechanism that could be useful in the future. I'm not sure what nefarious plan you have for it... $\endgroup$ – Davide Cervone Sep 11 '16 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.