Questions on the number-theoretic functionality of Mathematica.

learn more… | top users | synonyms

30
votes
2answers
2k views

Trying to visualize the Collatz conjecture

I happen to have this collatz collatz[x_, y_] := If[x == 3*y || x == 2*y + 1 || y == 3*x || y == 2*x + 2, 2, 0] So i want a visual 3D adjacency graph of my ...
8
votes
2answers
90 views

Efficiently checking whether a number is a perfect power

Goal The goal is to efficiently check whether a number is a perfect power. Attempts It is possible to check whether a number is a perfect power using ...
2
votes
3answers
180 views

Truncate an infinite continued fraction at order 2000

I want to solve an equation which contains an infinite continued fraction $F(n)$. Then I must (obviously) truncate this continued fraction at $n=2000$. The problem here is that Mathematica does not ...
2
votes
0answers
57 views

Rationalize error

The docs state that "Rationalize[x,dx] yields the rational number with smallest denominator that lies within dx of x." However, testing this out it appears to be false. ...
0
votes
0answers
40 views

Montgomery Modular reduction

I saw a Mathematica Implementation of Montgomery reduction at Montgomery Modular Exponentiation, a beautiful one by Simon Woods. I ran this in Mathematica and it was fast, but it does not give the ...
2
votes
0answers
114 views

Check Zagier theorem about Mahler's measure

I want to check the following theorem by using Mathematica: (from Heights of Polynomials and Entropy in Algebraic Dynamics, page 22) $\textbf{Theorem}.$ Let $\omega$ denote a primitive $6th$ ...
1
vote
0answers
63 views

Working with large integers in Modular Arithemetic

What would be the most efficient method of finding the remainder of the following division, 2^(2^330000000 - 1)/(2^330000001 - 1). I have tried using PowerMod function in Mathematica but i did not get ...
0
votes
1answer
338 views

Finite Field matrix rank calculation

How does one define a matrix over $\mathrm{GF}(p^r)$ in Mathematica in order to compute rank? I am working with $\mathrm{GF}(2)$?
3
votes
1answer
90 views

Factor a polynomial Root into Roots of smallest possible degree

Suppose I have a polynomial Root representing an algebraic number. I want to represent it (if possible) as a product of several polynomial ...
4
votes
3answers
599 views

Why is my solution to PE #5 so slow

I'm new to Mathematica and it was suggested to me to go through the Project Euler problems in order to learn it. However, I can't quite figure out why my solution to #5 is so slow. The problem: ...
3
votes
1answer
71 views

Numerical testing of Hardy's inequality

I want to check the following, Hardy's most fundamental inequality, by using Mathematica: $$\sum_{n=1}^\infty \left(\frac{A_n}{n}\right)^p<\left(\frac{p}{p-1}\right)^p\sum_{n=1}^\infty a_n^p$$ ...
-3
votes
1answer
156 views

Miller-Rabin algorithm [closed]

I want to implement the Miller-Rabin algorithm in Mathematica to check if a number is prime with at least 99.99% probability. I used this: ...
2
votes
2answers
348 views

Why is Mathematica getting this modular root wrong?

First, note that $4^{96}\equiv 96 \pmod {100}$. Mathematica claims that PowerMod[96, 1/96, 100] has no integer solutions. Even more obviously wrong, I get ...
1
vote
1answer
61 views

Get Mathematica to solve Modular Arithmetic problem [closed]

How would I get Mathematica to solve something like this for $x$? $4x \equiv 1 \pmod 5$
-2
votes
2answers
63 views

How can I implement Jordan's totient function?

How can I implement Jordan's totient function? It is a generalization of Euler's Phi function.
10
votes
1answer
188 views

Visualisation of the field of algebraic numbers in the complex plane

Hot to plot the field of algebraic numbers in the complex plane? In this picture, the color of a point indicates the degree of the polynomial of which it’s a root: red = rational numbers ...
0
votes
0answers
49 views

Efficiently create a list of factors of consecutive integers

I'm interested in a scalable (read: sublinear) algorithm for producing the list of integer factors of each integer from 1 to n. ...
3
votes
0answers
64 views

Are there any Mathematica programs on or about the LMFDB Archive?

I would like to explore the LMFDB Archive with L-functions using Mathematica. Is there any Mathematica sample code available to get me started?
15
votes
1answer
135 views

Is it better to completely forget about the existence of PowersRepresentations?

I noticed that in several cases the performance of PowersRepresentations is hugely worse than that of IntegerPartitions. (Mma 10....
3
votes
0answers
94 views

FrobeniusSolve: how does it work?

Can someone suggest any reference to read? I would like to understand how the algorithm works.
6
votes
3answers
212 views

Find the number of $n$ such that $n!$ is a sum of three squares

I want to check the following theorem by using Mathematica: $\textbf{Theorem} $. $\text{The estimate}$ $\# \{n \le x:n! \text{ is a sum of three squares}\}=7x/8+O(x^{2/3})$ $\text{holds.}...
0
votes
2answers
65 views

What would be the most efficient way of finding the first repeated term in Sylvester's sequence modulo the $n$th prime?

If a multiple of a prime, say 13, occurs in Sylvester's sequence, then Sylvester's sequence modulo that prime eventually gets stuck on a bunch of 1's, and FixedPoint...
3
votes
1answer
67 views

FindInstance only satisfies half of my double inequality

FindInstance[ 298973528525.436 < 10^10*(n - k*3.32192809488736) < 298973528539.862, {n, k}, Integers ] Result is: ...
0
votes
0answers
60 views

Factor Integer function with variable arguments

I'm trying to build a function that gives the highest power of a prime factor of a number. The following works perfectly: ...
2
votes
1answer
65 views

Twin Prime Max Gaps (Performance Tuning)

Ok, let's build a foundation here: A common way of testing primality, is dividing by all primes smaller than the number's square root. For instance, $97$ is prime because dividing by none of the ...
3
votes
2answers
167 views

Question about this Sieve of Eratosthenes graph

I googled for images of graphs and found nothing that even comes close to this one, so I want to experiment some more. ...
1
vote
2answers
164 views

Find the maximum Z in {(X + Y)==Z} using all the digits 0-9 only once

II want to add two integers with different digits to get a third integer with different digits. At the end, all 10 digits have to be different. So there should be 10 digits in total. How you ...
3
votes
1answer
20 views

What is the form of a PrimalityProving`PrimeQCertificate?

I understand the format of a proof of compositeness of an integer produced by PrimeQCertificate: it's well-documented that ...
3
votes
2answers
427 views

Plotting Chebyshev's theta function $\vartheta(x)$

The function I would like to plot is defined as $\sum\limits_{p\leq x}\log p.$ The following gives me I think a plot of the points of interest, but the function is defined for all $x > 0$ and so it'...
4
votes
0answers
48 views

Using Mathematica to find an alternative continued fraction for $\zeta(5)$

Given the Riemann zeta function $\zeta(n)$. I. $x=\zeta(3)$ Using Euler's continued fraction formula, we can form $\zeta(3)$'s cfrac as, $$Ax+B = \cfrac{1}{v_1 - \cfrac{1^6}{v_2 - \cfrac{2^6}{...
6
votes
5answers
880 views

Perfect numbers

The question given to me: a. Find the perfect numbers between $1$ and $10^6$ b: Find the abundant numbers between $1$ and $1000$ For a, I wrote ...
2
votes
2answers
196 views

Quadratic Equations $\bmod p^k$

As part of a larger program, I need to solve $A x^2+B x+C \equiv 0 \pmod {p^k}$ for prime $p$. Right now I'm doing this by calling ...
0
votes
2answers
142 views

Code for sum of exponential divisors function

Consider $n = p_{1}^{a_1}\cdots p_{r}^{a_{r}}$. An integer $d = p_{i}^{b_{i}} \cdots p_{r}^{b^{r}}$ is called an exponential divisor of $n$ if $b_{i}$ divides $a_{i}$ for every $1\leq i \leq r.$ I am ...
2
votes
2answers
102 views

`PrimeNu` counting function

Building on this question, what is the most efficient counting function for distinct prime factors? It would obviously be more efficient if Prime and ...
6
votes
2answers
370 views

Memory management and speed for Fast GCD

Let's say that we have some $300\,\text{K}$ digits (arbitrary function) and want to trial factor with $100{,}000{,}000$ first prime numbers. ...
10
votes
2answers
956 views

Number of digits for factorial of 12345678987654321

What is the number of digits (IntegerLength) of the factorial of 12 345 678 987 654 321? The number of zeros at the end of this factorial was calculated and it is huge: exactly 3 086 419 746 913 569 ...
22
votes
1answer
387 views

Fast calculation of discrete logarithms

Does Mathematica have any built-in fast algorithms for calculating discrete logarithms over $(\mathbb{Z}_p)^\times$ (the group of integers modulo $p$)? Essentially, for a fixed large prime ...
0
votes
1answer
84 views

What is the smallest number that equals the sum of two cubes in two ways? [closed]

How does one find the smallest number that equals the sum of two perfect cubes(positive) in two ways?
-5
votes
1answer
66 views

Finding a seven-digit number with all of its prime factors less than 20? [closed]

How can I find a seven-digit number with all of its prime factors less than 20? I have no clue how to do this.
4
votes
2answers
103 views

Goldbach Partition

I want to check the Goldbach conjecture for big number of $n$, but I don't know how to define this in Mathematica. There are my questions: Find a pair of primes $(p,q)$ for every even integer $n$, ...
3
votes
1answer
50 views

A function about prime gaps

I want to define a $f$ function on Mathematica such as this. $f[k]$ gives the smallest $m$ holds $2k=Prime[m+1]-Prime[m]$. For example, $$f[1]=2$$ $$f[2]=4$$ $$f[3]=9$$ $$f[4]=24$$ How can i do that?...
2
votes
1answer
105 views

One of the factors greater than $x$

Is there an easy way to tell Mathematica to find one of the prime factors of $n$ greater than $x$. For example, if $n=1299709\cdot 7919 \cdot 17$, is there a way to request a factor greater than $100$....
6
votes
1answer
90 views

Faster square test for integers

This question was asked already in Jan '12 and the most recent answer is from Oct '12, so it's several Mathematica versions out of date. What is a faster test for whether an integer is a perfect ...
0
votes
0answers
48 views

LatticeReduce question

Does LatticeReduce work with arbitrary precision arithmetic? That is, if I give it a linearly independent integer basis, but the integers are 40 decimal digits long ...
1
vote
0answers
46 views

Coppersmith's algorithm like Pari's zncoppersmith?

Is there some Mathematica package (or built-in that I missed) available, more or less equivalent to Pari's zncoppersmith function? Paraphrasing that source: given ...
4
votes
2answers
135 views

Finding vector of same direction with smallest integer coordinates

To determine Miller Indices of crystal lattice planes I would need a stable algorithm which determines the smallest set of integer coordinates of a vector which has same direction as a given vector (e....
0
votes
1answer
76 views

Why does this function return the largest integer less than or equal to √n?

I've been asked this question by my teacher. The function I'm talking about is the following: ...
52
votes
2answers
4k views

What is so special about Prime?

When we try to evaluate Prime on big numbers (e.g. 10^13) we encounter the following issue: ...