| 1 | # Copyright 2010, 2011, 2012, 2013, 2014, 2016, 2019, 2020, 2021 Kevin Ryde | ||||||||||||||||||||||||||||
| 2 | |||||||||||||||||||||||||||||
| 3 | # This file is part of Math-NumSeq. | ||||||||||||||||||||||||||||
| 4 | # | ||||||||||||||||||||||||||||
| 5 | # Math-NumSeq is free software; you can redistribute it and/or modify | ||||||||||||||||||||||||||||
| 6 | # it under the terms of the GNU General Public License as published by the | ||||||||||||||||||||||||||||
| 7 | # Free Software Foundation; either version 3, or (at your option) any later | ||||||||||||||||||||||||||||
| 8 | # version. | ||||||||||||||||||||||||||||
| 9 | # | ||||||||||||||||||||||||||||
| 10 | # Math-NumSeq is distributed in the hope that it will be useful, but | ||||||||||||||||||||||||||||
| 11 | # WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY | ||||||||||||||||||||||||||||
| 12 | # or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | ||||||||||||||||||||||||||||
| 13 | # for more details. | ||||||||||||||||||||||||||||
| 14 | # | ||||||||||||||||||||||||||||
| 15 | # You should have received a copy of the GNU General Public License along | ||||||||||||||||||||||||||||
| 16 | # with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>. | ||||||||||||||||||||||||||||
| 17 | |||||||||||||||||||||||||||||
| 18 | |||||||||||||||||||||||||||||
| 19 | # cf A206913 next binary palindrome <= n value_floor | ||||||||||||||||||||||||||||
| 20 | # A206914 next binary palindrome >= n value_ceil | ||||||||||||||||||||||||||||
| 21 | # A206920 sum first n binary palindromes | ||||||||||||||||||||||||||||
| 22 | |||||||||||||||||||||||||||||
| 23 | |||||||||||||||||||||||||||||
| 24 | package Math::NumSeq::Palindromes; | ||||||||||||||||||||||||||||
| 25 | 1 | ▶ | use 5.004; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 26 | 1 | ▶ | use strict; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 27 | 1 | ▶ | use List::Util 'max'; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 28 | |||||||||||||||||||||||||||||
| 29 | 1 | ▶ | use vars '$VERSION', '@ISA'; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 30 | 1 | $VERSION = 75; | |||||||||||||||||||||||||||
| 31 | |||||||||||||||||||||||||||||
| 32 | 1 | ▶ | use Math::NumSeq; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 33 | 1 | ▶ | use Math::NumSeq::Base::IterateIth; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 34 | 1 | @ISA = ('Math::NumSeq::Base::IterateIth', | |||||||||||||||||||||||||||
| 35 | 'Math::NumSeq'); | ||||||||||||||||||||||||||||
| 36 | 1 | *_is_infinite = \&Math::NumSeq::_is_infinite; | |||||||||||||||||||||||||||
| 37 | |||||||||||||||||||||||||||||
| 38 | 1 | ▶ | use Math::NumSeq::Repdigits; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 39 | 1 | *_digit_split_lowtohigh = \&Math::NumSeq::Repdigits::_digit_split_lowtohigh; | |||||||||||||||||||||||||||
| 40 | |||||||||||||||||||||||||||||
| 41 | # uncomment this to run the ### lines | ||||||||||||||||||||||||||||
| 42 | #use Smart::Comments; | ||||||||||||||||||||||||||||
| 43 | |||||||||||||||||||||||||||||
| 44 | |||||||||||||||||||||||||||||
| 45 | # use constant name => Math::NumSeq::__('Palindromes'); | ||||||||||||||||||||||||||||
| 46 | 1 | ▶ | use constant description => Math::NumSeq::__('Numbers which are "palindromes" reading the same backwards or forwards, like 153351. Default is decimal, or select a radix.'); | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 47 | 1 | ▶ | use constant i_start => 1; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 48 | 1 | ▶ | use constant values_min => 0; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 49 | 1 | ▶ | use constant characteristic_increasing => 1; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 50 | 1 | ▶ | use constant characteristic_integer => 1; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 51 | |||||||||||||||||||||||||||||
| 52 | use Math::NumSeq::Base::Digits | ||||||||||||||||||||||||||||
| 53 | 1 | ▶ | 'parameter_info_array'; # radix parameter | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 54 | |||||||||||||||||||||||||||||
| 55 | |||||||||||||||||||||||||||||
| 56 | #------------------------------------------------------------------------------ | ||||||||||||||||||||||||||||
| 57 | # cf A002385 - prime palindromes | ||||||||||||||||||||||||||||
| 58 | # A029732 - prime palindromes in base 16, written in base 10 | ||||||||||||||||||||||||||||
| 59 | # A110784 - palindrom and digits in ascending order | ||||||||||||||||||||||||||||
| 60 | # A029731 - palindromes in both decimal and hexadecimal | ||||||||||||||||||||||||||||
| 61 | # A029733 - n where n^2 hex palindrome | ||||||||||||||||||||||||||||
| 62 | # A029734 - squares which are hex palindromes | ||||||||||||||||||||||||||||
| 63 | # A016038 - not palindrome in any base, up to n-2 | ||||||||||||||||||||||||||||
| 64 | # A057891 - not a binary palindrome, including if trailing 0-bits stripped | ||||||||||||||||||||||||||||
| 65 | # A057148 - binary palindromes in binary | ||||||||||||||||||||||||||||
| 66 | |||||||||||||||||||||||||||||
| 67 | 1 | my @oeis_anum = ( | |||||||||||||||||||||||||||
| 68 | # OEIS-Catalogue array begin | ||||||||||||||||||||||||||||
| 69 | undef, # 0 | ||||||||||||||||||||||||||||
| 70 | undef, # 1 | ||||||||||||||||||||||||||||
| 71 | 'A006995', # radix=2 | ||||||||||||||||||||||||||||
| 72 | 'A014190', # radix=3 | ||||||||||||||||||||||||||||
| 73 | 'A014192', # radix=4 | ||||||||||||||||||||||||||||
| 74 | 'A029952', # radix=5 | ||||||||||||||||||||||||||||
| 75 | 'A029953', # radix=6 | ||||||||||||||||||||||||||||
| 76 | 'A029954', # radix=7 | ||||||||||||||||||||||||||||
| 77 | 'A029803', # radix=8 | ||||||||||||||||||||||||||||
| 78 | 'A029955', # radix=9 | ||||||||||||||||||||||||||||
| 79 | 'A002113', # | ||||||||||||||||||||||||||||
| 80 | 'A029956', # radix=11 | ||||||||||||||||||||||||||||
| 81 | 'A029957', # radix=12 | ||||||||||||||||||||||||||||
| 82 | 'A029958', # radix=13 | ||||||||||||||||||||||||||||
| 83 | 'A029959', # radix=14 | ||||||||||||||||||||||||||||
| 84 | 'A029960', # radix=15 | ||||||||||||||||||||||||||||
| 85 | 'A029730', # radix=16 | ||||||||||||||||||||||||||||
| 86 | # OEIS-Catalogue array end | ||||||||||||||||||||||||||||
| 87 | ); | ||||||||||||||||||||||||||||
| 88 | 9 | ▶ | sub oeis_anum { | ||||||||||||||||||||||||||
|
Subroutine
oeis_anum: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||
| 89 | 9 | my ($self) = @_; | |||||||||||||||||||||||||||
| 90 | 9 | return $oeis_anum[$self->{'radix'}]; | |||||||||||||||||||||||||||
| 91 | } | ||||||||||||||||||||||||||||
| 92 | |||||||||||||||||||||||||||||
| 93 | #------------------------------------------------------------------------------ | ||||||||||||||||||||||||||||
| 94 | |||||||||||||||||||||||||||||
| 95 | 13113 | ▶ | sub ith { | ||||||||||||||||||||||||||
|
Subroutine
ith: called CC=6 SCAR=17.9
Pod
documented
| |||||||||||||||||||||||||||||
| 96 | 13113 | my ($self, $i) = @_; | |||||||||||||||||||||||||||
| 97 | ### Palindrome ith(): $i | ||||||||||||||||||||||||||||
| 98 | |||||||||||||||||||||||||||||
| 99 | 13113 | ▶ | if (_is_infinite($i)) { # don't loop forever if $value is +/-infinity | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 100 | 0 | return undef; | |||||||||||||||||||||||||||
| 101 | } | ||||||||||||||||||||||||||||
| 102 | |||||||||||||||||||||||||||||
| 103 | 13113 | my $radix = $self->{'radix'}; | |||||||||||||||||||||||||||
| 104 | |||||||||||||||||||||||||||||
| 105 | 13113 | ▶ | if ($i < 1) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 106 | 36 | return 0; | |||||||||||||||||||||||||||
| 107 | } | ||||||||||||||||||||||||||||
| 108 | 13077 | $i -= 2; | |||||||||||||||||||||||||||
| 109 | |||||||||||||||||||||||||||||
| 110 | 13077 | my $digits = 1; | |||||||||||||||||||||||||||
| 111 | 13077 | my $limit = $radix-1; | |||||||||||||||||||||||||||
| 112 | 13077 | my $add = 1; | |||||||||||||||||||||||||||
| 113 | 13077 | my $ret; | |||||||||||||||||||||||||||
| 114 | 13077 | for (;;) { | |||||||||||||||||||||||||||
| 115 | 30253 | ▶ | if ($i < $limit) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 116 | ### first, no low ... | ||||||||||||||||||||||||||||
| 117 | 9699 | $i += $add; | |||||||||||||||||||||||||||
| 118 | 9699 | $ret = int($i / $radix); | |||||||||||||||||||||||||||
| 119 | 9699 | last; | |||||||||||||||||||||||||||
| 120 | } | ||||||||||||||||||||||||||||
| 121 | 20554 | $i -= $limit; | |||||||||||||||||||||||||||
| 122 | 20554 | ▶ | if ($i < $limit) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 123 | ### second ... | ||||||||||||||||||||||||||||
| 124 | 3378 | $i += $add; | |||||||||||||||||||||||||||
| 125 | 3378 | $ret = $i; | |||||||||||||||||||||||||||
| 126 | 3378 | last; | |||||||||||||||||||||||||||
| 127 | } | ||||||||||||||||||||||||||||
| 128 | 17176 | $i -= $limit; | |||||||||||||||||||||||||||
| 129 | 17176 | $limit *= $radix; | |||||||||||||||||||||||||||
| 130 | 17176 | $add *= $radix; | |||||||||||||||||||||||||||
| 131 | 17176 | $digits++; | |||||||||||||||||||||||||||
| 132 | } | ||||||||||||||||||||||||||||
| 133 | ### $limit | ||||||||||||||||||||||||||||
| 134 | ### $add | ||||||||||||||||||||||||||||
| 135 | ### $i | ||||||||||||||||||||||||||||
| 136 | ### $digits | ||||||||||||||||||||||||||||
| 137 | ### push under: $ret | ||||||||||||||||||||||||||||
| 138 | 13077 | ▶ | while ($digits--) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 139 | 30253 | $ret = $ret * $radix + ($i % $radix); | |||||||||||||||||||||||||||
| 140 | 30253 | $i = int($i / $radix); | |||||||||||||||||||||||||||
| 141 | } | ||||||||||||||||||||||||||||
| 142 | ### $ret | ||||||||||||||||||||||||||||
| 143 | 13077 | return $ret; | |||||||||||||||||||||||||||
| 144 | } | ||||||||||||||||||||||||||||
| 145 | |||||||||||||||||||||||||||||
| 146 | 12891 | ▶ | sub pred { | ||||||||||||||||||||||||||
|
Subroutine
pred: called CC=5 SCAR=16.1
Pod
documented
| |||||||||||||||||||||||||||||
| 147 | 12891 | my ($self, $value) = @_; | |||||||||||||||||||||||||||
| 148 | |||||||||||||||||||||||||||||
| 149 | 12891 | ▶ | if (_is_infinite($value) # don't loop forever if $value is +/-infinity | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition66%2/3
_is_infinite($value) or $value != int $value
MC/DC50%1/2
_is_infinite($value) or $value != int $value
_is_infinite($value)
$value != int $value
Truth table66%2/3
A or B
A= _is_infinite($value)B= $value != int $value
| |||||||||||||||||||||||||||||
| 150 | || $value != int($value)) { | ||||||||||||||||||||||||||||
| 151 | 6153 | return 0; | |||||||||||||||||||||||||||
| 152 | } | ||||||||||||||||||||||||||||
| 153 | |||||||||||||||||||||||||||||
| 154 | 6738 | my @digits = _digit_split_lowtohigh($value, $self->{'radix'}); | |||||||||||||||||||||||||||
| 155 | 6738 | for my $i (0 .. int(@digits/2)-1) { | |||||||||||||||||||||||||||
| 156 | 8433 | ▶ | if ($digits[$i] != $digits[-1-$i]) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 157 | 5596 | return 0; | |||||||||||||||||||||||||||
| 158 | } | ||||||||||||||||||||||||||||
| 159 | } | ||||||||||||||||||||||||||||
| 160 | 1142 | return 1; | |||||||||||||||||||||||||||
| 161 | } | ||||||||||||||||||||||||||||
| 162 | |||||||||||||||||||||||||||||
| 163 | 1 | 1; | |||||||||||||||||||||||||||
| 164 | __END__ | ||||||||||||||||||||||||||||