Tag Archives: number

Competitive programming in Haskell: Infinite 2D array, Level 4

Posted on February 24, 2023 by Brent

In a previous post, I challenged you to solve Infinite 2D Array using Haskell. After deriving a formula for that involves only a linear number of terms, last time we discussed how to efficiently calculate Fibonacci numbers and binomial coefficients … Continue reading →

Posted in competitive programming, haskell | Tagged , , | 3 Comments

Subtracting natural numbers: types and usability

Posted on February 7, 2023 by Brent

For several years now I have been working on a functional teaching language for discrete mathematics, called Disco. It has a strong static type system, subtyping, equirecursive algebraic types, built-in property-based testing, and mathematically-inspired syntax. If you want to know … Continue reading →

Posted in projects, teaching | Tagged , , , , | 3 Comments

Competitive programming in Haskell: Infinite 2D array, Levels 2 and 3

Posted on January 16, 2023 by Brent

In a previous post, I challenged you to solve Infinite 2D Array using Haskell. As a reminder, the problem specifies a two-parameter recurrence , given by for for for . Last time, we derived a formula for that involves only … Continue reading →

Posted in competitive programming, haskell | Tagged , , | 1 Comment

Competitive programming in Haskell: Infinite 2D array, Level 1

Posted on December 3, 2022 by Brent

In my previous post, I challenged you to solve Infinite 2D Array using Haskell. As a reminder, the problem specifies a two-parameter recurrence , given by for for for . We are given particular values of and , and asked … Continue reading →

Posted in competitive programming, haskell | Tagged , , | 2 Comments

Competitive programming in Haskell: Infinite 2D array

Posted on September 1, 2022 by Brent

If you like number theory, combinatorics, and/or optimizing Haskell code, I challenge you to solve Infinite 2D Array using Haskell. Level 1: can you come up with a general formula to compute ? Level 2: In general, how can you … Continue reading →

Posted in competitive programming, haskell | Tagged , , | 8 Comments

Competitive Programming in Haskell: modular arithmetic, part 2

Posted on March 3, 2020 by Brent

In my last post I wrote about modular exponentiation and egcd. In this post, I consider the problem of solving modular equivalences, building on code from the previous post. Solving linear congruences A linear congruence is a modular equivalence of … Continue reading →

Posted in haskell | Tagged , , , , | 4 Comments

Competitive Programming in Haskell: modular arithmetic, part 1

Posted on February 15, 2020 by Brent

Modular arithmetic comes up a lot in computer science, and so it’s no surprise that it is featured, either explicitly or implicitly, in many competitive programming problems. As a brief aside, to be good at competitive programming it’s not enough … Continue reading →

Posted in haskell | Tagged , , , , | 7 Comments

Competitive Programming in Haskell: primes and factoring

Posted on February 7, 2020 by Brent

Number theory is a topic that comes up fairly regularly in competitive programming, and it’s a very nice fit for Haskell. I’ve developed a bunch of code over the years that regularly comes in handy. None of this is particularly … Continue reading →

Posted in haskell | Tagged , , , , | 5 Comments