Factorials are the product of all integers in the interval [1;s]. 5! = 1*2*3*4*5.
Interval factorials are the product of all integers in the interval [i;s]. intfact(4,10) = 4*5*6*7*8*9*10
K-factorials are a generalization of the factorials. It is the product of all the numbers in the interval [1;n] that are congruent to n mod k (the residue class). 3-factorial 7 is computed as 1 * 4 * 7 as 1,4,7 are all congruent to 1 mod 3. We show an example of a k-factorial function below
k_fact(s,m)
for i ∈ [1;s]
if i mod m == s mod m
product <- product*i
end if
end for
return product
fn sirp(infinum: u64, suprenum: u64, modulo: u64, residue: u64)-> Vec< u64 >{
const RADIX : u128 = 0x8AC7230489E80000 ; // 10^19 in hexadecimal form
let product = Vec::new();
// let mut acc = 1u64; // Product accumulator for fewer array multiplications
for i in infinum..suprenum+1{ // inclusive range
if i % modulo == residue { // if i is of the residue class modulo n then multiply
if product.len() == 0{
product.push(1)
} // if acc < 6981463658332{ acc*=i} // Keep accumulating product if less than (2^64-1)^(2/3)
// if acc > 6981463658332{ // execute array multiplication if greater than (2^64-1)^(2/3)
let mut carry = 0u64;
for j in product.iter_mut(){
let total = *j as u128 * i as u128 + carry as u128;
*j = (total%RADIX) as u64; // to promote to Radix-2^64 replace line with *j = total as u64;
carry = (total/RADIX) as u64; // likewise carry = (total>>64) as u64;
} // end for
if carry > 0 {
product.push(carry)
} // acc = 1 } // resets accumulator to multiplicative identity and closes the previous conditional branch
} // end if
}
/* multiplies the last accumulation regardless of value
let mut carry = 0u64;
for j in product.iter_mut(){
let total = *j as u128 * i as u128 + carry as u128;
*j = total as u64;
carry = (total>>64) as u64;
}
if carry > 0 { product.push(carry) }
}
product */
}
sirplog(i,s,m,r,z)
slog <- 0
for n in [i;s]
if n mod m == residue
slog = slog + log(n,z)
end if
end for
return slog
Factorization Like with logarithms before we can compute the prime-factorization of the SIRP by factoring each of the individual factors. For efficiency purposes it's preferable to find the number of factors of a set prime for each sirp-factor. We first start with the function to count the factors of sirp-factor.
sirp_prime(i,s,m,r, factor)
count <- 0
for n in [i;s]
if n mod m == residue
k <- i
while k mod factor == 0
k <- k/factor;
count <- count + 1
end while
end if
end for
return count
zlog_fact(s,z) ≈ (s * ln(s) - s + ln(s*(1 + 4*s*(1 + 2*s))) /6 + ln(3.14159265359)/2.0)/ln(z);
Computing the logarithm of interval-factorial over the range of [i;s]
zlog_intfact(i,s,z) ≈ zlog_fact(s,z) - zlog_fact(i+1,z)
zlog_kfact(s,m,z) ) ≈ zlog_fact(s,z)/m + (ln(s)/ln(10))/m
zlog_twofact(s,z) ≈ zlog_fact(s,z)/2 + (0.249901354*log10(s))/z
zlog_twofact(s,z) ≈ zlog_fact(s,z)/2 + (0.249901354*log10(s)/2)/z
zlog_sirp(i,s,m,r,z) ≈ (zlog(s,z) - zlog(i+1,z))/m
count_factor(s,factor)
r <- 1/factor
p <- floor( log10(n)/log10(factor) )
(s/factor) * floor( (1 - r^(p+1)) /(1-r))
sirp_factor(i,s,m,r)
primes <- [1;s] ∈ P
for n in primes
factors <- n
factors <- (count_factor(s,n) - count_factor(i+1,n))/m
end for