Math::N...Diatomic(3)

💖 Math::NumSeq::SternDiatomic 💖

okay bestie, buckle up, this is a page from the User Contributed Perl Documentation for Math::N...Diatomic(3), and it's literally about Stern's diatomic sequence, which sounds fake but is real and gorgeous 🦋

---

✨ NAME ✨

Math::NumSeq::SternDiatomic — Stern's diatomic sequence, no cap 👑

---

🌸 SYNOPSIS 🌸

use Math::NumSeq::SternDiatomic;
my $seq = Math::NumSeq::SternDiatomic->new;
my ($i, $value) = $seq->next;

like, that's it, that's the whole vibe, you make one and then you just get values from it 💅

---

🎀 DESCRIPTION 🎀

This is Moritz Stern's diatomic sequence, and she is iconic:

0, 1, 1, 2, 1, 3, 2, 3, ...
starting i=0

She gets built up level by level with a recurrence:

D(0)     = 0
D(1)     = 1
D(2*i)   = D(i)
D(2*i+1) = D(i) + D(i+1)

So basically the sequence grows by copying the previous level and spreading it out onto the even indices, then filling in the odd indices with the sum of the adjacent terms. it's giving arts and crafts, but with numbers 🌈

0,                    i=0
1,                    i=1
1,      2,            i=2 to 3
1,  3,  2,  3,        i=4 to 7
1,4,3,5,2,5,3,4,      i=8 to 15

For example, that i=4 to 7 row? it's a copy of the preceding row's values 1,2, with sums 1+2 and 2+1 interleaved in between. obsessed with her fr fr.

For the new value at the end of each row, the sum wraps around — so it takes the last copied value and the first value of the next row, which is always 1. This means the last value in each row just increments 1,2,3,4,5,etc. lowkey satisfying 😌

🌟 Odd and Even 🌟

The sequence makes a repeating pattern even, odd, odd:

0, 1, 1, 2, 1, 3, 2, 3
E  O  O  E  O  O  E ...

You can see it from the copying in the recurrence above. For example, the i=8 to 15 row copying to i=16 to 31:

O . E . O . O . E . O . O . E .      spread
  O   O   E   O   O   E   O   O      sum adjacent

Adding adjacent terms, odd+even and even+odd are both odd. Adding adjacent odd+odd gives even. So the pattern E,O,O in the original row, when spread and added, gives E,O,O again in the next row. the way that pattern just persists?? main character energy 🫶

---

🔥 FUNCTIONS 🔥

See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence classes. (yes bestie, this is a whole family, she has siblings 👑)

• $seq = Math::NumSeq::SternDiatomic->new () — Create and return a new sequence object. ✨

💫 Random Access 💫

• $value = $seq->ith($i) — Return the $i'th value of the sequence.
• ($v0, $v1) = $seq->ith_pair($i) — Return two values ith($i) and ith($i+1) from the sequence. As described in "Ith Pair" below, two values can be calculated with the same work as one. two for the price of one, we love a deal 💖
• $bool = $seq->pred($value) — Return true if $value occurs in the sequence, which means simply integer $value>=0.

---

🧚 FORMULAS 🧚

🍓 Next 🍓

The sequence is iterated using a step given by Mike Stay in OEIS A002487 November 2006, and which follows from iterating across what is the Calkin-Wilf tree of pairs of diatomic sequence values.

"Recounting the Rationals, Continued", problem 10906, posed by Donald E. Knuth, answered variously by C. P. Rupert, Alex Smith, Eau Claire, Richard Stong, Moshe Newman, American Mathematical Monthly, volume 110, number 7, Aug-Sep 2003, pages 642-643, <http://www.jstor.org/stable/3647762>

Two successive sequence values are maintained and are advanced by a simple operation.

maintain p = seq[i], q = seq[i+1]
start p = seq[0] = 0
      q = seq[1] = 1

p_next = seq[i+1] = q
q_next = seq[i+2] = p+q - 2*(p mod q)
  where remainder rounds towards zero
  0 <= (p mod q) <= q-1

Newman gives a form using a floor operation. That suits expressing the iteration in terms of a rational x[i]=p/q.

p_next              1
------  =  ----------------------
q_next     1 + 2*floor(p/q) - p/q

A little rearrangement gives the separate p,q above

division p = q*floor(p/q) + rem      where rem = (p mod q)
then
p_next/q_next = 1 / (1 + 2*floor(p/q) - p/q)    per Newman
              = q / (2*q*floor(p/q) + q - p)
              = q / (2*(p - rem) + q - p)
              = q / (p+q - 2*rem)

In terms of the Calkin-Wilf tree this works because the number of trailing right leg steps is found by m=floor(p/q), then take a step across, then back down again by m many left leg steps. When at the right-most edge of the tree the step across goes down by one extra left, thereby automatically wrapping around at the end of each row. 🌈

seek_to_i() is implemented by calculating a pair of new p,q values with an ith_pair() per below.

🦋 Ith Pair 🦋

For ith_pair() the two sequence values at an arbitrary i,i+1 can be calculated from the bits of i,

p = 0
q = 1
for each bit of i from high to low
  if bit=1 then p += q
  if bit=0 then q += p
return p,q      # are ith(i) and ith(i+1)

For example i=6 is binary "110" so

                         p,q
                         ---
initial               0,1
high bit=1 so p+=q    1,1
next bit=1 so p+=q    2,1
low  bit=0 so q+=p    2,3   is ith(6),ith(7)

This is the same as the Calkin-Wilf tree descent, per "Calkin-Wilf Tree" in Math::PlanePath::RationalsTree. Its X/Y fractions are successive Stern diatomic sequence values. iykyk 💅

🌸 Ith Alone 🌸

If only a single ith() value is desired then a variation can be made on the "Ith Pair" above. Taking the bits of i from low to high (instead of high to low) gives p=ith(i), but q is not ith(i+1). Low zero bits can be ignored for this approach since initial p=0 means the steps q+=p for bit=0 do nothing. efficient queen behavior, honestly 🎀

---

👀 SEE ALSO 👀

• Math::NumSeq
• Math::PlanePath::RationalsTree

---

🌐 HOME PAGE 🌐

<http://user42.tuxfamily.org/math-numseq/index.html>

---

📜 LICENSE 📜

Copyright 2011, 2012, 2013, 2014, 2016, 2017, 2019, 2020 Kevin Ryde

Math-NumSeq is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

Math-NumSeq is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>.

---

okay that's the whole page bestie, you ate 💅✨ this was perl v5.42.0, dated 2025-07-25 — go forth and recurse responsibly 🫶💖