Questions on the number-theoretic functionality of Mathematica.

learn more… | top users | synonyms

2
votes
2answers
95 views

Need help with code for number theory problem

I'm completely new to Mathematica (used previously only for very simple cases). I need to write a quite complex function. The function must do the following: Input consists of two numbers: a and b. ...
2
votes
1answer
190 views

Using the Baby-Step Giant-Step algorithm

Here is a concept I am working through: As part of an attack on an El-Gamal cipher, solving the discrete logarithm problem $$10^x = 532107 \;\, {\rm mod} \;\, 1313839.$$ Using the ...
1
vote
1answer
179 views

Factoring large integers with the Pollard p-1 method

I am trying to use the Pollard $p-1$ method to find the factors of a large integer. Here is the problem: An RSA-type cipher is based on the integer $n = 140016480344628383$ and exponent ...
14
votes
3answers
742 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 ...
4
votes
5answers
352 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 ...
0
votes
1answer
94 views

solving quadratic and linear congruences with different modulus

We are able to solve the quadratic congruences $C^2 + Q^4 - 2\equiv mod 3072$ and $C - Q^2 - 2046\equiv mod 3072$ by entering ...
1
vote
3answers
135 views

Expressing a series formula

I want to generate a series of the following kind in Mathematica: $\quad \quad a(n+1) = a(n) + ({\rm prime}(n+1) - 1)/2 \quad \mbox{for odd primes},$ so that the resultant series is ...
0
votes
1answer
74 views

How to “de rationalize” a number? [closed]

How can 1/2 be represented as 0.5? Thanks!
0
votes
2answers
63 views

What would be the most efficient way of finding the first repeated term in Sylvester's sequence modulo the $n$th prime?

If a multiple of a prime, say 13, occurs in Sylvester's sequence, then Sylvester's sequence modulo that prime eventually gets stuck on a bunch of 1's, and ...
2
votes
1answer
140 views

What are the terms of the sequence generated by Zeta(3s)/Zeta(s)?

The LiouvilleLambda function has Dirichlet generating function of Zeta[2s]/Zeta[s]. I am curious about an analogous function with Dirichlet generating function of Zeta[3s]/Zeta[s]. Can Mathematica ...
0
votes
1answer
277 views

Finite Field matrix rank calculation

How does one define a matrix over $\mathrm{GF}(p^r)$ in Mathematica in order to compute rank? I am working with $\mathrm{GF}(2)$?
6
votes
2answers
164 views

Generating $\mathbb{Z}^*_n$

I'm using Mathematica to illustrate basic number theory concepts in a graduate cryptography class. To generate elements of the multiplicative group of integers modulo $n$, i.e. $\mathbb{Z}^*_n$, I can ...
1
vote
2answers
93 views

Arithmetic on algebraic numbers

I'd like to perform some elementary operations on algebraic numbers. ...
4
votes
3answers
226 views

Code for (a,b) with gcd(a,b)=1?

I am trying to make a big table that includes all ordered pairs (a,b) with a (1,2) (1,3) (2,3) (1,4) (3,4) (1,5) (2,5) (3,5) (4,5) (1,6) (5,6) ... Any ideas? Thanks!
7
votes
5answers
717 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 ...
2
votes
2answers
139 views

Can Mathematica return the first few terms of a sequence given the first few terms of a Dirichlet Generating Function?

For example: a=Sum[1/n^s,{n,1,6}]; Expand[a^2] returns a big mess. I want to see something like: 1/1^s + 2/2^s + 2/3^s + 3/4^s + 2/5^s + 4/6^s + ... + 1/36^s.
14
votes
3answers
728 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. ...
8
votes
2answers
231 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 ...
12
votes
8answers
597 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 ...
5
votes
1answer
172 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." ...
7
votes
3answers
484 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 ...
3
votes
1answer
106 views

Factoring an ideal in a number field into prime ideals

I'd like to factor an ideal in a number field into prime ideals, exactly as in this example from the Sage documentation: ...
2
votes
3answers
141 views

Can you compute more terms in this sequence?

I am trying to identify a sequence related to the von Mangoldt function matrix. Since I believe/conjecture that the columns in the matrix have period lengths as in this sequence b: ...
0
votes
0answers
106 views

Solution of a set of quadratic congruences (Chinese remainder)

Edit: Please remove this question. I think there are mathematics error in what I am asking. You are welcome to edit the question if you can state the problem correctly. I have a set of quadratic ...
2
votes
1answer
104 views

One of the factors greater than $x$

Is there an easy way to tell Mathematica to find one of the prime factors of $n$ greater than $x$. For example, if $n=1299709\cdot 7919 \cdot 17$, is there a way to request a factor greater than ...
17
votes
7answers
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 number with ...
1
vote
1answer
128 views

Mathematica spitting code back when using Resolve over a large range of interest

I've just started using Mathematica and have encountered my first issue. Below are two commands which only differ in the range of values I am asking Mathematica to check. The first works fine, but the ...
7
votes
2answers
379 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 ...
3
votes
6answers
546 views

Triangular numbers boolean function

I read the new book by Paul Wellin Programming in Mathematica. There is an exercise about triangular numbers. (The n-th triangular number is defined as the sum of ...
13
votes
1answer
530 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 ...
1
vote
5answers
333 views

Write a number as the product of its two largest divisors

For even n >= 10 && n <= 98 I want to write n as the product of its two largest divisors (excluding ...
3
votes
5answers
2k views

A question regarding 1 divided 243

Here is a problem due to Feynman. If you take 1 divided by 243 you get 0.004115226337 .... It goes a little cockeyed after 559 when you're carrying out the decimal expansion, but it soon straightens ...
6
votes
5answers
813 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, ...
7
votes
1answer
549 views

Calculating the density of nearest neighbours

I am trying to plot this which is a numerical simulation of the Montgomery-Odlyzko law for the nontrivial 1st $10^5$ zeros of the Riemann zeta function $ζ(s)$. The solid line is given by ...
3
votes
2answers
135 views

Symbolic multiplicative partitions

Let $p_n\#\equiv\prod_{k=1}^{n}p_k$ (primorial): p[n_] := Times @@ Prime[Range[n]] then the multiplicative partitions of $p_{1,2,3,4}\#$ are $$ \{\{2\}\},$$$$ ...
3
votes
2answers
306 views

Multiplicative partition function

I am trying to create a multiplicative partition function that would generate something like ...
4
votes
4answers
302 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 ...
10
votes
1answer
212 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 ...
0
votes
2answers
131 views

Testing the Erdos square free conjecture

Can someone please answer these two parts of my homework assignment? Adding an explanation would be appreciated! a. Test the Erdos square free conjecture for $n <= 30000$. You should use ...
1
vote
0answers
407 views

Elliptic curve cryptography in Mathematica

I can find no resources for doing elliptic curve cryptography. I have used the finite field package, but I find it cumbersome and it does not seem to have any builtin methods for ECC. How can I get ...
0
votes
1answer
90 views

Square root of a value defined in a finite field?

I am trying to find the right way to compute the square root of a number defined in a finite field. For example, ...
4
votes
1answer
109 views

Complex LogIntegral error

Going through Derbyshire's Prime Obsession & trying to take LogIntegral of 20^ZetaZero[1] & comes up with a value of ...
3
votes
1answer
141 views

How to calculate the residue of $1/f(z)$ at a numerical approximation to a root of $f(z)$?

The input Residue[1/DirichletL[19,10,s],{s,s0}] gives 0 even when s0 is a root. For ...
2
votes
2answers
393 views

Checking if a number is a perfect power

I wanted to know how would I use Mathematica in order to check if the number is a perfect power I saw the algorithm but couldn't grasp it enough to implement it, so can anybody help?
5
votes
2answers
186 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 ...
15
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). ...
11
votes
3answers
2k 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 ...
3
votes
1answer
210 views

Faster Solve for Fermat 4n+1 conjecture

Assuming that Fermat 4n+1 conjecture (each prime of the form 4n+1 is the sum of two squares) is true then I like to solve the ...
2
votes
3answers
161 views

Finding primes that have certain property

Let S[p] denote the sum of digits of p. A prime p is said to be stubborn if none of ...
2
votes
2answers
194 views

Quadratic Equations $\bmod p^k$

As part of a larger program, I need to solve $A x^2+B x+C \equiv 0 \pmod {p^k}$ for prime $p$. Right now I'm doing this by calling ...