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.02002';
3 2     2   143767 use warnings;
  2         18  
  2         124  
4 2     2   14 use strict;
  2         4  
  2         46  
5              
6 2     2   45 use 5.008;
  2         8  
7              
8              
9 2     2   1020 use parent qw(Math::GrahamFunction::Object);
  2         688  
  2         10  
10              
11 2     2   1006 use Math::GrahamFunction::SqFacts;
  2         6  
  2         9  
12 2     2   956 use Math::GrahamFunction::SqFacts::Dipole;
  2         6  
  2         12  
13              
14             __PACKAGE__->mk_accessors(qw(
15             _base
16             n
17             _n_vec
18             next_id
19             _n_sq_factors
20             primes_to_ids_map
21             ));
22              
23             sub _initialize
24             {
25 100     100   162 my $self = shift;
26 100         153 my $args = shift;
27              
28 100 50       280 $self->n($args->{n}) or
29             die "n was not specified";
30              
31 100         1498 $self->primes_to_ids_map({});
32              
33 100         1027 return 0;
34             }
35              
36              
37             sub _get_num_facts
38             {
39 844     844   1437 my ($self, $number) = @_;
40              
41 844         2494 return Math::GrahamFunction::SqFacts->new({ 'n' => $number });
42             }
43              
44             sub _get_facts
45             {
46 745     745   1389 my ($self, $factors) = @_;
47              
48             return
49 745 50       2923 Math::GrahamFunction::SqFacts->new(
50             { 'factors' =>
51             (ref($factors) eq "ARRAY" ? $factors : [$factors])
52             }
53             );
54             }
55              
56             sub _get_num_dipole
57             {
58 745     745   2136 my ($self, $number) = @_;
59              
60 745         1553 return Math::GrahamFunction::SqFacts::Dipole->new(
61             {
62             'result' => $self->_get_num_facts($number),
63             'compose' => $self->_get_facts($number),
64             }
65             );
66              
67             }
68              
69             sub _calc_n_sq_factors
70             {
71 100     100   169 my $self = shift;
72              
73 100         216 $self->_n_sq_factors(
74             $self->_get_num_dipole($self->n)
75             );
76             }
77              
78             sub _check_largest_factor_in_between
79             {
80 90     90   1000 my $self = shift;
81              
82 90         171 my $n = $self->n();
83             # Cheating:
84             # Check if between n and n+largest_factor we can fit
85             # a square of SqFact{n*(n+largest_factor)}. If so, return
86             # n+largest_factor.
87             #
88             # So, for instance, if n = p than n+largest_factor = 2p
89             # and so SqFact{p*(2p)} = 2 and it is possible to see if
90             # there's a 2*i^2 between p and 2p. That way, p*2*i^2*2p is
91             # a square number.
92              
93 90         853 my $largest_factor = $self->_n_sq_factors()->last();
94              
95 90         1495 my ($lower_bound, $lb_sq_factors);
96              
97 90         188 $lower_bound = $self->n() + $largest_factor;
98 90         819 while (1)
99             {
100 99         172 $lb_sq_factors = $self->_get_num_facts($lower_bound);
101 99 100       285 if ($lb_sq_factors->exists($largest_factor))
102             {
103 90         188 last;
104             }
105 9         83 $lower_bound += $largest_factor;
106             }
107              
108 90         343 my $n_times_lb = $self->_n_sq_factors->result->mult($lb_sq_factors);
109              
110 90         215 my $rest_of_factors_product = $n_times_lb->product();
111              
112 90         950 my $low_square_val = int(sqrt($n/$rest_of_factors_product));
113 90         167 my $high_square_val = int(sqrt($lower_bound/$rest_of_factors_product));
114              
115 90 100       184 if ($low_square_val != $high_square_val)
116             {
117 44         128 my @factors =
118             (
119             $n,
120             ($low_square_val+1)*($low_square_val+1)*$rest_of_factors_product,
121             $lower_bound
122             );
123             # TODO - possibly convert to Dipole
124             # return ($lower_bound, $self->_get_facts(\@factors));
125 44         185 return \@factors;
126             }
127             else
128             {
129 46         164 return;
130             }
131             }
132              
133             sub _get_next_id
134             {
135 416     416   581 my $self = shift;
136 416         783 return $self->next_id($self->next_id()+1);
137             }
138              
139             sub _get_prime_id
140             {
141 2118     2118   2986 my $self = shift;
142 2118         2918 my $p = shift;
143 2118         3783 return $self->primes_to_ids_map()->{$p};
144             }
145              
146             sub _register_prime
147             {
148 416     416   763 my ($self, $p) = @_;
149 416         702 $self->primes_to_ids_map()->{$p} = $self->_get_next_id();
150             }
151              
152             sub _prime_exists
153             {
154 819     819   1389 my ($self, $p) = @_;
155 819         1486 return exists($self->primes_to_ids_map->{$p});
156             }
157              
158             sub _get_min_id
159             {
160 1017     1017   5939 my ($self, $vec) = @_;
161              
162 1017         1467 my $min_id = -1;
163 1017         1436 my $min_p = 0;
164              
165 1017         1467 foreach my $p (@{$vec->result()->factors()})
  1017         1903  
166             {
167 1637         17429 my $id = $self->_get_prime_id($p);
168 1637 100 100     16989 if (($min_id < 0) || ($min_id > $id))
169             {
170 1144         1720 $min_id = $id;
171 1144         1873 $min_p = $p;
172             }
173             }
174              
175 1017         2605 return ($min_id, $min_p);
176             }
177              
178             sub _try_to_form_n
179             {
180 444     444   634 my $self = shift;
181              
182 444         918 while (! $self->_n_vec->is_square())
183             {
184             # Calculating $id as the minimal ID of the squaring factors of $p
185 573         6127 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       1224 return 0 if (!defined($self->_base->[$id]));
190 175         1746 $self->_n_vec->mult_by($self->_base->[$id]);
191             }
192              
193 46         830 return 1;
194             }
195              
196             sub _get_final_factors
197             {
198 100     100   164 my $self = shift;
199              
200 100         241 $self->_calc_n_sq_factors();
201              
202             # The graham number of a perfect square is itself.
203 100 100       1107 if ($self->_n_sq_factors->is_square())
    100          
204             {
205 10         120 return $self->_n_sq_factors->_get_ret();
206             }
207             elsif (defined(my $ret = $self->_check_largest_factor_in_between()))
208             {
209 44         178 return $ret;
210             }
211             else
212             {
213 46         108 return $self->_main_solve();
214             }
215             }
216              
217             sub solve
218             {
219 100     100 1 378 my $self = shift;
220              
221 100         209 return { factors => $self->_get_final_factors() };
222             }
223              
224             sub _main_init
225             {
226 46     46   68 my $self = shift;
227              
228 46         121 $self->next_id(0);
229              
230 46         504 $self->_base([]);
231              
232             # Register all the primes in the squaring factors of $n
233 46         431 foreach my $p (@{$self->_n_sq_factors->factors()})
  46         106  
234             {
235 78         1674 $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         1164 $self->_n_vec($self->_n_sq_factors->clone());
241              
242 46         461 return;
243             }
244              
245              
246             sub _update_base
247             {
248 444     444   774 my ($self, $final_vec) = @_;
249              
250             # Get the minimal ID and its corresponding prime number
251             # in $final_vec.
252 444         868 my ($min_id, $min_p) = $self->_get_min_id($final_vec);
253              
254 444 100       977 if ($min_id >= 0)
255             {
256             # Assign $final_vec as the controlling vector for this prime
257             # number
258 411         828 $self->_base->[$min_id] = $final_vec;
259             # Canonicalize the rest of the vectors with the new vector.
260             CANON_LOOP:
261 411         3986 for(my $j=0;$j_base()});$j++)
  3572         6707  
262             {
263 3161 100 100     32282 if (($j == $min_id) || (! defined($self->_base->[$j])))
264             {
265 1311         10193 next CANON_LOOP;
266             }
267 1850 100       18975 if ($self->_base->[$j]->exists($min_p))
268             {
269 414         821 $self->_base->[$j]->mult_by($final_vec);
270             }
271             }
272             }
273             }
274              
275             sub _get_final_composition
276             {
277 444     444   801 my ($self, $i_vec) = @_;
278              
279             # $final_vec is the new vector to add after it was
280             # stair-shaped by all the controlling vectors in the base.
281              
282 444         654 my $final_vec = $i_vec;
283              
284 444         598 foreach my $p (@{$i_vec->factors()})
  444         898  
285             {
286 819 100       9953 if (!$self->_prime_exists($p))
287             {
288 338         3549 $self->_register_prime($p);
289             }
290             else
291             {
292 481         4991 my $id = $self->_get_prime_id($p);
293 481 100       4631 if (defined($self->_base->[$id]))
294             {
295 387         3774 $final_vec->mult_by($self->_base->[$id]);
296             }
297             }
298             }
299              
300 444         7728 return $final_vec;
301             }
302              
303             sub _get_i_vec
304             {
305 645     645   1156 my ($self, $i) = @_;
306              
307 645         1171 my $i_vec = $self->_get_num_dipole($i);
308             # Skip perfect squares - they do not add to the solution
309 645 100       1630 if ($i_vec->is_square())
310             {
311 45         635 return;
312             }
313              
314             # Check if $i is a prime number
315             # We need n > 2 because for n == 2 it does include a prime number.
316             #
317             # Prime numbers cannot be included because 2*n is an upper bound
318             # to G(n) and so if there is a prime p > n than its next multiple
319             # will be greater than G(n).
320 600 100 66     6385 if (($self->n() > 2) && ($i_vec->first() == $i))
321             {
322 156         2143 return;
323             }
324              
325 444         5026 return $i_vec;
326             }
327              
328             sub _solve_iteration
329             {
330 645     645   1118 my ($self, $i) = @_;
331              
332 645 100       1120 my $i_vec = $self->_get_i_vec($i)
333             or return;
334              
335 444         814 my $final_vec = $self->_get_final_composition($i_vec);
336              
337 444         1031 $self->_update_base($final_vec);
338              
339             # Check if we can form $n
340 444 100       4334 if ($self->_try_to_form_n())
341             {
342 46         92 return $self->_n_vec->_get_ret();
343             }
344             else
345             {
346 398         4652 return;
347             }
348             }
349              
350             sub _main_solve
351             {
352 46     46   66 my $self = shift;
353              
354 46         111 $self->_main_init();
355              
356 46         97 for(my $i=$self->n()+1;;$i++)
357             {
358 645 100       1592 if (defined(my $ret = $self->_solve_iteration($i)))
359             {
360 46         970 return $ret;
361             }
362             }
363             }
364              
365              
366             1; # End of Math::GrahamFunction
367              
368             __END__