Project Euler Forum

Maybe it's a stupid or irrelevant question but anyway
Is ZERO a digit in the context of this problem?

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.

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.

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.

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.

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.

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 ?

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.

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).

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

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

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?

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.

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!

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.

Your program should find a longer sequence.

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.

What is a "non-expressible number" ?

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

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?