Questions on the number-theoretic functionality of Mathematica.

learn more… | top users | synonyms

43
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 : ...
36
votes
5answers
2k 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:
26
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 ...
25
votes
6answers
11k views

Even Fibonacci numbers

Today, I found the Euler Project. Problem #2 is Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: ...
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!]]]] ...
22
votes
2answers
1k views

Trying to Visualize a Collatz - The Collatz conjecture

So I'm new in this and learning--- and 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 ...
20
votes
4answers
844 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 ...
19
votes
2answers
366 views

Speeding up the built-in Rudin-Shapiro and Thue-Morse sequence functions

Version 10.2 introduced two well-studied sequences as functions: the (Golay-)Rudin-Shapiro sequence (RudinShapiro[]) and the (Prouhet-)Thue-Morse sequence (...
15
votes
4answers
2k views

Semi prime numbers

The high school textbook I am using has the example of semi-prime numbers. They wanted students to find (by "perspiration") all the semi-prime numbers less than $50$ (for a question on set theory). ...
15
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.
14
votes
6answers
1k views

Integers which are the sum of both two and three consecutive squares

This is a math problem I came across the other day: $365$ can be written as a sum of two and also three consecutive perfect squares: $365=14^2+13^2=12^2+11^2+10^2$ What is the next ...
14
votes
3answers
615 views

How can FactorInteger be so slow if PrimeQ is fast?

My 8th grade son had a homework problem to find a prime factor of $99!-1$. I thought to be clever/lazy and used FactorInteger[99!-1], but it takes forever. ...
14
votes
2answers
462 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: ...
14
votes
3answers
705 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 ...
13
votes
6answers
2k 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?
13
votes
3answers
525 views

Next highly composite number?

R language has this function 'nextn' (link) which computes the next highly composite number greater than a given one, which is used to find the optimal padding size for the subsequent FFT operation. ...
13
votes
1answer
376 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 ...
12
votes
8answers
519 views

Find the minimum integer r such that $(10^r - 1)/37$ is an integer

I know Element[(10^r - 1)/37, Integers] tests the condition. So what is the command that gives me the minimum integer value r ...
12
votes
5answers
719 views

Double series over primes

I'm very curious if the following double series over primes has a closed form: $$\sum_{k \in \mathcal{P}}\sum_{n \in \mathcal{P}}\frac{1}{k\;n(k+n)^2}$$ where $\mathcal{P}$ denotes the set of all ...
12
votes
1answer
441 views

the more effective method to find 21 digits armstrong number

In recreational number theory, a narcissistic number (also known as a pluperfect digital invariant (PPDI), an Armstrong number(after Michael F. Armstrong) or a plus perfect number) is a number that is ...
11
votes
2answers
579 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 ...
10
votes
1answer
679 views

Modular arithmetic - efficiently calculating the remainders of factorials

When working on this question regarding the divisibility of the sum of factorials, I decided to write some code to test "small values" of the problem using the following code. ...
10
votes
1answer
193 views

Is there a PrimeQ whose accuracy guarantee you can adjust?

Say I have a list of a million integers each with a million digits, and I want a crude sieve to see which have a chance at being prime. Mathematica has a PrimeQ function, which appears to be slow ...
9
votes
3answers
647 views

Proving (or at least 'being told by Mathematica') that Sqrt[2] is irrational?

I realize that Mathematica is not specifically an automated theorem prover. However, this article: http://www.wolfram.com/products/mathematica/newin6/content/EquationalTheoremProving/ Suggests that ...
9
votes
3answers
1k views

Has Mathematica a function to compute the Smith Normal Form?

The Smith normal form is a matrix that can be calculated for any matrix (not necessarily square) with integer entries. See Wikipedia for a more elaborate description. Has Mathematica a function to ...
9
votes
1answer
224 views

Possible improvements to this Syracuse (3x+1)/2 graph?

This algorithm produces the Syracuse disjoint tree graph without any duplicates. No need for Union, For, and ...
9
votes
1answer
135 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
0answers
620 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 ...
8
votes
4answers
342 views

Generate PrimePower counting function

Is there a way to generate a counting function for prime powers - i.e. to create a similar function to PrimePi, but including prime powers. The following will, of ...
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, ...
7
votes
5answers
547 views

Calculating weird numbers

A weird number is a number such that the sum of the proper divisors (divisors including 1 but not itself) of the number is greater than the number, but no subset of these divisors sums to to ...
6
votes
5answers
787 views

Write any positive integer as a sum of squares

With n = 17 I would like to get {4, 1} and with n = 999 {31, 6, 1, 1} so that, for example, ...
6
votes
3answers
694 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 ...
6
votes
3answers
181 views

On a strange pattern of triangular numbers in Ulam's spiral

In this MSE post, user GeMir noticed that, where the green dots are the triangular numbers, $$T_n = \frac{n(n+1)}{2} = 1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,\dots$$ in the Ulam spiral ...
6
votes
2answers
175 views

Number of divisors visualized with the QPochhammer function, how improve performance of code?

I have this code that is originally Jeffrey Stopple's code for the Riemann zeta function in the complex plane. Because I discovered yesterday that the number of divisors can be generated with the ...
6
votes
1answer
619 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
155 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
3answers
384 views

Better answer to Santa's riddle about sum of a number's divisors?

I was hoping to find an elegant solution to this riddle, using only a line or two of Mathematica: Santa Claus was telling one of his elves: "If I multiply the age of three of my reindeer, I get ...
6
votes
1answer
173 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 ...
5
votes
4answers
629 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 ...
5
votes
3answers
277 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
1answer
113 views

Find all “chains” in the poset of divisors

I want to input a set of divisors of an integer $n$ and return all subsets of these divisors ${d_1,d_2,...d_k=n}$ such that $d_1$ divides $d_2$, $d_2$ divides $d_3$, ... and $d_(k-1)$ divides $d_k$. I ...
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 ...
5
votes
1answer
165 views

Ruth-Aaron quadruple challenge

This a computational challenge, to find an efficient algorithm to discover a quadruple $(n,n+1,n+2,n+3)$ with the same sum of prime factors as described in the MO question, "Ruth-Aaron triples, etc." ...
5
votes
2answers
168 views

FactorInteger over UFDs

How can I factor 'integers' over other quadratic number fields (not just gaussian integers). For instance, how could I factor $7 = (3 + ω)(2 − ω)$ over Eisenstein integers ($ω = \frac{-1+ I ...
4
votes
5answers
262 views

On finding all the positive integral solutions of $x^2+y^2=z^2+1$

I am a new to Mathematica. My goal is to find many (if not all) positive integer solutions to the equation: $x^2+y^2=z^2+1$ using Mathematica. However the problem is that I can only find a ...
4
votes
4answers
283 views

Conveying density of 5-smooth (Hamming) numbers

A number is 5-smooth if its only prime factors are 2, 3 or 5. Example: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … Interesting thing is that as they become larger ...
4
votes
1answer
423 views

Von Mangoldt function

Can anybody evaluate the following sum for me $$ \sum\limits_{n=2}^\infty(-1)^n\left(\frac{\psi(n)}{n}-\frac{\Lambda(n)}{2n}\right) $$ where $\psi(n)$ is the Chebyshev function and $\Lambda(n)$ is ...
4
votes
1answer
170 views

How to further accelerate arithmetic with Fermat Pseudoprime and Fibonacci number

I've been working on this all night, and I have made this go pretty fast, compared to my first iteration of the program, but now I'm out of ideas. I'm trying to write a program to test (by good ...
4
votes
2answers
283 views

Approximation to the prime counting function

Is there a function similar to PrimePi that gives approximate value for large numbers? In particular, I need a reasonably good approximation for $\pi(x)$, where ...