Problem 093

kosiu_drumev · Post by **kosiu_drumev** » Sun Mar 13, 2011 11:22 pm

Maybe it's a stupid or irrelevant question but anyway

Is ZERO a digit in the context of this problem?

jaap · Post by **jaap** » Sun Mar 13, 2011 11:56 pm

kosiu_drumev wrote:Is ZERO a digit in the context of this problem?

Yes it is, but since you're not allowed to concatenate digits, it isn't of much use.

thundre · Post by **thundre** » Tue May 10, 2011 2:13 pm

bobfin wrote: My method correctly finds that the digit set {1,2,3,4} yields a run of consecutive numbers 1 .. 28.

Mine did too, even when I forgot to include division as a valid operation.

dconrad · Post by **dconrad** » Thu Jun 16, 2011 3:55 pm

When I first read the problem, I misread two parts of it. I didn't catch that only positive integers were allowed as results, and I didn't catch that the series of consecutive integers had to be from 1 .. n. If you allow negative results and look for the longest consecutive series of integers regardless of starting value, then there is a better solution.

There is a set of four digits that produce 80 consecutive integers, from -36 .. 43. Can you find them?

My Java program takes around 1 second (for Problem 093 or this extended problem); somewhat over if I allow 0 as a digit, a little under if I don't.

Francky · Post by **Francky** » Mon Jun 20, 2011 5:24 pm

I got 780ms in Python3 (interpreted), so you could do better in Java, I think

EDIT : 560ms, and I'm not proud of this algo.

Hibernatus34 · Post by **Hibernatus34** » Mon Jun 20, 2011 6:17 pm

780 ms sounds a bit long, i got 10 ms in C++ on an i5 2400 (from 3.1 to 3.4 GHz), and judging by the horrible code i think it was my first try and i never tried to optimize it.
Maybe you should try Psyco in order to get times that are closer to Java/C#/C++ times.

I bet one can achieve less than 1 ms on this problem

Maybe with a little low-level optimization, or with another super-smart algorithm.

Achab · Post by **Achab** » Thu Sep 08, 2011 1:07 pm

Hi,

My answer to this problem is wrong, but I don't find the bug in my algorithm. I've found 4 digits which give 65 consecutive integers from 1 to 65. I suppose the exact answer give a longer sequence ?

thundre · Post by **thundre** » Thu Sep 08, 2011 3:04 pm

Achab wrote:My answer to this problem is wrong, but I don't find the bug in my algorithm. I've found 4 digits which give 65 consecutive integers from 1 to 65. I suppose the exact answer give a longer sequence ?

65 is too long. The correct answer yields a shorter sequence.

Achab · Post by **Achab** » Thu Sep 08, 2011 4:19 pm

I may be wrong but i got a set of 4 digits, i can give the details if needed, which yields a sequence of 65 integers (from 1 to 65).

rayfil · Post by **rayfil** » Fri Sep 09, 2011 3:14 am

Send me a PM with your results and I will check them out.

Achab · Post by **Achab** » Fri Sep 09, 2011 8:33 am

Hi,
It won't be necessary, euler sent me a message detailing my mistake.
I actually used some digit 0 or 1 time instead of exactly 1 time.
regards

amidar1 · Post by **amidar1** » Wed Jan 18, 2012 11:44 pm

I'm getting a tie.

My algorithm gives results that match all the data that has been posted in this thread so far, but I have two different sets that produce the same longest string of accessible numbers. (I'm not sure whether it's appropriate to post how long that string is.)
Did anyone else hit that problem and / or have an idea what I might be missing?

MithrilTuxedo · Post by **MithrilTuxedo** » Thu Aug 28, 2014 9:24 pm

I wasn't mentally parsing the term "digit" correctly. I'd conflated it with the broader term "integer".

I discovered, in significantly more time than it took to find the actual answer, that there are longer runs possible beyond the scope of the solution set.

edmurray · Post by **edmurray** » Fri Sep 12, 2014 8:15 pm

MithrilTuxedo wrote:I wasn't mentally parsing the term "digit" correctly. I'd conflated it with the broader term "integer".

I discovered, in significantly more time than it took to find the actual answer, that there are longer runs possible beyond the scope of the solution set.

I'm very grateful that you posted this. I couldn't figure out why my answer wasn't being accepted, and as soon as I read your post I realised I had made the exact same mistake.

Thank you MithrilTuxedo!

kvom · Post by **kvom** » Sat Feb 21, 2015 6:49 pm

Just got back onto project Euler after a long layoff, and finally figured out an algorithm to solve this problem. Got the correct answer for 1234, and my program finds a maximum sequence of 43. Any hints would be appreciated. Program is conceptually simple and I've spent hours looking at it.

Georg · Post by **Georg** » Sat Feb 21, 2015 9:45 pm

Your program should find a longer sequence.

kvom · Post by **kvom** » Sun Feb 22, 2015 5:28 pm

After re-reading this thread I saw that intermediate values could be non-integer as long as the result is integer. Changed algorithm to use floating point for division and got the correct answer.

TiptTop · Post by **TiptTop** » Mon Aug 03, 2015 2:26 am

What is a "non-expressible number" ?

TripleM · Post by **TripleM** » Mon Aug 03, 2015 3:19 am

A number which cannot be expressed in the form stated in the problem statement.

TiptTop · Post by **TiptTop** » Mon Aug 03, 2015 4:20 am

TripleM wrote:A number which cannot be expressed in the form stated in the problem statement.

Is same operation (+ or - or * or /) allowed multiple times but separated by brackets/parentheses?

Project Euler Forum

Problem 093

Re: Problem 093

Re: Problem 093

Re: Problem 93

Re: Problem 093

Re: Problem 093

Re: Problem 093

Re: Problem 093

Re: Problem 093

Re: Problem 093

Re: Problem 093

Re: Problem 093

Re: Problem 093

Re: Problem 093

Re: Problem 093

Re: Problem 093

Re: Problem 093

Re: Problem 093

Re: Problem 093

Re: Problem 093

Re: Problem 093