# Golang hash digest sizes

Golang has several hash algorithms implemented in the crypto package. I needed their digest sizes. So it summed them up in this table:

hash algorithm digest size
MD4 128
MD5 128
SHA1 160
SHA224 224
SHA256 256
SHA384 384
SHA512 512
MD5SHA1 N/A
RIPEMD160 160
SHA3_224 224
SHA3_256 256
SHA3_384 384
SHA3_512 512
SHA512_224 224
SHA512_256 256

# When is Tutte’s theorem in K₅ violated?

##### Theorem

A graph, G = (V, E), has a perfect matching if and only if for every subset U of V, the subgraph induced by V − U has at most |U| connected components with an odd number of vertices.
Tutte’s theorem

##### Illustration

Consider the two examples given in Figure 1. G is a bipartite graph and we consider two possible subsets U the induced subgraph of G-U is given on the right side.

1. For U₁ the number of odd components in G-U is 1 and the size of U is given with 3. Because 1 ≤ 3, the Tutte theorem holds.
2. For U₂ the number of odd components in G-U is also 1 and the size of U is also given with 3. Again, the Tutte theorem holds.

For any U, this condition will hold. Underneath the perfect matching is given (vertex 1 is associated to vertex 2, etc).

##### Problem setting

Consider graph K₅. A perfect matching clearly cannot exist for K₅, because a perfect matching can only exist if the number of vertices is even (as every vertex is associated to another vertex). Because the Tutte theorem provides a necessary and sufficient condition for the existence of a perfect matching, it should yield

For some subset U of V, the subgraph induced by V − U
has less than |U| connected components with an odd number of vertices.

##### Question

What is U for K₅? The solution is equivalent for its incomplete variant, which was originally given to me.

##### Solution

I wasn’t able to come up with a solution. So I wrote a program to try all combinations:

```#!/usr/bin/env python3

import itertools

def component_sizes(G):
"""component sizes in an undirected graph"""
comps = list(set([v]) for v in G[0])
for e in G[1]:
s, t = e[0], e[1]
idx_s, idx_t = -1, -1
for i, comp in enumerate(comps):
if s in comp:
idx_s = i
if t in comp:
idx_t = i
if idx_s == idx_t:
continue
else:
for item in comps[idx_t]:
comps.remove(comps[idx_t])
return tuple(sorted(len(comp) for comp in comps))

assert component_sizes(([1], [])) == (1,)
assert component_sizes(([1, 2], [])) == (1, 1)
assert component_sizes(([1, 2], [(1, 2)])) == (2,)
assert component_sizes(([1, 2, 3], [(1, 2)])) == (1, 2)

def subgraph(G, excl_vs):
"""Subgraph induces by excluding vertices"""
red_V = tuple(filter(lambda v: v not in excl_vs, G[0]))
red_E = tuple(filter(lambda e: e[0] not in excl_vs and e[1] not in excl_vs, G[1]))
return (red_V, red_E)

assert subgraph(([1], []), [1]) == (tuple(), tuple())
assert subgraph(([1, 2], [(1, 2)]), [1]) == ((2,), tuple())
assert subgraph(([1, 2, 3], [(1, 2), (2, 3), (3, 1)]), [1]) == ((2, 3), ((2, 3),))

if __name__ == '__main__':
def excl_vs_selection(G):
for size in range(len(G[0])):
for sel in itertools.combinations(G[0], r=size):
yield set(sel)

K5 = ((1, 2, 3, 4, 5), list(itertools.combinations(range(1,6), r=2)))
reduced_K5 = ((1, 2, 3, 4, 5), [(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)])

G = K5
for excl_vs in excl_vs_selection(G):
sub = subgraph(G, excl_vs)
sizes = component_sizes(sub)
odd_sized_comps = len(list(map(lambda v: v % 2 == 0, sizes)))
if odd_sized_comps > len(excl_vs):
print(excl_vs)
#raise ValueError("Tutte theorem violated with exclusion vertices {}".format(excl_vs))
```

The program yields `set()`. Hence the only solution is the empty set.

Consider `U = {}`. Then the induced graph is K₅ itself. The number of connected components in K₅ is 1 (all pairs of vertices are reachable from each other) and this component has an odd number of vertices (namely 5). The size of U is 0. And `1 > 0`, so the Tutte theorem is violated and no perfect matching exists indeed.

# Make 24 out of 1, 3, 4 and 6

###### Problem

Give a mathematical expression which equals 24. This expression is only allowed to use the basic arithmetic operators +, -, * and /. The numbers 1, 3, 4 and 6 must occur exactly once. No magic or tricks!

###### Setting

I was given this problem last Friday by one colleague. It was ridiculously difficult to come up with a solution. As mathematician you try to understand the structure behind the problem. You look at the prime numbers involved. In the expression you have {3, 2, 2, 2, 3} and in 24 you have {2, 2, 2, 3}. So you need to get rid of one three. But how? None of us 6 guys came up with a solution in less than an hour. But we actually found one academic who found the solution after 2 hours (a bit of sleep was involved, because he was very tired).

Well, my mathematical brain failed, but my computer science brain screamed “brute force!”. So let’s do it. I wrote a python script, which solved a subproblem in 18 lines. This is a more complete version which solves the problem for any four numbers and any target value. This script prints possible correct solutions to stdout in less than 0.5 seconds:

```import itertools

def parenthesized(a, b, c, d):
"""Generate all expressions where operators
are represented with substitution characters
"""
yield '((`{} \$ <{}) @ (>{} ! _{}))'.format(a, b, c, d)
yield '((`{} \$ (<{} @ >{})) ! _{})'.format(a, b, c, d)
yield '(`{} \$ ((<{} @ >{}) ! _{}))'.format(a, b, c, d)
yield '(`{} \$ (<{} @ (>{} ! _{})))'.format(a, b, c, d)

def main():
"""Main routine generating math expressions equating 24
using numbers {1, 3, 4, 6} exactly once and using operators
-, +, / or *.
"""
for arr in itertools.permutations([1, 3, 4, 6]):
for expr in parenthesized(*arr):
# we can omit '-' in these iterations, because all values
# will also be considered with a sign
for fo, so, to in itertools.product(['+', '/', '*'], repeat=3):
for s1, s2, s3, s4 in itertools.product(['', '-'], repeat=4):
try:
# replace operators
e = expr.replace('\$', fo).replace('@', so).replace('!', to)
# use either sign '' (hence +) or '-' (hence -) at every place
e = e.replace('`', s1).replace('<', s2).replace('>', s3).replace('_', s4)
result = eval(e)
except ZeroDivisionError:
continue
if result == 24:
yield e

if __name__ == '__main__':
for solution_expression in main():
print(solution_expression)
```
###### Spoiler

In the following I will give a list of hints. The further below you go, the closer you come to the solution (select text to display items). The solution itself is not given here:

1. Most values we ended up with are too small for 24. So we conjectured that number 6 will occur as factor, which turned out to be true.
2. Factor 6? So we look for factor 4 as well, right? Actually no. I mean yes, but with an indirect representation.
3. Given {1, 4} on the left-hand side and {1, 3, 4} on the right-hand side. Find operators such that LHS and RHS equate.
4. How about 1 / (1 / 4)? Two ones? I guess one of them has to be 6.
5. Given 6 / (1 / 4)? How can we represent 1/4 using {1, 3, 4}?

# Running Donald Knuth’s CWEB programs

I just realized that no-one documented how to quickly run Donald Knuth’s programs he publishes in his WEB system.

Suppose you want to compile a program like commafree; a program he wrote between September and December 2015 for his Annual Christmas tree lecture in 2015 about Universal Commafree Codes.

1. Download the webfile which comprises documentation and source code.

`wget http://www-cs-faculty.stanford.edu/~uno/programs/commafree-eastman.w`
2. Recognize that the programming language used is C. Hence we need to use `cweave` and `ctangle`; not the original `weave` and `tangle` designed for Pascal.
All those programs come bundled with TeX distributions like TeXLive. Once you have them installed and your system can find executables like `pdflatex`, it will also find `cweave`, etc.
3. First, we generate the documentation.
1. We run

`cweave commafree-eastman.w`

On my system this gives the output

```This is CWEAVE, Version 3.64 (TeX Live 2015/dev/Debian)
*1*3*8
Writing the output file...*1*3*8
Writing the index...
Done.
(No errors were found.)```
2. Three files are generated, namely `commafree-eastman.idx`, `commafree-eastman.scn` and `commafree-eastman.tex`.
3. As a small remark, the TeX file uses the `cwebmac` definitions. So it is a file full of definitions and this file is also provided with your TeX distribution:
```% head -n 1 commafree-eastman.tex
\input cwebmac
% locate cwebmac
/usr/share/texlive/texmf-dist/tex/plain/cweb/cwebmac.tex
/usr/share/texlive/texmf-dist/tex/plain/cweb/pdfXcwebmac.tex
/usr/share/texlive/texmf-dist/tex/plain/cweb/pdfcwebmac.tex
/usr/share/texlive/texmf-dist/tex/plain/cweb/pdfdcwebmac.tex
/usr/share/texlive/texmf-dist/tex/plain/cweb/pdffcwebmac.tex
/usr/share/texlive/texmf-dist/tex/plain/cweb/pdficwebmac.tex```
4. Then we run the original tex program to build a dvi file.

`tex commafree-eastman.tex`

This gives me the output:

```This is TeX, Version 3.14159265 (TeX Live 2015/dev/Debian) (preloaded format=tex)
(./commafree-eastman.tex
(/usr/share/texlive/texmf-dist/tex/plain/cweb/cwebmac.tex) *1 [1] *3 [2]
[3] *8 Index: (./commafree-eastman.idx) [4] Section names:
[0] )
Output written on commafree-eastman.dvi (6 pages, 16116 bytes).
Transcript written on commafree-eastman.log.```
5. Followingly, a file `commafree-eastman.dvi` is written as the output states. Opening it directly with evince 3.14.2 shows the output with some errors (the typical font encoding problems of TeX like < in #include statements is replaced by ¡). With okular 0.21.3 I can view the document without any problems.
6. We convert the DVI file using the utility `dvipdfm` provided with your TeX distribution:
`dvipdfm commafree-eastman.dvi`

For me, this gives:

```commafree-eastman.dvi -> commafree-eastman.pdf
[1][2][3][4][5][6]
45807 bytes written```

Then we have a PDF output file `commafree-eastman.pdf` containing the documentation.
I think this is the usual way to view documents, you were looking for.

4. We generate the source code:

1. First we run `ctangle`:
`ctangle commafree-eastman.w`

which gives me:

```This is CTANGLE, Version 3.64 (TeX Live 2015/dev/Debian)
*1*3*8
Writing the output file (commafree-eastman.c):
Done.
(No errors were found.)```
2. Nice! So we got a `commafree-eastman.c` file.
3. We compile the C file with a C compile like the GCC:
`gcc -Wall -o commafree-eastman commafree-eastman.c`

This gives me:

```./commafree-eastman.w:38:1: warning: return type defaults to ‘int’ [-Wreturn-type]
main (int argc,char*argv[]) {
^
./commafree-eastman.w: In function ‘main’:
./commafree-eastman.w:42:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^```
4. We run this new executable program:
```./commafree-eastman
Usage: ./commafree-eastman x1 x2 ... xn```

This gives the same output as in the video.

So we got a `commafree-eastman.pdf` and `commafree-eastman.c` file which was what we were going for.
I will also refer here to my Literate programming talk at PyGraz back then.