The danish composer Per Nørgaard (1932-2025) invented a serial composition method based on a sequence of integers called the “Infinity Series”. The series is most famously used in the symphony “Voyage into the Golden Screen”.

Mathematically speaking, the series is actually a sequence, and is simple to define, e.g. by

a_0 = 0 \\
a_{2n} = -a_n \\
a_{2n + 1} = a_n + 1

There are many nice articles online explaining the properties of the sequence and many ways to derive it, so we won’t go into that here. Instead we will present a way to compute the sequence iteratively based on the following equivalent formula:

a_0 = 0 \\
a_{k} = (-1)^{\nu_2(k)} (\nu_2(k) + 1 - a_{k-1})

Here, \nu_2(k) is the 2-adic valuation of k which can be computed efficiently using a count trailing zeros (CTZ) function (e.g. trailing_zeros in Rust). This gives a way to compute the sequence as an iterator.

The correctness can be proven as follows. Write k = 2^v m with m odd and v = \nu_2(k). Applying a_{2n} = -a_n a total of v times peels off the trailing zeros, giving a_k = (-1)^v a_m. Since m is odd, m-1 is even and \nu_2(m-1) = 0. Writing m = 2t+1 we have a_m = a_{2t+1} = a_t + 1 and a_{m-1} = a_{2t} = -a_t, so a_m = 1 - a_{m-1}. Now k-1 = 2^v m - 1 consists of v trailing ones followed by the bits of m-1. Peeling off those v ones via a_{2n+1} = a_n+1 gives a_{k-1} = a_{m-1} + v, hence a_{m-1} = a_{k-1} - v. Combining,

a_k = (-1)^v a_m \\= (-1)^v(1 - a_{m-1}) \\= (-1)^v(1 - (a_{k-1}-v)) \\= (-1)^v(v + 1 - a_{k-1})

as desired.

In Rust, and implementation would look something like this:

pub struct NørgårdsInfinitySequence {
    previous: i64,
    index: u64,
}

impl NørgårdsInfinitySequence {
    pub fn new() -> Self {
        NørgårdsInfinitySequence {
            previous: 0,
            index: 0,
        }
    }
}

impl Iterator for NørgårdsInfinitySequence {
    type Item = i64;

    fn next(&mut self) -> Option<Self::Item> {
        if self.index > 0 {
            let v = self.index.trailing_zeros() as i64;
            self.previous = v + 1 - self.previous;
            if v.is_odd() {
                self.previous = -self.previous;
            }
        }
        self.index += 1;
        Some(self.previous)
    }
}