File Coverage

blib/lib/Math/NumSeq/FibonacciRepresentations.pm

Criterion	Covered	Total	%
statement	73	74	98.6
branch	13	14	92.8
condition	1	3	33.3
subroutine	16	16	100.0
pod	3	3	100.0
total	106	110	96.3

# Copyright 2014 Kevin Ryde

# This file is part of Math-NumSeq.
#
# 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 .


# https://eudml.org/doc/92679
# J. Berstel, An Exercise on Fibonacci Representations, RAIRO/
# Informatique Theorique, Vol. 35, No 6, 2001, pp. 491-498, in
# the issue dedicated to Aldo De Luca on the occasion of his
# 60-th anniversary.

# Paul K. Stockmeyer, "A Smooth Tight Upper Bound for the Fibonacci
# Representation Function R(N)", Fibonacci Quarterly, Volume 46/47, Number
# 2, May 2009.
# Free access only post 2003
# http://www.fq.math.ca/46_47-2.html
# http://www.fq.math.ca/Papers/46_47-2/Stockmeyer.pdf

# Klarner 1966
# Product (1+x^fib(i)) gives coefficients R(N)
# R(F[n])   = floor((n+2)/2)       n > 1
# R(F[n]-1) = floor((n+1)/2)       n > 0
# R(F[n]-2) = n-2                  n > 2
# R(F[n]-3) = n-3                  n > 4


package Math::NumSeq::FibonacciRepresentations;
use 5.004;
use strict;

use vars '$VERSION', '@ISA';
$VERSION = 71;

use Math::NumSeq;
use Math::NumSeq::Base::IterateIth;
@ISA = ('Math::NumSeq::Base::IterateIth', 'Math::NumSeq');
*_is_infinite = \&Math::NumSeq::_is_infinite;

# uncomment this to run the ### lines
# use Smart::Comments;

# use constant name => Math::NumSeq::__('Fibonacci Representations');
use constant description => Math::NumSeq::__('Fibonacci representations sequence, the number of ways i can be formed as a sum of distinct Fibonacci numbers.');
use constant default_i_start => 0;
use constant characteristic_count => 1;
use constant characteristic_smaller => 1;
use constant characteristic_integer => 1;
use constant characteristic_increasing => 0;
use constant values_min => 1;

#------------------------------------------------------------------------------
#
use constant oeis_anum => 'A000119';

#------------------------------------------------------------------------------

sub ith {
  my ($self, $i) = @_;
  return ($self->ith_pair($i))[0];
}

sub ith_pair {
  my ($self, $i) = @_;
  ### ith_pair(): $i

  if ($i < 0) {
    return (undef,undef);
  }
  if (_is_infinite($i)) {
    return ($i,$i);  # +inf or nan
  }

  # seeking f2 >= i+1
  # but stop at f1 >= i so not go past UV_MAX if i=UV_MAX
  #
  my @fibs;  # all Fibonacci numbers <= $i
  {
    # find biggest fibonacci f1 <= i
    # if f1+f0 > i then stop loop
    # f1+f0 might overflow UV_MAX so do the loop
    # condition as stop when f1 > i-f0, continue while f1 <= i-f0
    #
    my $f0 = ($i*0) + 1;   # $f0=1, inherit bignum from $i
    my $f1 = $f0 + 1;      # $f1=2, inherit bignum from $i
    while ($f0 <= $i-$f1) {
      push @fibs, $f0;
      ($f1,$f0) = ($f1+$f0,$f1);
    }
    ### @fibs
    ### $f0
    ### $f1

    # here have f1 <= i < f0+f1
    # subtract i+1 - f1
    $i -= $f1;
    $i += 1;
    ### i+1 - f1: $i

    # If i+1-f1 >= f0 then high fib is not the f1 just subtracted but
    # instead f2=f1+f0.  Subtract also f0 so i+1 - (f1+f0).  Now skip f1
    # since the Zeck form has no consecutive fibs.  Push f0 onto @fibs to be
    # the next fib tested in the loop.
    #
    # Actually i+1-(f1+f0) = 0 here, since f1 <= i and f0+f1 <= i+1 means
    # i+1==f0+f1 exactly.  Could return r += $#fibs/2 which is the effect of
    # every second 0-bit step, but i+1=fibonacci will be fairly rare.
    #
    # If i+1-f1 < f0 then high fib is f1 just subtracted.  Now skip f0 since
    # the Zeck form has no consecutive fibs.
    #
    if ($i >= $f0) {
      return (1, int(scalar(@fibs)/2) + 2);

      # $i -= $f0;
      # ### subtract f0, so i+1 sub f2=f1+f0: $i
      # push @fibs, $f0;
    }
  }

  my $r = 1;         # R(0) = 1
  my $rplus1 = 1;    # R(1) = 1
  my $odd_zeros = 1; # high zeck "10..." initial zero

  while (my $f = pop @fibs) {
    ### at: "f=$f i=$i  r=$r rplus1=$rplus1   odd_zeros=$odd_zeros"

    if ($i < $f) {
      ### 0-bit ...

      if ($odd_zeros) {
        ### odd zeros on i+1, add to rplus1 ...
        $rplus1 += $r;
      }
      $odd_zeros ^= 1;

    } else {
      $i -= $f;
      ### 1-bit sub: "$f to i=$i"

      if ($odd_zeros) {
        ### odd zeros on i+1, add to r ...
        $r += $rplus1;
      } else {
        ### even zeros on i+1, r same as rplus1 ...
        $r = $rplus1;
      }

      ### never consecutive fibs, so pop without comparing to i ...
      pop @fibs || last;
      $odd_zeros = 1;   # one trailing 0-bit is odd
    }
  }

  ### final: "r=$r  rplus1=$rplus1"
  return ($r, $rplus1);
}

sub pred {
  my ($self, $value) = @_;
  ### FibonacciRepresentations pred(): $value
  return ($value >= 1 && $value == int($value));
}

1;
__END__