Questions on the number-theoretic functionality of Mathematica.
27
votes
4answers
764 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:
25
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 :
...
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 ...
18
votes
6answers
768 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
504 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
288 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
315 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
395 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
792 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
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 ...
7
votes
1answer
71 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
239 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
148 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
94 views
Implementing Remainder Tree
I want to implement Remainder Tree based on this. With the answers on SE I've come up with:
...
6
votes
0answers
250 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 ...
5
votes
3answers
142 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
78 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
282 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 ...
4
votes
1answer
271 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
214 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
0answers
192 views
Parallel PowerMod
Is there anyway to parallelize the PowerMod function?
Here is my Left-To-Right modular exponentation:
...
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 ...
2
votes
3answers
50 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?
1
vote
3answers
247 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 ...
1
vote
1answer
115 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
1answer
55 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
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 ...
1
vote
0answers
85 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 ...
