Questions on the number-theoretic functionality of Mathematica.

learn more… | top users | synonyms

6
votes
3answers
692 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
2answers
368 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 ...
5
votes
1answer
340 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 ...
8
votes
1answer
209 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, ...
6
votes
1answer
153 views

Implementing Remainder Tree

I want to implement Remainder Tree based on this. With the answers on SE I've come up with: ...
14
votes
2answers
461 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: ...
3
votes
0answers
279 views

Parallel PowerMod

Is there anyway to parallelize the PowerMod function? Here is my Left-To-Right modular exponentation: ...
6
votes
1answer
616 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 ...
14
votes
5answers
2k 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.
23
votes
6answers
2k 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!]]]] ...
2
votes
0answers
148 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 ...
9
votes
0answers
619 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 ...
25
votes
1answer
3k 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 ...