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.
repeat until the shiftkey is down
ask "X" with 1000
put it into X
ask "N" with 3
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
put "Number <= [[X]] and divisible by [[N]] is [[theResult]]." into mergeStr
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
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
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.
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
-- even Fibs sums by first method
answer "First Method"
put 2 into F1
put 8 into F2
put 10 into theSum
repeat while F2 <= 4000000
put 4*F2 + F1 into newFib
add newFib to theSum
put F2 into F1
put newFib into F2
answer "Fib" && F1 & ", Sum" && theSum
answer "Second Method"
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
answer "Sum" && S3
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>
> <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
>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.
>http://www.andregarzia.com All We Do Is Code.
More information about the use-livecode