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.

Improve this question
$\endgroup$
15
  • 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, 2017 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, 2017 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, 2017 at 9:17
  • 4
    $\begingroup$ Yet another Parker square solution. $\endgroup$
    – Leo
    Apr 19, 2017 at 15:25
  • 3
    $\begingroup$ This seems relevant: arxiv.org/abs/1302.1479 $\endgroup$
    – aroth
    Apr 19, 2017 at 23:36

6 Answers 6

Reset to default
22
$\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$

Improve this answer
$\endgroup$
7
  • 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, 2017 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, 2017 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, 2017 at 3:17
  • 2
    $\begingroup$ I'm not sure finding "close enough" answer is what we're looking for here. $\endgroup$
    – justhalf
    May 2, 2017 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, 2017 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;
}
Improve this answer
$\endgroup$
3
  • $\begingroup$ For the record, I think the guy who doesn't list concatenation as an operator, but then uses it anyway, is cheating more than the guy who says it is an operator and uses it more cleverly. $\endgroup$
    – user16792
    Apr 21, 2017 at 3:27
  • $\begingroup$ I wrote a similar code in python, which performs random search over all possible expressions: github.com/basarane/10958-Problem---Random-Search/blob/master/… $\endgroup$
    – Ersin Basaran
    Apr 21, 2017 at 16:10
  • $\begingroup$ A slightly different approach: github.com/DaveJarvis/sequential $\endgroup$
    – user36263
    Apr 26, 2017 at 4:14
8
$\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$

Improve this answer
$\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$

Improve this answer
$\endgroup$
8
  • 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, 2017 at 19:14
  • 2
    $\begingroup$ (same for factorial) $\endgroup$
    – Rubio ♦
    Apr 19, 2017 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, 2017 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$
    – user33097
    Apr 19, 2017 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$
    – user33097
    Apr 19, 2017 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.

Improve this answer
$\endgroup$
3
  • 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, 2017 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, 2017 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, 2017 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.

Improve this answer
$\endgroup$
1
  • 4
    $\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, 2017 at 1:22

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