## Problem 259

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one

Don't post any spoilers
ac336
Posts: 5
Joined: Fri Aug 07, 2009 10:08 pm

### Problem 259

Can anyone tell me what kind of magnitude I should be expecting for this one? Just wanted to check I'm not miles off before I go delving in to solve my accuracy problems.

daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

### Re: Problem 259

No, the sum is much smaller, between 1010 and 1012.
Il faut respecter la montagne -- c'est pourquoi les gypa&egrave;tes sont l&agrave;.

ac336
Posts: 5
Joined: Fri Aug 07, 2009 10:08 pm

### Re: Problem 259

Thanks, realised where i went wrong - i wasn't taking them in the right order.

macgupta
Posts: 3
Joined: Sun Apr 05, 2015 3:13 pm

### Problem 259 - concatenation of digits

"Any successive digits can be concatenated (for example, using the digits 2, 3 and 4 we obtain the number 234)."

It is not clear whether concatenation is allowed only before applying +,-,*,/ or is allowed with any positive numbers along the way.
E.g., is a series of steps like (4 5 6 7) --> (4+5 6+7) = (9 13) --> 913 allowed?

Thanks!

mpiotte
Posts: 1914
Joined: Tue May 08, 2012 4:40 pm

### Re: Problem 259 - concatenation of digits

macgupta wrote:...It is not clear whether concatenation is allowed only before applying +,-,*,/ or is allowed with any positive numbers along the way.
E.g., is a series of steps like (4 5 6 7) --> (4+5 6+7) = (9 13) --> 913 allowed? ...
Only the original digits can be concatenated. The 913 example above would not be valid.
(Please don't create a new topic for a problem when one already exists).

macgupta
Posts: 3
Joined: Sun Apr 05, 2015 3:13 pm

### Re: Problem 259

Thanks!

It was also not clear whether a "topic" meant a particular clarification for a problem, or all clarifications for a problem. So I had to test that out.

user202729
Posts: 4
Joined: Tue Dec 29, 2015 2:58 pm

### Re: Problem 259

Anyone check my result?
I have checked:
+ Do not concatenate results
+ Do not include negative and fractional values in the sum, but calculate them
+ Generate a list of
Expand
reachable numbers + expression and check some random expressions
+ Do not use floating point type
+ Use 4-byte numerator and denominator.
Am I forget anything?

user202729
Posts: 4
Joined: Tue Dec 29, 2015 2:58 pm

### Re: Problem 259

Division by zero is not allowed, is it? (for example: 1/0/0 or 1/0*0)
I have no idea why my code can return wrong result because:
Expand

nicolas.patrois
Posts: 118
Joined: Fri Jul 26, 2013 3:54 pm
Contact:

### Re: Problem 259

user202729 wrote:
Expand
Are you sure? What about 12345*6789?

TripleM
Posts: 382
Joined: Fri Sep 12, 2008 2:31 am

### Re: Problem 259

nicolas.patrois wrote:Are you sure? What about 12345*6789?
12345*6789 < 12345*10000 < 123456789.

nicolas.patrois
Posts: 118
Joined: Fri Jul 26, 2013 3:54 pm
Contact:

### Re: Problem 259

Hm yes.

user202729
Posts: 4
Joined: Tue Dec 29, 2015 2:58 pm

### Re: Problem 259

My error. Now I have solved it.

rmacheshire
Posts: 5
Joined: Wed Nov 04, 2015 6:26 pm
Location: Portugal

### Re: Problem 259

My problem is that I get the solution but it takes nearly 15 minutes. I took some measurements and I am evaluating 3,392,923,553 expressions, about 3,951,693 per second, which actually seems quite fast. I just don't see how it can be done in 1 minute.

An approximate calculation for the number of expressions to evaluate: there are 8 operators each of which can be +, -, multiply, divide or concatenate, which gives 5^8 possibilities i.e. 390625. Also, by using brackets, the operators can be executed in any order, giving 8! =40320 combinations.

390625 x 40320 = 15,750,000,000

However, this does not allow for concatenation always being done before the other operators, which significantly reduces the number of combinations.

sjhillier
Posts: 511
Joined: Sun Aug 17, 2014 3:59 pm
Location: Birmingham, UK
Contact:

### Re: Problem 259

It is certainly possible in under a minute, the dedicated thread might have some useful ideas. I didn't get anywhere close to a minute on my first attempt.

On your calculation, yes, there are a lot of potential evaluations to make. But many will be duplicates, so it's an over-estimate of the number of distinct calculations that have to be made.

vamsikal3
Posts: 108
Joined: Sat Oct 01, 2016 8:25 am

### Re: Problem 259

Is 123456789 a valid reachable number? I am thinking yes, but, just want to confirm.

Thanks.
my friend key --> 990813_OZPwQtCjkD6KlvxirOoTSZxccMFsuw1L

traxex
Posts: 65
Joined: Thu Oct 19, 2017 12:30 pm

### Re: Problem 259

vamsikal3 wrote:
Sat Mar 03, 2018 10:05 am
Is 123456789 a valid reachable number?
Yes, it is.
Technically, everyone is full of himself.

vamsikal3
Posts: 108
Joined: Sat Oct 01, 2016 8:25 am

### Re: Problem 259

rmacheshire wrote:
Tue Sep 06, 2016 11:43 am
My problem is that I get the solution but it takes nearly 15 minutes. I took some measurements and I am evaluating 3,392,923,553 expressions, about 3,951,693 per second, which actually seems quite fast. I just don't see how it can be done in 1 minute.

An approximate calculation for the number of expressions to evaluate: there are 8 operators each of which can be +, -, multiply, divide or concatenate, which gives 5^8 possibilities i.e. 390625. Also, by using brackets, the operators can be executed in any order, giving 8! =40320 combinations.

390625 x 40320 = 15,750,000,000

However, this does not allow for concatenation always being done before the other operators, which significantly reduces the number of combinations.
Before solving any PE problem, I take a look at this forum to make sure I have as much information as possible. Now, for this problem I looked at this post and got a little scared about the amount of computation that might be needed to solve this problem. So, before solving the problem, I decided to accurately compute the number of expressions (of a length l, 1 <= l <= 9) that need to be computed to solve the problem. Without mentioning the details of my method of exhaustively enumerating the expressions to be evaluated, I get only 178913 different expressions (see below). Am I missing something or did I figure out a nice way to count/generate expressions so I don't have to do the kind of work suggested in the post above.

167763361

EDIT: I think the question might be answered, as the above post suggests, I am doing concatenation before any other operations.

EDIT2: My computation of the number of expressions that need to be evaluated was incorrect and I was getting a very low wrong value of about 180K expressions, after fixing the bug in computing that number, now I get 168 million expressions which is a big deal. I did find that there are enormous number of duplicates in the computed reachable numbers.
Last edited by vamsikal3 on Wed Mar 07, 2018 2:55 pm, edited 2 times in total.
my friend key --> 990813_OZPwQtCjkD6KlvxirOoTSZxccMFsuw1L

traxex
Posts: 65
Joined: Thu Oct 19, 2017 12:30 pm

### Re: Problem 259

The problem can be solved very comfortably in under 10 seconds. It doesn't require a scary amount of computation.

I think there are multiple reasonable ways to count distinct expressions that lead to different results. I saw only one count in the dedicated thread and it differs from yours, but you could both be right.
Technically, everyone is full of himself.

vamsikal3
Posts: 108
Joined: Sat Oct 01, 2016 8:25 am

### Re: Problem 259

Thanks for your comment. I will know whether my number is correct or not in a few days when I am done implementing my algorithm. In my expression count, two different expressions could possibly result in the same reachable number, so I would expect my number to be higher.

EDIT: The number I came up with originally about 180K expressions is completely wrong, because of a logic bug, I wasn't counting all the expressions. Now, with the bug fixed, I get about 167 million expressions.
my friend key --> 990813_OZPwQtCjkD6KlvxirOoTSZxccMFsuw1L

youth4ever
Posts: 11
Joined: Sun Jan 08, 2017 8:34 pm
Contact:

### Re: Problem 259

Hi Eulerians,

I really have frustration with this one. I get 72466 UNIQUE reachable numbers.
Is this even close to the total number of reachable numbers? Thanks.