1#!/usr/bin/env perl 2use strict; 3use warnings; 4 5use Test::More; 6use Math::Prime::Util qw/primes prev_prime next_prime 7 forprimes forcomposites foroddcomposites fordivisors 8 forpart forcomp forcomb forperm forderange formultiperm 9 forfactored forsquarefree forsemiprimes 10 forsetproduct 11 lastfor 12 is_power is_semiprime vecsum sqrtint 13 prime_iterator prime_iterator_object/; 14use Math::BigInt try => "GMP,Pari"; 15use Math::BigFloat; 16 17my $use64 = Math::Prime::Util::prime_get_config->{'maxbits'} > 32; 18my $broken64 = (18446744073709550592 == ~0); 19 20plan tests => 8 # forprimes errors 21 + 12 + 7 # forprimes simple 22 + 3 # forcomposites simple 23 + 2 # fordivisors simple 24 + 3 # iterator errors 25 + 7 # iterator simple 26 + 1 # other forprimes 27 + 2 # forprimes/iterator nesting 28 + 3 # forprimes BigInt/BigFloat 29 + 3 # oo iterator errors 30 + 7 # oo iterator simple 31 + 25 # oo iterator methods 32 + 12 # lastfor 33 + 5 # forfactored and forsquarefree 34 + 1 # forsemiprimes 35 + 9 # forsetproduct 36 + 0; 37 38ok(!eval { forprimes { 1 } undef; }, "forprimes undef"); 39ok(!eval { forprimes { 1 } 2, undef; }, "forprimes 2,undef"); 40ok(!eval { forprimes { 1 } undef, 2; }, "forprimes 2,undef"); 41# This is caught at compile type because of the prototype 42#ok(!eval { forprimes { 1 } 2, 3, 4; }, "forprimes 2,3,4"); 43ok(!eval { forprimes { 1 } -2, 3; }, "forprimes -2,3"); 44ok(!eval { forprimes { 1 } 2, -3; }, "forprimes 2,-3"); 45ok(!eval { forprimes { 1 } "abc"; }, "forprimes abc"); 46ok(!eval { forprimes { 1 } 2, "abc"; }, "forprimes 2, abc"); 47ok(!eval { forprimes { 1 } 5.6; }, "forprimes abc"); 48 49{my @t; forprimes {push @t,$_} 1; is_deeply( [@t], [], "forprimes 1" ); } 50{my @t; forprimes {push @t,$_} 2; is_deeply( [@t], [2], "forprimes 3" ); } 51{my @t; forprimes {push @t,$_} 3; is_deeply( [@t], [2,3], "forprimes 3" ); } 52{my @t; forprimes {push @t,$_} 4; is_deeply( [@t], [2,3], "forprimes 4" ); } 53{my @t; forprimes {push @t,$_} 5; is_deeply( [@t], [2,3,5], "forprimes 5" ); } 54{my @t; forprimes {push @t,$_} 3,5; is_deeply( [@t], [3,5], "forprimes 3,5" ); } 55{my @t; forprimes {push @t,$_} 3,6; is_deeply( [@t], [3,5], "forprimes 3,6" ); } 56{my @t; forprimes {push @t,$_} 3,7; is_deeply( [@t], [3,5,7], "forprimes 3,7" ); } 57{my @t; forprimes {push @t,$_} 5,7; is_deeply( [@t], [5,7], "forprimes 5,7" ); } 58{my @t; forprimes {push @t,$_} 6,7; is_deeply( [@t], [7], "forprimes 6,7" ); } 59{my @t; forprimes {push @t,$_} 5,11; is_deeply( [@t], [5,7,11], "forprimes 5,11" ); } 60{my @t; forprimes {push @t,$_} 7,11; is_deeply( [@t], [7,11], "forprimes 7,11" ); } 61 62{ my @t; forprimes { push @t, $_ } 50; 63 is_deeply( [@t], [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47], "forprimes 50" ); 64} 65{ my @t; forprimes { push @t, $_ } 2,20; 66 is_deeply( [@t], [2,3,5,7,11,13,17,19], "forprimes 2,20" ); 67} 68{ my @t; forprimes { push @t, $_ } 20,30; 69 is_deeply( [@t], [23,29], "forprimes 20,30" ); 70} 71{ my @t; forprimes { push @t, $_ } 199, 223; 72 is_deeply( [@t], [199,211,223], "forprimes 199,223" ); 73} 74{ my @t; forprimes { push @t, $_ } 31398, 31468; 75 is_deeply( [@t], [], "forprimes 31398,31468 (empty region)" ); 76} 77{ my @t; forprimes { push @t, $_ } 2147483647,2147483659; 78 is_deeply( [@t], [2147483647,2147483659], "forprimes 2147483647,2147483659" ); 79} 80{ my @t; forprimes { push @t, $_ } 3842610774,3842611326; 81 is_deeply( [@t], [3842611109,3842611139,3842611163,3842611181,3842611211,3842611229,3842611249,3842611259,3842611261,3842611291,3842611301], "forprimes 3842610774,3842611326" ); 82} 83{ my @t; forcomposites { push @t, $_ } 2147483647,2147483659; 84 is_deeply( [@t], [qw/2147483648 2147483649 2147483650 2147483651 2147483652 2147483653 2147483654 2147483655 2147483656 2147483657 2147483658/], "forcomposites 2147483647,2147483659" ); 85} 86{ my @t; forcomposites { push @t, $_ } 50; 87 is_deeply( [@t], [qw/4 6 8 9 10 12 14 15 16 18 20 21 22 24 25 26 27 28 30 32 33 34 35 36 38 39 40 42 44 45 46 48 49 50/], "forcomposites 50" ); 88} 89{ my @t; forcomposites { push @t, $_ } 200,410; 90 is_deeply( [@t], [qw/200 201 202 203 204 205 206 207 208 209 210 212 213 214 215 216 217 218 219 220 221 222 224 225 226 228 230 231 232 234 235 236 237 238 240 242 243 244 245 246 247 248 249 250 252 253 254 255 256 258 259 260 261 262 264 265 266 267 268 270 272 273 274 275 276 278 279 280 282 284 285 286 287 288 289 290 291 292 294 295 296 297 298 299 300 301 302 303 304 305 306 308 309 310 312 314 315 316 318 319 320 321 322 323 324 325 326 327 328 329 330 332 333 334 335 336 338 339 340 341 342 343 344 345 346 348 350 351 352 354 355 356 357 358 360 361 362 363 364 365 366 368 369 370 371 372 374 375 376 377 378 380 381 382 384 385 386 387 388 390 391 392 393 394 395 396 398 399 400 402 403 404 405 406 407 408 410/], "forcomposites 200,410" ); 91} 92{ 93 my $a = 0; 94 fordivisors { $a += $_ + $_*$_ } 54321; 95 is($a, 3287796520, "fordivisors: d|54321: a+=d+d^2"); 96 # Matches Math::Pari: 97 # my $a = PARI(0); my $j; fordiv(54321,$j,sub { $a += $j + $j**2 }); 98} 99{ 100 # Pari: v=List(); for(n=1, 50, fordiv(n, d, listput(v, d))); Vec(v) 101 my @A027750 = (1,1,2,1,3,1,2,4,1,5,1,2,3,6,1,7,1,2,4,8,1,3,9,1,2,5,10,1,11,1,2,3,4,6,12,1,13,1,2,7,14,1,3,5,15,1,2,4,8,16,1,17,1,2,3,6,9,18,1,19,1,2,4,5,10,20,1,3,7,21,1,2,11,22,1,23,1,2,3,4,6,8,12,24,1,5,25,1,2,13,26,1,3,9,27,1,2,4,7,14,28,1,29,1,2,3,5,6,10,15,30,1,31,1,2,4,8,16,32,1,3,11,33,1,2,17,34,1,5,7,35,1,2,3,4,6,9,12,18,36,1,37,1,2,19,38,1,3,13,39,1,2,4,5,8,10,20,40,1,41,1,2,3,6,7,14,21,42,1,43,1,2,4,11,22,44,1,3,5,9,15,45,1,2,23,46,1,47,1,2,3,4,6,8,12,16,24,48,1,7,49,1,2,5,10,25,50); 102 my @a; 103 do { fordivisors { push @a, $_ } $_ } for 1..50; 104 is_deeply(\@a, \@A027750, "A027750 using fordivisors"); 105} 106 107ok(!eval { prime_iterator(-2); }, "iterator -2"); 108ok(!eval { prime_iterator("abc"); }, "iterator abc"); 109ok(!eval { prime_iterator(4.5); }, "iterator 4.5"); 110 111{ my $it = prime_iterator(); 112 is_deeply( [map { $it->() } 1..10], [2,3,5,7,11,13,17,19,23,29], "iterator first 10 primes" ); 113} 114{my $it = prime_iterator(47); 115 is_deeply( [map { $it->() } 1..5], [47,53,59,61,67], "iterator 5 primes starting at 47" ); 116} 117{my $it = prime_iterator(199); 118 is_deeply( [map { $it->() } 1..3], [199,211,223], "iterator 3 primes starting at 199" ); 119} 120{my $it = prime_iterator(200); 121 is_deeply( [map { $it->() } 1..3], [211,223,227], "iterator 3 primes starting at 200" ); 122} 123{my $it = prime_iterator(31397); 124 is_deeply( [map { $it->() } 1..3], [31397,31469,31477], "iterator 3 primes starting at 31397" ); 125} 126{my $it = prime_iterator(31396); 127 is_deeply( [map { $it->() } 1..3], [31397,31469,31477], "iterator 3 primes starting at 31396" ); 128} 129{my $it = prime_iterator(31398); 130 is_deeply( [map { $it->() } 1..3], [31469,31477,31481], "iterator 3 primes starting at 31398" ); 131} 132 133# Make sure things work when the type of $_ changes 134{ my $sum = 0; 135 forprimes { $sum += int(12345/$_) } 1000; 136 is(27053, $sum, "forprimes handles \$_ type changes"); 137} 138 139# For fun, nest them. 140{ 141 my @t; 142 forprimes { 143 forprimes { 144 forprimes { push @t, $_ } $_,$_+10; 145 } 10*$_,10*$_+10; 146 } 10; 147 is_deeply( [@t], [qw/23 29 31 29 31 37 31 37 41 37 41 43 47 53 59 61 59 61 67 71 73 79 73 79 83 79 83 89/], "triple nested forprimes" ); 148} 149{ 150 my @t; 151 my $ita = prime_iterator(); 152 while ((my $a = $ita->()) <= 10) { 153 my $itb = prime_iterator(10*$a); 154 while ((my $b = $itb->()) <= 10*$a+10) { 155 my $itc = prime_iterator($b); 156 while ((my $c = $itc->()) <= $b+10) { 157 push @t, $c; 158 } 159 } 160 } 161 is_deeply( [@t], [qw/23 29 31 29 31 37 31 37 41 37 41 43 47 53 59 61 59 61 67 71 73 79 73 79 83 79 83 89/], "triple nested iterator" ); 162} 163 164# With BigInt and BigFloat objects 165{ my @t; 166 forprimes { push @t, $_ } Math::BigInt->new("5"), Math::BigInt->new("11"); 167 is_deeply( [@t], [5,7,11], "forprimes with BigInt range" ); 168} 169{ my @t; 170 forprimes { push @t, $_ } Math::BigFloat->new("5"), Math::BigFloat->new("11"); 171 is_deeply( [@t], [5,7,11], "forprimes with BigFloat range" ); 172} 173{my $it = prime_iterator(Math::BigInt->new("68719476736")); 174 is_deeply( [map { $it->() } 1..3], 175 [68719476767,68719476851,68719476853], 176 "iterator 3 primes with BigInt start" ); 177} 178 179# Test new object iterator 180ok(!eval { prime_iterator_object(-2); }, "iterator -2"); 181ok(!eval { prime_iterator_object("abc"); }, "iterator abc"); 182ok(!eval { prime_iterator_object(4.5); }, "iterator 4.5"); 183 184{ my $it = prime_iterator_object(); 185 is_deeply( [map { $it->iterate() } 1..10], [2,3,5,7,11,13,17,19,23,29], "iterator first 10 primes" ); 186} 187{my $it = prime_iterator_object(47); 188 is_deeply( [map { $it->iterate() } 1..5], [47,53,59,61,67], "iterator 5 primes starting at 47" ); 189} 190{my $it = prime_iterator_object(199); 191 is_deeply( [map { $it->iterate() } 1..3], [199,211,223], "iterator 3 primes starting at 199" ); 192} 193{my $it = prime_iterator_object(200); 194 is_deeply( [map { $it->iterate() } 1..3], [211,223,227], "iterator 3 primes starting at 200" ); 195} 196{my $it = prime_iterator_object(31397); 197 is_deeply( [map { $it->iterate() } 1..3], [31397,31469,31477], "iterator 3 primes starting at 31397" ); 198} 199{my $it = prime_iterator_object(31396); 200 is_deeply( [map { $it->iterate() } 1..3], [31397,31469,31477], "iterator 3 primes starting at 31396" ); 201} 202{my $it = prime_iterator_object(31398); 203 is_deeply( [map { $it->iterate() } 1..3], [31469,31477,31481], "iterator 3 primes starting at 31398" ); 204} 205 206{ 207 my $it = prime_iterator_object; 208 do { $it->next } for 1..10; 209 is( $it->value(), 31, "iterator object moved forward 10 now returns 31"); 210 $it->prev; 211 is( $it->value(), 29, "iterator object moved back now returns 29"); 212 is( $it->iterate(), 29, "iterator object iterates to 29"); 213 is( $it->iterate(), 31, "iterator object iterates to 31"); 214 $it->rewind->next->next->next->prev; 215 is( $it->value(), 5, "iterator object rewind and move returns 5"); 216 # Validate that it automatically handles bigint range traversal. 217 SKIP: { 218 skip "Skipping bigint traversals on a Perl that can't add correctly",5 if $broken64; 219 my $top_prime = prev_prime(~0); 220 my $big_prime = next_prime(Math::BigInt->new(''.~0)); 221 ok( $big_prime > ~0, "internal check, next_prime on big int works"); 222 $it->rewind($top_prime); 223 is( $it->value(), $top_prime, "iterator object can rewind to $top_prime"); 224 $it->next; 225 is( $it->value(), $big_prime, "iterator object next is $big_prime"); 226 $it->rewind(~0); 227 is( $it->value(), $big_prime, "iterator object rewound to ~0 is $big_prime"); 228 $it->prev; 229 is( $it->value(), $top_prime, "iterator object prev goes back to $top_prime"); 230 } 231 232 # Validation for the Math::NumSeq compatiblity stuff 233 $it->rewind; 234 do { $it->next } for 1..200; 235 is( $it->tell_i(), 201, "iterator object tell_i"); 236 is( $it->i_start, 1, "iterator object i_start = 1"); 237 like( $it->description, qr/prime numbers/, "iterator object description"); 238 is( $it->values_min, 2, "iterator object values_min = 2"); 239 is( $it->values_max, undef, "iterator object values_max = undef"); 240 # missing: characteristic 241 is( $it->oeis_anum, "A000040", "iterator object oeis_anum = A000040"); 242 # missing: parameter_info_array / parameter_info_list 243 is( $it->seek_to_i(156)->value, 911, "iterator object seek_to_i goes to nth prime"); 244 is( $it->seek_to_value(156)->value, 157, "iterator object seek_to_value goes to value"); 245 is( $it->ith(589), 4289, "iterator object ith returns nth prime"); 246 ok( $it->pred(577), "iterator object pred returns true if is_prime"); 247 is( $it->value_to_i(4289), 589, "iterator object value_to_i works"); 248 is( $it->value_to_i(4290), undef, "iterator object value_to_i for non-prime returns undef"); 249 is( $it->value_to_i_floor(4290), 589, "iterator object value_to_i_floor"); 250 is( $it->value_to_i_ceil(4290), 590, "iterator object value_to_i_ceil"); 251 my $est = $it->value_to_i_estimate( 4171510507 ); 252 my $act = 197710788; 253 # We will get an estimate that is much, much closer than Math::NumSeq 254 ok( ($est > ($act-500)) && ($est < ($act+500)), 255 "iterator object value_to_i_estimage is in range"); 256} 257 258{ my @zn; 259 forprimes { 260 my $p=$_; 261 forprimes { 262 lastfor, push @zn,$_ if $_ % $p == 1; 263 } 1000; 264 } 100; 265 is_deeply( \@zn, 266 [3,7,11,29,23,53,103,191,47,59,311,149,83,173,283,107,709,367,269,569,293,317,167,179,389], 267 "lastfor works in forprimes" ); 268} 269{ my @zn; 270 forprimes { 271 my $p=$_; 272 forcomposites { 273 lastfor, push @zn,$_ if $_ % $p == 1; 274 } 1000; 275 } 100; 276 is_deeply( \@zn, 277 [9,4,6,8,12,14,18,20,24,30,32,38,42,44,48,54,60,62,68,72,74,80,84,90,98], 278 "lastfor works in forcomposites" ); 279} 280{ my @zn; 281 forprimes { 282 my $p=$_; 283 foroddcomposites { 284 lastfor, push @zn,$_ if $_ % $p == 1; 285 } 1000; 286 } 100; 287 is_deeply( \@zn, 288 [9,25,21,15,45,27,35,39,93,117,63,75,165,87,95,213,119,123,135,143,147,159,333,357,195], 289 "lastfor works in foroddcomposites" ); 290} 291{ my @powers; 292 for my $n (1..20) { 293 fordivisors { lastfor,push @powers,$_ if is_power($_) } $n; 294 } 295 is_deeply( \@powers, [4,4,9,4,4,9,4], "lastfor works in fordivisors" ); 296} 297{ my $firstpart; 298 forpart { lastfor,return if @_ < 4; $firstpart++; } 7; 299 is($firstpart, 6, "lastfor works in forpart"); 300} 301{ my $firstcomp; 302 forcomp { lastfor,return if @_ < 4; $firstcomp++; } 7; 303 is($firstcomp, 15, "lastfor works in forcomp"); 304} 305{ my $smallcomb; 306 forcomb { lastfor,return if vecsum(@_) > 11; $smallcomb++; } 7,4; 307 is($smallcomb, 9, "lastfor works in forcomb"); 308} 309{ my $t; 310 forperm { lastfor,return if $_[3]==5; $t++; } 7; 311 is($t, 12, "lastfor works in forperm"); 312} 313{ my $t; 314 forderange { lastfor,return if $_[3]==5; $t++; } 7; 315 is($t, 5, "lastfor works in forderange"); 316} 317{ my $t; 318 formultiperm { lastfor if "miles" eq join("",@_); $t++; } [split(//,"smile")]; 319 is($t, 81, "lastfor works in formultiperm"); 320} 321{ my @ps; 322 forprimes { 323 lastfor if $_ >= 7; 324 # Note we keep going, unlike "last". 325 push @ps, $_; 326 forcomposites { 327 push @ps,$_; 328 } $_; 329 # Our lastfor indicator is separate from the inside loop. 330 } 20; 331 is_deeply( \@ps, [2,3,5,4,7,4,6], "nested lastfor semantics" ); 332} 333{ 334 my $t; 335 forcomposites { $t=$_; lastfor if $_ > 2000; } 20000; 336 is($t, 2001, "lastfor in forcomposites stops appropriately"); 337} 338 339sub a053462 { 340 my($s,$n)=(0,10**$_[0]-1); 341 forsquarefree { $s += int($n / ($_*$_)) * ((scalar(@_) & 1)?-1:1); } sqrtint($n); 342 $s; 343} 344 345################### forfactored 346 347{ 348 my $s; 349 $s=0; forfactored { $s += $_ } 1; is($s, 1, "forfactored {} 1"); 350 $s=0; forfactored { $s += vecsum($_,@_) } 100; is($s, 7330, "forfactored {} 100"); 351 $s=0; forsquarefree { $s += vecsum($_,@_) } 100; is($s, 4763, "forsquarefree {} 100"); 352 $s=0; forfactored { $s += vecsum($_,@_) } 1e8,1e8+10; is($s, 1208835222, "forfactored {} 10^8,10^8+10"); 353 is( a053462(6), 607926, "A053462 using forsquarefree"); 354} 355 356################### forsemiprimes 357 358{ 359 my @got; 360 forsemiprimes { push @got, $_; } 1000; 361 is_deeply(\@got, [grep { is_semiprime($_) } 0 .. 1000], "forsemiprimes 1000"); 362} 363 364################### forsetproduct 365 366{ 367 ok(!eval { forsetproduct { } 1,2; }, "forsetproduct not array ref errors"); 368 369 my(@set,@out); 370 371 @set=(); @out=();forsetproduct {push @out,"@_"}@set; 372 is_deeply(\@out, [], 'forsetproduct empty input -> empty output'); 373 374 @set=([1..3]); @out=();forsetproduct {push @out,"@_"}@set; 375 is_deeply(\@out, [1..3], 'forsetproduct single list -> single list'); 376 377 @set=([1],[2],[3],[4],[5]); @out=();forsetproduct {push @out,"@_"}@set; 378 is_deeply(\@out, ['1 2 3 4 5'], 'forsetproduct five 1-element lists -> single list'); 379 380 @set=([1,2],[3,4,5],[]); @out=();forsetproduct {push @out,"@_"}@set; 381 is_deeply(\@out, [], 'forsetproduct any empty list -> empty output'); 382 383 @set=([],[1,2],[3,4,5]); @out=();forsetproduct {push @out,"@_"}@set; 384 is_deeply(\@out, [], 'forsetproduct any empty list -> empty output'); 385 386 @set=([1,2],[qw/a b c/]); @out=();forsetproduct {push @out,"@_"}@set; 387 is_deeply(\@out, ['1 a','1 b','1 c','2 a','2 b','2 c'], 'forsetproduct simple test'); 388 389 @set=([1,2],[qw/a b c/]); @out=();forsetproduct {push @out,"@_"; $#_=0; }@set; 390 is_deeply(\@out, ['1 a','1 b','1 c','2 a','2 b','2 c'], 'forsetproduct modify size of @_ in block'); 391 392 @set=([1,2],[qw/a b c/]); @out=();forsetproduct {push @out,"@_"; @_=(1..10); }@set; 393 is_deeply(\@out, ['1 a','1 b','1 c','2 a','2 b','2 c'], 'forsetproduct replace @_ in sub'); 394} 395