Questions on the number-theoretic functionality of Mathematica.
29
votes
2answers
3k 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 :
...
27
votes
4answers
773 views
Factorisation diagrams
Here is a way to visualize the factorisation of natural numbers. How do we get this or a similar kind of output using Mathematica?
See the list of images generated for number from 1 to 36:
21
votes
1answer
2k views
Finding long strings of identical digits in transcendental numbers
Introduction
Describing the three main streams of present-day mathematical philosophy (formalism, Platonism and intuitionism) in a well-known book, The Emperor's New Mind, R. Penrose says:
...it ...
20
votes
6answers
834 views
efficient way to count the number of zeros at the (right) end of a very large number
If I want to count the number of zeros at the (right) end of a large number, like $12345!$, I can use something like:
Length[Last[Split[IntegerDigits[12345!]]]]
...
17
votes
4answers
515 views
Why does Mathematica claim there is no even prime?
I wonder if this is a bug, or if I'm misunderstanding something:
Exists[n, EvenQ[n] && PrimeQ[n]] // Resolve
(*
==> False
*)
So if I interpret this ...
13
votes
2answers
301 views
Why does iterating Prime in reverse order require much more time?
Say I would like to display the $10$ greatest primes that are less than $10^5$. I could do the following:
...
13
votes
3answers
347 views
How to know if a number is the square of a rational?
I'm pretty new with Mathematica and I was looking for a way to know whether a number is a square of a rational. I thought of
Head[Sqrt[myNumber]] == Rational
...
10
votes
6answers
431 views
How to find lattice points on a line segment?
How do I find points on the line segment joining {-4, 11} and {16, -1} whose coordinates are positive integers?
9
votes
5answers
827 views
Fastest square number test
What is the fastest possible square number test in Mathematica 7, both for machine size and big integers?
I presume in version 8 the fastest will be a dedicated C LibraryLink function.
9
votes
2answers
349 views
FiniteFields package is very slow. Any fast substitute for Mathematica?
I want to compute the inverse of matrix, say with dimensions $100 \times 100$, defined over a large finite field extension such as $GF(2^{120})$. I am using the package FiniteFields, but Mathematica's ...
7
votes
1answer
72 views
ToNumberField won't recognize Root[…] as explicit algebraic number
In Mathematica 9.0.1, it appears that ToNumberField will not always recognize a Root object as an explicit algebraic number.
...
7
votes
1answer
247 views
What is the confidence limit on this convergence?
When I run this,
Product[n^MoebiusMu[n],{n,1,Infinity}]
I get $\frac{1}{4 \pi^{2}}$
Over on Math Overflow they are saying it shouldn't happen. So, how do ...
7
votes
1answer
151 views
Testing for primality in quadratic rings?
Testing for primality in $\mathbb{Z}[\sqrt{-1}]$ in Mathematica is easy:
PrimeQ[n, GaussianIntegers -> True]
But how can I test for primality in, say, ...
7
votes
0answers
264 views
Does Mathematica use the Elliptic Curve Method (ECM) in FactorInteger[]?
I'm not a mathematician, and I'm not even going to pretend that I understand anything of the ECM. But I know it can be a fast method for factorization.
I benchmarked the factorization of ...
6
votes
1answer
305 views
Evaluate continued fraction
Mathematica has the ContinuedFraction[] function to give the continued fraction expansion of a rational (or approximation of a real) number. I'm interested in the ...
6
votes
1answer
98 views
Implementing Remainder Tree
I want to implement Remainder Tree based on this. With the answers on SE I've come up with:
...
5
votes
3answers
144 views
How could I implement the equivalent of NextPrime
I would like to know what an implementation of the function NextPrime would look like if it were implemented in Mathematica's core language.
5
votes
0answers
81 views
Doing computations in a modulo ring
I need to perform some computations in a modulo ring, like
Mod[Subfactorial[n], m]
Mod[Binomial[n, k], m]
However, this is obviously much too slow for large ...
4
votes
1answer
76 views
How can I program the RiemannR function using the LogIntegral command?
I would like to program the RiemannR function using the LogIntegral command
because I would like to later experiment with a ...
4
votes
1answer
276 views
Which DirichletCharacter is KroneckerSymbol?
If $d$ is a fundamental discriminant, KroneckerSymbol[d,n] is a Dirichlet character modulo $|d|$. Which one is it? If $d>0$ is a prime $\equiv 1\bmod 4$, then ...
3
votes
3answers
234 views
Implementing the Farey sequence efficiently
There is of course the silly implementation:
FareySequence[n_] := Union[Flatten[Table[j/i, {i, 1, n}, {j, 0, i}]]]
However, there are numerous properties and ...
3
votes
1answer
95 views
How does Mathematica calculate the nth prime?
When I enter Prime[2000000000000], the two-trillionth prime, Mathematica gives 61427839512211 for the answer after several ...
3
votes
1answer
160 views
Function to Determine Lucky Numbers
Given a list of the form {1, 3, 5, 7, ...}, the lucky numbers are obtained by looking at the first list element after 1 (so 3 in this case), and deleting all list ...
3
votes
1answer
120 views
Finding the largest integer that cannot be partitioned in a certain way
I want to use Mathematica to solve the problem:
Find the maximum $k$ such that $6x+9y+20z=k$ does not have a non-negative solution.
I tried FrobeniusSolve. ...
3
votes
0answers
194 views
Parallel PowerMod
Is there anyway to parallelize the PowerMod function?
Here is my Left-To-Right modular exponentation:
...
2
votes
3answers
137 views
Why do these two different zetas produce the same value?
Zeta[-13] == Zeta[-1] == -1/12
Why do these two different zetas produce the same value?
2
votes
3answers
269 views
Generating pairs of additive and multiplicative factors for integers
Given an integer $n$, I want to get two lists:
a) the set of pairs of the divsors $a,b$ into exactly two factors $n=a\cdot b$,
b) the set of pairs $a,b$ of two summands $n=a+b$.
The code I ...
2
votes
2answers
194 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 ...
2
votes
1answer
93 views
Expressing large numbers in index form
I have a quick question. Is there anyway of expressing a large number as a power of another number in Mathematica? By this, I mean for example, $1237940039285380274899124224 = 512^{10}$. Is there a ...
2
votes
1answer
89 views
Generating a list of all factorizations
What is the best way to generate a list of all factorizations of some number $n$? I'm quite new to Mathematica so this might be obvious. I have been trying some basic stuff with ...
2
votes
0answers
86 views
PowersRepresentations Algorithm
I'm trying to understand the mathematics behind counting the number of representations of a positive integer by $n$ distinct $k$th powers, i.e. I would really like to know how to do the Mathematica ...
1
vote
1answer
59 views
Hermite Normal Form in “columns” convention
After describing the Hermite Normal Form (HNF), MathWorld explains:
The Hermite normal form for integer matrices is implemented in Mathematica as ...
1
vote
1answer
119 views
Another MoebiusMu question
When I evaluate the Mertens function to infinity:
NSum[MoebiusMu[k], {k, 1, \[Infinity]}]
I get -1, but I expected to get -2.
I wanted to modify the ...
1
vote
0answers
154 views
Faster GCD Implementation
Is there any chance to write a faster GCD than the built-in one in Mathematica?
@Mr.Wizard has written one in this question (although it's not for this purpose) which is 6 times slower on a 100k ...
