/ 
Math-NumSeq-75
River stage zero No dependents
/ Math::NumSeq::GolayRudinShapiroCumulative

NAME

Math::NumSeq::GolayRudinShapiroCumulative -- cumulative Golay/RudinShapiro sequence

SYNOPSIS

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

DESCRIPTION

This is the Golay/Rudin/Shapiro sequence values accumulated as GRS(0)+...+GRS(i),

starting from i=0 value=GRS(0)

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

The total is always positive, and in fact a given cumulative total k occurs precisely k times (per Brillhart and Morton). For example the three occurrences of 3 shown above are all the places 3 occurs.

This GRS cumulative arises as in the alternate paper folding curve as the coordinate sum X+Y. The way k occurs k many times has a geometric interpretation as the points on the diagonal X+Y=k of the curve visited a total of k many times. See "dSum" in Math::PlanePath::AlternatePaper.

FUNCTIONS

See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence classes.

$seq = Math::NumSeq::GolayRudinShapiroCumulative->new ()

Create and return a new sequence object.

Random Access

$value = $seq->ith($i)

Return the $i'th value from the sequence, being the total GRS(0)+GRS(1)+...+GRS($i).

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

Return true if $value occurs in the sequence. All positive integers occur, so this simply means integer $value >= 1.

FORMULAS

Ith

The cumulative total GRS(0)+...+GRS(i-1) can be calculated from the 1-bits of i. Each 1-bit becomes a value 2^floor((pos+1)/2) in the total,

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

The value is added or subtracted from the total according to the number of 11 bit pairs above that bit position, not including the bit itself,

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

For example i=27 is 110011 in binary so

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 is negated as value -2 because there's one "11" bit pair above it, and -1 the same because above and not including that bit there's just one "11" bit pair.

Or for example i=31 is 11111 in binary so

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, not including bit2 itself. Then at pos=1 there's two 11 pairs above so +2, and at pos=0 there's three so -1.

The total can be formed by examining the bits high to low and counting adjacent 11 bits on the way down to add or subtract. Or it can be formed from low to high by negating the total so far when a 11 pair is encountered.

For an inclusive sum GRS(0)+...+GRS(i) as per this module, the extra GRS(i) can be worked into the calculation by its GRS definition +1 or -1 according to the total number of adjacent 11 bits. This can be thought of as an extra value 1 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)

For low to high calculation, this lowest +/-1 can be handled simply by starting the total at 1. It then becomes +1 or -1 by the negations as 11s are encountered for 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 arises implicitly in the alternate paper folding curve to calculate 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. See the author's alternate paperfolding curve write-up for some more ("GRScumul" in the index)

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.

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