Posts

Microsoft Azure Notebooks - Live code - F#, R, and Python

I was exploring Jupyter notebooks, that combines live code, markdown and data, through Microsoft's implementation, known as MS Azure Notebooks, putting together a small library of R and F# notebooks.

As Microsoft's FAQ for the service describes it as : ...a multi-lingual REPL on steroids. This is a free service that provides Jupyter notebooks along with supporting packages for R, Python and F# as a service. This means you can just login and get going since no installation/setup is necessary. Typical usage includes schools/instruction, giving webinars, learning languages, sharing ideas, etc. Feel free to clone and comment...
In R Azure Workbook for R - Memoisation and Vectorization Charting Correlation Matrices in R In F# Charnownes Constant in FSharp.ipynb Project Euler - Problems 18 and 67 - FSharp using Dynamic Programming

Consecutive Prime Sum (Project Euler - Problem 50)

Problem

The prime 41, can be written as the sum of six consecutive primes:
41 = 2 + 3 + 5 + 7 + 11 + 13
This is the longest sum of consecutive primes that adds to a prime below one-hundred.
The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.
Which prime, below one-million, can be written as the sum of the most consecutive primes?
Note
Some libraries used in this code are F# modules I use, but have also published as a Nuget library, such as EulerLib.GetPrimes() and EulerLib.isPrime(). You need to reference the NuGetLibrary to use this code as is.
Solution

#load "Stat.fs" #load "Print.fs" #load "EulerLib.fs" open Stat open Print open EulerLib open System let rec FindLongestPrimeSequenceSum (primeList:list) (nextItem:int) lessThanValue (primeArray:list) bestPrime (correctArray:list) = if List.sum(primeArray) + pr…

Champernowne's Constant - Project Euler Problem 40

Problem

An irrational decimal fraction is created by concatenating the positive integers:

0.12345678910
It can be seen that the 12th digit of the fractional part is 1.

If dn represents the nth digit of the fractional part, find the value of the following expression.

d1 x d10 x d100 x d1000 x d10000 x d100000 x d1000000
Original Problem Source


Solution

//speed depends on using StringBuilder, non-idiomatic since it is mutable let rec NumArray start max maxLength (numString:System.Text.StringBuilder) = if start = max || numString.Length >= maxLength then numString.Append(start.ToString()) else let newString = numString.Append(start.ToString()) let nextNum = start + 1 NumArray nextNum max maxLength newString //cast string to int let convertStringToInt32 (value:string) = let mutable result = 0 let found = System.Int32.TryParse(value, &result) result …

Coin Sums (Project Euler Problem 31)

Problem

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation: 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p). It is possible to make £2 in the following way: 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p How many different ways can £2 be made using any number of coins?
Original problem description...

Note

This is a clean, although slow, solution, taking longer than one minute to complete.

Solution


// code for finding result, returned as a sequence let sumCurrencies ones twos fives tens twenties fifties oneHundreds twoHundreds limit = //seq{ [let counter = 0 for twoHundred in twoHundreds do for oneHundred in oneHundreds do for fifty in fifties do for twenty in twenties do for ten in tens do for five in fives do for …

Integer Right Triangles (Project Euler Problem 39)

Poblem

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p ≤ 1000, is the number of solutions maximised?

Link to original problem description

Solution

open System let buildArrays xs ys zs limits = seq{ for x in xs do for y in ys do if x < y then for z in zs do if (x*x + y*y = z*z) then for limit in limits do if (x + y + z = limit) then yield limit, x, y, z} let First (a,b,c,d) = a let pyhtosArrays = buildArrays [1..999] [1..999] [1..999] [1..999] |> Seq.toList |> List.map (fun x -> First x) let results = pyhtosArrays |> Seq.countBy id |> Se…

Digit cancelling fractions (Project Euler Problem 33)

Problem

The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s.

We shall consider fractions like, 30/50 = 3/5, to be trivial examples.

There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator. If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

(link to Problem 33 on the Project Euler site)

Note

This is a somewhat crude solution, since I am only just getting back into solving these problems, or working with F#, but there are several similar problems for which I can develop properly factored, reusable functions.

Solution

open System let product xs ys = seq{for x in xs do for y in ys do let a = float x % float 10 let b = System.Math…

Published Mathematical Librabry on NuGet

I recently published a library of mine to NuGet, as Mathematical Library. It is a library for functions used in solving Project Euler problems along with some basic statistical functions, coded in F#. The Project Euler functions cover primes, factorials, narcissism, random numbers, arrays and series/sequences (Collatz, Terra, Fibonacci).  The statistical functions cover variance, standard deviation, and sum of squares.

Greetings

For Visitors

I have not worked on this site for over two (2) years, but it covers many of the basics of F#, while trying to be idiomatically-correct and algorithmically efficient, solving mathematical problems functionally:

Functions (non-state, no side effects)Tail recursionNon-mutable variablesCurryingLambda notationPattern matchingSequences, arrays, lists, and tuplesArray slicing
Additionally, some solutions are improved upon using .NET components to speed the process, e.g., parallel processing.

Also, you might find these interesting, additional work done in F#:


Basic Statistical Functions, a very basic F# class for performing standard deviation and variance calculations.


Various Number Functions, a collection of basic mathematical functions written in F# as part of my learning via Project Euler. This module has functions for creating arrays or calculating values for the following:
PrimesFactorialsNarcissismCollatz SequenceTerra SequenceFibonnaciDistinct PrimesRandom Numbers and A…

New On-Line Script Editor

Microsoft is promoting F# via a new website, which includes an on-line script editor.


Project Euler: Problems 18 and 67

Problem 18


By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.


3
7 4
2 4 6
8 5 9 3


That is, 3 + 7 + 4 + 9 = 23.


Find the maximum total from top to bottom of the triangle below:


75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23


NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)


Solution


By extension, this solves problem 67 as well.


This uses a tail-recursive function requiring the pyramid to be flattened into an array and…

Project Euler - Problem 17 (Match-based Solution)

Problem


If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.


If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?


NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.


Note


I have done two (2) solutions for this problem. The original in a prior post requires less code, but is 'ugly' and is less reusable that this match-based solution. This solution is based on smaller methods using the match function, with larger number functions able to call and reuse code from the functions for smaller numbers.  Calling the method is much cleaner as well.


Solution (Match-Based)



let GetThousandthsLetters prefix fourth third second first = 
    match fourth with
 …

Project Euler - Problem 17

Problem


If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.


If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?


NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.


Solution


//this is a very ugly solution, which I will return to to properly factor to smaller recursive methods




let GetThousandsLetters num = 
    match num with
        | 1 -> "one thousand"
        | 2 -> "two thousand"
        | 3 -> "three thousand"
        | 4 -> "four thousand"
        | 5 -> "five thousand"
        | 6 -> "six thousand"
        | 7 -> "seven thousand"
        | 8 -> "eight th…

Project Euler - Problem 12

Description

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred (500) divisors?

Solution 

//from rosetta code site
//code for finding the distinct factors of a number
let factors number = seq {
    for divisor in 1 .. (float >> sqrt >> int) number do
    if number % divisor = 0 then
        yield divisor
        yield number / divisor
}

//verification of factor code
let factorTest = Seq.toArray(factors 28)

//basic method for calculating the triangle number oin a recursive function
let rec generateTriangleNumber (priorValue:int) …

Project Euler - Problem 28

Description


Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows: 


21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13


It can be verified that the sum of the numbers on the diagonals is 101. What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way? 


Solution 



//calculates the sum for the level of the square
//each increase in level only requires calculating 4 new values, the corners
let levelValue (start:int) (side:int) =
    let diffAtLevel = side - 1
    let sum = (start + diffAtLevel) + (start + (diffAtLevel * 2)) + (start + (diffAtLevel * 3)) + (start + (diffAtLevel * 4)) 
    sum 


//recursively iterates from level 0, which is the center
//to the outer part of the array
//and for each level calculates the additional sum and sums that to running sum
let rec sumByPowers start priorLevelSquared level endSide sum =
    if level > endSide then
        sum
    else
        let newSum =…

Project Euler - Problem 30 Redux (using Parallel)

The original post Project Euler - Problem 30 was done some time ago, and I recently read about using parallel methods to improve performance, and in this case, Parallel reduces execution time by 33%.


Description


Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits.  Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.


Solution (using Parallel)



open System
open System.Threading
open System.Threading.Tasks


let isNarcissistic num power =
    let numAsString = num.ToString()
    let arr = [for i=0 to (numAsString.Length - 1) do
                yield (float(numAsString.Chars(i).ToString()))**power]
    if num = int(List.sum arr) then
        num
    else
        0


let GetAllNarcissistic2_Start = System.DateTime.UtcNow


let GetAllNarcissistic2 =
    [|2..999999|]
    |> Array.Parallel.map (fun x -> isNarcissistic x 5.0)
    |> Array.sum


printfn "%f" ((System.DateTime.UtcNow).Subtract(GetAllNarcissi…