Goto Chapter: Top 1 2 3 4 5 6 7 8 Bib Ind

### 4 Number-theoretic functions

#### 4.1 Functions for integers

##### 4.1-1 AllSmoothIntegers
 ‣ AllSmoothIntegers( maxp, maxn ) ( function )
 ‣ AllSmoothIntegers( maxp, L ) ( function )

This function has been transferred from package RCWA.

The function AllSmoothIntegers(maxp,maxn) returns the list of all positive integers less than or equal to maxn whose prime factors are all in the list L = {p ~|~ p leqslant maxp, p~mboxprime }.

In the alternative form, when L is a list of primes, the function returns the list of all positive integers whose prime factors lie in L.


gap> AllSmoothIntegers( 3, 1000 );
[ 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96,
108, 128, 144, 162, 192, 216, 243, 256, 288, 324, 384, 432, 486, 512, 576,
648, 729, 768, 864, 972 ]
gap> AllSmoothIntegers( [5,11,17], 1000 );
[ 1, 5, 11, 17, 25, 55, 85, 121, 125, 187, 275, 289, 425, 605, 625, 935 ]
gap> Length( last );
16
gap> List( [3..20], n -> Length( AllSmoothIntegers( [5,11,17], 10^n ) ) );
[ 16, 29, 50, 78, 114, 155, 212, 282, 359, 452, 565, 691, 831, 992, 1173,
1374, 1595, 1843 ]



##### 4.1-2 AllProducts
 ‣ AllProducts( L, k ) ( function )

This function has been transferred from package RCWA.

The command AllProducts(L,k) returns the list of all products of k entries of the listÂ L. Note that every ordering of the entries is used so that, in the commuting case, there are bound to be repetitions.


gap> AllProducts([1..4],3);
[ 1, 2, 3, 4, 2, 4, 6, 8, 3, 6, 9, 12, 4, 8, 12, 16, 2, 4, 6, 8, 4, 8, 12,
16, 6, 12, 18, 24, 8, 16, 24, 32, 3, 6, 9, 12, 6, 12, 18, 24, 9, 18, 27,
36, 12, 24, 36, 48, 4, 8, 12, 16, 8, 16, 24, 32, 12, 24, 36, 48, 16, 32,
48, 64 ]
gap> Set(last);
[ 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 64 ]
gap> AllProducts( [(1,2,3),(2,3,4)], 2 );
[ (2,4,3), (1,2)(3,4), (1,3)(2,4), (1,3,2) ]



##### 4.1-3 RestrictedPartitionsWithoutRepetitions
 ‣ RestrictedPartitionsWithoutRepetitions( n, S ) ( function )

This function has been transferred from package RCWA.

For a positive integer n and a set of positive integers S, this function returns the list of partitions of n into distinct elements of S. Unlike RestrictedPartitions, no repetitions are allowed.


gap> RestrictedPartitions( 20, [4..10] );
[ [ 4, 4, 4, 4, 4 ], [ 5, 5, 5, 5 ], [ 6, 5, 5, 4 ], [ 6, 6, 4, 4 ],
[ 7, 5, 4, 4 ], [ 7, 7, 6 ], [ 8, 4, 4, 4 ], [ 8, 6, 6 ], [ 8, 7, 5 ],
[ 8, 8, 4 ], [ 9, 6, 5 ], [ 9, 7, 4 ], [ 10, 5, 5 ], [ 10, 6, 4 ],
[ 10, 10 ] ]
gap> RestrictedPartitionsWithoutRepetitions( 20, [4..10] );
[ [ 10, 6, 4 ], [ 9, 7, 4 ], [ 9, 6, 5 ], [ 8, 7, 5 ] ]
gap> RestrictedPartitionsWithoutRepetitions( 10^2, List([1..10], n->n^2 ) );
[ [ 100 ], [ 64, 36 ], [ 49, 25, 16, 9, 1 ] ]



##### 4.1-4 ExponentOfPrime
 ‣ ExponentOfPrime( n, p ) ( function )

This function has been transferred from package RCWA.

ExponentOfPrime(n,p) returns the exponent of the prime p in the prime factorization of n.

It has been pointed out (07/09/2018) that the GAP function PValuation produces the same results, and does so more quickly. So this function should be considered obsolete, and liable to removal in due course.


gap> ExponentOfPrime( 13577531, 11 );
3
gap> PValuation( 13577531, 11 );
3
gap> List( [1..40], n -> ExponentOfPrime( 3^n-1, 2 ) );
[ 1, 3, 1, 4, 1, 3, 1, 5, 1, 3, 1, 4, 1, 3, 1, 6, 1, 3, 1, 4, 1, 3, 1, 5, 1,
3, 1, 4, 1, 3, 1, 7, 1, 3, 1, 4, 1, 3, 1, 5 ]
gap> List( [1..40], n -> PValuation( 3^n-1, 2 ) );
[ 1, 3, 1, 4, 1, 3, 1, 5, 1, 3, 1, 4, 1, 3, 1, 6, 1, 3, 1, 4, 1, 3, 1, 5, 1,
3, 1, 4, 1, 3, 1, 7, 1, 3, 1, 4, 1, 3, 1, 5 ]
gap> List( [1..40], n -> ExponentOfPrime( n^2-1, 2 ) );
[ infinity, 0, 3, 0, 3, 0, 4, 0, 4, 0, 3, 0, 3, 0, 5, 0, 5, 0, 3, 0, 3, 0, 4,
0, 4, 0, 3, 0, 3, 0, 6, 0, 6, 0, 3, 0, 3, 0, 4, 0 ]
gap> List( [1..40], n -> PValuation( n^2-1, 2 ) );
[ infinity, 0, 3, 0, 3, 0, 4, 0, 4, 0, 3, 0, 3, 0, 5, 0, 5, 0, 3, 0, 3, 0, 4,
0, 4, 0, 3, 0, 3, 0, 6, 0, 6, 0, 3, 0, 3, 0, 4, 0 ]



##### 4.1-5 NextProbablyPrimeInt
 ‣ NextProbablyPrimeInt( n ) ( function )

This function has been transferred from package RCWA.

The function NextProbablyPrimeInt(n) does the same as NextPrimeInt(n) except that for reasons of performance it tests numbers only for IsProbablyPrimeInt(n) instead of IsPrimeInt(n). For large n, this function is much faster than NextPrimeInt(n)


gap> n := 2^251;
3618502788666131106986593281521497120414687020801267626233049500247285301248
gap> time;
0
gap> NextProbablyPrimeInt( n );
3618502788666131106986593281521497120414687020801267626233049500247285301313
gap> time;
1
gap> NextPrimeInt( n );
3618502788666131106986593281521497120414687020801267626233049500247285301313
gap> time;
12346



 ‣ PrimeNumbersIterator( [chunksize] ) ( function )

This function has been transferred from package RCWA.

This function returns an iterator which runs over the prime numbers n ascending order; it takes an optional argument chunksize which specifies the length of the interval which is sieved in one go (the default is 10^7), and which can be used to balance runtime vs. memory consumption. It is assumed that chunksize is larger than any gap between two consecutive primes within the range one intends to run the iterator over.


gap> for i in [1..100] do  p := NextIterator(iter);  od;
gap> p;
541
gap> sum := 0;;
gap> ## "prime number race" 1 vs. 3 mod 4
gap> for p in PrimeNumbersIterator() do
>       if p <> 2 then sum := sum + E(4)^(p-1); fi;
>       if sum > 0 then break; fi;
>    od;
gap> p;
26861


Goto Chapter: Top 1 2 3 4 5 6 7 8 Bib Ind

generated by GAPDoc2HTML