# Project Euler

Mick Collins mickclns at mac.com
Thu Feb 25 14:13:18 CST 2010

```First, thanks, Andre for starting the thread and turning us / me onto the Euler Project.

I enjoy implementing algorithms, but math is fun, too!
Since Euler was a mathematician, how about a more mathematical approach.

I haven't seen these approaches yet in my quick scan of  the posts, so I will put them out there:

For the first problem
*********** mathematical note
The number of natural numbers below X that are divisible by 3 or 5 is:
the number divisible by 3, plus the number divisible by 5, minus the number divisible by 15 (since these number have already been counted twice).
For combining in a more general fashion, i.e. other than 3 and 5, rather than using the multiple you would use the Least Common Multiple (not implemented here).  For instance, if you wanted the number divisible by 6 or 4, you would use numdiv(4) + numdiv(6) - numdiv(12), since if you used numdiv(24) you would miss subtracting off many numbers divisible by both 4 and 6 but not by 24 (12*1, 12*3, 12*5 ...)

Here is a testing routine, followed by a generalization of the problem (no error correction).  For the testing routine, as soon as you are satisfied that it works as advertised, hold the shift key to jump out of the loop.  Then it will display the results of divisibility by 3 or 5.

on doTest
repeat until the shiftkey is down
put it into X
put it into N
answer "<= or plain <" with "Eq" or "NoEq"
put it into EorNo
put numOfNumsBelowXandDivisByN(X,N,EorNo) into theResult
if EorNo is "NoEq" then
put "Number < [[X]] and divisible by [[N]] is [[theResult]]." into mergeStr
else
put "Number <= [[X]] and divisible by [[N]] is [[theResult]]." into mergeStr
end if
end repeat

put 1000 into X
put "NoEq" into EorNo
put 3 into N
put numOfNumsBelowXandDivisByN(X,N,EorNo) into theResult3
put 5 into N
put numOfNumsBelowXandDivisByN(X,N,EorNo) into theResult5
put 15 into N
put numOfNumsBelowXandDivisByN(X,N,EorNo) into theResult15
put "Number < [[X]] and divisible by 3 or 5 is " & \
"[[theResult3 + theResult5 - theResult15]]." into mergeStr
end doTest

function numOfNumsBelowXandDivisByN X,N, EqOrNoEq
put X into X_
put X_ mod N into XmodN
-- X div N will be the number returned EXCEPT ...
if EqOrNoEq = "NoEq" and XmodN = 0 then   -- X divisible by N and it matters
subtract 1 from X_   end if
return X_ div N
end numOfNumsBelowXandDivisByN

For the second problem
******************
The even Fibonacci numbers form a Fibonacci-like sequence
E(1) = 0, E(2) = 2, for n>2: E(n) = 4E(n-1) + E(2)
0, 2, 8, 34, 144, 610, 2584, etc.
Also, the sums of the even Fibs form a slightly less Fibonacci-like sequence
S(1) = 0, S(2)=2, S(3) = 10,  for n>3: S(n) = 5*S(n-1) - 3*S(n-2) - S(n-3)
0, 2, 10, 44, 188, 798, 3382, etc.

There may be an even more direct approach to one or both of these sequences
(I don't know if there is), such as with the plain vanilla (no offense intended) Fibonacci sequence.
The i-th member of the sequence is:
(g^i-(-1/g)^i) / rt5 where rt5 is the square root of 5 and g is the golden ratio: (  (1+rt5)/2  ).
So that sequence can be calculated explicitly (rather than recursively).

In the testing routine, I start by displaying the explicit calculation of the first
8 members of the Fibonacci sequence

Then the recursive method of the even Fibs, keeping track of the sums.
Then the recursive method of the sums, only using the even Fibs, by calculation
to test whether to stop.

on doTest
put sqrt(5) into rt5
put (1+rt5)/2 into g
repeat with i = 1 to 8
put (g^i-(-1/g)^i) / rt5 into theF
end repeat

-- even Fibs sums by first method

put 2 into F1
put 8 into F2
put 10 into theSum
repeat while F2 <= 4000000
put 4*F2 + F1 into newFib
put F2 into F1
put newFib into F2
end repeat
answer "Fib" && F1 & ",   Sum" && theSum

put 0 into S1
put 2 into S2
put 10 into S3
repeat while S3 - S2 <= 4000000
put 5*S3 - 3*S2 - S1 into newFib
put S2 into S1
put S3 into S2
put newFib into S3
end repeat
end doTest

I'd welcome any comments on these.

>Date: Tue, 23 Feb 2010 13:28:37 -0300
>From: Andre Garzia <andre at andregarzia.com>
>Subject: Project Euler
>To: How to use Revolution <use-revolution at lists.runrev.com>
>Message-ID:
>	<7c87a2a11002230828ia2f0ff1s399ab3ae1b2d0c01 at mail.gmail.com>
>Content-Type: text/plain; charset=ISO-8859-1
>
>Hi There Folks,
>
>I don't know if you guys are familiar with http://www.projecteuler.net which
>is officially a very fun project according to my own concepts of fun. It is
>a repository of mathematical problems which require more than simple math to
>solve, it usually require some programming. You can go solving your problems
>and getting scores. I just solved the first one in Rev.
>
>"Add all the natural numbers below one thousand that are multiples of 3 or
>5."
>
>Now, the second one is giving me trouble... rsrsrsrs
>
>"Find the sum of all the even-valued terms in the Fibonacci sequence which
>do not exceed four million."
>
>I think I am going to reach the upper limits of rev math with it.
>
>:D
>
>--
>http://www.andregarzia.com All We Do Is Code.
>
>
>

```