14
$\begingroup$

Suppose you are allowed to use all 10 digits (0,1,2,...9) at most once each; 4 arithmetic operations ($-$,$+$,$\times$,$\div$), each any number of times; parenthesises to group operations; and you can create numbers from digits by writing them together.
What is the smallest natural number which you would not be able to write?

For example, you can write:
$135 = 12*3*(9+6)/4$
and you can't write:
$11 = 11$
$3 = 2+3/3$
$27 = 3+4!$
$81 = 3^4$
$1 = 5/3$

Improve this question
$\endgroup$
15
  • $\begingroup$ @JoeZ don't forget you can "create numbers from digits writing them together" so $4817*(90+23)=544321$ $\endgroup$
    – kaine
    Jul 3, 2014 at 14:41
  • 2
    $\begingroup$ What about parenthesis, or how is operator precedence handled? $\endgroup$
    – Cephalopod
    Jul 3, 2014 at 15:12
  • $\begingroup$ @Cephalopod, you can use parenthesises. thank you. $\endgroup$
    – klm123
    Jul 3, 2014 at 16:23
  • 2
    $\begingroup$ I don't think there's any algorithm which will help solve this - it's just going to have to be bruteforce. $\endgroup$
    – Bobson
    Jul 3, 2014 at 18:41
  • 1
    $\begingroup$ @N3buchadnezzar, em? You just wrote this number using only digits from 1 to 9 and stringing them together. $\endgroup$
    – klm123
    Jul 3, 2014 at 20:06

5 Answers 5

Reset to default
8
$\begingroup$

Concatenation is the "most efficient" among the allowed operations, which is exmplified by this observation: If $x$ is a nonzero rational number obtained according to the rules using the $k$ digits $d_1>d_2>\ldots >d_k$, then $$\tag1 \max\left\{|x|,\tfrac1{|x|}\right\}\le 10^k\cdot 0.d_1d_2\ldots d_k$$ This is clear for direct concatenations and otherwise follows by induction and using $(1)$ for the summands, factors, etc.

We can strengthen this: If the last operation is $\times$ or $\div$, then $$\tag2\max\left\{|x|,\tfrac1{|x|}\right\}<10^k\cdot 0.85598232 $$ This follows because not both parts can use the digit $9$, hence the largest digit in on subterm is either $8$, leading to a bounding factor $0.97654321\cdot 0.87654321$; or the largest digit in one factor is $\le 7$, leading to a bounding factor $0.987654321\cdot 0.7654321$. If one takes these case distinctions a bit further, one readily finds that $$\tag{2'} \max\left\{|x|,\tfrac1{|x|}\right\}\le10^k\cdot 0.843973902$$ if the last operation is $\times$ or $\div$ (with the extreme given by $9642\cdot 875310$).

Moreover, if the last operation is $+$ or $-$, then $$\tag3|x|\le (10^{k-1}+1)\cdot 0.987654321 $$

We thus are led to believe that $987654323$ is likely not expressible: Because of two difgits $3$ it cannot be obtained from concatenation; because of $(3)$ is cannot be obtained as sum or difference; because it is prime, it cannot be obtained as product of integers (unless one factor is $1$ and we are effectively using at most $9$ digits). Remains the case that the number is obtained as a product or quotient of fractions, but at first sight this seems unplausible.

Meanwhile I brute-forced all numbers that can be obtained with only $+,-,\times$ and digit concatenation (and with all intermediate resuls $\le 10^7$). The first number that cannot be expressed this way turns out to be $$ 8480902.$$ So unless someone manages to express $8480902$ under the original rules (i.e. with division allowed), this is the answer to the original problem.

Improve this answer
$\endgroup$
4
  • $\begingroup$ "This follows because not both parts can use the digit 9" Why? This is in assumption that all previous operations were concatenations, but why must they? $\endgroup$
    – klm123
    Jul 7, 2014 at 5:49
  • $\begingroup$ @klm123 Each digit shall be used at most once, hence $9$ cannot occur as used in both parts (it may of course occur as digit in both parts, e.g. if we combine (e.g. multiply) $4+5$ and $92$, but then $9$ is used only in the second part). - After the brute-force result, however, the introductory estimates have become mostly useless. $\endgroup$
    – Hagen von Eitzen
    Jul 7, 2014 at 14:10
  • $\begingroup$ I'm missing something here. I followed you up to the brute-force consideration. How did you do that? And why are you discarding the division? Using just 0-5 digits, I have found numbers that are expressed as division (i.e. 27155=54310/2), although I cannot be certain that all of them are expressable only as a division. $\endgroup$
    – Frazz
    Jul 7, 2014 at 21:57
  • $\begingroup$ Exhaustive searches show that for digits up to 6 and 7 the solution is unchanged by the removal of division from the permitted operations, so it's quite likely that 8480902 is the desired answer. $\endgroup$
    – Peter Taylor
    Jul 9, 2014 at 17:05
4
$\begingroup$

I have written a Delphi application to brute force a solution. Unfortunately I see no way of solving the problem: what expression(s) results in number N? That is I see no solution other than generating all expressions and then seeing what natural numbers they result in.

So I can't really help with Bobson's crowd-sourcing approach.

I am following klm123's idea, and I have ran the application with:

N = 3 : 0,1,2

Execution time: 00:00:00
Expressions processed: 441 [Average: 27.562,5/sec]
Expressions calculated: 34 [Average: 2.125,0/sec]
Natural numbers calculated: 28 [Average: 1.750,0/sec]
Distinct natural numbers found: 14 [Average: 875,0/sec]
Highest natural found: 210
Lowest natural not found: 4

N = 4 : 0,1,2,3

Execution time: 00:00:00
Expressions processed: 22.924 [Average: 363.873,0/sec]
Expressions calculated: 1.464 [Average: 23.238,1/sec]
Natural numbers calculated: 871 [Average: 13.825,4/sec]
Distinct natural numbers found: 110 [Average: 1.746,0/sec]
Highest natural found: 3.210
Lowest natural not found: 25

N = 5 : 0,1,2,3,4

Execution time: 00:00:04
Expressions processed: 1.679.977 [Average: 401.812,2/sec]
Expressions calculated: 98.228 [Average: 23.493,9/sec]
Natural numbers calculated: 45.423 [Average: 10.864,1/sec]
Distinct natural numbers found: 884 [Average: 211,4/sec]
Highest natural found: 43.210
Lowest natural not found: 89

N = 6 : 0,1,2,3,4,5

Execution time: 00:08:39
Expressions processed: 159.888.346 [Average: 307.590,0/sec]
Expressions calculated: 8.867.950 [Average: 17.060,0/sec]
Natural numbers calculated: 3.236.479 [Average: 6.226,3/sec]
Distinct natural numbers found: 8.661 [Average: 16,7/sec]
Highest natural found: 543.210
Lowest natural not found: 653

N = 7 : 0,1,2,3,4,5,6

Execution time: 19:36:02
Expressions processed: 18.788.082.577 [Average: 266.262,5/sec]
Expressions calculated: 1.014.272.742 [Average: 14.374,2/sec]
Natural numbers calculated: 308.146.445 [Average: 4.367,0/sec]
Distinct natural numbers found: 93.219 [Average: 1,3/sec]
Highest natural found: 6.543.210
Lowest natural not found: 5.683

Now on to N=8. I got a few small optimizations in mind, but nothing that will cut this drastically, I presume.

Explanation of what the application is doing

I have two input parameters: Digits and Operators. I also have some other parameters to handle output dump to disk, but they have nothing to do with the algo.

The application starts processing the empty expression: 0 length string.

Every time an expression E is processed, I do the following:

1. check all Digits - for any single digit D not already included in E, I process the expression E+D (concatenation, not sum). To optimize a bit I avoid this step if E ends with a closed parenthesis. I also avoid this if D is 0 and E does not end with any other Digit.

2. check all Operators - for any single operator O, I process the expression E+O. To optimize I avoid this step if E is empty or ends with another operator or with an open parenthesis.

3. check ")" - if E ends with a Digit or a closed parenthesis, and it has a pending unclosed parenthesis, and this contains at least one operatore, then I process the expression E+).

4. check "(" - if E is empty or ends with an Operator or an open parenthesis, then I process the expression E+(. To avoid infinite recursion there is some magic here... I do it only if the number of Digits still unused in E is greater the number of pending unclosed parenthesis in E plus 1.

5. calculate the expression - if E ends with a Digit or a closed parenthesis, and all parenthesis are balanced and are useful (contain at least one operator), and it does not start with ( and end with ) then I calculate the expression. If it turns out to be a natural number, then I check it with the highest found natural and lowest unfound natural.

Processing of derived expressions is obviously done through recursion. The algo seems quite efficient, apart from the parenthesis part. I have made some changes to this code and it now validates parenthesis better, avoiding some recursion in useless branches and evaluation os redundant expressions. It's not perfect, but it does cut times as N goes up. (I am using Artem V. Parlyuk's ArtFormula package of nonvisual Delphi component for symbolic expression parsing and evaluation).

As an aside, I also keep track of the shortest expression that can generate each natural number found. The shortest is meaningful, as it is usually the most immediate and readable. It is also always the one with no useless parenthesis ;)

Update

Tweaking the parenthesis logic, I have stumbled upon a small bug. It was generating a lot of useless expressions (with redundant parenthesis) but it was not generating some useful expressions. With N<=5 this bug did not have any effects. With N=6 I did find 6 more natural numbers, though the lowest unfound natural is 653.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ This should run faster if you only search the numbers less than the lowest one not found, in theory. That way, you can answer the question without waiting years :P $\endgroup$
    – user20
    Jul 7, 2014 at 17:51
  • $\begingroup$ And how do you propose to "search" for a specific value? I generate expressions, and then evaluate them... using a specific library, which is actually quite fast. But if you have ideas on how to limit the generation/evaluation of expressions, please let me know. A part from that... when I say that 2908 is the lowest, I mean the application has already found expressions for all numbers up to 2907. So what I actually need is to verify if 2908 has an expression or not. $\endgroup$
    – Frazz
    Jul 7, 2014 at 18:36
  • $\begingroup$ Hmm, I see what you're saying. Guess it isn't as straightforward as I thought... I'm sure there's a way to, but I'll have to think on it. $\endgroup$
    – user20
    Jul 7, 2014 at 19:10
  • $\begingroup$ I confirm your values for the lowest natural number not found, although I think your code is quite inefficient. Mine takes 20 seconds to check N=7. $\endgroup$
    – Peter Taylor
    Jul 9, 2014 at 16:31
  • $\begingroup$ 20 secs to evaluate about one billion expressions... wow. I don't think choice of programming language or tool can make so much of a difference. Would you mind sharing the logic or the code? What are you using? How long will it take to process N=10? $\endgroup$
    – Frazz
    Jul 9, 2014 at 16:41
2
$\begingroup$

Here is my attempt at finding an upper bound:

We have 10 atomic values ($0..9$) and five operations ($+$, $-$, $*$, $/$, $○$; according to rules concatenation may not be used on results of other operators, let's ignore this for now)

Since all operations are binary, we need 9 operators to get a single result out of 10 values. There are 4862 binary trees with nine nodes.

There are $5^9 = 1953125$ ways to choose operators for a tree and $10! = 3628800$ ways to arrange the digit leaves.

Thus, the number must be smaller than $3628800*1953125*4862 = 34459425000000000$. Hey, this still fits into a signed 64-bit integer, so good look to the brute forcers :-)

It is possible to reduce the upper limit. The following rules were not considered by my approximation

  • Concatenation may not be used on results of other operators
  • $+$ and $*$ are commutative
  • not all combinations result in integers
  • some integers can be computed in more than one way
Improve this answer
$\endgroup$
6
  • $\begingroup$ The maximum you can get with 9 digits and all operators are 96420*87531, so the upper bound can be much smaller: 8439739021. $\endgroup$
    – klm123
    Jul 4, 2014 at 11:21
  • 1
    $\begingroup$ You can do better than that just by stringing all the digits in descending order to make 9876543210, though. $\endgroup$
    – user88
    Jul 4, 2014 at 14:12
  • $\begingroup$ @JoeZ. It may technically have to be an expression of some sort, meaning the upper bound would therefore be 8439739021. $\endgroup$
    – Neil
    Jul 4, 2014 at 15:52
  • $\begingroup$ @neil It depends on if "any number of times" include zero times? $\endgroup$
    – Adam Speight
    Jul 7, 2014 at 20:23
  • $\begingroup$ @AdamSpeight That cannot be the case, or else the problem would be trivial, being able to represent all possible expression valuations from 0 to 9876543210 as a number without operations and hence everything can be represented and there is no solution. $\endgroup$
    – Neil
    Jul 8, 2014 at 8:33
1
$\begingroup$

In the interest of crowd-sourcing the brute forcing, I've made a google spreadsheet with the list of the 4765 numbers from 1 to 9999 which can't be formed by simple concatenation. Please pick a couple of them and work out solutions.

Spreadsheet

If we finish this set with solutions for all numbers, I'll add more.

I don't really expect it to be in this set, but we've got to start somewhere...

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ I brute-forced expressions using only digits $0,\ldots, 7$ and allowing only $+,-,\times$ and initially concatenation. Then the bound is at $48528$. $\endgroup$
    – Hagen von Eitzen
    Jul 6, 2014 at 15:14
  • $\begingroup$ @HagenvonEitzen - Good to know. I didn't really expect it to be solvable by hand, but it was worth the attempt. $\endgroup$
    – Bobson
    Jul 7, 2014 at 19:53
0
$\begingroup$

I'm trying to approach the task solving simpler tasks with $N<9$ digits allowed.

  1. N = 3: 0,1,2.
    The Answer would be $A=4$.
    Obviously, you can't reach $(N-1)N/2+1 = 4$ if you use only $-,\div,+$ operations. $\times$ operation also would help here.
    So you need to use grouping operation. But then you will get a number $R \ge 10$ and the only way to decrease it drastically to $4$ is to use division. But $10/2 = 5$ - the division is not enough too.

    It is easy to check that you can make any number $\le4$.

  2. N = 4: 0,1,2,3.
    The Answer is $A=25$.
    Similarly you can't reach $7$ if you use only $-,\div,+$ operations. The maximum you can get adding $\times$ operation is (2+1)*3 = 9 (you have to multiply maximum possible numbers to reach the maximum).
    So you need to use grouping operation.
    If you group 1 and other digit, you would need to use multiplication to reach 25, but 10*2 =20 and 10*3 = 30 leaves us with 3 or 2 to finish... 12*3 = 36 and 13*2 = 26 lives us with 0... so you can do nothing here.
    If you group 2 and other digit, for example, 20 you would need to add to it something and can't reach 25 with additional 1 and 3. The same for 21,23.
    If you group 3 and other digit, like 30, you would need to subtract from it something, similarly you can't reach 25.
    If you group three digits, then you would get $R>100$ and you would need to use division, but $100/3 > 25$.

    You can check that you can make any number $\le24$.

This really looks like there is no simple pattern, the $A$ is rapidly increases with $N$, the same for number of possible ways to achieve the result.
The only patter I see is that $A < 10^{N-2}/(N-1)$, possibly this can be proven. And $10^{N-3} < A$, which is most probably will fail for big $N$.

Most probably there is no pattern for $A$ at all, and one would need to brute force it for big $N$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ It is a ridiculously difficult problem to try to take on mathematically. Even brute forcing a solution would likely take more seconds than have passed since the universe was founded. Don't beat yourself up. $\endgroup$
    – Neil
    Jul 4, 2014 at 8:00
  • $\begingroup$ @Neil: Can you prove that it's mathematically difficult? $\endgroup$
    – justhalf
    Jul 4, 2014 at 8:55
  • $\begingroup$ @justhalf How do you expect I go about that exactly? Divide the number of head scratches by the inverse frequency of pencil eraser usage? I didn't say that to prove anything. If you wish to demonstrate that it is, in fact easy, then I think it's safe to assume you could provide a solution, no? $\endgroup$
    – Neil
    Jul 4, 2014 at 9:06
  • $\begingroup$ I think this might be a good approach, but you'd need to do it in a base-$N$ system. Otherwise you get gaps - there's probably no way to represent 79 using only the digits 0-3, for instance. $\endgroup$
    – Bobson
    Jul 6, 2014 at 14:58
  • $\begingroup$ @Bobson, I don't understand why are you talking about 79 via 0-3 digits. May be you see more in my approach than I do? Could you explain it, please? $\endgroup$
    – klm123
    Jul 6, 2014 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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