I included iostream but it disappeared from the comment
etc. Tho you could also refactor that to a single fx and then do a yield return.
I amazed on your solution.I seen your code After i got my solution.I UNDERSTAND STILL IM IN CODE PLAY SCHOOL .I placed my time consuming code.How to see the time taken by code.it would be useful for others too.
Newbie there and doing UG in CS(2nd yr)(U asked my level-novice++).
My first suggestion to solving one of these problems, is usually to bruteforce it. In order to bruteforce the first problem, we need to iterate over all the numbers from one to 1000, and we need a way to check if the number we are checking is divisible by 3 and/or 5.
[] the project euler 1 solution. For more information about the methods and details you can check this blog which have all the []
Then do the same for 1000/5 = 200 times.
Funcint, List, int MultiplesOf = (x, range) =
Since we are looping through the all the numbers, and a two comparisons and possibly one addition is needed for each number, the algorithm scales linearly with p , which inBig Onotation can be expressed as O(n), not a bad scalability as a such. However the geometric approach has a constant computation time, which is expressed as O(1), which is obviously better ?
So are there any books(specific for Maths) which are prefectly meant for programming purpose from zero to highAs I find myself lame for questions of Higher level on Project Eulerand I dont want to submit every sol.n after peeping into yours..
N is the highest number less than p divisible by n. In the case of 5 this is 995. However, with integer division N can be expressed as
Range [Sum of multiples of 3 and 5]
Thanks for the tipsVery usefulgave me a direction to go upon.
There are multiple methods for finding the solution for this problem
I think there are two pieces of advice I can give you right now. The first advice here, is to have fun. You probably already have an official study plan, so things you do besides that should be fun. I dont mean you need to sit and laugh all the time, you might even be frustrated some of the time. But somewhere deep down it should satisfy something in you to do this.
So I think U suggested me to first study all the Programming concepts(Frm the book U suggested for efficient progrmm.)and for strengthening math go from High School level to beyondand then switch to solving.
Solution to Project Euler, Problem 1, using Python (v.3.6.1)
In the first bit of code we check if a number was divisible by 3 and/or 5, and this way we only checked each number once. Another solution would be to find the sum of all numbers divisible by three, and the sum of all numbers divisible by 5. We could define a function that did this.
The sum of all numbers dividable by 3 or 5 is: 233168
The sum of numbers divisible by 6 or 10 between 1 and 999999 is 6
The sum of numbers divisible by 3 or 5 between 1 and 9 is 23
sum([i for i in range(1000) if (i%3)*(i%5)==0])
Thank you for a great question which also warrants a great answer. First of all the programming part, it is not necessary to know more than one programming language, but there is certainly a benefit to it I think. However, programming is more than the language, there is a whole lot to learn about algorithms and data structures which is almost generic regardless of the language you program in.
On the math side, I dont think there is any one book or series of books that will lead you to be able to solve these problems. There are a whole lot of number theory in them, but also some linear algebra, some statistics and so on. it is even more difficult to actually recommend something without knowning your current level.
As expected, if we calculate the sum of numbers divisible by 6 or 10,
int three_total,five_total,Result = 0;
If the problems were small you could just make an array, but I am not sure that is a feasible approach since the N can be rather large. So you will need to find a way to compress the data ranges.
The sum of numbers divisible by 6 or 10 between 1 and 9999 is 12495006
The sum of numbers divisible by 3 or 5 between 1 and 99 is 2318
Click to share on Twitter (Opens in new window)
5+10+15+20++995 = 5*(1+2+3+4++199)
long long SumDivisibleBY(long int a,long int b);
[] rather than a pure math solution. For a more efficient but more maths focused solution see the MathBlog post on the topic. Anyway, here is what I ended up []
Hope then I will turn as good as you ?
if (((i % 3) == 0) ((i % 5) == 0))
Output of the results using extension of RosettaCode in C
Would you pleas post the entire compilable C source for the optimized solution ? I am new to C and I cannot figure out ow to call each function ( Solve() and SumDivisibleBy() ) from my static void Main() method.
Tags:ArithmeticBig OBrute ForceCModuloProject Euler
I dont think it is that easy to answer your question. Being a cs undergrad I am pretty sure you are already having quite a few courses in different subjects.
With python we can express the sum like :
SumDivisbleBy(3, 999) + SumDivisbleBy(5, 999) SumDivisbleBy(15, 999)
So instead of the previous check we can write
thanks mr Kristian for such best explanation with different approaches.
Click to share on Google+ (Opens in new window)
print( %s seconds % (time.time() start_time))
Sign upfor the Mathblog newsletter, and get updates every two weeks. I promise I will includecool tidbitsfor you.
After that I should go on to the books you referred as containing lots of number theory,LA,stats..etc.
Public void Solve() result = SumDivisbleBy(3,999)+SumDivisbleBy(5,999)-SumDivisbleBy(15,999); private int SumDivisbleBy(int n, int p) return n*(p/n)*((p/n)+1)/2;
umi dont know why no ones mentioned it yet but why not use modulo? my JS code(runs fast enough)-
And the result of running the code is
This solution can handles the sum below any given number almost equally fast, if the sum can be stored in an integer.
Plz Pardon me for this unrelated post
Its me again, thanks for your feedback.I solved the problem and your code is fine. It was from the printf I wrote wrong. Thanks and sorry for bothering you.
Hello, can you tell me how I can make this code work? I tried simplifying this but Im getting the wrong number and I dont know why.
The sum of numbers divisible by 3 or 5 between 1 and 9999 is 23331668
However, we need to put something clever inside the SumDivisbleBy function, otherwise we have an even slower solution.
Click to share on Reddit (Opens in new window)
The sum of numbers divisible by 3 or 5 between 1 and 999999 is 8
I dont know why it doesnt work for you. Have you read this post it gives you are little background for the the pieces of code you have to wrap around the functions I provide here in order to run.
I am afraid I cant help you out on that one right now. I simply dont have time. Besides I dont think it is fair to give out spoilers like that when ever then contest is running.
Save my name, email, and website in this browser for the next time I comment.
So you are meant to use coding not your head ?
can you please suggest me other sites where i can practice c pragramming
The sum of numbers divisible by 6 or 10 between 1 and 99 is 1206
The sum of numbers divisible by 6 or 10 between 1 and 9 is 6
Without going into details about what happens if the numbers become greater than what can be stored in aninteger or longlets have a look at the scalability of the algorithms.
long long SumDivisibleBY(long int n,long int p)
c.WriteLine(Enumerable.Range(1, 9).Sum(x= voke(x, range)));
Either modulus is definitely not the way to go because it creates an O(n) i.e. linear algo.
One of my personal favorites for that topic is this one
I have started solving problems on code-chef also. I am trying the problems in August Challenge. I am stuck with the problem DRANGE (Range of Data). If it is possible, could you please take a look and share what your approach could have been? Though I know they would be giving the editorials out when the contest ends, I do not find their explanation as helpful as I have found your explanation for the project euler problems.
The description ofproblem 1onProject Eulerreads
Wont the arithmetic/geometric approach double add numbers that are both multiples of 3 and 5 (e.g. 15)?
um That is exactly what I do in my first solution.
Reduces the iteration from 1000 times to (333 +200) = 533. i.e. approx halve the iterations.
However, this can be written much shorter using themodulo operator, which finds the remainder of the integer division. The modulo operator in C is written %.
I changed the upper limit to 99999 but the result by two methods came out to be different and i am wondering why?
Uva online judge, code foces as well as code chef have some really interesting problems I think.
I know these are not specific things you can read, but I hope they do help you on your way. I will see if I can come up with some interesting reads later on.
Thanks a lot sir. Your explanation is really easy to understand for novice like me.
As you can see, for such small problems, it takes less than a millisecond on my computer to solve, so there really is not need to find faster solutions. However, lets explore the problem a bit more.
It is pretty expensive, but from the chapter I have skimmed, it looks pretty good.
I understand. Thanks anyways. I will try to bang my head on the question.
the answer will be 234168, not 233168 as given here
start_time = time.time()
The trick is to express the sum by other means, and in this case the sum
A geometric explanation is givenhereand an arithmetic explanation is givenhere. A more general explanation on arithmetic progression is given onwikipedia.
I just want to ask where should I start from,(Confused)As theres lot just then programming U hv to learn Data,Ada etc then U must knw Maths
it is not correct. The answer is: 233168
3+6+9+12++999 = 3*(1+2+3+4++333)
a relatively simple pattern is obtained:
Click to share on Facebook (Opens in new window)
Thus the sequences for any number divisible by n can be written as n*N*(N+1)/2.
cout SumDivisibleBY(3,99999)+SumDivisibleBY(5,99999)-SumDivisibleBY(15,99999);
Find the sum of all the multiples of 3 or 5 below 1000.
The sum of numbers divisible by 6 or 10 between 1 and 99999 is 1249950006
And the output of the algorithm is once again
Excuse me, but how it can be that N=p/n when N=995, p=999, and n=5?
The sum of numbers divisible by 3 or 5 between 1 and 999 is 233168
Sorry, I am a beginner in programming but when I compile and run the code you provided there is no result, actually if I put a printf to display the result, it shows 1000. Where is the problem?
Hi Kristian,this is your code i translated to C++
Now that the fluff around the coding is covered, we are ready to solve the first problem.
I was looking for something about number theory which is a very integral part of the Project Euler problems. I found this book
One way we can check if 3 is a divisor of x (which is declared as integer) is by the following line
The reason for the wrong results could happen due to integer overflow.
Sorry but i can not understand why we subtract
Remember that the reason I wrote this, is not to give you the answer, but rather to explain different approaches to the solution. I hope you have found it useful and have learned from it. Feel free to make comments and correct mistakes.
// A Map/Reduce pattern to solve this problem
If what you are really looking for is some programming challenges to throw yourself at, there are a lot of options which are less math focused then Project Euler, not that I will try to discourage you by any means. You can see a whole lot of ideas right here
it is important to note the parenthesis around p/n, if these are not there, the result will deviate since the program n*below/n = n, which is different from n*(below/n).
wow such an elaborate explanation.
The second advice I will give you is that the most important thing to learn in order to solve problems like these are to think abstractly. This probably comes from a mixture of trying some of the problems, learning a bit of new theory while trying to solve it (google is your friend here), and reading math. Become familiar with the notation and give your self some problems where you push yourself a bit.
And no you havent offended me by asking this kind of question. I take it as a compliment.
The first 6 chapters are available here
So lets look at the numbers divisible by n=3:
I can recommend which is a great learning place that will take you far.
It can get 23 if the stop number is changed, and will print 23, but when the stop number is 1000 I get 266333.
Now we have all the parts needed to express an efficient solution, which in C can be written as
Wow!! Such an amazing alternate solution!
Oh scratch that. Misread the question.
The sum of numbers divisible by 6 or 10 between 1 and 999 is 124506
I hope I have not offended you in any way.
var answer = range.Select(r = (x % r) == 0);
Why not floor(1000/3) = 333. Iterate 333 times 1*3, 2*3, 3*3 etc.
Console.WriteLine(The sum of multiples of 3 and 5 number is + (Result ));
And the result of running the code is
The sum of numbers divisible by 3 or 5 between 1 and 99999 is 2333316668
if i % 3 == 0 or i % 5 == 0:
Here we useinteger division, which means that we will discard the fractional part of the result. An example of integer division is 10/3 = 3.
return answer.Any(i = i == true) ? x : 0;
where n is the divisor, and p is the greatest number we want to check. Which in this case p=999, and n=3,5In this case we have counted number which are divisible by 3 and 5 twice, and therefore need to subtract them such that the solution would be
Digits distribution pattern in the sums of multiples of 3 and 5