SageMath: Number Theory and Algorithms

I used Google's NotebookLM to upload all my SageMath documents. Here was the summary it provided of the 27 sources that I provided:

These SageMath excerpts explore various mathematical concepts and algorithms. They present definitions and computational methods for topics such as balanced primes, factorial and p-adic number bases, and Bell numbers. The texts also investigate number theory problems, including palindrome properties, divisibility rules, and prime number sequences like those found in OEIS (Online Encyclopedia of Integer Sequences). Furthermore, the sources cover graph theory applications with dictionaries, geometric concepts like Dyck paths, and calculations involving mathematical constants like Pi and the Golden Ratio. Finally, they illustrate probabilistic simulations and the use of plotting functions within the SageMath environment.

*********************************

I then asked the following question:

Can you summarise what the sources have to say about matters relating prime numbers?

Here was the response:

The sources provide a comprehensive overview of various aspects related to prime numbers, their definitions, properties, classifications, and applications within SageMath.

Here's a summary of what the sources say about matters relating to prime numbers:

Basic Definitions and Concepts

• A prime number is frequently identified using the is_prime() function in SageMath, which returns True if a number is prime and False otherwise.
• The distinct prime factors of a number n are given by prime_factors(n) or prime_divisors(n).
• The total number of prime factors counted with multiplicity is referred to as bigomega(n) or Ω(n), which can be found using sloane.A001222 or by summing the exponents from list(factor(n)).
• The number of different prime divisors of n is called omega(n) or ω(n), available through sloane.A001221 or len(prime_divisors(n)).
• To see all prime factors with their powers, the factor() command is used, which returns a factored form or a list of (base, index) pairs.

Types of Prime Numbers

The sources define and provide algorithms for various special types of prime numbers:

• Balanced Primes: A prime number is balanced if it is the average of an equal number of primes above and below it. An algorithm generates balanced primes of a given order within a range.
• Cuban Primes: Primes that are the difference of two consecutive cubes.
• Emirps: A prime number that remains prime when its digits are reversed (e.g., 17 and 71). This concept can be generalized to n-almost primes.
• Luhn Primes: Primes where the sum of the prime and its reverse (or their powers) is also a prime. Orders 1, 2, and 4 are mentioned, with algorithms provided for any order, though results are assured only for orders 1, 2, and 4.
• Quintan Primes: Primes of the form (x^5 - y^5) / (x - y).
• Twin Primes: A pair of primes that differ by 2 (e.g., (26111, 26113)). An algorithm lists them in a given range. The twin prime constant is also listed.
• Truncatable Primes:
  • Left Truncatable Primes: Generated by successively removing digits from the left (e.g., 5372126317, where 12 needs to be added to the front for the next prime). Algorithms are provided for sequences starting from 3 or 7.
  • Right Truncatable Primes: Generated by successively removing digits from the right (e.g., 31193 -> 3119 -> 311 -> 31 -> 3). Algorithms are provided for sequences starting from 3 or 5.
• Carmichael Numbers: Composite numbers that satisfy k^(n-1) ≡ 1 (mod n) for all k coprime to n. They are a special case of n-Knödel numbers where the subscript is 1. The smallest Carmichael number is 561.
• Pseudoprimes:
  • Fermat Pseudoprimes: Composite numbers x that pass the Fermat primality test for a given base b, meaning b^(x-1) % x == 0 (where b is coprime to x).
  • Strong Fermat Pseudoprimes: Composite numbers that pass an additional, stronger primality test.
  • Euler Pseudoprimes: Odd composite integers n that satisfy a^((n-1)/2) ≡ ±1 (mod n) for a coprime to n. Every Euler pseudoprime is also a Fermat pseudoprime. Absolute Euler pseudoprimes are Euler pseudoprimes to every base coprime to themselves, and they are a subset of Carmichael numbers. The smallest absolute Euler pseudoprime is 1729.
• Almost Primes: Numbers with a specific total count of prime factors (counted with multiplicity).
• Semiprimes: Numbers that are the product of two primes. Algorithms are provided to generate them and apply them in other contexts, such as finding primes that are the sum of two and three successive semiprimes. A special type is Golden Semiprimes, where the factors p and q satisfy abs(p * phi - q) < 1 (where phi is the golden ratio). This can be generalized to other ratios like HDTV.
• Sphenic Numbers: Products of three distinct primes. They can occur in pairs and triples, but not more than three consecutive ones. Algorithms generate them and calculate associated properties like surface area and ratio if viewed as rectangular prisms.
• Ulam Numbers: Defined recursively: U1=1, U2=2. For k>2, Uk is the smallest integer that can be written in exactly one way as Ui + Uj with i < j < k. A list of the first 10,000 Ulam numbers is available, and code demonstrates their unique sum property.
• Untouchable Numbers: Numbers that cannot be expressed as the sum of the divisors of any other number. Erdős proved there are infinitely many. An algorithm helps identify them by excluding numbers that are one or three more than a prime.
• Euclid Numbers: Integers of the form Pn# + 1, where Pn# is the nth primorial (product of the first n prime numbers).
• Moran Numbers: A composite number that, when divided by the sum of its digits, results in a prime number.
• Hoax Numbers: Composite numbers where the sum of their digits equals the sum of the digits of their distinct prime factors. They are a subset of Smith numbers.
• Smith Numbers: Composite numbers where the sum of their digits equals the sum of the digits of their prime factors (counted with multiplicity).
• Home Prime: For a number n, its home prime is the prime reached by repeatedly concatenating its prime factors (smallest to largest) until a prime is found. Algorithms determine the home prime and the number of steps required.
• De Polignac Numbers: Odd numbers that cannot be expressed as 2^k + p for a prime p.
• Interprime Numbers: Numbers midway between two prime numbers.
• n-Knödel Numbers: Composite numbers n such that for every k coprime to n, k^(n-subscript) ≡ 1 (mod n). Carmichael numbers are a special case where the subscript is 1.
• Duffinian Numbers: Numbers that have no factors in common with their sum of divisors.
• Zumkeller Numbers and Half-Zumkeller Numbers: Numbers whose divisors can be partitioned into two disjoint sets with equal sums.

Prime-Related Algorithms and Applications in SageMath

• Generating Primes: prime_range(start, end) generates primes within a specified range.
• Prime Indexing: prime_pi(n) gives the count of primes less than or equal to n (with 2 being the 1st prime). Primes().unrank(k) gives the k-th prime (with 2 being the 0th prime), while nth_prime(k) gives the k-th prime (with 2 being the 1st prime).
• Consecutive Primes: next_prime(p) and previous_prime(p) find adjacent primes.
• Prime Gaps: Algorithms determine and track record prime gaps (the difference between consecutive primes).
• Density of Primes: An algorithm investigates the density of primes based on the number of digits, showing an approximately constant product of percentage of primes and number of digits.
• Goldbach Conjecture/Decomposition/Partition: Goldbach's conjecture states every even number greater than 2 is a sum of two primes. Algorithms find the number of decompositions and the minimal decomposition. The conjecture is also extended to lucky numbers.
• Euler Project Problem 50: An algorithm is provided to find the prime below one million that can be written as the sum of the most consecutive primes (which is 997651, sum of 543 consecutive primes).
• Primorials: The product of the first n primes can be generated and used as a mixed radix number base.
• Sum of Prime Factors with Multiplicity: This operation can be iterated until a 4 or a prime number is reached, with some numbers requiring many steps.
• Numbers as Sums of Cubes of Distinct Primes: An algorithm identifies primes that are the sum of cubes of three distinct prime numbers.
• Connections to Pi: Algorithms are provided to find primes by merging successive digits from the decimal expansion of Pi or Pi squared.
• Ruth-Aaron Pairs & eRAPs: Algorithms identify pairs of consecutive integers that share the same sum of prime factors (either distinct or counted with multiplicity). An extension, eRAPs, considers consecutive numbers where the sums of their prime factors (with multiplicity) are consecutive.
• Prime Attractors: In the "Odds and Evens" recursive process (adding sum of odd digits, subtracting sum of even digits), some numbers lead to attractors, and algorithms can identify prime attractors.
• Dates and Primes: An algorithm checks if a person's age in days on their birthday is a prime number. Another algorithm identifies dates that correspond to prime numbers in a given year.
• Palindromes and Primes: Algorithms identify composite palindromes whose sum of prime factors (with multiplicity) is also palindromic, and to list prime palindromes within a range.
• Sum of Cubes and Primes: An algorithm identifies twin primes that are both expressible as the sum of three cubes.
• Divisors and Coprimality: The gcd() function is used for various calculations, including identifying unitary divisors and Carmichael numbers. n.coprime_integers(m) returns integers less than m that are coprime to n.
• Modular Arithmetic: The IntegerModRing() function allows for computations in modular arithmetic, essential for primality tests and properties of numbers modulo n.
• Multipurpose Algorithm: A single algorithm can perform multiple number theory checks on a given number, including primality tests, factorisation, sum of divisors, pseudoperfectness, Zumkeller status, practicality, Duffinian nature, cyclicity, d-powerful property, sum of squares/cubes of digits, and de Polignac property.

OEIS Sequences Related to Primes

Many algorithms are designed to generate terms for specific OEIS (Online Encyclopedia of Integer Sequences) sequences related to primes and prime-derived numbers:

• A002858: Ulam numbers.
• A048168: n is divisible by the square of the number of unitary divisors of n.
• A064599: Sum of non-unitary divisors of n divides n.
• A129485: Odd unitary abundant numbers.
• A005114: Untouchable numbers.
• A048128: Numbers becoming prime or 4 after exactly 6 iterations of f(x) = sum of prime factors of x.
• A002407: Cuban primes.
• A137365: Prime numbers n such that n = p1^3 + p2^3 + p3^3, a sum of cubes of 3 distinct primes.
• A138938: Indices k such that cyclotomic_polynomial(k, 8) is prime.
• A003635: Inconsummate numbers.
• A046411: Composite numbers where the concatenation of their prime factors is a prime (single step to home prime).
• A108540: Golden semiprimes.
• A255897: Primes equal to the sum of both two and three successive semiprimes.
• A006558: Start of the first run of n consecutive integers with the same number of divisors.
• A045983: Numbers k such that n or more consecutive integers starting at k have the same number of distinct prime divisors.
• A046354: Composite palindromes whose sum of prime factors (with multiplicity) is palindromic.
• A056215: Primes p for which the period of reciprocal 1/p equals (p-1)/10.
• A104825 / A104928: Primes from merging successive digits in the decimal expansion of Pi or Pi squared.
• A048131: Numbers becoming prime or 4 after exactly 9 iterations of f(x) = sum of prime factors of x.
• A006038: Odd primitive abundant numbers.
• A005835: Pseudoperfect numbers.
• A262054: Euler pseudoprimes to base 7.
• A002649: Quintan primes.
• A085158 / A289697: Sextuple factorial and numbers k such that k!6 - 24 is prime.
• A131354: Number of primes in the open interval between successive tribonacci numbers.
• A053584: Smallest prime ending with a(n), where a(1)=7 (related to left truncatable primes).
• A000005: The tau function (number of divisors).
• A270865: Smallest primes of 4x4 semi-magic squares formed from consecutive primes.
• A038369: Sum-product numbers.

The sources provide algorithms, definitions, and examples, often linking to OEIS for further information. They also highlight the computational challenges of generating very large numbers or sequences in SageMathCell due to timeouts.

*********************************

The NotebookLM provides links to all the items referenced which is quite useful. These are lost in the copy-paste to Blogger. Gemini admits this limitation and it's just another example of Google's lack of support for this blogging platform. Here is the link to the SageMath: Number Theory and Algorithms NotebookLM.