| 1 | # Copyright 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 | |||||||||||
| 19 | # http://oeis.org/wiki/Lucky_numbers | ||||||||||
| 20 | # | ||||||||||
| 21 | # Gardiner, R. Lazarus, N. Metropolis and S. Ulam,"On certain sequences of | ||||||||||
| 22 | # integers defined by sieves", Mathematics Magazine 29:3 (1955), | ||||||||||
| 23 | # pp. 117-122. | ||||||||||
| 24 | |||||||||||
| 25 | |||||||||||
| 26 | package Math::NumSeq::LuckyNumbers; | ||||||||||
| 27 | 2 | ▶ | use 5.004; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 28 | 2 | ▶ | use strict; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 29 | |||||||||||
| 30 | 2 | ▶ | use vars '$VERSION','@ISA'; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 31 | 2 | $VERSION = 75; | |||||||||
| 32 | |||||||||||
| 33 | 2 | ▶ | use Math::NumSeq 7; # v.7 for _is_infinite() | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 34 | 2 | @ISA = ('Math::NumSeq'); | |||||||||
| 35 | 2 | *_is_infinite = \&Math::NumSeq::_is_infinite; | |||||||||
| 36 | |||||||||||
| 37 | # uncomment this to run the ### lines | ||||||||||
| 38 | # use Smart::Comments; | ||||||||||
| 39 | |||||||||||
| 40 | |||||||||||
| 41 | # use constant name => Math::NumSeq::__('Lucky Numbers'); | ||||||||||
| 42 | 2 | ▶ | use constant description => Math::NumSeq::__('Sieved out multiples according to the sequence itself.'); | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 43 | 2 | ▶ | use constant values_min => 1; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 44 | 2 | ▶ | use constant i_start => 1; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 45 | 2 | ▶ | use constant characteristic_increasing => 1; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 46 | 2 | ▶ | use constant characteristic_integer => 1; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 47 | |||||||||||
| 48 | #------------------------------------------------------------------------------ | ||||||||||
| 49 | # cf A145649 - 0,1 characteristic of Lucky numbers | ||||||||||
| 50 | # A050505 - complement, the non-Lucky numbers | ||||||||||
| 51 | # | ||||||||||
| 52 | # A007951 - ternary sieve, dropping 3rd, 6th, 9th, etc | ||||||||||
| 53 | # 1,2,_,4,5,_,7,8,_,10,11,_,12,13,_,14,15,_ | ||||||||||
| 54 | # ^9th | ||||||||||
| 55 | # 1,2,4,5,7,8,10,11,14,16,17,19,20,22,23,25,28,29,31,32,34,35,37,38,41, | ||||||||||
| 56 | # | ||||||||||
| 57 | 2 | ▶ | use constant oeis_anum => 'A000959'; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 58 | |||||||||||
| 59 | #------------------------------------------------------------------------------ | ||||||||||
| 60 | |||||||||||
| 61 | # i=22 | ||||||||||
| 62 | # mod: '8,12,14,20,24' | ||||||||||
| 63 | # int(21/24)=0 to i=21 | ||||||||||
| 64 | # int(21/20)=1 to i=22 | ||||||||||
| 65 | # int(22/14)=1 to i=23 two_pos=2 three_pos=1 | ||||||||||
| 66 | # int(23/12)=1 to i=24 | ||||||||||
| 67 | # int(24/8)=3 to i=27 | ||||||||||
| 68 | # int(27/6)=4 to i=31 | ||||||||||
| 69 | # int(31/2)=15 to i=46 | ||||||||||
| 70 | # 2*46+1=93 | ||||||||||
| 71 | # | ||||||||||
| 72 | # i+1 then twos advance for +1 more = +2 | ||||||||||
| 73 | # threes advance | ||||||||||
| 74 | # i>3*mod[pos] i-=2 pos++ | ||||||||||
| 75 | # i-2>3*mod[pos+1] | ||||||||||
| 76 | # 3*2 | ||||||||||
| 77 | |||||||||||
| 78 | 5 | ▶ | sub rewind { | ||||||||
|
Subroutine
rewind: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||
| 79 | 5 | my ($self) = @_; | |||||||||
| 80 | 5 | $self->{'i'} = $self->i_start; | |||||||||
| 81 | 5 | $self->{'mod'} = [ 8 ]; | |||||||||
| 82 | 5 | $self->{'mod_pos'} = 0; | |||||||||
| 83 | 5 | $self->{'one_pos'} = 0; | |||||||||
| 84 | 5 | $self->{'two_pos'} = 0; | |||||||||
| 85 | 5 | $self->{'three_pos'} = 0; | |||||||||
| 86 | } | ||||||||||
| 87 | |||||||||||
| 88 | 2 | my @twelve = (1,3, | |||||||||
| 89 | 7,9, | ||||||||||
| 90 | 13,15, | ||||||||||
| 91 | 21, | ||||||||||
| 92 | 25,27, | ||||||||||
| 93 | 31,33, | ||||||||||
| 94 | 37 | ||||||||||
| 95 | ); | ||||||||||
| 96 | |||||||||||
| 97 | 189 | ▶ | sub next { | ||||||||
|
Subroutine
next: called CC=5 SCAR=16.1
Pod
documented
| |||||||||||
| 98 | 189 | my ($self) = @_; | |||||||||
| 99 | ### LuckyNumbers next(): "i=$self->{'i'}" | ||||||||||
| 100 | |||||||||||
| 101 | 189 | my $ret_i = $self->{'i'}++; | |||||||||
| 102 | 189 | my $i = $ret_i - 1; | |||||||||
| 103 | 189 | my $mod = $self->{'mod'}; | |||||||||
| 104 | 189 | ▶ | if ($i >= $mod->[-1]) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 105 | ### extend mod ... | ||||||||||
| 106 | 35 | my $mod_i = $#$mod + 4; | |||||||||
| 107 | 35 | my $mod_pos = $self->{'mod_pos'}; | |||||||||
| 108 | 35 | ▶ | if ($mod_i >= $mod->[$mod_pos]) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 109 | 7 | $self->{'mod_pos'} = ++$mod_pos; | |||||||||
| 110 | } | ||||||||||
| 111 | 35 | push @$mod, _ith_by_mod($mod, $mod_i, $mod_pos) - 1; | |||||||||
| 112 | } | ||||||||||
| 113 | |||||||||||
| 114 | # my $one_pos = $#$mod; | ||||||||||
| 115 | 189 | my $two_pos = $self->{'two_pos'}; | |||||||||
| 116 | |||||||||||
| 117 | ### mod: join(',',@{$self->{'mod'}}) | ||||||||||
| 118 | ### at: "i=$i one_pos=$#$mod two_pos=$self->{'two_pos'} diff=".($#$mod - $two_pos) | ||||||||||
| 119 | |||||||||||
| 120 | 189 | $i += $#$mod - $two_pos; | |||||||||
| 121 | ### after ones: "i=$i cmp ".(2*$mod->[$two_pos]) | ||||||||||
| 122 | |||||||||||
| 123 | 189 | ▶ | if ($i > 2*$mod->[$two_pos]) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 124 | ### advance two ... | ||||||||||
| 125 | 19 | $self->{'two_pos'} = ++$two_pos; | |||||||||
| 126 | 19 | $i--; | |||||||||
| 127 | } | ||||||||||
| 128 | ### after twos: "i=$i two_pos=$two_pos three_pos=$self->{'three_pos'}" | ||||||||||
| 129 | |||||||||||
| 130 | 189 | my $three_pos = $self->{'three_pos'}; | |||||||||
| 131 | 189 | $i += 2*($two_pos - $three_pos); | |||||||||
| 132 | ### increased i with twos: $i | ||||||||||
| 133 | |||||||||||
| 134 | ### cmp: "i=$i three_pos=$three_pos cmp ".(3*$mod->[$three_pos]) | ||||||||||
| 135 | 189 | ▶ | if ($i > 3*$mod->[$three_pos]) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 136 | ### advance three ... | ||||||||||
| 137 | 11 | $self->{'three_pos'} = ++$three_pos; | |||||||||
| 138 | 11 | $i -= 2; | |||||||||
| 139 | } | ||||||||||
| 140 | |||||||||||
| 141 | 189 | return ($ret_i, | |||||||||
| 142 | _ith_by_mod($mod, $i, $three_pos)); | ||||||||||
| 143 | } | ||||||||||
| 144 | |||||||||||
| 145 | 224 | ▶ | sub _ith_by_mod { | ||||||||
|
Subroutine
_ith_by_mod: called CC=2 SCAR=6.9
| |||||||||||
| 146 | 224 | my ($mod, $i, $pos) = @_; | |||||||||
| 147 | ### _ith_by_mod(): "i=$i pos=$pos is mods=".join(',',@{$mod}[0..$pos-1]) | ||||||||||
| 148 | |||||||||||
| 149 | 224 | ▶ | while (--$pos >= 0) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 150 | ### at: "pos=$pos i=$i" | ||||||||||
| 151 | 954 | $i += int($i / $mod->[$pos]); | |||||||||
| 152 | } | ||||||||||
| 153 | ### final: "i=$i result=".(int($i/12)*21 + $twelve[$i%12]) | ||||||||||
| 154 | 224 | return int($i/12)*42 + $twelve[$i%12]; | |||||||||
| 155 | } | ||||||||||
| 156 | |||||||||||
| 157 | # i~=value/log(value) | ||||||||||
| 158 | # | ||||||||||
| 159 | 2 | ▶ | use Math::NumSeq::Primes; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 160 | 2 | *value_to_i_estimate = \&Math::NumSeq::Primes::value_to_i_estimate; | |||||||||
| 161 | |||||||||||
| 162 | 2 | 1; | |||||||||
| 163 | __END__ | ||||||||||