13

2

## Background

This puzzle is a variation on the four fours puzzle (itself the topic of a past question). Like that puzzle, the aim is to find mathematical expressions for different whole numbers, using only four digits and certain mathematical operators. In this case, however, the **permitted digits are just 2, 0, 1 and 5**. Each must appear precisely once in the solution and in the correct order. Surprisingly many whole numbers can be represented this way. Solvers are encouraged to try solving it by hand first, as it's strangely enjoyable.

## Rules

Constants may be constructed from single or multiple digits:

- Integers: e.g. 2, 0, 15, etc.
- Decimals: e.g. .2, .01, 1.5, etc.
- Repeating decimals: e.g. .2~ (=0.222...), .15~ (=0.1555...), 20.15~~ (=20.1515...)

The following unary operations are permitted:

- Unary negation: -x
- Square root: sqrt(x)
- Integer factorial: x!

The following binary operations are permitted:

- Standard arithmetic operators: x+y, x-y, x*y and x/y
- Arbitrary exponentiation: x^y
- Arbitrary roots: rt[x](y) (= x'th root of y)

## Task

Your program should print out expressions for as many of the integers between 0 and 100 as it can, and then output the number of expressions it has produced.

- The solutions must be printed in order in the format n=[expr].
- The expressions must use all the digits 2, 0, 1, 5, once each in that order.
- The expressions must be printed using the notation described above. Unnecessary parentheses are permitted but not required, as is whitespace. The order of operator precedence is unary negation, factorial, exponentiation, multiplication/division and addition/subtraction.
- The program need not return solutions for all the numbers. A program that simply outputs 0 is therefore valid; however, see the scoring section below.
- The program should run in under 15 minutes on a modern computer.

You may write a program or function. The expressions should be printed to STDOUT (or closest alternative). The number of expressions can be printed to STDOUT or returned as an integer. Standard code golf restrictions apply.

## Example output

```
0=2*0*1*5
10=20*1*.5
42=((2+0!)!+1)!/5!
100=20*1*5
4
```

## Scoring

**Update**: *@orlp has noted a flaw in the scoring system. See http://meta.codegolf.stackexchange.com/questions/5106/way-of-salvaging-two-zero-one-five-puzzle-challenge for a discussion of how or whether this should be fixed.*

Solutions are scored *first* by the number of expressions they produce and *then* by their code length in bytes. Hence, a 1000 byte program that produce 80 results will beat a 100 byte program that produces only 79 (though the latter could easily be extended to include the missing results).

For those who would like a motivating target, below is a lower bound on the number of expressions that can be represented. I don't plan to submit an entry, so it may well be possible to win with less!

At least 85 (out of 101), though it may well be higher.

## Scoreboard

As an extra incentive, here is a summary of the score progression. Whenever you beat the highest score, feel free to add yourself to the top of the table (or ask someone else to).

- 0 expressions, 1 byte (Pyth):
*implementation that just outputs 0*

Is .20 a permitted constant? – Luke – 2015-04-16T18:25:53.723

1@Luke: yes, though it can also be represented as (.2 + 0) so it doesn't increase expressivity – Uri Granta – 2015-04-16T18:39:41.137

Is the root function ever necessary in a solution?

`rt[0](y)`

is undefined,`rt[1](y)`

is the same as`1*y`

, and the square root is unlikely to lead anywhere useful, since any factorial is unlikely to be a square number. You could do`rt[2](0-1+5)`

, but that's not as useful as`2*0-1+5`

.... 20th or 3rd roots are even less likely to be useful, and doing roots with decimals will mostly just lead to numbers that are too big. – mbomb007 – 2015-04-16T20:21:44.290Remember that the root function handles arbitrary roots, not just integers. For example, rt-.1 is the same as .5^(1/-.1) which is 1024. That said, I know of only two numbers between 0 and 100 which seem to require the use of roots.

– Uri Granta – 2015-04-17T00:36:05.833@UriZarfaty Care to gives those numbers (not their expressions)? – orlp – 2015-04-17T00:53:33.520

Also, you didn't give runtime requirements, so I think we'll be likely to see some absolutely ridiculous heat-death combinatorics solution win. – orlp – 2015-04-17T00:56:09.507

@orlp One of the numbers was 86. Though the program that produced this made a few simplifying assumptions that may be wrong, so there may be other ways of producing it. – Uri Granta – 2015-04-17T01:25:56.287

@UriZarfaty You can make a well-optimized exhaustive algorithm, prove a solution is optimal, then dump the combinatorics solution together with the optimal score. – orlp – 2015-04-17T01:36:31.277

You wouldn't actually be able to state your score, just that you'd won. Still, I'll add a run time restriction, since this clearly isn't the i tent of the puzzle. – Uri Granta – 2015-04-17T02:05:58.117

There seem to be 204 distinct sets of constants: https://gist.github.com/orlp/e76014113ab8a2c29589

– orlp – 2015-04-17T05:27:17.2631@orlp Note that leading zeros and fractions greater than zero don't add any expressivity: e.g. 015 = 0 + 15 and 1.5 = 1 + .5. – Uri Granta – 2015-04-17T08:39:31.680

I tried building a Python program, but I've kept hitting a block where I can't figure out well enough how to generate expressions using permutations or whatever. I just don't have enough experience with that. I you want though, I can write a program that merely prints the solutions I discovered by hand... So far I have found expressions for 37 of the numbers. – mbomb007 – 2015-04-17T14:40:45.890

@mbomb007 That's totally fine (as long as the program also outputs the number of expressions). I've also added a scoreboard to the question which you can update with your program once you post it. – Uri Granta – 2015-04-17T15:11:57.700

This isn't directly linked, but I have a program that I'm using to help turn a repeating decimal into a fraction, and it's giving wrong answers sometimes. I think the unreduced numerator is too large by the amount preceding the decimal. Any help? If not, I can use StackOverflow. http://ideone.com/PU6taR

– mbomb007 – 2015-04-17T15:40:58.5601

@mbomb007 That's way too complicated. Here's a quick explanation I wrote: https://gist.github.com/orlp/e92b3b7d26ad9b11378e

– orlp – 2015-04-17T16:29:42.4702

@UriZarfaty Then there are 99 distinct useful sets of constants: https://gist.github.com/orlp/eb997e49e41878c76d0a

– orlp – 2015-04-17T16:38:07.680@orlp You realize that's what my program is trying to do, right? I just have gcd stuff to reduce the fractions. If the user wants to see

`0.3~`

you don't have a`b`

, so do you make`b`

equal`3`

also? If`b`

was zero, it'd represent`0.03~`

... – mbomb007 – 2015-04-17T18:06:37.670@orlp Also, my program cannot divide the numbers like in your explanation, else it'll just turn it into a decimal again. I need the numerator and denominator independently, then reduce them with gcd. Maybe I can use the

`fraction`

module...? – mbomb007 – 2015-04-17T18:12:22.607@mbomb007 Yes, use the fraction module - it's there exactly for this purpose. Once you have a working solution you might be able to golf it out later, but for now just use it. – orlp – 2015-04-17T18:15:24.230

Do any of the numbers require an irrationial intermediate result? – orlp – 2015-04-17T19:21:17.480

@UriZarfaty Is "37" the other number that requires root? – kennytm – 2015-04-17T22:10:29.993

@orlp None that I know of, but I haven't proved that. – Uri Granta – 2015-04-18T09:51:04.677

@kennytm No: 37 = sqrt(2^(0!/.1))+5 – Uri Granta – 2015-04-18T09:51:29.323

@UriZarfaty: Ok. I found

`rt[.2](0!+1) = 32`

before that. – kennytm – 2015-04-18T09:57:45.333@kennytm Wrong again -

`(20*.1)^5`

. – orlp – 2015-04-18T11:42:20.420@orlp:

`rt[.2](0!+1) = 32`

is a partial solution, and`rt[.2](0!+1)+5 = 37`

and`rt[.2](0!+1)-5 = 27`

. Note that there is no "5" in`rt[.2](0!+1)`

.`2^(0+1*5) = 32`

. – kennytm – 2015-04-18T16:13:01.923