# Copyright 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 <http://www.gnu.org/licenses/>.
package Math::NumSeq::KaprekarRoutineSteps;
use 5.004;
use strict;
use List::Util 'min';
use vars '$VERSION', '@ISA';
$VERSION = 72;
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::__('...');
use constant description => Math::NumSeq::__('Number of steps of the Kaprekar iteration digits ascending + digits descending until reaching a cycle.');
use constant i_start => 1;
use constant characteristic_count => 1;
use constant characteristic_smaller => 1;
use constant characteristic_integer => 1;
use Math::NumSeq::Base::Digits
'parameter_info_array'; # radix parameter
use constant values_min => 0;
#------------------------------------------------------------------------------
# A151949 - decimal one step
# A164734 - number of n-digit 2-cycles
# A164735 - number of n-digit 3-cycles
# A164736 - number of n-digit 5-cycles
#
# A164993 - base-3 one step
# A164994 - base-3 one step / 2
# A164995 - base-3 pre-periodic length
#
# A164727 - cycles 5
# A164731 - number of cycles
# A164732 - cycles
# A164727 - cycles 5
my @oeis_anum;
# $oeis_anum[]
sub oeis_anum {
my ($self) = @_;
return $oeis_anum[$self->{'radix'}];
}
#------------------------------------------------------------------------------
sub ith {
my ($self, $i) = @_;
### ith(): $i
if (_is_infinite($i)) {
return $i; # don't loop forever if $i is +infinity
}
my $radix = $self->{'radix'};
my @digits = _digit_split($i, $radix);
my %seen = (join(',',@digits) => undef);
my $count = 0;
for (;;) {
### at: "count=$count ".join(', ', @digits)
@digits = sort {$a<=>$b} @digits;
### sorted: join(', ', @digits)
my @diff;
my $borrow = 0;
foreach my $i (0 .. $#digits) { # low to high
my $diff = $digits[$i] - $digits[-1-$i] - $borrow;
if ($borrow = ($diff < 0)) {
$diff += $radix;
}
$diff[$i] = $diff;
}
### diff: join(', ', @diff)
### assert: $borrow == 0
# while ($diff[-1] == 0) {
# ### strip high zero ...
# pop @diff;
# if (! @diff) {
# return $count;
# }
# }
@digits = @diff;
my $key = join (',',@digits);
if (exists $seen{$key}) {
last;
}
$seen{$key} = undef;
$count++;
}
return $count;
}
sub _digit_split {
my ($n, $radix) = @_;
### _digit_split(): $n
my @ret;
while ($n) {
push @ret, $n % $radix;
$n = int($n/$radix);
}
return @ret; # low to high
}
1;
__END__