Eulerian Tendencies?

[Thargy]

Folks,

since so many of you obviously enjoy these puzzles, how about teaming up to tackle some of the project Euler problems?

Although the answers are already known (otherwise how were the puzzles set in the first place?) it might prove beneficial for us all to learn from one another about the techniques they're using.

Or is project Euler just too geeky?

Regards

T

 

[Olaf Doschke]

That's a nice idea. I found it at

http://projecteuler.net

How about getting it started with problem 1:

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.

An analytical solution:

Spoiler

There is a simple formula for the sum of all numbers from 1 To n, which is (n+1)*n/2. Simply based on the observation that you can pair numbers, eg with N=1000 you can pair 1+1000, 2+999, 3+998 etc, each pair giving 1001, you have N/2 pairs, so the formula (n+1)*n/2 results.

This can be modified to only sum multiples of some number m by changing the upper limit to integer of n/m and multiplying the sum of all numbers from 1 to the reduced upper limit with m, eg multiples of 3 from 1 to 1000 are 3,6,9...999 or 3 times the sum of all numbers from 1 to 333.

In this case for m=3 the reduced upper limit is int(1000/3)=333, so the sum of all multiples of 3 between 1 and 1000 is 3*334*333/2 = 166833

For m=5 the reduced upper limit is int(1000/5)=200 and the sum is 5*201*200/2 = 100500

We need to reduce that by the all the numbers, which are both multiples of 3 and 5, which means all multiples of 15, so we also need the sum for m=15 which is: 15*67*66/2 = 33165

The total sum then is 166833 + 100500 - 33165 = 234168

In a more general formula with N1 for the first number (eg 3) and N2 for the second number (5) and an Upper Limt U (eg 1000) we need three upper limits U1, U2 and U3 as

U1=int(U/N1)
U2=int(U/N2)
U3=int(U/(N1*N2))

and then we need three sums

S1 = N1*(U1+1)*U1/2
S2 = N2*(U2+1)*U2/2
S3 = (N1*N2)*(U3+1)*U3/2

to get the total result as
Stot = S1+S2-S3

There might be a more elegant way to get to these formulas or a more elegant formula based only on U, N1 and N2.

A programmatical solution (

http://codepad.org/NaOATw9i)

Spoiler

/* Project Euler, problem #1 */

#include <stdio.h>
#include <iostream>

#define N1 3
#define N2 5

#define UPPERLIMIT 1000

int main(int argc, char **argv)
{
int counter, sum = 0;

for (counter = 1;counter <= UPPERLIMIT; counter++)
if (counter%N1==0 || counter%N2==0)
{/* cout << counter << '\n'; */ sum+=counter;}

cout << "Solution:" << sum;
return 0;

//Solution is 234168
}

In fact to get to the programmatical solution was much faster than finding and computing the analytical solution, especially writing all the explanations.

Without a computer I'd choose the analytical solution to need less computations, which I could easily do with pen&paper.

I tink this gets more and more true, eg you rather need the computer for the harder Euler problems.

Bye, Olaf.

 

[Thargy]

Olaf,

a superb first solution.

I forgot to mention that once solved, all the project Euler problems unlock a forum in which the various solutions and approaches are discussed.

They are all designed to require mathematical thought of increasing difficulty, requiring the solver to learn more powerful techniques. However, if this is done, as Olaf pointed out, even some of the more advanced problems are soluble with pen and paper. You don't have to be a programming geek to do them.

Regards

T

 

[kwbMitel]

Olaf - Curious, as to your simple formula. That formula I worked out myself way back. It is simple and I use it quite a lot but I've never come across anyone else who knew of it or understood its application.

Without looking at your answer, I used your analytical approach step for step for my own method. The programming method where you just get a computer to add it all up does not interest me. Where's the fun in that?

My method resulted in a single formula that you've provided piece by piece. Simple and equally functional. Meets the requirements of my signature.

*******************************************************
Occam's Razor - All things being equal, the simplest solution is the right one.

 

[Olaf Doschke]

kwbMitel,

well, there's the anecdote Carl Friedrich Gauß once found the formula to sum all numbers from 1 to 100, which was a task the teacher assigned to the class to keep them busy for some time.

Besides that there is a whole area of computational mathematics, which in much more complex computations can solve problems, simulate and model things etc.

http://en.wikipedia.org/wiki/Computational_mathematics

Bye, Olaf.

 

[Olaf Doschke]

By the way my solution is wrong as I included the upper limit, but the problem asked for the sum of all the multiples of 3 or 5 below 1000, so the last number to consider is 999 and not 1000.

Bye, Olaf.

 

[kwbMitel]

I made the same error and included 1000. Nice to have company for a change.

As for the computational mathematics, I usually figure these things out on my own, sometimes in unconventional ways. It's nice to see when my way matches a conventional way but I don't typically know where to start looking to see if they match.

E.g. A teacher once suggested I memorize all the perfect squares up to 25[sup]2[/sup]. I am not good at memorization so I instead found a quick way to calculate the difference of squares from 1 I know to 1 I don't. I know 20[sup]2[/sup] but not 23[sup]2[/sup]. Add 20+23 and multiply by 3 to get 129. add 129 to 400 and get 529. 23[sup]2[/sup] = 529. Take the root of the square you know, add the root of the square you don't and multiply by the difference. If there is a "Standard" application of this rule I don't know it, but it sure works for me. It even works for fractions.

*******************************************************
Occam's Razor - All things being equal, the simplest solution is the right one.

 

[Olaf Doschke]

Well, that's simply binomials: (a+b)(a-b) = a^2-b^2, so a^2 = (a+b)(a-b)+b^2 and for a=23 and b=20 you know b^2=20^2 is 400, so you only need to compute (a+b)(a-b), which is (23+20)*3. Of course you choose some nearby known square.

And yes, this works with fractions too, of course, the binomial is not limited to integers.

Bye, Olaf.

 

[kwbMitel]

Well, I would say my interest is so-so. Out of the first 20, I can solve 4 or 5 without a computer. Of the remaining, most require no strategy for simplification but are instead simply number crunching problems. My interest lies towards problems that require some sideways thinking to solve or some method of simplification to eliminate possibilities.

Problem 8 intrigues me because I simply glanced at the puzzle and I think I discovered the answer. Problem 11 not so much but under a minute of simply looking my confidence is high that I know the answer.

*******************************************************
Occam's Razor - All things being equal, the simplest solution is the right one.

 

[Olaf Doschke]

how about teaming up to tackle some of the project Euler problems?

Well, I registered to Project Euler and until now solved #1-#7 and #10, of which #7 was a side result.

It's true that there are other puzzles more interesting than many of these number crunching problems, still you can find more or less elegant algorithms and so yes, I'd join you in your effort, Thargy.

Do you have one problem in mind, where you would like to team up?

From the latest problems what I see is problem 295 was solved the least times. Looks like a good candidate to me.

Bye, Olaf.

 

[CajunCenturion]

I'll help too, if you'd like.

--------------
Good Luck
To get the most from your Tek-Tips experience, please read
FAQ181-2886
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein

 

[IPGuru]

Remarkably easy in Python

[hidden]
threes=range (0,1000,3)
total = sum(threes)
for fives in range (0,1000,5):
if five not in threes:
total+=fives
print total
return 0
[/hidden]

 

[Thargy]

Olaf,

that'w weird, as I had an eye on that one too.

I looked at the beastie, and thought about developing algorithms for determining lenticular holes. Right now, I have no idea where to start.

Can anyone start the ball rolling?

Regards

T

 

[joel76]

In SWI-Prolog :

euler_1(N) :-
	N1 is N - 1,
	numlist(1,N1, L1),
	include(select, L1, L2),
	sumlist(L2, S),
	format('Sum of multiples of 3 and 5 below ~w : ~w~n', [N, S]).

select(N) :-
	(0 =:= N mod 3; 0 =:= N mod 5).

 

[Thargy]

Cajun, Olaf,

my first thoughts on the lenticular holes.

For a circle to be a candidate for a lenticular hole, there must exist two pairs of integers, all of which are different, and less than or equal to the radius, the sum of whose squares = radius.

If this is not the case, then the radius will never intersect two lattice points, and the circle can therefore never be part of a lenticular hole.

The numbers must be different, otherwise the points are duplicates.

W.R.T. the Euler diagram, the radius 5 circle has two such pairs, i.e. (5,0) and (3,4).
0[sup]2[/sup] + 5[sup]2[/sup] = 25
3[sup]2[/sup] + 4[sup]2[/sup] = 25

The root 65 circle also has two such pairs, i.e.

4[sup]2[/sup] + 7[sup]2[/sup] = 65
1[sup]2[/sup] + 8[sup]2[/sup] = 65

I am currently thinking that the number of combinations of 4 integers from 11 (N.B. the range 0-10 has eleven digits) is 11 x 10 x 9 x 8 = 7,920 possible combinations. I haven't yet thought of a way to whittle these down to only those whose squares match the squares of a different two integers. Any ideas, or should I just do a brute-force check on the 7,920 combinations?

I believe that lenticular holes will only occur between circles whose pairs of points differ by the same amount, but have yet to demonstrate this to my own satisfaction. Any thoughts?

Regards

T

 

[CajunCenturion]

Good thoughts and ideas. Need to think on them a bit, but at first glance, looks possible.
I started a thread specifically for lenticular circles.


--------------
Good Luck
To get the most from your Tek-Tips experience, please read
FAQ181-2886
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein

 

[Olaf Doschke]

Nice thoughts, Thargy

I'll join you in the other thread.

Bye, Olaf.