File Coverage

blib/lib/Math/GrahamFunction.pm
Criterion Covered Total %
statement 128 128 100.0
branch 34 36 94.4
condition 8 9 88.8
subroutine 26 26 100.0
pod 1 1 100.0
total 197 200 98.5


line stmt bran cond sub pod time code
1             package Math::GrahamFunction;
2             $Math::GrahamFunction::VERSION = '0.02003';
3 2     2   136700 use warnings;
  2         25  
  2         74  
4 2     2   12 use strict;
  2         4  
  2         41  
5              
6 2     2   46 use 5.008;
  2         6  
7              
8              
9 2     2   937 use parent qw(Math::GrahamFunction::Object);
  2         606  
  2         12  
10              
11 2     2   946 use Math::GrahamFunction::SqFacts;
  2         5  
  2         10  
12 2     2   959 use Math::GrahamFunction::SqFacts::Dipole;
  2         7  
  2         12  
13              
14             __PACKAGE__->mk_accessors(
15             qw(
16             _base
17             n
18             _n_vec
19             next_id
20             _n_sq_factors
21             primes_to_ids_map
22             )
23             );
24              
25             sub _initialize
26             {
27 100     100   169 my $self = shift;
28 100         188 my $args = shift;
29              
30             $self->n( $args->{n} )
31 100 50       318 or die "n was not specified";
32              
33 100         1516 $self->primes_to_ids_map( {} );
34              
35 100         1039 return 0;
36             }
37              
38              
39             sub _get_num_facts
40             {
41 844     844   1356 my ( $self, $number ) = @_;
42              
43 844         2590 return Math::GrahamFunction::SqFacts->new( { 'n' => $number } );
44             }
45              
46             sub _get_facts
47             {
48 745     745   1590 my ( $self, $factors ) = @_;
49              
50 745 50       2671 return Math::GrahamFunction::SqFacts->new(
51             { 'factors' => ( ref($factors) eq "ARRAY" ? $factors : [$factors] ) } );
52             }
53              
54             sub _get_num_dipole
55             {
56 745     745   2163 my ( $self, $number ) = @_;
57              
58 745         1451 return Math::GrahamFunction::SqFacts::Dipole->new(
59             {
60             'result' => $self->_get_num_facts($number),
61             'compose' => $self->_get_facts($number),
62             }
63             );
64              
65             }
66              
67             sub _calc_n_sq_factors
68             {
69 100     100   156 my $self = shift;
70              
71 100         212 $self->_n_sq_factors( $self->_get_num_dipole( $self->n ) );
72             }
73              
74             sub _check_largest_factor_in_between
75             {
76 90     90   1031 my $self = shift;
77              
78 90         199 my $n = $self->n();
79              
80             # Cheating:
81             # Check if between n and n+largest_factor we can fit
82             # a square of SqFact{n*(n+largest_factor)}. If so, return
83             # n+largest_factor.
84             #
85             # So, for instance, if n = p than n+largest_factor = 2p
86             # and so SqFact{p*(2p)} = 2 and it is possible to see if
87             # there's a 2*i^2 between p and 2p. That way, p*2*i^2*2p is
88             # a square number.
89              
90 90         842 my $largest_factor = $self->_n_sq_factors()->last();
91              
92 90         1565 my ( $lower_bound, $lb_sq_factors );
93              
94 90         208 $lower_bound = $self->n() + $largest_factor;
95 90         839 while (1)
96             {
97 99         195 $lb_sq_factors = $self->_get_num_facts($lower_bound);
98 99 100       279 if ( $lb_sq_factors->exists($largest_factor) )
99             {
100 90         173 last;
101             }
102 9         86 $lower_bound += $largest_factor;
103             }
104              
105 90         329 my $n_times_lb = $self->_n_sq_factors->result->mult($lb_sq_factors);
106              
107 90         238 my $rest_of_factors_product = $n_times_lb->product();
108              
109 90         934 my $low_square_val = int( sqrt( $n / $rest_of_factors_product ) );
110 90         171 my $high_square_val =
111             int( sqrt( $lower_bound / $rest_of_factors_product ) );
112              
113 90 100       195 if ( $low_square_val != $high_square_val )
114             {
115 44         137 my @factors = (
116             $n,
117             ( $low_square_val + 1 ) *
118             ( $low_square_val + 1 ) *
119             $rest_of_factors_product,
120             $lower_bound
121             );
122              
123             # TODO - possibly convert to Dipole
124             # return ($lower_bound, $self->_get_facts(\@factors));
125 44         222 return \@factors;
126             }
127             else
128             {
129 46         177 return;
130             }
131             }
132              
133             sub _get_next_id
134             {
135 416     416   569 my $self = shift;
136 416         796 return $self->next_id( $self->next_id() + 1 );
137             }
138              
139             sub _get_prime_id
140             {
141 2118     2118   2917 my $self = shift;
142 2118         2807 my $p = shift;
143 2118         3793 return $self->primes_to_ids_map()->{$p};
144             }
145              
146             sub _register_prime
147             {
148 416     416   690 my ( $self, $p ) = @_;
149 416         700 $self->primes_to_ids_map()->{$p} = $self->_get_next_id();
150             }
151              
152             sub _prime_exists
153             {
154 819     819   1400 my ( $self, $p ) = @_;
155 819         1482 return exists( $self->primes_to_ids_map->{$p} );
156             }
157              
158             sub _get_min_id
159             {
160 1017     1017   5822 my ( $self, $vec ) = @_;
161              
162 1017         1379 my $min_id = -1;
163 1017         1416 my $min_p = 0;
164              
165 1017         1363 foreach my $p ( @{ $vec->result()->factors() } )
  1017         1956  
166             {
167 1637         17051 my $id = $self->_get_prime_id($p);
168 1637 100 100     16875 if ( ( $min_id < 0 ) || ( $min_id > $id ) )
169             {
170 1144         1587 $min_id = $id;
171 1144         1847 $min_p = $p;
172             }
173             }
174              
175 1017         2689 return ( $min_id, $min_p );
176             }
177              
178             sub _try_to_form_n
179             {
180 444     444   654 my $self = shift;
181              
182 444         916 while ( !$self->_n_vec->is_square() )
183             {
184             # Calculating $id as the minimal ID of the squaring factors of $p
185 573         6056 my ( $id, undef ) = $self->_get_min_id( $self->_n_vec );
186              
187             # Multiply by the controlling vector of this ID if it exists
188             # or terminate if it doesn't.
189 573 100       1163 return 0 if ( !defined( $self->_base->[$id] ) );
190 175         1811 $self->_n_vec->mult_by( $self->_base->[$id] );
191             }
192              
193 46         487 return 1;
194             }
195              
196             sub _get_final_factors
197             {
198 100     100   156 my $self = shift;
199              
200 100         248 $self->_calc_n_sq_factors();
201              
202             # The graham number of a perfect square is itself.
203 100 100       1051 if ( $self->_n_sq_factors->is_square() )
    100          
204             {
205 10         112 return $self->_n_sq_factors->_get_ret();
206             }
207             elsif ( defined( my $ret = $self->_check_largest_factor_in_between() ) )
208             {
209 44         167 return $ret;
210             }
211             else
212             {
213 46         112 return $self->_main_solve();
214             }
215             }
216              
217             sub solve
218             {
219 100     100 1 401 my $self = shift;
220              
221 100         228 return { factors => $self->_get_final_factors() };
222             }
223              
224             sub _main_init
225             {
226 46     46   70 my $self = shift;
227              
228 46         120 $self->next_id(0);
229              
230 46         498 $self->_base( [] );
231              
232             # Register all the primes in the squaring factors of $n
233 46         449 foreach my $p ( @{ $self->_n_sq_factors->factors() } )
  46         95  
234             {
235 78         1566 $self->_register_prime($p);
236             }
237              
238             # $self->_n_vec is used to determine if $n can be composed out of the
239             # base's vectors.
240 46         1190 $self->_n_vec( $self->_n_sq_factors->clone() );
241              
242 46         446 return;
243             }
244              
245              
246             sub _update_base
247             {
248 444     444   796 my ( $self, $final_vec ) = @_;
249              
250             # Get the minimal ID and its corresponding prime number
251             # in $final_vec.
252 444         824 my ( $min_id, $min_p ) = $self->_get_min_id($final_vec);
253              
254 444 100       1010 if ( $min_id >= 0 )
255             {
256             # Assign $final_vec as the controlling vector for this prime
257             # number
258 411         844 $self->_base->[$min_id] = $final_vec;
259              
260             # Canonicalize the rest of the vectors with the new vector.
261             CANON_LOOP:
262 411         4332 for my $j ( keys @{ $self->_base } )
  411         722  
263             {
264 3161 100 100     10955 if ( ( $j == $min_id ) || ( !defined( $self->_base->[$j] ) ) )
265             {
266 1311         10392 next CANON_LOOP;
267             }
268 1850 100       19404 if ( $self->_base->[$j]->exists($min_p) )
269             {
270 414         835 $self->_base->[$j]->mult_by($final_vec);
271             }
272             }
273             }
274             }
275              
276             sub _get_final_composition
277             {
278 444     444   807 my ( $self, $i_vec ) = @_;
279              
280             # $final_vec is the new vector to add after it was
281             # stair-shaped by all the controlling vectors in the base.
282              
283 444         715 my $final_vec = $i_vec;
284              
285 444         604 foreach my $p ( @{ $i_vec->factors() } )
  444         891  
286             {
287 819 100       9827 if ( !$self->_prime_exists($p) )
288             {
289 338         3388 $self->_register_prime($p);
290             }
291             else
292             {
293 481         4929 my $id = $self->_get_prime_id($p);
294 481 100       4673 if ( defined( $self->_base->[$id] ) )
295             {
296 387         3766 $final_vec->mult_by( $self->_base->[$id] );
297             }
298             }
299             }
300              
301 444         7716 return $final_vec;
302             }
303              
304             sub _get_i_vec
305             {
306 645     645   1051 my ( $self, $i ) = @_;
307              
308 645         1184 my $i_vec = $self->_get_num_dipole($i);
309              
310             # Skip perfect squares - they do not add to the solution
311 645 100       1531 if ( $i_vec->is_square() )
312             {
313 45         600 return;
314             }
315              
316             # Check if $i is a prime number
317             # We need n > 2 because for n == 2 it does include a prime number.
318             #
319             # Prime numbers cannot be included because 2*n is an upper bound
320             # to G(n) and so if there is a prime p > n than its next multiple
321             # will be greater than G(n).
322 600 100 66     6484 if ( ( $self->n() > 2 ) && ( $i_vec->first() == $i ) )
323             {
324 156         2111 return;
325             }
326              
327 444         5203 return $i_vec;
328             }
329              
330             sub _solve_iteration
331             {
332 645     645   1142 my ( $self, $i ) = @_;
333              
334 645 100       1159 my $i_vec = $self->_get_i_vec($i)
335             or return;
336              
337 444         852 my $final_vec = $self->_get_final_composition($i_vec);
338              
339 444         1079 $self->_update_base($final_vec);
340              
341             # Check if we can form $n
342 444 100       973 if ( $self->_try_to_form_n() )
343             {
344 46         98 return $self->_n_vec->_get_ret();
345             }
346             else
347             {
348 398         4726 return;
349             }
350             }
351              
352             sub _main_solve
353             {
354 46     46   88 my $self = shift;
355              
356 46         109 $self->_main_init();
357              
358 46         100 for ( my $i = $self->n() + 1 ; ; ++$i )
359             {
360 645 100       1576 if ( defined( my $ret = $self->_solve_iteration($i) ) )
361             {
362 46         1088 return $ret;
363             }
364             }
365             }
366              
367              
368             1; # End of Math::GrahamFunction
369              
370             __END__