Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Project Euler #01 on HackerRank, Performance issue?
(Arjun Comar)
2. Re: Project Euler #01 on HackerRank, Performance issue?
(Jean Lopes)
3. Re: GPIO/I2C/PWM and Haskell (Chadda? Fouch?)
4. Re: Project Euler #01 on HackerRank, Performance issue?
(Chadda? Fouch?)
5. Re: Project Euler #01 on HackerRank, Performance issue?
(Arjun Comar)
----------------------------------------------------------------------
Message: 1
Date: Wed, 28 Jan 2015 09:56:14 -0500
From: Arjun Comar <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Project Euler #01 on HackerRank,
Performance issue?
Message-ID:
<CADjRcrX5y5J4G1_yG0Tx=hgzre45-upbs8xuq1m8d-fau_j...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Jean,
This is going to be a bit tough over email, but here goes.
The main trick here is to realize that you can write the multiples of k as
k*i and sum from 1 to floor(n/k) to get the sum of the multiples of k from
1 to n. For example, the sum of the multiples of 3 can be written as:
sum(3*i, 1, n / 3)
Because of distributivity, we can pull the 3 out of the sum and get
3 * sum(i, 1, n / 3)
which is pretty cool because now we have a sum from 1 to n/3. We can now
apply the formula that gives us the sum of numbers from 1 to m:
m * (m + 1) / 2
and substitute m = n / 3. This gives us:
3 * n / 3 * [(n / 3) + 1] / 2
More generally, we can write the sum of the multiples of k as:
k * n / k * [(n/k) + 1] / 2
and simplify to:
n/2 * [(n/k) + 1]
Now you can write out the 3 sums in this form and simplify to an analytic
answer for a closed form answer to the problem:
n/2 * [(n / 3) + 1] + n/2 * [(n/5) + 1] - n/2 * [(n/15) + 1]
Factor out the n/2:
n/2 * [(n/3) + (n/5) - (n/15) + (1 + 1 - 1)]
We can now give a common base to the n/k fractions and simplify:
n/2 * [ 5n/15 + 3n/15 - n/15 + 1] = n/2 * [7n/15 + 1]
Which is the closed form solution you were hoping for.
All that said, don't trust my math and work it out by hand for yourself. I
likely made some mistakes through this procedure :).
Thanks,
Arjun
On Wed, Jan 28, 2015 at 6:12 AM, Frerich Raabe <[email protected]> wrote:
> On 2015-01-28 00:57, Jean Lopes wrote:
>
>> I'm not really good at math, maybe I am missing something obvious ?
>> Maybe some pointers as of where to start studying math in order to avoid
>> this brute force attempts, at least to help in this particular
>> problem
>>
>
> I'm not too familiar with 'Project Euler', but summing all multiples of 3
> and 5 below some given 'n' made me think: e.g. 16 it
> would be...
>
> 3 + 5 + 6 + 9 + 10 + 12 + 15
> = 3 + 6 + 9 + 12 + 15 + 5 + 10 | reordered summands
> = 3 + 6 + 9 + 12 + 15 + 5 + 10 + 15 - 15 | +15-15 appended to
> prepare factoring out
> = 3 + 6 + 9 + 12 + 15 + 5 + 10 + 15 - 15 | whitespace for
> readability
> = 3 * (1+2+3+4+5) + 5 * (1+2+3) - 15 * (1) | factoring out
>
> Now I remembered a trick to get the sum of the first N numbers (I only
> remember it's called "der kleine Gau?" in german):
>
> 1 + 2 + ... + n = (n^2 + n) / 2
>
> Maybe that'll help.
>
> - Frerich
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20150128/abddfaa6/attachment-0001.html>
------------------------------
Message: 2
Date: Wed, 28 Jan 2015 13:14:15 -0300
From: Jean Lopes <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Project Euler #01 on HackerRank,
Performance issue?
Message-ID:
<CAKeoKsiPmsXFo0dxvNo3enNxr+qhUS5dnV=scbs2-f6_2ox...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
I got it now, thanks everyone.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20150128/d070f3cd/attachment-0001.html>
------------------------------
Message: 3
Date: Wed, 28 Jan 2015 21:39:23 +0100
From: Chadda? Fouch? <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] GPIO/I2C/PWM and Haskell
Message-ID:
<canfjzrzb69xqttzszf_ul2oxjyjttefbn8heqmnb9c2j1gv...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Tue, Jan 27, 2015 at 5:02 PM, Michael Jones <[email protected]> wrote:
> Michal,
>
> I am doing similar things (not arial) on a MinnowBoardMax. Did not want to
> deal with ARM and Haskell. But if you make that work, I think it would be
> worth publishing how you did it. I struggled to build a cross compiler for
> ARM and gave up.
>
> As for MinnowBoardMax, I am running Ubuntu with a 3.18.1 kernel and a
> solid state drive. A little heavy on the weight when you consider the
> batteries required to run a 5W system.
>
> I have libraries for I2C, UART, and GPIO, but not published.
>
> Here is an example of how I deal with ALERTB
>
> module SMBusAlert (
> alert
> ) where
>
> import System.IO
>
> alert :: IO Bool
> alert = do
> writeFile "/sys/class/gpio/export" "340"
> writeFile "/sys/class/gpio/gpio340/direction" "in"
> s <- readFile "/sys/class/gpio/gpio340/value"
> s `seq` writeFile "/sys/class/gpio/unexport" "340"
> if s!!0 == '0' then return True else return False
>
>
While I do not understand much about what you're doing, I would suggest
instead :
alert :: IO Bool
alert = do
writeGpio "export" "340"
writeGpio "gpio340/direction" "in"
c <- withFile "/sys/class/gpio/gpio340/value" ReadMode getChar
writeGpio "unexport" "340"
return (c == '0')
where
writeGpio p = writeFile ("/sys/class/gpio/" ++ p)
and maybe writeGpio (or a general gpio transformer) should be part of an
utility library since those IO to related files/devices seems to form a
large part of your code.
(Also the "if blabla then return True else return False" == "return blabla"
is a common mistake)
--
Jeda?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20150128/5b551622/attachment-0001.html>
------------------------------
Message: 4
Date: Wed, 28 Jan 2015 22:04:54 +0100
From: Chadda? Fouch? <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Project Euler #01 on HackerRank,
Performance issue?
Message-ID:
<CANfjZRZxQ3zntHqqdn2Yy3z8=6gagusmdpfhrkebw5eaw3c...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Well I did it pretty dirty, not trying to simplify my solution (I'm skeptic
of "k * n/k = n" given that this "n / k" is really "floor (n / k)" ... does
this really work for you ?), this gave me :
import Control.Monad (replicateM_)
main = do
t <- readLn
replicateM_ t (readLn >>= print . pe1 . subtract 1)
pe1 n = ( (3 + m3 * 3) * m3 + (5 + m5 * 5) * m5 - (15 + m15 * 15) * m15 )
`quot` 2
where
m3 = n `quot` 3
m5 = n `quot` 5
m15 = n `quot` 15
Note that the sum of multiples of 3/5/15 can be seen as a sum of terms of
an arithmetic sequence which is always "number of terms * (first term +
last term) / 2", easily proven by the expedient of writing the sequence
twice : one in the right order and the other in reverse under it, you then
see that the sum of two term in column is always the same so ...
--
Jeda?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20150128/9821b0c1/attachment-0001.html>
------------------------------
Message: 5
Date: Wed, 28 Jan 2015 20:27:22 -0500
From: Arjun Comar <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Project Euler #01 on HackerRank,
Performance issue?
Message-ID:
<cadjrcrx8bar8ffvgrsx8tx_4cdgq4pe8jk_yuspyqj4zohj...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
That's why I warned about errors :).
Thanks for the catch.
On Wed, Jan 28, 2015 at 4:04 PM, Chadda? Fouch? <[email protected]>
wrote:
> Well I did it pretty dirty, not trying to simplify my solution (I'm
> skeptic of "k * n/k = n" given that this "n / k" is really "floor (n / k)"
> ... does this really work for you ?), this gave me :
>
> import Control.Monad (replicateM_)
>
> main = do
> t <- readLn
> replicateM_ t (readLn >>= print . pe1 . subtract 1)
>
> pe1 n = ( (3 + m3 * 3) * m3 + (5 + m5 * 5) * m5 - (15 + m15 * 15) * m15 )
> `quot` 2
> where
> m3 = n `quot` 3
> m5 = n `quot` 5
> m15 = n `quot` 15
>
>
> Note that the sum of multiples of 3/5/15 can be seen as a sum of terms of
> an arithmetic sequence which is always "number of terms * (first term +
> last term) / 2", easily proven by the expedient of writing the sequence
> twice : one in the right order and the other in reverse under it, you then
> see that the sum of two term in column is always the same so ...
>
> --
> Jeda?
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20150128/adbbbafa/attachment.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 79, Issue 37
*****************************************
