The binomial coefficients $^nC_k$ can be arranged in triangular form, Pascal's triangle, like this:
| 1 | ||||||||||||||
| 1 | 1 | |||||||||||||
| 1 | 2 | 1 | ||||||||||||
| 1 | 3 | 3 | 1 | |||||||||||
| 1 | 4 | 6 | 4 | 1 | ||||||||||
| 1 | 5 | 10 | 10 | 5 | 1 | |||||||||
| 1 | 6 | 15 | 20 | 15 | 6 | 1 | ||||||||
| 1 | 7 | 21 | 35 | 35 | 21 | 7 | 1 | |||||||
It can be seen that the first eight rows of Pascal's triangle contain twelve distinct numbers: $1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21$ and $35$.
A positive integer $n$ is called squarefree if no square of a prime divides $n$. Of the twelve distinct numbers in the first eight rows of Pascal's triangle, all except $4$ and $20$ are squarefree. The sum of the distinct squarefree numbers in the first eight rows is $105$.
Find the sum of the distinct squarefree numbers in the first $51$ rows of Pascal's triangle.
In [1]:
open Euler
let p203() =
let n = 50L
let sqrFree (n:int64) = Math.FactorInteger n |> Seq.forall (fun (n,p) -> p=1)
set [ for row in 0L..n do
for i in 0L..row ->
(Math.Binomial(row, i)) ]
|> Set.filter sqrFree
|> Seq.sum
Euler.Timer(p203)
Out[1]:
A Hamming number is a positive number which has no prime factor larger than $5$. So the first few Hamming numbers are $1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15$. There are $1105$ Hamming numbers not exceeding $10^8$.
We will call a positive number a generalised Hamming number of type $n$, if it has no prime factor larger than $n$. Hence the Hamming numbers are the generalised Hamming numbers of type $5$.
How many generalised Hamming numbers of type $100$ are there which don't exceed $10^9$?
In [1]:
open Euler
let p204() =
let m = 9.0
let primes = Math.Primes32 |> Seq.takeWhile (fun n -> n < 100)
let pl = [for p in primes -> log10 (float p)]
let rec loop pos limit =
if pos = 0 then int(limit/pl.[0])+1
else
let v = pl.[pos]
let s = ref 0
let nextLimit = ref limit
while !nextLimit > 0.0 do
s := !s + loop (pos - 1) !nextLimit
nextLimit := !nextLimit - v
!s
loop (pl.Length-1) m
Euler.Timer(p204)
Out[1]:
In [ ]: