If you’re going to move onto a new problem, please post it first.
4 Likes
Sorry 
I didn’t want to imply that everyone need to move on to the next one already.
3 Likes
Wow, I didn’t know there was a closed form for the sum of squares. Can you link to a proof? 
Edit - nvm ^^
Here my crude solution
Problem 6, python
def sumOfSquares(n):
s = 0
for i in range(n+1):
s += i**2
return s
def difSquareOfSumVsSumOfSquares(n):
squareOfSum = ((n * (n+1))/2)**2
print(squareOfSum)
return squareOfSum - sumOfSquares(n)
print(difSquareOfSumVsSumOfSquares(100)
1 Like
While the visual proof above is one of my favorites, this is probably one of the ugliest visual proofs I’ve seen 
It’s just too hard for my brain to visualize the three pieces fitting together in the first step, and so unsatisfying that there’s that jagged part leftover that has to be flipped.
And it absolutely does not help me remember the formula, I have to look it up every time I need it (which is admittedly not very often, but today was one of those days 
).
This alternate presentation of the same proof is simultaneously better and worse:
4 Likes
I find the first one quite understandable, and the second one a lot less so.
3 Likes
I prefer a simple proof by induction on n.
Many years ago my father showed me a method on how to find formulae for the sum of any fixed power of the first n natural numbers. I don’t remember it exactly, but I believe it was some kind of polynomial interpolation (which gets very tedious for high powers when done by hand).
3 Likes
I found some info here, didn’t know about this one before
3 Likes
You can do it for all the consecutive n^th powers.
Each one uses the previous formulas to evaluate like with the binomial expansion formula.
I think in the one @antonTobi linked, the idea to use binomial expansion makes sense.
I’m not quite following this one.
I thought one could do something similar with
(n+1)^(k+1)-n^(k+1)
Basically if you sum that for n=0 to N you get (N+1)^(k+1) which is fixed and then if you binomially expand you have n^k as the highest power and then the lower powers which presumably you have a formula for.
E.g. (n+1)^2-n^2=2*n+1
If you sum from 0 to N you get (N+1)^2=2*sum n + (N+1)
Then rearranged to get N^2+N=2 sum n and recover the usual formula sum from 1 to N of n is (N)(N+1)/2
To get the squares you can look at
(n+1)^3-n^3=3n^2+3n+1
Then sum over n
(N+1)^3=3(sum of squares) + 3(sum of integers) + N+1
Then use the sum of integers formula and solve for (sum of squares).
And so on
1 Like
So, what’s your progress so far? Here’s how far I’ve gotten through the first 100 problems:
Project Eulerle #1-100 30/100
screenshot with numbers (sorry, I couldn't resist Wordefiling it above)
I have also solved problem #205, but that’s the only one I’ve done outside of the first 100.
I created my account many years ago, but, prior to March 10, I had only solved problems 1, 3, 5, 7, 10, and 205.
4 Likes
I only learned of this project from here, will try to stick to the pace here, but probably skip problems which I find uninteresting.
I can follow the idea, but it seems there are still some formidable equations to solve to get [{\sum\limits_{m = 1}^k {{m^p}} }]
2 Likes
I was missing the understanding of that first step
I think the final formula should make it relatively easy to iterate to get to one’s desired k.
For example a Maxima function that uses the formula recursively to generate all the formulas up to k, since you need them anyway to get the kth one.
sum_kth_powers(k):=block([kth_list,jth_term],
kth_list:[N],
if (k=0) then return(kth_list),
for j:1 thru k do (
jth_term:makelist(binomial(j+1,q)*kth_list[q+1],q,0,length(kth_list)-1),
jth_term:(N+1)^(j+1)-1-apply("+",jth_term),
jth_term:jth_term/binomial(j+1,j),
kth_list:append(kth_list,[factor(jth_term)])
),
return(kth_list));
Maxima is a CAS like Maple, Mathematica etc but open source. That code seems reasonably right, using the formulas, at least from the examples it looks like it’s working
So the output of sum_kth_powers(4) is
Or you could modify it to spit out only the last term with the last() command on a list.
Here’s the sixth one from last(sum_kth_powers(6))
1 Like
I did these 40 in 2014:
I think most of my solutions were brute-force, which isn’t feasible anymore for the later problems. Going back and redoing the first few ones now, it was much easier for me to spot some optimizations, so maybe I could get further now?
I would set a goal like “solve all the first 100”, but I think some of the problems just don’t appeal as much to me, so maybe “get 100 solved total” would be a better goal
1 Like
Maybe by problem 100 someone else could have found a way to make the uninteresting ones interesting for you by discussing it in this thread I’m not sure how far the thread will go, but even the ones that seem uninteresting to me have had someone post something that seemed interesting
2 Likes
My experience so far:
1. Skim through the first page, do 1 or 2 problems
2. "Bah this is too easy, get me something worth thinking"
3. Go to #51
4. Stuck 4 hours at #51
5. Give up
6. 2~4 years later...
1.
5 Likes
I wonder if there’s a more algorithmic set of problems than Euler’s. This set strikes me as very mathematical because at its core the solutions are just a bunch of loops if you do it the programming way.
I remember doing some fun programming tasks back in college, for example “in c++ build an abstract consecutive list of nodes in which each node is connected to both neighbours and implement an interface that allows adding, removing, substituting a node at any position”. Tasks like these I like more than brute forcing maths.
1 Like
I guess the plus side of some of the maths themed ones so far is that they’re reasonably accessible. That is one can just give some examples like a number is a palindrome if…, the fibonacci sequence is… and then just go for it.
So while I don’t think adding up the even fibonacci numbers is an interesting problem in that I don’t really see the point in it as a task, I still think being able to do things with loops is kind of a key aspect beginning to learn to write some code.
However it’s not clear that any of the problems so far would certainly make it a “good way” to learn to code either. A good way probably to find something you want to do and learn to do it, but in the absence of that or if that happens to be too tough, then maybe a book, course, videos or a set of problems seems reasonable.
Is that some kind of linked list type thing? Probably not knowing what it is, or some more specifications, might make it less accessible.
Indeed one of the nice things I guess about the problems in Project Euler so far is that the answer was a number and one could just see if you got the same number as other people
Yes a linked list. Basically recreating the entire library like boost or qtl or a more recent stl is always a nice programming challenge.
In case you didn’t notice this one mentioned in the top post, here’s a set of programming exercises:
The Euler problems are primarily math challenges. A lot of the easier ones can even be figured out with pen and paper, and maybe a basic 4-function calculator, within a few minutes. The whole point is to avoid naive for-loops and brute-force solutions. For many of the harder ones, the brute force approach is computationally infeasible. However, all of the problems are designed with a “one-minute rule”, meaning that a correctly designed algorithm should easily run within one minute on modest hardware.
1 Like