Questions tagged [number-theory]

Questions on the number-theoretic functionality of Mathematica.

Filter by
Sorted by
Tagged with
56
votes
2answers
5k 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: ...
37
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:
34
votes
8answers
31k 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: ...
34
votes
2answers
8k views

Trying to visualize the Collatz conjecture

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 a visual 3D adjacency graph of my ...
27
votes
7answers
3k 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!]]]] ...
27
votes
1answer
1k views

Fast calculation of discrete logarithms

Does Mathematica have any built-in fast algorithms for calculating discrete logarithms over $(\mathbb{Z}_p)^\times$ (the group of integers modulo $p$)? Essentially, for a fixed large prime ...
26
votes
1answer
4k 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 ...
24
votes
3answers
565 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 (...
21
votes
4answers
1k 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
4answers
3k views

Find the 5566th digit after the decimal point of 7/101

I want to find the 5566th digit after the decimal point of 7/101. I input the following code into Mathematica 11: Mod[IntegerPart[7/101*10^5566], 10] The output ...
18
votes
7answers
2k 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 number with ...
18
votes
6answers
3k views

Fastest square number test

What is the fastest possible square number test in Mathematica, both for machine size and big integers? I presume starting in version 8 the fastest will be a dedicated C LibraryLink function.
17
votes
3answers
876 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 ...
16
votes
4answers
1k 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. ...
16
votes
4answers
3k 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). ...
16
votes
4answers
868 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. ...
16
votes
1answer
205 views

Is it better to completely forget about the existence of PowersRepresentations?

I noticed that in several cases the performance of PowersRepresentations is hugely worse than that of IntegerPartitions. (Mma 10....
15
votes
1answer
549 views

InverseTotient[ ]?

Maple has a function InverseTotient( c ), which returns all those natural numbers $n$ whose Euler totient function $\phi( n ) = c$. Is there an equivalent inverse ...
15
votes
1answer
963 views

Visualisation of the field of algebraic numbers in the complex plane

Hot to plot the field of algebraic numbers in the complex plane? In this picture, the color of a point indicates the degree of the polynomial of which it’s a root: red = rational numbers ...
15
votes
2answers
414 views

Factor a polynomial Root into Roots of smallest possible degree

Suppose I have a polynomial Root representing an algebraic number. I want to represent it as a product of several polynomial Root...
15
votes
2answers
580 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
6answers
6k 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?
14
votes
2answers
962 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 ...
14
votes
3answers
2k 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
7answers
2k views

Finding vampire numbers

How to find vampire numbers by using Mathematica? A number $v=xy$ with an even number $n$ of digits formed by multiplying a pair of $n/2$-digit numbers (where the digits are taken from the ...
13
votes
5answers
983 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 ...
13
votes
2answers
805 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 ...
13
votes
1answer
284 views

Accuracy of PrimeQ function

Using PrimeQ in Mathematica 10 on integers up to $2\cdot 10^{5717}$ the function appears to work. The Documentation for Mathematica 5 says that ...
13
votes
1answer
443 views

What is the confidence limit on this convergence?

Bug introduced in 7.0 and fixed in 10.0.0 When I run this, Product[n^MoebiusMu[n],{n,1,Infinity}] I get $\frac{1}{4 \pi^{2}}$ Over on Math Overflow they ...
12
votes
8answers
2k 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
3answers
815 views

Double Sum Involving Condition

I would like to compute the dimensions of some small free nilpotent Lie algebras. However, I am totally new to this and I could not figure out how to write the double sum which gives the dimension of ...
12
votes
3answers
3k 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 ...
12
votes
1answer
455 views

SquaresR memory leak?

I have tried the following code in Mathematica 11.0.1.0 on my MacBook: ...
12
votes
2answers
623 views

Ulam's Spiral with Oppermann's Diagonals (quarter-squares)

First we craft a function to return the quadrant boundary based on Oppermann's Conjecture a[n_] := (Mod[n, 2] + n^2 + 2 n)/4 Then we create a few lists ...
12
votes
1answer
346 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 ...
11
votes
2answers
1k views

Number of digits for factorial of 12345678987654321

What is the number of digits (IntegerLength) of the factorial of 12 345 678 987 654 321? The number of zeros at the end of this factorial was calculated and it is huge: exactly 3 086 419 746 913 569 ...
11
votes
3answers
1k views

François Viète's approximation to π

How do I program the approximation to π devised by François Viète, which is given by 2 * 2/Sqrt[2] * 2/Sqrt[2 + Sqrt[2]] * 2/Sqrt[2 + Sqrt[2 + Sqrt[2]]] * ... ...
11
votes
3answers
4k views

Easier program for period of Fibonacci sequence modulo p

For a little project I need to calculate the period of a Fibonacci sequence modulo p, for which p is a prime number. For example, the Fibonacci sequence modulo 19 would be: $$0, 1, 1, 2, 3, 5, 8, 13, ...
11
votes
2answers
870 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. ...
11
votes
2answers
1k views

Finding Ramanujan's taxicab numbers

How to find Hardy-Ramanujan Numbers by using Mathematica? Definition: Taxicab number is defined as the smallest number that can be expressed as a sum of two positive cubes in $n$ distinct ways. ...
10
votes
1answer
194 views

How to calculate $\displaystyle \prod_{p}\frac{p^2+1}{p^2-1}$?

When I input $$ \prod _{p=2}^{\infty } \text{If}\left[\text{PrimeQ}[p],\frac{p^2+1}{p^2-1},1\right] $$ in Mathematica 12.0, it gives out the value $1$. The result is ridiculous, for that according to ...
10
votes
1answer
229 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
4answers
380 views

First two n such that $1355297$ divides$10^{6n+5}-54n-46$ for $n>0$

I have problem solving this equation, smallest n such that $1355297$ divides $10^{6n+5}-54n-46$. I tried everything using my scientific calculator, but I never got the correct results(!).and finally I ...
9
votes
2answers
505 views

Number of divisors visualized with the QPochhammer function, how to 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 $q$-...
9
votes
1answer
345 views

Calculate $140$ digits of Conway's Constant from the Look and Say Sequence

The look-and-say sequence is the sequence of numbers $1, 11, 21, 1211, 111221, 312211, …,$ in which each term is constructed by “reading” the previous term in the sequence. For example, the term $1$ ...
9
votes
2answers
199 views

Efficiently checking whether a number is a perfect power

Goal The goal is to efficiently check whether a number is a perfect power. Attempts It is possible to check whether a number is a perfect power using ...
9
votes
2answers
600 views

Visualizing the primes with the Riemann Zeta function

I am trying to plot the identity seen here, namely that if we define: $$\psi _{0}(x)={\frac 12}\left(\sum _{{n\leq x}}\Lambda (n)+\sum _{{n<x}}\Lambda (n)\right)$$ Then, it equal to the following,...
9
votes
1answer
161 views

Modular equation problem

I have problem solving this modular equation $67^n \equiv 67 \pmod {317026939759222841944}$ with $n>1$. I have tried my Laptop and Wolfram Alpha engine, but I don't get any solution, I'm very ...
9
votes
1answer
246 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
0answers
846 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 $$...