hardy ramanujanalgo Algorithm
The Hardy-Ramanujan Algorithm, named after the famous mathematicians G.H. Hardy and Srinivasa Ramanujan, is an efficient method for approximating the partition function P(n), which represents the number of ways a given positive integer n can be expressed as the sum of positive integers. This algorithm is based on the circle method, which involves analyzing a complex function over a contour in the complex plane. The Hardy-Ramanujan Algorithm is also known as the Hardy-Ramanujan-Rademacher formula, as Hans Rademacher later refined the method to improve its convergence properties.
The algorithm's core idea is to express the partition function as an infinite series involving the sum of complex numbers, where each term in the series corresponds to a specific contour integral. By carefully choosing the contour and exploiting the underlying symmetry of the problem, one can efficiently compute the partition function with high accuracy. The Hardy-Ramanujan Algorithm has been widely used in number theory, combinatorics, and statistical mechanics, and has served as the foundation for many subsequent partition function approximations and generalizations.
# This theorem states that the number of prime factors of n
# will be approximately log(log(n)) for most natural numbers n
import math
def exactPrimeFactorCount(n):
"""
>>> exactPrimeFactorCount(51242183)
3
"""
count = 0
if n % 2 == 0:
count += 1
while n % 2 == 0:
n = int(n / 2)
# the n input value must be odd so that
# we can skip one element (ie i += 2)
i = 3
while i <= int(math.sqrt(n)):
if n % i == 0:
count += 1
while n % i == 0:
n = int(n / i)
i = i + 2
# this condition checks the prime
# number n is greater than 2
if n > 2:
count += 1
return count
if __name__ == "__main__":
n = 51242183
print(f"The number of distinct prime factors is/are {exactPrimeFactorCount(n)}")
print("The value of log(log(n)) is {:.4f}".format(math.log(math.log(n))))
"""
The number of distinct prime factors is/are 3
The value of log(log(n)) is 2.8765
"""
