26
$\begingroup$

Here is the task:

Write down 10958 using all 1-9 digits in ascending order and only one time.

You are allowed to:
1) group digits into numbers
2) use 5 basic operations: + - * / ^ ("^" means power)
3) set order of operations with brackets ()

For example, 10957 = (1+2)^(3+4)*5-67+89

Sounds simple, right? If you are interested, there is a video on this topic, which says it is known that you can write this way all numbers from 1 to 11111... all, but 10958, for which they don't know the solution at the moment.

And there is cheaty solution by that guy:

10958 = 1 * 2||3 + ((4*5*6)||7+8)*9,
where "||" states for a twisted rule #1: concatenation operation.

I believe in SE, there should be a guy who will find the true solution! Or, even if not true, may be some other a bit cheaty, but close to the solution. Try it out.

$\endgroup$
  • 1
    $\begingroup$ What is the difference between concatenation and "grouping digits"? Also is this all in base ten? (I imagine so.) $\endgroup$ – Jonathan Allan Apr 19 '17 at 9:03
  • 1
    $\begingroup$ @JonathanAllan, the spoiler should have explained it clearly. Concatenation is an operation, you can apply it to results of other operations and do it in any order, if you use brackets. Meanwhile with grouping digits you can... only group Digits to write numbers like 67. $\endgroup$ – klm123 Apr 19 '17 at 9:08
  • 6
    $\begingroup$ @JonathanAllan I think the difference is that the concat operation can be used to fuse results and not just digits. (2+3)||(4+5) = 59 $\endgroup$ – stack reader Apr 19 '17 at 9:17
  • 4
    $\begingroup$ Yet another Parker square solution. $\endgroup$ – Leo Apr 19 '17 at 15:25
  • 3
    $\begingroup$ This seems relevant: arxiv.org/abs/1302.1479 $\endgroup$ – aroth Apr 19 '17 at 23:36
21
$\begingroup$

I wrote a program to solve all possible conditions including everything. The code is running for some days now and I have found lots of close results. According to the benchmark, it will take a couple of days to go and as a result I would have checked every single possibility and share the result with you guys.

For $1,2,3,4,5,6,7,8,9$, I am going to update close ones to the below:

1

$(1+234)*5/6*7*8-9=10957.67 \simeq 10958$

2

$(12*3*4/5*6*7+8)*9=10958.4\simeq 10958$

3

$-1+(234-5/6)*(7*8-9)=10957.83\simeq 10958$

4

$1+((((2+34)/(5))^6)*(7/89))=10958.28\simeq 10958$

5.

$(((1+(2+3)^{4})*56)-7)^{8/9}=10957.50\simeq 10958$

6.

$1+(2+3^{4/5+6+(7+8)/9})=10958.36\simeq 10958$

7.

$(1+((2-3/(4*56))^7))*89=10957.61\simeq 10958$

8.

$-1+(2+((3/4)^{5-6*7*8/9}))=10957.85\simeq 10958$

9

$1+(2*3)^{4-1/8*(5/6)^7}*9=10958.25\simeq 10958$

10

$((1+(2/3+4))^5*6-7)^{8/9}=10958.12\simeq 10958$

11

$-1+2-3+4^{5-(6-7)/8}*9=10957.73\simeq 10958$

12

$(((1+2/3)/4)^5)^{6 + 7/8 - 9}=10958.33\simeq 10958$

13

$((1+(2^{3^{(4/(5 + 6)} + 7)-8})^9=10957.63 \simeq 10958$

14

$(-1/(2 + 3) + 4^{5 - (6 - 7)/8}*9=10957.93\simeq 10958 $

15

$-1-2/3-4^{5-(6-7)/8}*9=10958.06 \simeq 10958$

16 Closest One

$-(1 - 2^{3^4/5}/(6 + 7/8) - 9)=10957.98 \simeq 10958$

I believe this is close enough to be accepted as an answer!

Moreover, I have found exact solution without using number $6$ as below:

$1-2+3*457*8-9=10958$

$\endgroup$
  • 1
    $\begingroup$ I don't like your first approach, It clearly states that the digits need to be in ascending order. But I like your second one. It's almost not cheating. +1 $\endgroup$ – Marius Apr 20 '17 at 12:22
  • $\begingroup$ Even allowing for reversing the digits, I'm unsure if the 5th and 6th solutions count as they rely upon the unary negation operator. It's unclear from the OP if that's intended to be in-bounds or not. $\endgroup$ – aroth Apr 20 '17 at 13:44
  • $\begingroup$ There is already a solution for 10958 in descending order, so the first 6 don't count. $\endgroup$ – Klyzx Apr 28 '17 at 3:17
  • 1
    $\begingroup$ I'm not sure finding "close enough" answer is what we're looking for here. $\endgroup$ – justhalf May 2 '17 at 9:38
  • $\begingroup$ @justhalf a day left to complete my run. it is still running, i have found everything until 12k except 10958. after the run complete i will share my code and result, probably telling no solution for 10958. Close enough results for ur information only. $\endgroup$ – Oray May 2 '17 at 9:41
12
$\begingroup$

With square roots you can do this:

$(1234-5)\times6+7\times8^{\sqrt9} = 10958$

Without square roots or concatenation of the results of other operators, the best I can do is:

$\left((1+2\div3+4)^5\times6-7\right)^{8\div9} \approx 10958.1155551728$

It's just a coincidence that the best result without concatenation of results of other operators also involves no concatenation of digits.

This is the program that did the search. I wrote it a few years ago to solve another puzzle in the "stick some operators in this string of numbers" genre.

It doesn't do unary minus though, so maybe there's still room for improvement.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <float.h>
#include <math.h>

static double best;

#define MAXDIGITS 9
/* Also try MAXSQRT 1 for solution with sqrts. It's a lot slower! */
#define MAXSQRT 0

struct node {
  enum {
    LEAF, /* must be 0 */
    ADD, /* must be first binary op */
    SUB,
    MUL,
    DIV,
    EXP /* must be last binary op */
  } type;

  /* valid in LEAF nodes only */
  char digits[MAXDIGITS+1];
  double leafval[MAXSQRT+1];
  int digitsoffset;

  /* valid in non-LEAF nodes only */
  struct node *left, *right;

  /* valid in all nodes */
  int sqrtcount;
};

static void usage(const char *progname)
{
  fprintf(stderr, "Usage: %s digits goal depth\n", progname);
  exit(2);
}

static double getval(struct node *n)
{
  double v;
  int i;
  switch(n->type) {
    case LEAF: return n->leafval[n->sqrtcount];
    case ADD: v=getval(n->left) + getval(n->right); break;
    case SUB: v=getval(n->left) - getval(n->right); break;
    case MUL: v=getval(n->left) * getval(n->right); break;
    case DIV: v=getval(n->left) / getval(n->right); break;
    case EXP: v=pow(getval(n->left), getval(n->right)); break;
    default: assert(!"Unreachable");
  }
  for(i=0;i<n->sqrtcount;++i)
    v=sqrt(v);
  return v;
}

static void printexpr(struct node *n)
{
  int i;
  for(i=0;i<n->sqrtcount;++i)
    printf("sqrt(");
  switch(n->type) {
    case LEAF:
      printf("%s", n->digits);
      break;
    case ADD:
      if(!n->sqrtcount) printf("(");
      printexpr(n->left);
      printf("+");
      printexpr(n->right);
      if(!n->sqrtcount) printf(")");
      break;
    case SUB:
      if(!n->sqrtcount) printf("(");
      printexpr(n->left);
      printf("-");
      printexpr(n->right);
      if(!n->sqrtcount) printf(")");
      break;
    case MUL:
      if(!n->sqrtcount) printf("(");
      printexpr(n->left);
      printf("*");
      printexpr(n->right);
      if(!n->sqrtcount) printf(")");
      break;
    case DIV:
      if(!n->sqrtcount) printf("(");
      printexpr(n->left);
      printf("/");
      printexpr(n->right);
      if(!n->sqrtcount) printf(")");
      break;
    case EXP:
      if(!n->sqrtcount) printf("(");
      printexpr(n->left);
      printf("**");
      printexpr(n->right);
      if(!n->sqrtcount) printf(")");
      break;
    default:
      assert(!"Unreachable");
  }
  for(i=0;i<n->sqrtcount;++i)
    printf(")");
}

int nodesused;
struct node nodes[MAXDIGITS*2-1];
#define root (&nodes[0])
int last_split_offset;

static void do_splits(int maxsplits, double goal)
{
  struct node *n;
  int splitnode, length, leftlength, save_last_split_offset;
  double v, e;

  v=getval(root);
  e=fabs(v-goal);
  if(e < best) {
    best=e;
    printexpr(root);
    printf(" = %.18g\n", v);
  }

  if(!maxsplits)
    return;

  /* Try each leaf node with more than 1 digit that is not left of the last
     split point */
  for(splitnode=0 ; splitnode<nodesused ; ++splitnode) {
    n=&nodes[splitnode];
    if(n->type!=LEAF || !n->digits[1] || n->digitsoffset<last_split_offset)
      continue;

    /* Record the node being split, and remember the previous one */
    save_last_split_offset=last_split_offset;
    last_split_offset=n->digitsoffset;

    /* Attach children */
    n->left=&nodes[nodesused++];
    n->left->type=LEAF;
    n->right=&nodes[nodesused++];
    n->right->type=LEAF;

    /* Try each split point */
    length=strlen(n->digits);
    memcpy(n->left->digits, n->digits, length-1);
    n->left->digitsoffset=n->digitsoffset;
    n->right->digitsoffset=n->digitsoffset+length-1;
    for(leftlength=length-1 ; leftlength>0 ; --leftlength) {
      /* Distribute digits to children */
      /*memcpy(n->left->digits, n->digits, leftlength);*/
      n->left->digits[leftlength]=0;
      n->left->leafval[0]=atof(n->left->digits);
#if MAXSQRT
      n->left->leafval[1]=sqrt(n->left->leafval[0]);
#endif
      strcpy(n->right->digits, n->digits+leftlength);
      n->right->leafval[0]=atof(n->right->digits);
#if MAXSQRT
      n->right->leafval[1]=sqrt(n->right->leafval[0]);
#endif
      --n->right->digitsoffset;

      /* Try each binary operator */
      for(n->type=ADD ; n->type<=EXP ; ++n->type) {
        do_splits(maxsplits-1, goal);
#if MAXSQRT==1
        ++n->left->sqrtcount;
        do_splits(maxsplits-1, goal);
        ++n->right->sqrtcount;
        do_splits(maxsplits-1, goal);
        --n->left->sqrtcount;
        do_splits(maxsplits-1, goal);
        --n->right->sqrtcount;
#endif
      }
    }

    /* Unsplit: free children and revert to leaf. n->digits[] is still good. */
    nodesused-=2;
    n->type=LEAF;

    /* Restore remembered stuff */
    last_split_offset=save_last_split_offset;
  }
}

static void search(const char *digits, int maxsplits, double goal)
{
  root->type=LEAF;
  strcpy(root->digits, digits);
  root->leafval[0]=atof(root->digits);
#if MAXSQRT
  root->leafval[1]=sqrt(root->leafval[0]);
#endif
  root->digitsoffset=0;
  root->sqrtcount=0;
  nodesused=1;

  last_split_offset=0;

  do_splits(maxsplits, goal);
#if MAXSQRT
  ++root->sqrtcount;
  do_splits(maxsplits, goal);
  --root->sqrtcount;
#endif

  assert(nodesused==1);
  nodesused=0;
}

int main(int argc, char **argv)
{
  const char *digits;
  char *endp;
  double goal;
  int splits;

  if(argc!=4)
    usage(argv[0]);

  digits=argv[1];
  if(strspn(digits, "0123456789")!=strlen(digits))
    usage(argv[0]);

  if(strlen(digits)>MAXDIGITS) {
    fprintf(stderr, "Too many digits (max is %d).\n"
                    "Increase MAXDIGITS and recompile.\n", MAXDIGITS);
    return 1;
  }

  goal=strtod(argv[2], &endp);
  if(*endp)
    usage(argv[0]);

  splits=strtol(argv[3], &endp, 10);
  if(*endp)
    usage(argv[0]);

  if(splits>=(int)strlen(digits)) {
    fprintf(stderr, "Not enough digits to perform %d splits\n", splits);
    return 1;
  }

  best=DBL_MAX;
  search(digits, splits, goal);
  return 0;
}
$\endgroup$
7
$\begingroup$

I found this solution on the YouTube video (not my solution), and it's even closer than the closest one in the original comment: $1 + (2-(3^{(4*5/6/7))})^{(-8)} + 9 = 10958.0020579103$

$\endgroup$
1
$\begingroup$

I believe this question already have the answer, here is the link Rendering the number 10,958 with the string 1 2 3 4 5 6 7 8 9

$(1+2+34) \times (5 \times 6+7) \times 8+\sqrt{9}!=10958$

(or)

$(12 \times 3 \times \frac{4}{5} \times 6 \times 7+8) \times 9 = 10958.4$

$\endgroup$
  • 2
    $\begingroup$ Welcome to Puzzling.SE! Please try to adhere to the rules posted in the question above. Specifically, this uses square root, which is not allowed. $\endgroup$ – Ian MacDonald Apr 19 '17 at 19:14
  • 2
    $\begingroup$ (same for factorial) $\endgroup$ – Rubio Apr 19 '17 at 20:15
  • $\begingroup$ @Rubio & lan, We can't get the exact answer by using basic operations. In that case you have to repeat any number for 10958, like this.. (based on rules my answer: (1+2)^(3+4)*5+(6+(-7+7)+8+9)=10958) $\endgroup$ – CR241 Apr 19 '17 at 22:48
  • 1
    $\begingroup$ But how do you know we can't get the exact answer using those rules? That'd be an interesting proof, I think, and I'd be curious to see it. $\endgroup$ – tilper Apr 19 '17 at 23:08
  • 1
    $\begingroup$ No, I didn't get an exact answer. It sounds like you said it isn't possible ("We can't get the exact answer by using basic operations") so I was wondering how you came to that conclusion. $\endgroup$ – tilper Apr 19 '17 at 23:23
0
$\begingroup$

$1||(2||(3*4)*5-6)-7-89$

We have decided that PEMDAS becomes PCEMDAS where the "C" is the concat function. Enjoy a second solution!

EDIT: We have some dedication enterprise machines with some decent specs running some tests, should only take roughly 3 million years to hit all cases. But the majority of the plausible ones should finish in the next week.

$\endgroup$
  • 1
    $\begingroup$ I wouldn't qualify this as an answer as the OP did not include concatenation as an acceptable operation. While it may be the correct answer, it does not follow the puzzle guidelines. $\endgroup$ – Jason V Nov 2 '17 at 19:04
  • 1
    $\begingroup$ Yeah we have been trying to find a solution without using concatenation but started by allowing it since we knew of one solution that involved using concat as a function. The original paper can be found arxiv.org/pdf/1302.1479.pdf and there he say that a^b is allowed as well as ab (aka concat). But in his solutions he does things like (1+2)^3 meaning "a" would be "(1+2)" and following that we thought it should be allow to do "(1+2)b". Again we are hoping to find a solution that doesn't involve doing this trick :D $\endgroup$ – Cole K Nov 2 '17 at 19:40
  • $\begingroup$ UPDATE: found 27 exact solutions, and checked most of them. All include that dumb concatenation trick sadly:/ $\endgroup$ – Cole K Nov 7 '17 at 14:12
-1
$\begingroup$

$1-2+(-3+6)*457*8-9 = 10958$ Is it allowed to have an operation before and after the bracket? I basically stole this from the person who found the answer that didn't use 6.

$\endgroup$
  • 3
    $\begingroup$ This isn't "using all 1-9 digits in ascending order and only one time" - the digits are not in ascending order. $\endgroup$ – Rubio Jun 15 '17 at 1:22

protected by Community May 1 '18 at 4:19

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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