eulerlib package

Library of number theory related functions inspired by Project Euler.

Submodules

eulerlib.prime_numbers module

eulerlib.prime_numbers.prime_gen()

A generator function that yields prime numbers using the Sieve of Eratosthenes algorithm.

Note

This function is based on the erat2a function which can be found here. Variable names were changed and comments added for clarity.

eulerlib.prime_numbers.prime_wheel_fact_gen()

A generator function that yields prime numbers using the wheel factorized Sieve of Eratosthenes.

Note

This function is based on the erat3 function which can be found here. Variable names were changed and comments added for clarity.

eulerlib.prime_numbers.primes(num)

Returns a list of prime numbers. Uses the eulerlib.prime_numbers.prime_gen() generator function.

Parameters:num – The upper limit for prime numbers list (pn < num) Returns:List of prime numbers [p1,p2,...pn] such that pn < num.

Uses the prime_gen function that uses Sieve of Eratosthanes.

eulerlib.prime_numbers.primes_wheel_fact(num)

Returns a list of prime numbers. Uses the eulerlib.prime_numbers.prime_wheel_fact_gen() generator function.

Parameters:num – The upper limit for prime numbers list (pn < num) Returns:List of prime numbers [p1,p2,...pn] such that pn < num.

Uses the prime_wheel_fact_gen function that uses Sieve of Eratosthanes with wheel factorization based on the first 3 primes: 2, 3 and 5.

eulerlib.prime_numbers.is_prime(num)

Primality checking function: returns True if num is a prime number.

eulerlib.numtheory module

eulerlib.numtheory.is_square(num)

Determines if a positive integer num is the perfect square.

Parameters:num – Integer to be checked Returns:A tuple (is_square,root)

Note

• is_square is True if num is a perfect square.
• The integer root <= (square root of num).

Uses Digit-by-digit algorithm in base 10.

eulerlib.numtheory.gcd(a, b)

Calculates Greatest Common Divisor of two integers.

Parameters:

• a – First integer
• b – Second integer

Returns:

Greatest Common Divisor (GCD) of a and b

Uses Euclid’s algorithm.

eulerlib.numtheory.lcm(a, b)

Calculates the Least Common Multiple (LCM) of two integers.

Parameters:

• a – First integer
• b – Second integer

Returns:

Least Common Multiple (LCM) of a and b

eulerlib.numtheory.lcm_n(num_list)

Calculate the Least Common Multiple of a list of integers.

Parameters:num_list – A list of integers [i1,i2,i3,...,in] Returns:LCM of the integers in num_list

Uses the associative property LCM(a,b,c) = LCM(LCM(a,b),c)

eulerlib.numtheory.nCr(n, r)

Calculate ways of selecting r members out of a collection of n members.

Parameters:

• n – Size of the collection
• r – Number of members to be selected from the collection

Returns:

n!/[r!(n-r)!]

Note

ⁿ C _r is typically read as n combination r. Order of members is not important in the combination. E.g. There are ⁴ C ₂ = 6 ways of selecting two members out of a collection (A, B, C, D) => AB, AC, AD, BC, BD, CD.

eulerlib.numtheory.nPr(n, r)

Calculate number of permutations of length r out of a collection of n members (No repeated members).

Parameters:

• n – Size of the collection
• r – Number of members to be permutated.

Returns:

n!/[(n-r)!]

Note

ⁿ P _r is typically read as n permutation r. Order of members is important in the permutation. E.g. There are ⁴ P ₂ = 12 permutations of length 2 out of a collection (A, B, C, D) => AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC.

eulerlib.numtheory.digital_sum(num)

Calculate the digital sum of a number num in base 10

Parameters:num – Number for which digital sum is to be calculated. num should be in base 10. Returns:Digital sum of num in base 10.

eulerlib.numtheory.digital_root(num)

Calculate the digital root of a number num in base 10.

Parameters:num – Number for which digital root is to be calculated. num should be in base 10. Returns:Digital root of num in base 10.

class eulerlib.numtheory.Divisors(maxnum=1000)

Implements methods related to prime factors and divisors.

Parameters:maxnum – Upper limit for the list of primes. (default = 1000)

divisors(num)

Returns a list of ALL divisors of num (including 1 and num).

Parameters:num – An integer for which divisors are needed. Returns:A list [d1,d2,...dn] of divisors of num

phi(num)

Returns the number of totatives of num

Parameters:num – Integer for which number of totatives are needed. Returns:Number of totatives of num

Note

A totative of an integer num is any integer i such that, 0 < i < n and GCD(i,num) == 1.

Uses Euler’s totient function.

prime_factors(num)

Returns the prime factors pf _i of num and the maximum power a _i for each prime factor pf _i.

Parameters:num – An integer for which prime factors are needed Returns:A list of tuples [(pf1,a1),...(pfi,ai)]

Note

num = (pf1**a1)*(pf2**a2)..*(pfi**ai)

prime_factors_only(num)

Returns the prime factors pf _i of num.

Parameters:num – An integer for which prime factors are needed Returns:A list [pf1,pf2,...pfi] of prime factors of num

sigma_function(num)

Calculates the divisor functions (sigma functions).

Parameters:num – Integer for which sigma functions are needed. Returns:A tuple (sigma0,sigma1,s(n))

Note

• sigma0 = number of divisors of num.
• sigma1 = sum of all divisors of num
• s(n) = sum of proper divisors of num (includes 1, excludes num)

eulerlib.fibonacci module

eulerlib.fibonacci.fibo_gen(start=1)

A generator function that yields the Fibonacci sequence.

Parameters:start – Starting digit of Fibonacci sequence (0 or 1, default=1)

eulerlib.fibonacci.first_n_fibo(n, start=1)

Get first n numbers in the Fibonacci sequence.

Parameters:

• n – Desired length of Fibonacci sequence
• start – Starting digit of Fibonacci sequence (0 or 1, default=1)

Returns:

A list [f1,f2,...,fn] where f1 = 1 if start = 1

eulerlib.fibonacci.fibo_less_than(n, start=1)

Get the Fibonacci sequence [f1,f2,...fi] such that fi < n.

Parameters:

• n – Desired maximum value.
• start – Starting digit of Fibonacci sequence (0 or 1, default=1)

Returns:

A list [f1,f2,...,fi] such that fi < n

eulerlib.fibonacci.fibo_num_digits(num, start=1)

Get the Fibonacci sequence [f1,f2,...fi] such that fi is the first Fibonacci number to have num digits.

Parameters:

• num – Desired number of digits in the last term of sequence.
• start – Starting digit of Fibonacci sequence (0 or 1, default=1)

Returns:

A list [f1,f2,..fi] such that fi is the first Fibonacci number to have num digits

eulerlib.pythagoras module

eulerlib.pythagoras.triplet_gen()

A generator function that yields primitive Pythagorean triples.

eulerlib.pythagoras.primitive_triples(n)

Returns n primitive Pythagorean triples.

Parameters:n – Maximum number of primitive triples desired. Returns:A list of tuples [(a1,b1,c1),(a2,b2,c2),...,(an,bn,cn)]

eulerlib.etc module

eulerlib.etc.decimal_to_base(num, b)

Converts num from decimal to base b

Parameters:

• num – A decimal integer
• b – A decimal integer value for the base. 1 < b <= 36

Returns:

String that represents decimal num in base b

For example:

>>> decimal_to_base(8,2)
'1000'

eulerlib.etc.is_palindrome(num, base=10)

Returns True if decimal number num is a Palindrome number in base.

Parameters:

• num – Decimal number to be tested
• base – Base of the number system in which num is to be tested. (Default = 10)

Returns:

True if num is palindromic in base

For example:

>>> is_palidrome(3875783) #Test in default base = 10
>>> True
>>> is_palidrome(9,2) # 9 in base 2 is 1001
>>> True

eulerlib.etc.is_pandigital(num, start, stop)

Returns True if num is Pandigital.

Parameters:

• num – An integer to be checked for pandigitalness.
• start – Strating digit. 0 <= start <= 9
• stop – Ending digit start < stop <= 9

For example:

>>> is_pandigital(2134, 1, 4) 
True

eulerlib.etc.num_to_list(num)

Returns a list of digits in num (most significant digit first).

eulerlib.etc.list_to_num(list_of_digits)

Returns an integer from a list_of_digits.

eulerlib.etc.word_numerical_val(word)

Returns the sum of numerical value of each letter in the word based on its position in the alphabet.

eulerlib.etc.write_number(num)

Return the written English language string representation of num

Parameters:num – An integer number

For example:

>>> write_num(132)
>>> 'one hundred and thirty-two'

eulerlib.etc.collapse_lists(list1, list2, compf, pathf)

Function to collapse two lists into a single list based on comparison and path functions.

Parameters:

• list1 – First list
• list2 – Second list
• compf – Comparator function to compare values returned by path function.
• pathf – Function that takes a list of elements and returns a value of the same type.

Returns:

A list with length = len(list2)

Note

• Both lists must have values of the same type ‘T’
• Comparison function should take a list of values of type ‘T’ and return a value of type ‘T’.
• Path function should take a list of values of type ‘T’ and return a value of type ‘T’.
• The function calculates path totals based on paths from list1 to list2.
• The difference between lengths of list1 and list2 should be 1

For example: To calculate maximum sum of path values - path function => sum, comparison function => max:

>>> list1 = [12,37,53,46]
>>> list2 = [23,34,47]
>>> compf = max
>>> pathf = sum
>>> collapse_lists(list1,list2,compf,pathf)
>>> [60, 87, 100]