skip to content
Wo

Cool number sequence #0: Congruent numbers

math , plot

This is a series where I talk about cool number sequences that I found and expound on them

Congruent numbers

Some time ago whilst researching for my Master thesis1, I stumbled upon a pretty cool number sequence, which goes

with . Do you notice what is the pattern of the sequence shown in eqn () above? If yes, congratulations! You are adept at noticing patterns! If not, that’s also fine, we shall go through this together.

The pattern of the sequence is that it is just the usual non-negative integer sequence, but every other 4 numbers are skipped! Now, if you’re like me, you’re probably wondering

How does one even write a formula for generating such a sequence?

Well, fret not, turns out this sequence is already on the Online Encyclopedia of Integer Sequences (OEIS) and it’s sequence number A0474542, albeit offset by 1. One of the formulas given on the page is (adjusted to start from 0)

where . We can perform a sanity check of eqn () in Python with the following

f = lambda n: (-3+(-1)**n+1j*(-((-1+1j)*(-1j)**n)-1j**n*(1+1j))+4*n)/2
[f(n) for n in range(10)]
# Outputs [0j, (1+0j), (2+0j), (3+0j), (8+0j), (9+0j), (10+0j), (11+0j), (16+0j), (17+0j)]

This sequence is formally known as numbers that are congruent to .

However, I am still not quite satiated by this form because of two reasons: (1) it uses the imaginary number to produce purely real results and (2) I couldn’t find a way to generalise the form to give numbers that are congruent to , which as far as I know, is a generalised sequence that is not documented anywhere.

Generalised formula

Then, while browsing OEIS unsuspectingly, I stumbled upon the sequence A0429483, which happened to contain the following formula for generating numbers that are congruent to

After fiddling around with eqn () in Wolfram Mathematica, I found out that by performing a rudimentary modification that I’d achieve what I want

Thus, with eqn (), I have obtained my holy grail for “Cool number sequence #0”. Now, you might be wondering,

Hmm, is this useful in any practical applications?

This is a question that I’d like you to ponder about. But if you’re impatient, then here is my answer: yes. One application that I found with this, without going too much into details, is performing highly efficient symmetric matrix operations (maybe I’ll talk about this in a future blog in more detail). The prospects of other potential applications that have yet to be discovered/documented is exciting nonetheless.

Low-level implementation

Below is a low-level implementation in C/C++ for the curious. You can easily translate this to other languages such as Python and JavaScript since most languages use the same symbol for bit operators.

// In binary algebra, you can rewrite `n mod 2^k` as `n & ((1<<k)-1)`
// where `&` is the `bit and` operator
// and `<<` is the `bit left shift` operator
int congMod(int n, int k) {
    return 2*n - (n & ((1 << k) - 1));
}

Interactive plot

The first 2001 values of the sequence in eqn () is plotted below, where . You can use the slider below to adjust the value of to see how the sequence changes.

Footnotes

  1. https://repository.tudelft.nl/islandora/object/uuid:649f5fe9-0266-4be2-a3a5-4b5ffd13073e ↩

  2. https://oeis.org/A047454 ↩

  3. https://oeis.org/A042948 ↩