Description

Consider a sequence u where u is defined as follows:

  1. The number u(0) = 1 is the first one in u.
  2. For each x in u, then y = 2 * x + 1 and z = 3 * x + 1 must be in u too.
  3. There are no other numbers in u.

Ex: u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]

1 gives 3 and 4, then 3 gives 7 and 10, 4 gives 9 and 13, then 7 gives 15 and 22 and so on…

Task

Given parameter n the function dbl_linear (or dblLinear…) returns the element u(n) of the ordered (with <) sequence u (so, there are no duplicates).

Example

dbl_linear(10) should return 22

Note

Focus attention on efficiency

Solutions

R

library(tidyverse)

dblLinear <- function(n) {
    u <- 1
    i <- 1
    j <- 1
    while (length(u) < n + 1) {
        y <- 2 * u[i] + 1
        z <- 3 * u[j] + 1
        if (y < z) {
            u[length(u) + 1] <- y
            i <- i + 1
        } else if (y > z) {
            u[length(u) + 1] <- z
            j <- j + 1
        } else {
            u[length(u) + 1] <- y
            i <- i + 1
            j <- j + 1
        }
    }
    u[n + 1]
}


library(testthat)
testing <- function(n, expected) {
    actual <- dblLinear(n)
    expect_equal(actual, expected)
}
test_that("tests", {
    testing(10, 22)
    testing(20, 57)
    testing(50, 175)
})
#> Test passed 🥳

JavaScript

function dblLinear(n) {
    let u = [1], i = 0, j = 0; //two pointer
    while (u.length < n + 1) {
        let newTerm = Math.min(2 * u[i] + 1, 3 * u[j] + 1);
        u.push(newTerm)
        if (newTerm === 2 * u[i] + 1) i++;
        if (newTerm === 3 * u[j] + 1) j++;
    }
    return u[n];
}

console.log(dblLinear(10));

module.exports = dblLinear;
#> 22