Problem 001

[alpink]

I am new to this. I have worked out the answer to problem 1 to be 200003. I have tried in different ways and I always get the same answer. I am probably misreading the question somehow but I do not know. Why is my answer wrong!

My brute force algorythm is

Code: Select all

code snipped by hk

Thanks

[euler]

What would your algorithm make of i=15?

[alpink]

I read the program as meaning either 3 or 5. 15 is both so it will not count. Hence the lines
if a=0 and b<>0 then total=total+i
if b=0 and a<>0 then total=total+i
which will exclude multiples of 15.

Thanks

[quilan]

Inclusive or, not exclusive

[georgopanos]

I cannot understand why my answer is wrong? Please let me know if I am doing something wrong.

Code: Select all

code snipped by hk

[ed_r]

What happens when counter = 15 ?

[georgopanos]

The total is 75
3 equals 45
and
5 equals 30

[euler]

ed_r was giving you a good hint as to why it won't work. To be less subtle...

s = 3 + 6 + 9 + 12 + 15
s1 = 5 + 10 +15

Notice anything?

[georgopanos]

15 is added twice in the total sum!

[phillip1882]

i "sovled" this one fairly quickly but the answer i submited was wrong. ???
i did it both with a program and pencil and paper and got the same answer both ways.
i even tried putting a comma in the answer sperating the thousands from the hundereds and still no luck. %$#@! any suggestions? can i email someone my answer? i know i'm probalby doing something basic wrong but i can't figure out what.

[daniel.is.fischer]

Maybe you misinterpreted "below one thousand"? That means strictly less than 1000.
If that's not it, PM me your reasoning and result, and I could perhaps give you a hint.

[Danooka]

I am also having trouble with this. I started by recreating the example, then once I got that I scaled it to 1000, but my answer is still rejected as incorrect. I would be happy to post my code (I was using python) and receive any suggestions, but I'm unfamiliar with site policies and don't know if it's acceptable to do so.

[daniel.is.fischer]

It's preferred not to post code openly. You can PM me your code.

[terrabit]

arghh i am new to c++ and am having difficulties with testing and removing duplicates from my addition. i can send my full code if needs be

}

Code: Select all

code snipped by hk

does this make any sense to anybody? i am trying to use the fact that if a multiple of 5 is also a multiple of 3 the multiple of 5 will divide by 3 without decimal whereas any other won't. and when a variable which can store decimals is subtracted by one which cant the difference is either 0 for multiple of 5 + 3 or some random decimal for only multiple of 5

[jaap]

If at all possible, don't use floats or doubles for this kind of thing. Floating point numbers are approximations, and a calculation that you expect to result in an integral value might only be very close to one. This is because intermediate values in a calculation might not be representable exactly in a floating point type, and so be rounded at the last digit. Further calculation can then increase that slight error more.

In your code you could use

if ((divid-maybe) <= 1e-6)

but it is much better to use integers only. For example:

int x = some value;
if( (x/3) *3 == x )

or even better

if( x%3 == 0 )

[terrabit]

now i've been to bed i can see kind of what you mean. so if i do....

Code: Select all

code snipped by hk

it should work. the problem was with c++ substituting values very close to 0 for 0. is that right

[jaap]

now i've been to bed i can see kind of what you mean. so if i do....
<snip>
it should work.

That should probably work, but as I said you don't need floating point stuff here. It is much better to use:

Code: Select all

code snipped by hk

Here (5*multiplyer) % 3 means the remainder after (5*multiplyer) is divided by 3. This is of course 0 if it is a multiple of 3.

the problem was with c++ substituting values very close to 0 for 0. is that right

It has nothing to do with c++ in particular. Approximations will happen with any programming language or even any calculator (unless it is representing the numbers as rationals). You cannot represent 1/3 exactly in a finite number of digits.

P.S. After thinking about it longer, the original test for being a multiple of 3 should work too, as integers are exactly representable in floating point variables. I still would not recommend relying on it when there is no good reason to. Maybe there is some other incorrect logic in your program.

[terrabit]

argh now i have to check all the rest of the code. at least that works now

[Programmist]

I noticed that no one has added to this post in a while, so I hope you don't mind me "commandeering" it briefly.

I just found Project Euler and solved problem #1. I know it's not very difficult, but I wanted to find out what the optimum solution was. Since the forum on the Euler site has 900+ posts and I did not see a way to search, I'm hoping someone here can let me know how close to optimal mine is. If I assume my constant time operations to be O(1) then my solution is O(2n/7). Testing indicates that for values of n = {1000, 10000, ... , 1000000000} my solution seems to run about an order of magnitude faster than the naive solution. How am I doing? Can I improve this?

Thanks.

[Ikcelaks]

The optimal solution to problem #1 runs in O(1) within the range of values that can be added and multiplied in constant time (arithmetic on numbers too large to represent natively in the hardware will have some non-constant runtime based on the size (in bits) of the numbers).

Note: The question doesn't ask you to find the numbers. It asks you to find how many numbers there are.