Math::N...mulative(3)

🌸 Math::NumSeq::GolayRudinShapiroCumulative 🌸

heyyy bestie so this page lives in the User Contributed Perl Documentation corner of the perl universe, and it's about a sequence that's genuinely kinda iconic. buckle up 💖

---

✨ NAME ✨

Math::NumSeq::GolayRudinShapiroCumulative — it's the cumulative Golay/RudinShapiro sequence. say that five times fast, i dare you 🫶

---

🌈 SYNOPSIS 🌈

the whole vibe, fr fr:

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

---

💫 DESCRIPTION 💫

okay so. this is the Golay/Rudin/Shapiro sequence values, but accumulated, like a running total situation:

GRS(0)+...+GRS(i)

and it starts from i=0 value=GRS(0), so the sequence goes:

1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 7, 6, 5, 4, 5, 4, ...

and here's the part that made me gasp: the total is always positive, and lowkey wilder than that — a given cumulative total k occurs precisely k times (per Brillhart and Morton). so if you see a 3, bestie, there are exactly three 3s in the whole sequence, and the three occurrences shown above? yeah those are all of them. no more. periodt. 👑

this GRS cumulative also shows up in the alternate paper folding curve as the coordinate sum X+Y. the whole "k occurs k many times" thing has a geometric interpretation too — it's the points on the diagonal X+Y=k of the curve, visited a total of k many times. see "dSum" in Math::PlanePath::AlternatePaper. geometry ate that 💅

---

🧚 FUNCTIONS 🧚

common behaviour for all sequence classes lives in "FUNCTIONS" in Math::NumSeq — go peek there if you want the full lore.

• "$seq = Math::NumSeq::GolayRudinShapiroCumulative->new ()" — creates and returns a brand new sequence object. main character energy, freshly spawned ✨

🦋 Random Access 🦋

• "$value = $seq->ith($i)" — hands you the $i'th value from the sequence, which is the total "GRS(0)+GRS(1)+...+GRS($i)".
• "$bool = $seq->pred($value)" — returns true if $value actually occurs in the sequence. plot twist: all positive integers occur, so this is literally just checking that $value is an integer with "$value >= 1". that's it, that's the whole test 😭

---

💜 FORMULAS 💜

🎀 Ith 🎀

the cumulative total GRS(0)+...+GRS(i-1) can be computed straight from the 1-bits of i. every single 1-bit turns into a value of 2^floor((pos+1)/2) in the total, like so:

    pos    value
    ---    -----
     0       1
     1       2
     2       2
     3       4
     4       4
    ...     ...
     k      2^ceil(k/2)

whether that value gets added or subtracted depends on how many 11 bit pairs sit above that bit position — and not counting the bit itself:

add value    if even count of adjacent 11 bit pairs above
sub value    if odd count

so for example, i=27 is 110011 in binary, and:

    1      -1      bit0 low bit
    1      -2      bit1
    0              bit2
    1      +4      bit3
    1      +4      bit4 high bit
          ----
            5      cumulative value GRS(0)+...+GRS(26)

the second lowest bit gets negated to value -2 because there's one 11 bit pair above it, and the -1 is the same story — above it, and not including it, there's just one 11 bit pair.

or, another example, i=31 is 11111 in binary:

    1      -1      bit0 low bit
    1      +2      bit1
    1      -2      bit2
    1      +4      bit3
    1      +4      bit4 high bit
          ----
            7      cumulative total GRS(0)+...+GRS(30)

here at bit2 the value is -2 because there's one adjacent 11 above it, not counting bit2 itself. then at pos=1 there's two 11 pairs above, so it's +2, and at pos=0 there's three, so -1. the math is mathing 🔥

you can build the total by scanning the bits high to low and counting adjacent 11 bits on the way down to add or subtract. or you can build it low to high by negating the total-so-far whenever you hit a 11 pair. two paths, same destination, slay.

now, for an inclusive sum GRS(0)+...+GRS(i) — which is what this module does — the extra GRS(i) gets worked into the calculation through its GRS definition, +1 or -1 depending on the total number of adjacent 11 bits. you can think of it as one extra value 1 sitting below the least significant bit. for example, i=27 inclusive:

           +1      below all bits
    1      -1      bit0 low bit
    1      -2      bit1
    0              bit2
    1      +4      bit3
    1      +4      bit4 high bit
          ----
            5      cumulative value GRS(0)+...+GRS(27)

and for a low-to-high calculation, that lowest +/-1 is handled simply by starting the total at 1. it then becomes +1 or -1 through the negations as 11s are encountered during the rest of the bit handling:

total = 1   # initial value below all bits to be inclusive GRS(i)
power = 1   # 2^ceil(bitpos/2)
thisbit = take bit from low end of i

loop
  nextbit = take bit from low end of i
  if thisbit&&nextbit
    then total = -total    # negate lower values added
  if thisbit
    then total += power
  thisbit = nextbit

  power *= 2
  exit loop if i==0

  nextbit = bit from low end of i
  if thisbit&&nextbit
    then total = -total    # negate lower values added
  if thisbit
    then total += power
  thisbit = nextbit
  exit loop if i==0
endloop

total += power     # final for highest 1-bit in i
# total=GRS(0)+...+GRS(i)

this sort of calculation also arises implicitly in the alternate paper folding curve, to work out X,Y for a given N point on the curve. bits of the cumulative GRS can be generated from base 4 digits of 2*N. the author's alternate paperfolding curve write-up has some more of this — it's under "GRScumul" in the index:

<http://user42.tuxfamily.org/alternate/index.html>

---

👀 SEE ALSO 👀

• Math::NumSeq
• Math::NumSeq::GolayRudinShapiro
• Math::PlanePath::AlternatePaper

---

🏠 HOME PAGE 🏠

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

---

📜 LICENSE 📜

Copyright 2012, 2013, 2014, 2016, 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. (translation: it's free, bestie, but nobody's promising it'll be perfect, so don't come for anyone if it acts up 🙈)

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!! go forth and accumulate some GRS values, you gorgeous genius 💖

and that's a wrap on this one, bestie — page generated by perl v5.42.0 on 2025-07-25 💅✨ take care of yourself and hydrate, ily 🫶🌸