Mathematical programming challenges for humans and other processes

For years now I’ve been jotting down “benchmarks” (which are to be fair more like “fun puzzles”) intended for competent genetic programming systems to try to solve. Sometimes they’re easy little homework problems that any person could do quickly with some thought, but which most extant GP systems might stumble over because of missing chunks of flow control, type system, precision, or patience—computational complexity and solution timing are things GP people don’t really want to talk about.

And sometimes they’re little nerd-snipes that honestly touch on open problems and conjectures in active fields of computer science and mathematics, which I’ve spent a few hours prodding but which I’d much rather ask an open-ended GP system to suggest a path towards. A lot of these are of the form “I saw an existence proof—due to Erdős, like as not–that there is always a number X that solves a class of problem Y, but what I want is an algorithm that will tell me X for some given Y.” Which in most cases you can imagine is an ambitious ask.

Anyway, here are some recent jottings, in no particular order. Worse, I kept poor notes on what specifically inspired them, so just assume there’s an antique library book or a recent preprint as a causal agent here.

fixed-size Egyptian fractions with negatives

Given a strictly positive integer \(k\), return exactly five nonzero integers \(a,b,c,d,e\) so that \(\frac{1}{k} = \frac{1}{a} + \frac{1}{b} + \frac{1}{c} + \frac{1}{d} + \frac{1}{e}\), where all of \(\{k,a,b,c,d,e\}\) are unique.

Note that unlike traditional Egyptian fraction representations, negative constants are permitted, so subtraction (and cancellation) is allowed. If you can find a shorter representation that uses three terms, you can fudge the other two by picking an arbitrary dummy integer and making one positive and one negative.

Note also that some integers can get big, depending on how this is approached. The greedy algorithm for (standard) Egyptian fractions of fixed number of terms grows those integers very quickly, for example.

same but for a general rational target

As above, but two integers are given, as numerator and denominator of the target fraction. The five results are still required to be unique and different from the input values.

Rational number from reptend (and filler)

Given two strictly positive integers \(k,n; k \neq n\), produce two integers \(a\) and \(b\) such that \(\frac{a}{b} = 0.k\overline{n}\) in decimal notation. For example given \(k=539, n=4762\) return integers \(a, b\) such that \(\frac{a}{b}= 0.539\overline{4762}\).

Note that most floating point representations won’t handle this for large constants. That makes me think it probably should be an algorithm focused on rational numbers and/or integers that works most generally. You don’t want to fall down on the approximation of an IEEE decimal here.

I note also that the longer \(k\) is (in terms of digits), then the farther the (minimal) answer will be from just \(\frac{n}{9[i]}\), where \(9[i]\) indicates the integer with the same number of 9 digits as \(n\) has digits. When there is no \(k\), then you can always find \(0.\overline{n}\) by taking \(\frac{n}{9[i]}\). For example, \(0.\overline{4762}\) is trivially \(\frac{4762}{9999}\).

The weird digitwise-modulo decimal-incrementing reciprocal fraction function

Given integer \(n\), calculate the repeating decimal \(\frac{1}{n}\), and take only the part to the right of the decimal point (discard the integer part, treat a non-repeating decimal as ending in repeating zeros). Now, increment every digit (including the repeated zero at the end, if any) modulo 10, and convert the result back into a rational number. Return the result as a pair of numerator, denominator integer. The rational number doesn’t have to be reduced, I guess; we’ll score it by actually dividing the integers to get the correct decimal and its reptend.

This is weird and basically made up, but it has some features that make it harder for a genetic programming system (of the sort I’ve seen) to handle. For instance, the idea of “incrementing each digit” involves type conversion or something very fancy in terms of arithmetic. Whereas a human coder could do it all pretty quickly with a rational number standard library.

Some examples:

\[\begin{align} n=1: \frac{1}{1} &= 1.0 \rightarrow 0.\overline{0} \rightarrow 0.\overline{1} \rightarrow \frac{1}{9} \rightarrow (1,9)\\ n=2: \frac{1}{2} &= 0.5 \rightarrow 0.5\overline{0} \rightarrow 0.6\overline{1} \rightarrow \frac{11}{18} \rightarrow (11,18)\\ n=3: \frac{1}{3} &= 0.\overline{3} \rightarrow 0.\overline{4} \rightarrow \frac{4}{9} \\ n=4: \frac{1}{4} &= 0.25\overline{0} \rightarrow 0.36\overline{1} \rightarrow \frac{13}{36} \\ n=5: \frac{1}{5} &= 0.2\overline{0} \rightarrow 0.3\overline{1} \rightarrow \frac{14}{45} \\ n=6: \frac{1}{6} &= 0.1\overline{6} \rightarrow 0.2\overline{7} \rightarrow \frac{5}{18} \\ n=7: \frac{1}{7} &= 0.\overline{142857} \rightarrow 0.\overline{253968} \rightarrow \frac{16}{163} \\ n=8: \frac{1}{8} &= 0.125\overline{0} \rightarrow 0.236\overline{1} \rightarrow \frac{17}{72} \\ n=9: \frac{1}{9} &= 0.\overline{1} \rightarrow 0.\overline{2} \rightarrow \frac{2}{9} \\ n=10: \frac{1}{10} &= 0.1\overline{0} \rightarrow 0.2\overline{1} \rightarrow \frac{19}{90} \\ n=11: \frac{1}{11} &= 0.\overline{09} \rightarrow 0.\overline{10} \rightarrow \frac{10}{99} \\ n=12: \frac{1}{12} &= 0.08\overline{3} \rightarrow 0.19\overline{4} \rightarrow \frac{7}{36} \\ n=13: \frac{1}{13} &= 0.\overline{076923} \rightarrow 0.\overline{187034} \rightarrow \frac{187034}{999999} \\ n=14: \frac{1}{14} &= 0.0\overline{714285} \rightarrow 0.1\overline{825396} \rightarrow \frac{23}{126} \\ \dots \end{align}\]

I can’t say this is “hard” or “a good idea”, but it does some odd things in a deterministic and low-complexity way that GP will definitely have a challenging time working through.