++ed by:

2 PAUSE users

Kevin Ryde


Math::NumSeq::SternDiatomic -- Stern's diatomic sequence


 use Math::NumSeq::SternDiatomic;
 my $seq = Math::NumSeq::SternDiatomic->new;


This is Moritz Stern's diatomic sequence

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

It's constructed by successive levels with a recurrence

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

So the sequence is extended by copying the previous level to the next spead out to even indices, and at the odd indices fill in the sum of adjacent terms,

    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 the i=4to7 row is a copy of the preceding row values 1,2 with sums 1+2 and 2+1 interleaved.

For the new value at the end of each row the sum wraps around so as to take the last copied value and the first value of the next row, which is always 1. This means the last value in each row increments 1,2,3,4,5,etc.

Odd and Even

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

    E  O  O  E  O  O  E ...

This can be seen 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.



$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.



$bool = $seq->pred($value)

Return true if $value occurs in the sequence, which means simply integer $value>=0.



The sequence is iterated using a method by Moshe Newman in

    "Recounting the Rationals, Continued", answers to problem 10906 posed by Donald E. Knuth, C. P. Rupert, Alex Smith and Richard Stong, 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.

    maintaining p = seq[i], q = seq[i+1]  
    initial 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 the mod operation rounds towards zero
      0 <= (p mod q) <= q-1

The form by Newman uses 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

For separate p,q a little rearrangement gives it in terms of the remainder p mod q, as per formula a(n)=a(n-2)+a(n-1)-2*(a(n-2) mod a(n-1)) by Mike Stay OEIS A002487, November 2006.

    division p = q*floor(p/q) + rem      where rem = (p mod q)
    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)               using p,q

In terms of the Calkin-Wilf tree this method works because the number of trailing right leg steps can be 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

   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.

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.







Copyright 2011, 2012, 2013, 2014 Kevin Ryde


