Project Euler

[Mick Collins]

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
      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
      else 
         put "Number <= [[X]] and divisible by [[N]] is [[theResult]]." into mergeStr
      end if
      answer merge(mergeStr)
   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
   answer merge(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
      answer theF
   end repeat
   
   -- 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
   end repeat
   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
   end repeat
   answer    "Sum" && S3
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.
>
>
>