Questions on the number-theoretic functionality of Mathematica.
2
votes
1answer
66 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 ...
28
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 :
...
2
votes
3answers
131 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
1answer
82 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 ...
1
vote
1answer
116 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 ...
3
votes
3answers
218 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 ...
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.
...
2
votes
2answers
189 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 ...
10
votes
6answers
400 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?
4
votes
1answer
272 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 ...
7
votes
1answer
244 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
150 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, ...
5
votes
3answers
143 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.
6
votes
1answer
95 views
Implementing Remainder Tree
I want to implement Remainder Tree based on this. With the answers on SE I've come up with:
...
1
vote
0answers
150 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 ...
13
votes
2answers
296 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:
...
9
votes
1answer
306 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 ...
1
vote
3answers
255 views
Generating pairs of additive and multiplicative factors for integers
Given an integer $n$, I want 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 came up ...
3
votes
0answers
192 views
Parallel PowerMod
Is there anyway to parallelize the PowerMod function?
Here is my Left-To-Right modular exponentation:
...
6
votes
1answer
295 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 ...
5
votes
0answers
79 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 ...
9
votes
5answers
797 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.
18
votes
6answers
777 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!]]]]
...
13
votes
3answers
316 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
...
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 ...
27
votes
4answers
768 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:
7
votes
0answers
251 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 ...
17
votes
4answers
514 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 ...
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 ...
