Jump to content

  • Log In with Google      Sign In   
  • Create Account


Trying to solve mathematical problem using programing skills


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
13 replies to this topic

#1 BaneTrapper   Members   -  Reputation: 1112

Like
0Likes
Like

Posted 28 November 2012 - 12:39 PM

Hello.
The question i was posed is:
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
The program i made
int main()
{
    int sum = 0;
   
    for(int i = 0; i < 1000; i++)
    {
	    if((i % 3) == 0)
	    {
		    sum += i;
	    }
	    if((i%5) == 0)
	    {
		    sum += i;
	    }
    }
    std::cout<<sum<<std::endl;
}
Output is "266333"
The answer is "233168"
what em i doing wrong?

Current projects:
The Wanderer, 2d turn based rpg style game

www.gamedev.net/topic/641117-check-up-the-wanderer/


Sponsor:

#2 Brother Bob   Moderators   -  Reputation: 7781

Like
3Likes
Like

Posted 28 November 2012 - 12:43 PM

You're accumulating multiples of 15 twice since those numbers are divisible by both 3 and 5. I'm not going to provide a solution though, but let you think about it.

#3 BaneTrapper   Members   -  Reputation: 1112

Like
0Likes
Like

Posted 28 November 2012 - 12:51 PM

You're accumulating multiples of 15 twice since those numbers are divisible by both 3 and 5. I'm not going to provide a solution though, but let you think about it.

You don't have to, and thanks for the answer.
I feel oddly stupid.

The output now is now correct
Combined the if statement to one
if((i % 3) == 0 || (i%5) == 0)
        {
            sum += i;
            OStream << i << "\n";
        }

Edited by BaneTrapper, 28 November 2012 - 12:52 PM.

Current projects:
The Wanderer, 2d turn based rpg style game

www.gamedev.net/topic/641117-check-up-the-wanderer/


#4 AlexB.hpp   Members   -  Reputation: 201

Like
0Likes
Like

Posted 28 November 2012 - 01:06 PM

Read opened thread for this problem to find out better solution. It's really interesting.
C x 2 C x o C x C f nice C x C s C x C c

#5 Nypyren   Crossbones+   -  Reputation: 3693

Like
2Likes
Like

Posted 28 November 2012 - 01:10 PM

I feel dumb for only now realizing that Project Euler used a FizzBuzz-like situation on their first problem. :)

Edited by Nypyren, 28 November 2012 - 01:11 PM.


#6 IvanK   Members   -  Reputation: 116

Like
2Likes
Like

Posted 28 November 2012 - 04:00 PM

I think you can solve it in constant time on paper (or with one expression in your programming language), no need for loops :)

#7 Bacterius   Crossbones+   -  Reputation: 8158

Like
4Likes
Like

Posted 28 November 2012 - 08:58 PM

I think you can solve it in constant time on paper (or with one expression in your programming language), no need for loops


For 3 and 5, yeah, you can for any bound (inclusive, use if you don't want to include it), it's just:



Which simplifies down to (the floor symbols indicate integer division):



For , this gives . For , we get as expected.

You can see the general pattern - sum up the multiples of each number required (here 3 and 5), and then subtract any numbers which are multiples of any two of them at the same time. You can generalize this to more than two numbers, but it gets pretty messy as you need individual sums to get the correct result for different numbers, so it gets impractical if you need to consider many different divisors.

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis


#8 BaneTrapper   Members   -  Reputation: 1112

Like
0Likes
Like

Posted 29 November 2012 - 05:10 AM

Read opened thread for this problem to find out better solution. It's really interesting.

I was asking what is wrong with my code, tho i made mistake.
I tried looking for other codes to see how they where made, i keep crossing on PHP code, so i open thread :P.

I think you can solve it in constant time on paper (or with one expression in your programming language), no need for loops :)

I have so low mathematical knowledge. Don't know these formulas at all.

For 3 and 5, yeah, you can for any bound (inclusive, use if you don't want to include it), it's just:

Which simplifies down to (the floor symbols indicate integer division):

For , this gives . For , we get as expected.
You can see the general pattern - sum up the multiples of each number required (here 3 and 5), and then subtract any numbers which are multiples of any two of them at the same time. You can generalize this to more than two numbers, but it gets pretty messy as you need individual sums to get the correct result for different numbers, so it gets impractical if you need to consider many different divisors.

If they have shown me how to do it from 0 - 1000 id know how to do it from 0 - 10000^^.
But yea, its kinda too much for me since you most know good math for those problems. I didn't get far with it, 3/10 problems solved and am pleased since i don't understand 70% of those questions.
Thanks on good mood.

Current projects:
The Wanderer, 2d turn based rpg style game

www.gamedev.net/topic/641117-check-up-the-wanderer/


#9 Khatharr   Crossbones+   -  Reputation: 2820

Like
1Likes
Like

Posted 29 November 2012 - 06:37 AM

Sigma notation can be difficult to read if you're not used to it. It's actually quite straightforward, but for some reason large Greek letters can stun the brain for several seconds. (This happens to me often and is probably a sign of poor nutrition or a brain injury resulting from sitting too close to the television as a kid.)

Edited by Khatharr, 29 November 2012 - 06:39 AM.

void hurrrrrrrr() {__asm sub [ebp+4],5;}

There are ten kinds of people in this world: those who understand binary and those who don't.

#10 TheChubu   Crossbones+   -  Reputation: 3705

Like
0Likes
Like

Posted 29 November 2012 - 07:53 AM

Sigma notation can be difficult to read if you're not used to it. It's actually quite straightforward, but for some reason large Greek letters can stun the brain for several seconds. (This happens to me often and is probably a sign of poor nutrition or a brain injury resulting from sitting too close to the television as a kid.)

Quoted for truth. Its my experience in Mathematical Analysis, Algebra and Algorithms courses summed up in a single quote.

"I AM ZE EMPRAH OPENGL 3.3 THE CORE, I DEMAND FROM THEE ZE SHADERZ AND MATRIXEZ"

 

My journals: dustArtemis ECS framework and Making a Terrain Generator


#11 hupsilardee   Members   -  Reputation: 486

Like
0Likes
Like

Posted 29 November 2012 - 08:43 AM

Python is great for this kind of thing. I just pull up the shell and hack a quick function together. Great for GCD, LCM, co-primality, etc. Quicker than C++ to compile and run.
I just rewrite the function every session I want to use it, which ends up with me learning the definitions of these things very thoroughly (and degrading my mental arithmetic).

Sigma notation can be difficult to read if you're not used to it. It's actually quite straightforward, but for some reason large Greek letters can stun the brain for several seconds. (This happens to me often and is probably a sign of poor nutrition or a brain injury resulting from sitting too close to the television as a kid.)


What scares you more, a sigma with a large expression or an integral sign with a large expression?

#12 BCullis   Crossbones+   -  Reputation: 1813

Like
0Likes
Like

Posted 29 November 2012 - 08:47 AM

I love math notation for two reasons.
1) Being able to read it feels like translating hieroglyphics, which is kind of fun
2) It is incredibly condensed communication: throw 4 symbols down on paper and you've just described a vector space, or a specific group of values, or an entire relationship between values

Especially things like set notation descriptions, those looked like gibberish to me until I sat through a discrete math course.

Anyhow, Project Euler is interesting because there's groups of people who are so focused on the most elegant or minimalist answer, and there's people who want to use their language of choice to solve the problems in any means necessary (treating it as an art or a learning task, respectively). The bottom line is still the same though, so I never give someone crap for using a brute-force or messy algorithm: programming lets us solve problems and complete tasks in a fraction of the time it would take to obtain the answer in meat-space.

...Except that problem asking for the nth prime, looking up prime numbers on the internet is just way too easy.
Hazard Pay :: FPS/RTS in SharpDX
DeviantArt :: Because right-brain needs love too

#13 BCullis   Crossbones+   -  Reputation: 1813

Like
0Likes
Like

Posted 29 November 2012 - 08:49 AM

What scares you more, a sigma with a large expression or an integral sign with a large expression?

Depends if you're asking for series simplification or not. I loved calculus because it was algebra on steroids and felt like number alchemy. But I was always crap with series. The one place I loved seeing sigmas was in induction proofs.
Hazard Pay :: FPS/RTS in SharpDX
DeviantArt :: Because right-brain needs love too

#14 Cagnazzo   Members   -  Reputation: 140

Like
0Likes
Like

Posted 29 November 2012 - 10:32 AM

Python is great for this kind of thing. I just pull up the shell and hack a quick function together. Great for GCD, LCM, co-primality, etc. Quicker than C++ to compile and run.
I just rewrite the function every session I want to use it, which ends up with me learning the definitions of these things very thoroughly (and degrading my mental arithmetic).

Python is pretty good, but you'd be amazed at how well Haskell does with Project Euler.

There are tons of problems that it just chews through with no thought. Which is exactly what you'd expect from a purely functional language, really Posted Image




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS