File Coverage

blib/lib/Math/NumSeq/HofstadterFigure.pm

Criterion	Covered	Total	%
statement	66	66	100.0
branch	12	12	100.0
condition			n/a
subroutine	13	13	100.0
pod	4	4	100.0
total	95	95	100.0

# Copyright 2011, 2012, 2013, 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 .

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

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

use Math::NumSeq;
@ISA = ('Math::NumSeq');

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


# use constant name => Math::NumSeq::__('Hofstadter Figure');
use constant description => Math::NumSeq::__('Hofstadter figure sequence.');
use constant characteristic_increasing => 1;
use constant characteristic_integer => 1;
use constant i_start => 1;

use constant parameter_info_array =>
  [
   { name    => 'start',
     type    => 'integer',
     default => '1',
     width   => 2,
     minimum => 1,
     # description => Math::NumSeq::__(''),
   },
  ];

sub values_min {
  my ($self) = @_;
  return $self->{'start'};
}

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

# A005228 - seq and first diffs make all integers, increasing
#  A030124 - the first diffs
#
# cf A061577 - starting from 2
#     A061578 - starting from 2 first diffs
#     2, 3, 7, 12, 18, 26, 35, 45,
#      1, 4, 5,  6,   8,  9, 10, 11, 13,
#
#    A140778 - seq and first diffs make all positive integers,
#     each int applied to one of the two in turn
#      A140779 - its first diffs
#
#    A037257 - seq + first diffs + second diffs make all integers
#     A037258 - the first diffs
#     A037259 - the second diffs
#    A081145
#
my @oeis_anum = (
                 # OEIS-Catalogue array begin
                 undef,     # start=0
                 'A005228', #
                 'A061577', # start=2
                 'A022935', # start=3
                 'A022936', # start=4
                 'A022937', # start=5
                 'A022938', # start=6
               # OEIS-Catalogue array end
                );
sub oeis_anum {
  my ($self) = @_;
  return $oeis_anum[$self->{'start'}];
}

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

# start S
# S, S+1, S+2, ..., S+(S-1), S+(S+1), S+(S+2)

# $upto[0] is the previous value returned
# $inc[0] is the amount to increment it by next time
#
# $upto[1] is the sequence at a previous position
# if $inc[0] == $upto[1] then that increment must be skipped,
# and advance $upto[1] for the next to skip#
#
# initial
# upto[0] = 1
# inc[0] = 0
#
# return 1+0=1, small inc[0] -> 2
# upto[0] = 1
# inc[0] = 2
#
# return 1+2=3, small inc[0] -> 4
# upto[0] = 3
# inc[0] = 4
#
# return 3+4=7, small inc[0] 4 -> 5
# upto[0] = 7
# inc[0] = 5
#
# return 7+5=12, small inc[0] 5 -> 6
# upto[0] = 12
# inc[0] = 6
#
# return 12+6=18, small inc[0] 6 -> outside
# upto[0] = 12
# inc[0] = 8
# upto[1] = 12
# inc[1] = 6
#
# inc[0]==upto[1] so skip to inc[0]=4
# add 4 to return upto[0]=3+4=7
# $inc[0]++
# next upto[1] is 7
# upto[0] = 7
# upto[1] = 7
# inc[0] = 5
# inc[1] = 4
#
# add 7+5 to 12, inc[0]++
# upto[0] = 12
# upto[1] = 7
# inc[0] = 6
# inc[1] = 4
#
# add 12+6=18, inc[0]++
# upto[0] = 18
# upto[1] = 7
# inc[0] = 7
# inc[1] = 4
#
# inc[0]==upto[1] so skip to inc[0]=8
# add 8 to return upto[0]=18+8=26
# step upto[1] add inc[1]++ to 7+5=12
# upto[0] = 26
# upto[1] = 12
# inc[0] = 7
# inc[1] = 6
#

# start=1
# seq  1, 3, 7, 12, 18, 26, 35, 45, 56, 69, 83, 98, 114, 131, 150, 170, 191,
# diffs  2, 4, 5, 6,  8,  9,  10, 11, 13, 14, 15, 16,  17,  19,  20,  21, 22,
#
# start=2
# seq  2, 3, 7, 12, 18, 26,
# diffs  1  4  5   6   8
#
# start=4
# seq  4, 5, 7, 10, 16, 24,
# diffs  1  2  3  6   8   9
#
# start=5
# seq  5, 6, 8, 11, 15, 22, 31,
# diffs  1  2  3  4,  7   9   10
#
# start=6
# seq  6, 7, 9, 12, 16, 21, 29,
# diffs  1  2  3  4,  5,  8   10
#
# start=7
# seq  7, 8, 10, 13, 17, 22, 28, 37
# diffs  1  2   3  4,  5,  6   9   11

my @small_inc
  = (undef, # start=0 impossible

     # 0      1      2      3      4  5      6  7
     #
     [ 2, undef,     4, undef,     5, 6,     7  ],  # start=1
     [ 1,     4, undef, undef,     5, 6,     7  ],  # start=2

     # start=3
     # seq  3, 4, 6, 11, 18, 26,
     # diffs  1  2  5   7   8   9
     #
     # 0  1  2      3      4  5      6  7
     [ 1, 2, 5, undef, undef, 7, undef, 8 ],

     # # start=4
     # [ 1,     2,     3,     6,    ],

     # # start=5
     # [ 1, 2, 3, 4, 7, undef, undef, 9 ],

     # # start=6
     # # 0  1  2  3  4  5
     # [ 1, 2, 3, 4, 5, 8  ],

     # # start=7
     # # 0  1  2  3  4  5  6
     # [ 1, 2, 3, 4, 5, 6, 9  ],
    );
my @small_upto = (undef, # 0
                  7,     # 1
                  7,     # 2
                  11,    # 3

                  # 7,     # 4
                  # 11,    # 5
                  # 9,     # 6
                  # 10,    # 7
                 );
my @small_upto_inc = (undef,  # 0
                      5,      # 1
                      5,      # 2
                      7,      # 3

                      # 3,      # 4
                      # 4,      # 5
                      # 3,      # 6
                      # 3,      # 7
                     );
sub rewind {
  my ($self) = @_;
  $self->{'i'} = $self->i_start;

  my $start = $self->{'start'};
  $self->{'small_inc'}  = $small_inc[$start];

  if ($self->{'small_inc'}) {
    $self->{'grow_upto'} = $small_upto[$start];
    $self->{'grow_inc'} = $small_upto_inc[$start];
  } else {
    $self->{'small_inc'} = [ (1 .. $start-1), $start+2 ];
    $self->{'grow_upto'} = $start+3;
    $self->{'grow_inc'} = 3;
  }
  $self->{'upto'} = [ $start,
                      $self->{'grow_upto'} ];
  $self->{'inc'}  = [ 0,
                      $self->{'grow_inc'} ];
}

# # 1->2->4->5->6->7
# #                    0  1  2    3    4  5  6
# my @small_inc = (undef, 2, 4, undef, 5, 6);

sub next {
  my ($self) = @_;
  ### HofstadterFigure next(): "$self->{'i'}"
  ### upto: join (', ',@{$self->{'upto'}})
  ### inc : join (', ',@{$self->{'inc'}})

  my $i = $self->{'i'}++;
  my $upto = $self->{'upto'};
  my $inc = $self->{'inc'};

  my $add = $inc->[0]++;
  ### prospective add: $add

  if (defined (my $next_inc = $self->{'small_inc'}->[$add])) {
    ### small next_inc: $next_inc
    $inc->[0] = $next_inc;

  } elsif ($add >= $upto->[1]) {
    ### must skip this increment ...
    ### add now: $inc->[0]
    $add = $inc->[0]++;

    # diff=26 already seen (6), at i=22 value=311 prev_value=285

    my $pos = 1;
    for (;;) {
      ### $pos
      if ($pos >= $#$upto) {
        ### grow ...
        push @$upto, $self->{'grow_upto'};
        push @$inc, $self->{'grow_inc'};
      }

      my $posadd = $inc->[$pos]++;
      ### $posadd
      $upto->[$pos] += $posadd;

      if (defined (my $next_inc = $self->{'small_inc'}->[$posadd])) {
        ### small pos next_inc: $next_inc
        $inc->[$pos] = $next_inc;
        last;
      }
      if ($posadd < $upto->[$pos+1]) {
        ### less than next upto: $upto->[$pos+1]
        last;
      }
      $upto->[$pos]++; # skip and to next level
      $inc->[$pos]++;
      $pos++;
    }
  }
  ### $add
  ### for return value: $upto->[0] + $add
  return ($i,
          ($upto->[0] += $add));
}

1;
__END__