Yes you missed the point
which is not present in your list. If I would be able to find motivation I would post solution in bash - but - well seems thread is about python - I mean how powerful it is.

At first I didn't think bash could do it, because it has only integer math, but I'm reconsidering. Since all the answers are integers, integer math should be sufficient. I'll give it a try. "Powerful" is not a requirement in this forum.

^ It's not because all results are eventually integers that bash can handle the job
bc is getting closer to the right answer but not totally:

1 members found this post helpful.

I have been using floating point division and worrying about its errors. Perhaps it is not the right tool for the job. Integer division and modulo may solve the problem better. In integer math, there is no uncertainty. If the modulo function is zero, then we know the division is exact and the solution is useful. If the modulo is nonzero, the solution in not useful and will be discarded.

Well, thanks - you gave me motivation. Out of static data it should be at most 30 lines of code. So, I plan to do this today.

that is a question (at least for me) if something like 1^(9/20) or 102/sqrt(9) are acceptable? (probably irrelevant).

Here 102/sqrt(9) is not cause = 102/9^(1/2) and you see there are repeating 1 and 2. But if non-integers are allowed then 90^(1/2) = sqrt(90)=3*sqrt(10) appprox 9.486833 but as sqrt(10) is irrational there is no way to calculate exact value.

I have not had much time to participate the past few days, so will try to catch up with replies to all here. These are just the things that have caught my attention when reading through the thread today, and not in any priority order - and apologies if I have neglected anyone's reply directed to myself (please let me know).

Point partly missed. It is not only about concatenation of the original digits, 2,0,1 and 9 in most examples in this thread. It is about how many and which whole numbers between 0 and 100 inclusive can be generated using those four digits exactly once each in expressions using only addition, subtraction, multiplication, division and exponentiation, plus parenthesis for grouping and change of sign. Concatentaion is allowed only on the original digits, not on other operations, and leading zero is not a valid concatenation..

For a few examples, here I represent the four original digits as 'a', 'b', 'c' and 'd', in any permuted ordering, 'a*b' is multiplication, 'ab' is concatenation.

a+b+c+d - Valid

a*b*c*d - Valid

a^b/(c-d) - Valid unless c=d, or both a and b equal zero

ab/cd - Valid concatenation, only if 'a' and 'c' are non-zero

(a-b)c/d - Invalid, attemp to concatenate 'c' to difference of a and b

a/c*d - Invalid, does not use the 'b' digit

sqrt(a)+b+c+d - Invalid operation, only +, -, * and / allowed

And to repeat, only whole number solutions are valid, rounding and truncation not allowed (* See below).

Actually, it is similar(**) to what happens when you do the math with pencil and paper. Dividing 1 by 3 still produces .3333... to how ever many places you want to continue. But no matter how far you go, the final digit is always going to produce truncation error (i.e. you have truncated the result to that number of digits).

(** - As correctly pointed out by ntubski below, with pencil and paper we truncate decimal digits, whereas the computer truncates bits, or binary digits. The idea is the same, but the numeric result is not)

On a computer, when you then use that result in another operation, the bits of the mantissa (the significant digits) are shifted as necessary, and any shifted to the right are lost into the void! This is rounding error. You can pretty much assume that any operation will introduce an error equivalent to the value of the least significant bit of the operands, and this will accumulate when the results are used in further operations.


Now, if we are paying attention, we will see the (1/3) * 3 and realize that if we do the multiplication first, we will get an exact answer, 3/3 = 1, by avoiding the intermediate result altogether. Such methods may also be used by well designed computer programs where they will not affect the validity of the result, even though they may violate PEMDAS.

Just a guess, but if the python math routines are smart enough to "see" that 1/3 will be multiplied by 3 and chooses to do the multiplication first, the result will be equivalent to 3/3 = 1, 1 * 7 = 7 exactly.

Change the order and whether or not it does the multiplication first, there is an intermediate truncated result. That is, whether it does 1/3 * 7 * 3 (.3333... * 7 * 3) or 7/3 * 3 (2.3333... * 3), it includes the truncation error.

Unless you use another application such as bc to do the required operations, you will not be able to do this in bash, as noted by others.

That does not seem correct to me. First it would only apply if division were the final operation in a chain, something like (5+7)/3, but not 2*(3/6)+1 (unless you evaluated each step in the chain). Integer math is only exact if every operation, that is the math, in fact, produces an integer result as an operand for the next operation. If an intermediate operation actually produces a fractional result, the value of the final result will be in error. Integer math is really just more extreme truncation in this respect - it truncates everything to the right of the decimal point!


The truth is that discrete math is only ever an approximation to the continuum of the real number system, anyway. We can use more bits to increase precision and range (i.e. integer to float, float to double precision, double precision to long double precision), but the very best we can do is make the error ever smaller, we can never make it zero. If you have a simple calculus background, think in terms of the little epsilon introduced with the idea of limits - it is the digital equivalent.

Then again, as your explorations have shown, the algorithms used by the programming languages do a really good job of keeping the error small, and in this exercise accumulated errors are not really a problem. The problem I reported with your code produciing a zero when my C code did not, as I understand it now, was more due to your use of an explicit larger limit (epsilon) to test for equality than simply that provided by the language itself.

And in any case, there will always be a difference that results from the different languages, on different platforms and different hardware, and not something with an actual single cause or solution. We can make epsilon as small as we like, but we can never make it exactly zero!

I think the better approach would be to figure out ways to avoid operations which are not allowed by the math (division by zero, 0^0), or will actually exceed reasonable limits (i.e. a^(b^(c^d)) ), and defer to the precision of the language and platform for the rest.

So, I would suggest that we add a stipulation or two to the "rules" of this exercise, as follows:

Then we can get back to watching the little numbers stream by!

The only operations allowed are addition, subtraction, multiplication and division, and exponentiation involving the four digits themselves. Use of a square root operator, or other math functions is not allowed.

So with the digits 2,0,1 and 9, for example, this would be valid, 9^(1/2)+0 = 3, as would your example of 1^(9/20), but not use of the sqrt(...) operator.

Beryllos and I have taken much different approaches to the problem, and arguably have different objectives, but it has been a fruitful, fun and ongoing exercise! Please contribute your own thoughts, suggest new directions!

1 members found this post helpful.

It's a coincidence that the rounding errors happen to cancel out in this particular case. Note that the result of 1/3 is not exactly 0.333..., because these are binary fractions, not decimal ones. When python prints out the value, it doesn't use maximal precision by default, but you can force it:

There is also .hex() to see something more representative of the actual bits:
Now we can see how the result comes about: 0x1.555... * 2⁻² * 3 = 0x3.FFF... * 2⁻², since the number left of the binary point is now more than 1, we need to shift right. So the FFF... rounds up and we have 0x4.000... * 2⁻² = 0x1.000... * 2⁰.

Again the answers aren't actually exact, C's printf probably makes different choices about default precision. If you have GNU libc, its printf should support %A which does the same as Python's .hex() (for other platforms, you can use frexp() to implement it). There may be small differences in the computation as well, since depending on optimization settings, intermediate values may be stored in 64 bit RAM locations or 80 bit FPU registers (though I think the default is to use 64bit SSE registers on x86-64 machines).


Apparently it varies by platform/compiler: https://en.wikipedia.org/wiki/Long_double


As I noted above, using bits vs digits can make it slightly different.

2 members found this post helpful.

Thanks ntubski!

I completely neglected to consider the rounding done by printf itself, and the ability to use other output formats to see the whole internal representation of a number.

Dealing with the problems resulting from quantization inherent to digital computing presents many choices. Dealing with much of that complexity gracefully, and describing it consistently is the point of the various specifications. Different programmers and platforms make different choices, but overall they do a good job of minimizing the effects to the end user, although the effects are always there waiting for those who look closely enough.

While thinking about my previous post and dusting off my own memory, I ran across this quote in Numerical Recipes In C: The Art Of Scientific Computing...

How many whole numbers can you generate from the digits of the year and a few simple math operations? Be careful what you ask, you never know where the answer may lead!

1 members found this post helpful.

@astrogeek, Thanks for your remarks (3 posts above) about truncation errors and machine precision. I totally agree.

When I suggested using integer math, I wasn't completely giving up on floating point. I was "thinking out loud" about the possibility of another approach which uses integer math without sacrificing accuracy.

Permutations might be part of such an approach. Every order of digits and operations can be tried. For every error-magnifying expression like (1/3)*7*3, there will be a error-avoiding permutation like (1*3*7)/3.

I was trying to think of more difficult cases. Addition of fractions, like (1/3)+(2/3), is one that cannot be directly evaluated by integer math. However, if the permutation-combination method generates the equivalent (1+2)/3, integer math can do that (although there would be an unused digit 3 from the first expression).

Fractional powers, for example, 8^(2/3) or 9^(1/2), are another area of difficulty for integer math. Difficult but not impossible.

Just thinking about the possibilities!

Thanks, ntubski, for clarifying digits vs. bits, providing useful printing examples, and other fine points of the craft.

Trying to reinvent the wheel...

In the New Year Puzzle, we don't need to calculate arbitrary floating point numbers. The only non-integer numbers we are interested in are fractions, since those might be multiplied up to whole numbers in the end.

I was about to write some python functions for handling fractions when I remembered to check: in python, many basic classes have already been built. It turns out that python has a module for creating and manipulating fractions:
Basic fraction arithmetic works.
The only problem that I am aware of: Powers with fractional exponents yield float results, even when they are algebraically solvable:
Using the fraction module, I only had to change or add a few lines of my program to switch all the calculations to fraction arithmetic... except for powers with fractional exponents. Before I post the program, I will add a few lines to calculate fractional powers when the result can be expressed as a fraction.

The bottom line: Fraction arithmetic completely eliminates truncation error in this application.

1 members found this post helpful.

Here is my latest program, using python fraction arithmetic and a fraction power function I designed. The fraction arithmetic is strictly integer-based. There is no floating-point math at all. This eliminates all my concerns about truncation errors.

newyear-v4.py.txt

A while back, I considered writing a bash equivalent, just to prove that it could be done, but on further thought I am not going to pursue that. There is no question that it is possible, but to implement it well in a set of bash scripts would, in my hands, take too long. Likewise, I would translate it to C if there was a need for speed, but there is not. So I'll stick with python for now.

1 members found this post helpful.

Please post it here. It is not a python only forum.
I'm really interested.