Programming the Look-and-Say Sequence in Racket

Trust the natural recursion with a recursive sequence

Racket is an interesting programming language that I learned in my first year of college that I never get to use in my work. It’s a modern “dialect” of Lisp, one of the oldest programming languages. Let’s try programming the Look-and-say sequence in it.

WarningSpoiler Warning

This article contains the solution for LeetCode problem #38. If you want to try this problem on your own, you probably should do that first before looking at my solution.

(require racket/date)
(require racket/format)
(require rackunit)

A (Very Brief) Intro to Racket

Like other languages descended from Lisp, Racket’s syntax is built with s-expressions in parentheses that indicate both how the program is structured and how it should be executed. The left side of the s-expression contains the function name or operator (e.g., +, sqrt) and everything to the right of the operator are inputs or operands. Compound s-expressions also describe order, as they evaluated from the inside out like parentheses in mathematics.¹

Here are some examples of Racket code.

;; Calculate `1 + 2`
(+ 1 2)

3

;; Calculate `sqrt(1 + 2 * 3)`
(sqrt (+ 1 (* 2 3)))

2.6457513110645907

Since Racket is a functional programming language, functions themselves can be inputs to other functions.²

;; Quadratic Formula function
(define (quadratic-formula a b c)
  ;; Solves the quadratic equation `ax^2 + bx + c = 0` and returns its 2 roots
  ;; as a list of numbers.
  (map (lambda (op)
         (/ (op ; this acts as `±` since `+` and `-` are passed through `map`
             (- b)
             (sqrt (- (expt b 2) (* 4 a c))))
            (* 2 a)))
       (list + -)))

;; Using the above function, solve `x^2 - 10x + 16 = 0` for x
(quadratic-formula 1 -10 16)

'(8 2)

Look-and-Say Sequence

The Look-and-say Sequence is a sequence of numbers starting from 1 that obeys the following rule: to generate the next number in the sequence, we look at the previous number and describe it by splitting it into groups of the same digit and reading off each group’s count and digit type. Here are some of the first numbers of the Look-and-say sequence, \(\mathrm{LAS}_n\), and how they are used to generate the next number in the sequence:

\(n\)	\(\mathrm{LAS}_{n}\)	Description of \(\mathrm{LAS}_{n}\)	\(\mathrm{LAS}_{n+1}\)
1	1	one one	11
2	11	two ones	21
3	21	one two, one one	1211
4	1211	one one, one two, two ones	111221
5	111221	three ones, two twos, one one	312211
6	312211	one three, one one, two twos, two ones	13112221

The Look-and-say sequence is recursive: finding \(\mathrm{LAS}_{n}\) is dependent on finding \(\mathrm{LAS}_{n-1}\), which in turn is dependent on \(\mathrm{LAS}_{n-2}\) and so on. But finding \(\mathrm{LAS}_{1}\) is the base case of this recursive sequence, as it’s equal to 1 by definition.³ From this, we can get a sense of how we want to implement the Look-and-say sequence in Racket.

Implementing the Look-And-Say Sequence in Racket

How would I go about building a function (look-and-say n) in Racket that returns the \(n\)th element of the Look-and-Say sequence \(\mathrm{LAS}_{n}\)? We need to build a recursive function in Racket that acts in one of two ways: return the output “1” when \(n = 1\) in the base case; otherwise, return a modified output of \(\mathrm{LAS}_{n-1}\) that gets built sequentially through the recursive case.

Let’s first write a function in Racket that converts \(\mathrm{LAS}_{n}\) to \(\mathrm{LAS}_{n-1}\) and call it look-and-say-str. Instead of representing a number in the Look-and-say sequence \(\mathrm{LAS}_{n}\) as an integer, let’s represent it as a string (i.e., a list of characters), which will make parsing it easier. As we traverse through the list of characters in the string, let’s count how many of the same digit we saw. When we see a change of digits in the sequence, we’ll append the number of digits we previously saw to a new string and restart counting.

graph TD
  accTitle: Generation of 1113213211 from 13112221 in the Look-and-Say Sequence.
  accDescr: Top-down diagram. Box 13112221 at the top points downward to 5 boxes labeled "1", "3", "11", "222", and "1" respectively. These five boxes each point downard with arrows reading "one one", "one three", "two ones", "three twos", and "one one" respectively to boxes labeled "11", "13", "21", "32", and "11", respectively. The last five boxes all point to a box labeled "1113213211".
  LAS7[13112221] --> LAS71[1]
  LAS7[13112221] --> LAS72[3]
  LAS7[13112221] --> LAS73[11]
  LAS7[13112221] --> LAS74[222]
  LAS7[13112221] --> LAS75[1]

  LAS71 -- "one one" --> LAS81[11]
  LAS72 -- "one three" --> LAS82[13]
  LAS73 -- "two ones" --> LAS83[21]
  LAS74 -- "three twos" --> LAS84[32]
  LAS75 -- "one one" --> LAS85[11]

  LAS81 --> LAS8[1113213211]
  LAS82 --> LAS8
  LAS83 --> LAS8
  LAS84 --> LAS8
  LAS85 --> LAS8

Racket’s s-expression syntax for for-loops is different from other more common programming languages like Python, so instead our best bet to build this look-and-say-str is to use recursion again. We’ll perform this function on the entire input string in the beginning and recursively call look-and-say-str to peel off the characters in the string one-by-one until we get to our base case at the last digit. To keep track of the current group’s digit count, we’ll pass through an accumulator as input to the function as well called current-group-count that contains the number of digits before the current string equal to the string’s first digit.

To recap, this is what we want our look-and-say-str function to do for a given string:

• If the string only contains 1 digit, return both the count of the current group and the digit type.
• If the string’s first & second digits are the same, add 1 to the current group count & return look-and-say-str on the substring starting from the second character.
• If the string’s first & second digits are different, return the current group count and append the result to look-and-say-str applied on the substring starting from the second character.

Alright, let’s make that in Racket. I’m going to split the functions of finding the first character, second character, and “rest” of a string as helper functions so that the end result looks cleaner. Let’s also run some unit tests to make sure look-and-say-str is working as intended.

(define (string-first a-str)
  ;; Returns the first character of `str` as a string.
  (substring a-str 0 1))

(define (string-second str)
  ;; Returns the second character of `str` as a string.
  (substring str 1 2))

(define (string-rest str)
  ;; Returns the substring of `str` starting from the second character.
  (substring str 1))

(define (look-and-say-str str current-group-count)
  ;; Returns the Look-And-Say string of `str`, where `current-group-count` is
  ;; how many numbers before the current string have the same digit as the
  ;; first digit of `str`.
  (cond
    [(eq? 1 (string-length str))
     (string-append (~a (+ 1 current-group-count)) str)]
    [(equal? (string-first str) (string-second str))
     (look-and-say-str (string-rest str) (+ current-group-count 1))]
    [else
     (string-append (~a (+ 1 current-group-count))
                    (string-first str)
                    (look-and-say-str (string-rest str) 0))]))

For the Look-and-say sequence function itself, we build the recursive function that implements the base case for \(n = 1\) and the iterative case of sequentially applying look-and-say-str to the base case until we get the desired output.

(define (look-and-say n)
  ;; Returns the nth element of the Look-and-say sequence as a string.
  (if (eq? n 1) "1" (look-and-say-str (look-and-say (- n 1)) 0)))

To make sure everything is working properly, I’ve written a couple of unit tests using Racket’s built-in testing library rackunit.

;; Test Single Digit Case
(check-equal? (look-and-say-str "1" 0) "11")
(check-equal? (look-and-say-str "1" 1) "21") ; base case for the string "11"
(check-equal? (look-and-say-str "1" 2) "31") ; base case for the string "111"

;; Test Same 2-Digit Case
(check-equal? (look-and-say-str "11" 0) "21")
(check-equal? (look-and-say-str "11" 1) "31") ; base case for the string "111"
(check-equal? (look-and-say-str "11" 2) "41") ; base case for the string "1111"

;; Test Different 2-Digit Case
(check-equal? (look-and-say-str "12" 0) "1112")
(check-equal? (look-and-say-str "12" 1) "2112") ; second-to-last call for "112"
(check-equal? (look-and-say-str "12" 2) "3112") ; second-to-last call for "1112"
(check-equal? (look-and-say-str "21" 0) "1211")
(check-equal? (look-and-say-str "21" 1) "2211") ; second-to-last call for "221"
(check-equal? (look-and-say-str "21" 2) "3211") ; second-to-last call for "2221"

;; Check Look-and-say function
(check-equal? (look-and-say 1) "1")
(check-equal? (look-and-say 2) "11")
(check-equal? (look-and-say 3) "21")
(check-equal? (look-and-say 4) "1211")
(check-equal? (look-and-say 5) "111221")
(check-equal? (look-and-say 6) "312211")

Everything’s working properly since no errors occurred. Let’s now see what the 25th element in the Look-and-say sequence is:

;; Find LAS_25
(look-and-say 25)

"132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312111312212231131122211311123113322112111312211312111322111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312212221121123222112132113213221133112132123123112111311222112132113213221132213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121132211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321231231121113112221121321132122311211131122211211131221131211322113322112111312211322132113213221123113112221131112311311121321122112132231121113122113322113111221131221"

Wow! That’s a lot of numbers.

Conclusion

Racket, like the other functional Lisp-based and programming languages, are still able to perform everything that object-oriented code can. I like the functional programming paradigm; passing functions as inputs into other functions leads into interesting topics like lambda calculus and combinators. Recursion in and of itself was a bit hard for me to wrap my head around, but it’s a really useful tool in mathematics that can be improved in programming with memoization.

Package Versions & Last Run Date

(println (~a "Racket Version " (version)))
(println (~a "Last Run " (date->string (seconds->date (current-seconds) #f))))

"Racket Version 8.16"
"Last Run Saturday, October 4th, 2025"

References

Conway, John Horton. “A005150: Look and Say Sequence: Describe the Previous Term! (Method A - Initial Term Is 1).” The On-Line Encyclopedia of Integer Sequences. OEIS Foundation, Inc., n.d. https://oeis.org/A005150.

Felleisen, Matthias, Robert Bruce Findler, Matthew Flatt, and Shriram Krishnamurthi. How to Design Programs. 2nd ed. Cambridge, Massachusetts: The MIT Press, 2018. https://htdp.org/.

Footnotes

1. Felleisen et al., How to Design Programs.

2. Felleisen et al.

3. Conway, John Horton, “OEIS A005150”.