Problem 259
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.
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
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 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
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
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.
Is 17 digits about right?
Is 17 digits about right?
 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 10^{10} and 10^{12}.
Il faut respecter la montagne  c'est pourquoi les gypaètes sont là.
Re: Problem 259
Thanks, realised where i went wrong  i wasn't taking them in the right order.
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!
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!
Re: Problem 259  concatenation of digits
Only the original digits can be concatenated. The 913 example above would not be valid.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? ...
(Please don't create a new topic for a problem when one already exists).
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.
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.

 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 reachable numbers + expression and check some random expressions
+ Do not use floating point type
+ Use 4byte numerator and denominator.
Am I forget anything?
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
+ Do not use floating point type
+ Use 4byte numerator and denominator.
Am I forget anything?

 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:
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
Are you sure? What about 12345*6789?user202729 wrote:Expand
Re: Problem 259
12345*6789 < 12345*10000 < 123456789.nicolas.patrois wrote:Are you sure? What about 12345*6789?
 nicolas.patrois
 Posts: 118
 Joined: Fri Jul 26, 2013 3:54 pm
 Contact:
Re: Problem 259
Hm yes.

 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.
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
 Administrator
 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 overestimate of the number of distinct calculations that have to be made.
On your calculation, yes, there are a lot of potential evaluations to make. But many will be duplicates, so it's an overestimate of the number of distinct calculations that have to be made.
Re: Problem 259
Is 123456789 a valid reachable number? I am thinking yes, but, just want to confirm.
Thanks.
Thanks.
my friend key > 990813_OZPwQtCjkD6KlvxirOoTSZxccMFsuw1L
Re: Problem 259
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.rmacheshire wrote: ↑Tue Sep 06, 2016 11:43 amMy 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.
vamsi@vamsilaptop:~/learn/project_euler/257_to_384/problem_259$ ../Downloads/kawa3.0/bin/kawa
#kawa:1# (load "main.scm")
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
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.
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.
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.
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.
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.