| 1 | # Copyright 2011, 2012, 2013, 2014, 2016, 2019, 2020 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 | package Math::NumSeq::JugglerSteps; | ||
| 19 | use 5.004; | ||
| 20 | use strict; | ||
| 21 | |||
| 22 | use vars '$VERSION', '@ISA'; | ||
| 23 | $VERSION = 75; | ||
| 24 | |||
| 25 | use Math::NumSeq; | ||
| 26 | use Math::NumSeq::Base::IterateIth; | ||
| 27 | @ISA = ('Math::NumSeq::Base::IterateIth', | ||
| 28 | 'Math::NumSeq'); | ||
| 29 | |||
| 30 | use Math::NumSeq::Base::Cache | ||
| 31 | 'cache_hash', | ||
| 32 | 'make_key'; | ||
| 33 | |||
| 34 | # uncomment this to run the ### lines | ||
| 35 | #use Devel::Comments; | ||
| 36 | |||
| 37 | # use constant name => Math::NumSeq::__('Juggler Steps'); | ||
| 38 | use constant description => Math::NumSeq::__('Number of steps to reach 1 in the Juggler sqrt sequence.'); | ||
| 39 | use constant characteristic_count => 1; | ||
| 40 | use constant characteristic_smaller => 1; | ||
| 41 | use constant characteristic_increasing => 0; | ||
| 42 | use constant values_min => 0; | ||
| 43 | use constant i_start => 1; | ||
| 44 | |||
| 45 | use constant parameter_info_array => | ||
| 46 | [ | ||
| 47 | { name => 'step_type', | ||
| 48 | display => Math::NumSeq::__('Step Type'), | ||
| 49 | type => 'enum', | ||
| 50 | default => 'both', | ||
| 51 | choices => ['up','down','both'], | ||
| 52 | choices_display => [Math::NumSeq::__('Up'), | ||
| 53 | Math::NumSeq::__('Down'), | ||
| 54 | Math::NumSeq::__('Both'), | ||
| 55 | ], | ||
| 56 | description => Math::NumSeq::__('Which steps to count, the n^(3/2) ups, the n^(1/2) downs, or both.'), | ||
| 57 | }, | ||
| 58 | { name => 'juggler_type', | ||
| 59 | display => Math::NumSeq::__('Juggler Algorithm Type'), | ||
| 60 | type => 'string', | ||
| 61 | default => '1/2-3/2', | ||
| 62 | width => 9, | ||
| 63 | choices => ['1/2-3/2','2/3-3/2','3/4-4/3'], | ||
| 64 | description => Math::NumSeq::__('Juggler algorithm type, as the even power and odd power.'), | ||
| 65 | }, | ||
| 66 | # { name => 'round_type', | ||
| 67 | # display => Math::NumSeq::__('Rounding Type'), | ||
| 68 | # type => 'enum', | ||
| 69 | # default => 'floor', | ||
| 70 | # choices => ['floor','round'], | ||
| 71 | # choices_display => [Math::NumSeq::__('Floor'), | ||
| 72 | # Math::NumSeq::__('Round'), | ||
| 73 | # ], | ||
| 74 | # description => Math::NumSeq::__('Rounding type.'), | ||
| 75 | # }, | ||
| 76 | ]; | ||
| 77 | |||
| 78 | #------------------------------------------------------------------------------ | ||
| 79 | # eg. 78901 peaks at about 370,000 digits ... | ||
| 80 | # | ||
| 81 | # cf | ||
| 82 | # A094683 - iteration, ie. n^(1/2) or n^(3/2) | ||
| 83 | # A094670 - smallest requiring n iterations | ||
| 84 | # A094679 - start requiring n iterations | ||
| 85 | # A094684 - records in plain seq | ||
| 86 | # A094698 - num steps where new record | ||
| 87 | # A143745 - next largest | ||
| 88 | # A094716 - largest value in trajectory starting from n | ||
| 89 | # A094778 - dropping time from odd | ||
| 90 | # A094804 - num primes in trajectory | ||
| 91 | # A094819 - steps starting 10^n | ||
| 92 | # A143742 - producing larger value | ||
| 93 | # A143743 - num digits | ||
| 94 | # A143744 - steps next largest | ||
| 95 | # | ||
| 96 | # A007321 - rounded steps | ||
| 97 | # A094685 - rounded iteration, ie. single powering | ||
| 98 | # A094693 - rounded records | ||
| 99 | # A094725 - rounded largest value in trajectory starting from n | ||
| 100 | # A095910 - rounded records | ||
| 101 | # A095911 - rounded num steps to records | ||
| 102 | # | ||
| 103 | # A095396 - 2/3-3/2 iteration | ||
| 104 | # A095397 - 2/3-3/2 largest in trajectory starting from n | ||
| 105 | # A095398 - 2/3-3/2 steps | ||
| 106 | # | ||
| 107 | # A095399 - 3/4-4/3 iteration | ||
| 108 | # A095400 - 3/4-4/3 largest value in trajectory starting from n | ||
| 109 | # A095401 - 3/4-4/3 steps | ||
| 110 | # | ||
| 111 | # up => '', | ||
| 112 | # # OEIS-Catalogue: step_type=up | ||
| 113 | # | ||
| 114 | # down => '', | ||
| 115 | # # OEIS-Catalogue: step_type=down | ||
| 116 | # | ||
| 117 | my %oeis_anum = ( | ||
| 118 | # both up and down | ||
| 119 | both => { '1/2-3/2' => 'A007320', | ||
| 120 | # OEIS-Catalogue: A007320 | ||
| 121 | |||
| 122 | '2/3-3/2' => 'A095398', | ||
| 123 | # OEIS-Catalogue: A095398 juggler_type=2/3-3/2 | ||
| 124 | |||
| 125 | '3/4-4/3' => 'A095401', | ||
| 126 | # OEIS-Catalogue: A095401 juggler_type=3/4-4/3 | ||
| 127 | }, | ||
| 128 | ); | ||
| 129 | sub oeis_anum { | ||
| 130 | my ($self) = @_; | ||
| 131 | return $oeis_anum{$self->{'step_type'}}->{$self->{'juggler_type'}}; | ||
| 132 | } | ||
| 133 | |||
| 134 | #------------------------------------------------------------------------------ | ||
| 135 | |||
| 136 | sub rewind { | ||
| 137 | my ($self) = @_; | ||
| 138 | ($self->{'epow'},$self->{'eroot'}, $self->{'opow'},$self->{'oroot'}) | ||
| 139 | = ($self->{'juggler_type'} =~ m{(\d+)/(\d+)-(\d+)/(\d+)}); | ||
| 140 | $self->{'i'} = i_start(); | ||
| 141 | } | ||
| 142 | |||
| 143 | use constant 1.02; # for leading underscore | ||
| 144 | use constant _UV_3_2_LIMIT => do { | ||
| 145 | my $limit = ~0; | ||
| 146 | my $bits = 0; | ||
| 147 | while ($limit) { | ||
| 148 | $bits++; | ||
| 149 | $limit >>= 1; | ||
| 150 | } | ||
| 151 | $bits = int($bits / 3); | ||
| 152 | (1 << $bits) - 1 | ||
| 153 | }; | ||
| 154 | |||
| 155 | my %cache_upto; | ||
| 156 | sub next { | ||
| 157 | my ($self) = @_; | ||
| 158 | ### JugglerSteps next(): $self->{'i'} | ||
| 159 | |||
| 160 | my $i = $self->{'i'}++; | ||
| 161 | my $pkey = ($self->{'pkey'} ||= do { | ||
| 162 | ### make pkey ... | ||
| 163 | my $k = make_key('JugglerSteps', | ||
| 164 | $self->{'juggler_type'}, | ||
| 165 | $self->{'step_type'}); | ||
| 166 | $cache_upto{$k} ||= 0; | ||
| 167 | $k | ||
| 168 | }); | ||
| 169 | my $key_i = $pkey . $i; | ||
| 170 | |||
| 171 | ### $pkey | ||
| 172 | ### $key_i | ||
| 173 | ### cache upto: "$cache_upto{$pkey} cf i=$i" | ||
| 174 | |||
| 175 | if ($i < $cache_upto{$pkey}) { | ||
| 176 | ### fetch from cache ... | ||
| 177 | return ($i, cache_hash()->{$key_i}); | ||
| 178 | } else { | ||
| 179 | ### store to cache ... | ||
| 180 | my $ret = $self->ith($i); | ||
| 181 | cache_hash()->{$key_i} = $ret; | ||
| 182 | $cache_upto{$pkey} = $i; | ||
| 183 | ### cache upto now: $cache_upto{$pkey} | ||
| 184 | return ($i, $ret); | ||
| 185 | } | ||
| 186 | } | ||
| 187 | |||
| 188 | sub ith { | ||
| 189 | my ($self, $i) = @_; | ||
| 190 | ### JugglerSteps ith(): $i | ||
| 191 | my $count = 0; | ||
| 192 | if ($i <= 1) { | ||
| 193 | return $count; | ||
| 194 | } | ||
| 195 | |||
| 196 | my $pkey = $self->{'pkey'}; | ||
| 197 | my $step_type = $self->{'step_type'}; | ||
| 198 | my $count_up = ($step_type ne 'down'); | ||
| 199 | my $count_down = ($step_type ne 'up'); | ||
| 200 | my %seen; | ||
| 201 | |||
| 202 | if ($self->{'juggler_type'} eq '1/2-3/2') { | ||
| 203 | ### 1/2 and 3/2 ... | ||
| 204 | for (;;) { | ||
| 205 | if ($pkey && $i < $cache_upto{$pkey}) { | ||
| 206 | my $c = cache_hash()->{$pkey.$i}; | ||
| 207 | ### from cache: "$c at i=$i" | ||
| 208 | if ($c < 0) { | ||
| 209 | return $c; | ||
| 210 | } else { | ||
| 211 | return $c + $count; | ||
| 212 | } | ||
| 213 | } | ||
| 214 | |||
| 215 | if ($i & 1) { | ||
| 216 | ### 1/2 odd: $i | ||
| 217 | |||
| 218 | if ($i > _UV_3_2_LIMIT) { | ||
| 219 | $i = Math::NumSeq::_to_bigint($i); | ||
| 220 | ### using bigint: "$i" | ||
| 221 | for (;;) { | ||
| 222 | if ($pkey && $i < $cache_upto{$pkey}) { | ||
| 223 | my $c = cache_hash()->{$pkey.$i}; | ||
| 224 | ### from cache: "$c at i=$i" | ||
| 225 | if ($c < 0) { | ||
| 226 | return $c; | ||
| 227 | } else { | ||
| 228 | return $c + $count; | ||
| 229 | } | ||
| 230 | } | ||
| 231 | |||
| 232 | if ($i & 1) { | ||
| 233 | ### 1/2 odd: "$i" | ||
| 234 | $i->bmul($i*$i); | ||
| 235 | $count += $count_up; | ||
| 236 | } else { | ||
| 237 | ### 1/2 even: "$i" | ||
| 238 | $count += $count_down; | ||
| 239 | } | ||
| 240 | $i->bsqrt(); | ||
| 241 | if ($i <= 1) { | ||
| 242 | return $count; | ||
| 243 | } | ||
| 244 | ### now: "$i count=$count" | ||
| 245 | if ($seen{$i}++) { | ||
| 246 | ### repeat of bigint: $i | ||
| 247 | return -1; | ||
| 248 | } | ||
| 249 | } | ||
| 250 | } | ||
| 251 | |||
| 252 | $i *= $i*$i; | ||
| 253 | $count += $count_up; | ||
| 254 | } else { | ||
| 255 | ### even: $i | ||
| 256 | $count += $count_down; | ||
| 257 | } | ||
| 258 | $i = int(sqrt($i)); | ||
| 259 | if ($i <= 1) { | ||
| 260 | return $count; | ||
| 261 | } | ||
| 262 | ### now: "$i count=$count" | ||
| 263 | if ($seen{$i}++) { | ||
| 264 | return -1; | ||
| 265 | } | ||
| 266 | } | ||
| 267 | |||
| 268 | } else { | ||
| 269 | ### general case: "$self->{'epow'}/$self->{'eroot'}-$self->{'opow'}/$self->{'oroot'}" | ||
| 270 | $i = Math::NumSeq::_to_bigint($i); | ||
| 271 | |||
| 272 | unless (($self->{'opow'} % $self->{'oroot'}) | ||
| 273 | && ($self->{'epow'} % $self->{'eroot'})) { | ||
| 274 | return -1; | ||
| 275 | } | ||
| 276 | |||
| 277 | for (;;) { | ||
| 278 | if ($pkey && $i < $cache_upto{$pkey}) { | ||
| 279 | my $c = cache_hash()->{$pkey.$i}; | ||
| 280 | ### from cache: "$c at i=$i" | ||
| 281 | if ($c < 0) { | ||
| 282 | return $c; | ||
| 283 | } else { | ||
| 284 | return $c + $count; | ||
| 285 | } | ||
| 286 | } | ||
| 287 | |||
| 288 | if ($i->is_odd) { | ||
| 289 | ### odd: "$i" | ||
| 290 | $i->bpow($self->{'opow'}); | ||
| 291 | $i->broot($self->{'oroot'}); | ||
| 292 | $count += $count_up; | ||
| 293 | } else { | ||
| 294 | ### even: "$i" | ||
| 295 | $i->bpow($self->{'epow'}); | ||
| 296 | $i->broot($self->{'eroot'}); | ||
| 297 | $count += $count_down; | ||
| 298 | } | ||
| 299 | if ($i <= 1) { | ||
| 300 | return $count; | ||
| 301 | } | ||
| 302 | ### now: "$i count=$count" | ||
| 303 | if ($seen{$i}++) { | ||
| 304 | ### repeat of: $i | ||
| 305 | return -1; | ||
| 306 | } | ||
| 307 | } | ||
| 308 | } | ||
| 309 | } | ||
| 310 | |||
| 311 | sub pred { | ||
| 312 | my ($self, $value) = @_; | ||
| 313 | return ($value == int($value) | ||
| 314 | && $value >= 0); | ||
| 315 | } | ||
| 316 | |||
| 317 | 1; | ||
| 318 | __END__ |