Questions tagged [number-theory]

Questions on the number-theoretic functionality of Mathematica.

Filter by
Sorted by
Tagged with
2
votes
3answers
181 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: ...
2
votes
1answer
123 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 $100$....
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 ...
1
vote
1answer
138 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
778 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 $x\...
1
vote
3answers
210 views

factorization of integer into two parts with specific prime factors

I would like to write a Mathematica code to decompose an integer into two or more parts with primes in special intervals. For instance, I want to decompose $m=\binom{n}{k}$ into two parts U and V ...
3
votes
6answers
1k 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 ...
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 ...
1
vote
5answers
402 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 ...
2
votes
6answers
4k views

A question regarding 1 divided 243 [closed]

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
927 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, ...
2
votes
2answers
402 views

Why is Mathematica getting this modular root wrong?

First, note that $4^{96}\equiv 96 \pmod {100}$. Mathematica claims that PowerMod[96, 1/96, 100] has no integer solutions. Even more obviously wrong, I get ...
7
votes
1answer
824 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
162 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\}\},$$$$ \{...
4
votes
3answers
497 views

Multiplicative partition function

I am trying to create a multiplicative partition function that would generate something like ...
2
votes
1answer
428 views

Implementing Kane's Subset Sum Algorithm

In the following paper, D. Kane describes an algorithm for subset sum that runs in logspace: http://arxiv.org/pdf/1012.1336v2.pdf. I am trying to implement it ...
4
votes
4answers
363 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 and ...
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 ...
0
votes
2answers
163 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 ...
2
votes
0answers
116 views

Approximate to the speed of Built-In functions

In Mathematica, there is a function PowerMod[a,b,m], which computes a^b mod m. I will concern only this case: ...
5
votes
0answers
993 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
181 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
3answers
637 views

Why is my solution to PE #5 so slow

I'm new to Mathematica and it was suggested to me to go through the Project Euler problems in order to learn it. However, I can't quite figure out why my solution to #5 is so slow. The problem: ...
5
votes
1answer
136 views

Complex LogIntegral error

Going through Derbyshire's Prime Obsession & trying to take LogIntegral of 20^ZetaZero[1] & comes up with a value of <...
5
votes
1answer
220 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 ...
3
votes
2answers
835 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?
6
votes
2answers
271 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 \sqrt{3}}{...
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). ...
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 ...
3
votes
1answer
245 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
189 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
278 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 ...
2
votes
2answers
143 views

`PrimeNu` counting function

Building on this question, what is the most efficient counting function for distinct prime factors? It would obviously be more efficient if Prime and ...
0
votes
2answers
200 views

Code for sum of exponential divisors function

Consider $n = p_{1}^{a_1}\cdots p_{r}^{a_{r}}$. An integer $d = p_{i}^{b_{i}} \cdots p_{r}^{b^{r}}$ is called an exponential divisor of $n$ if $b_{i}$ divides $a_{i}$ for every $1\leq i \leq r.$ I am ...
6
votes
2answers
418 views

Memory management and speed for Fast GCD

Let's say that we have some $300\,\text{K}$ digits (arbitrary function) and want to trial factor with $100{,}000{,}000$ first prime numbers. ...
5
votes
1answer
811 views

Negative Continued Fraction of a Rational

The $n^{\text{th}}$ negative continued fraction convergent $x_n$ of a positive real $x$ is computed by the nested function \begin{align} x_n = k_1 - \frac{1}{k_2 - \frac{1}{k_3 - \dots - \tfrac{1}{k_n}...
8
votes
4answers
408 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 ...
1
vote
4answers
305 views

Generating a list of cubefree numbers

I am trying to generate a list of cubefree numbers (i.e. numbers when prime factorized contain no tripled factors) within a given range. Of DivisorSigma, ...
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: ...
5
votes
1answer
957 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 ...
2
votes
1answer
605 views

How can I calculate all irreducible polynomials of 31 degree in $\mathbb Z_2[x]$?

How can I calculate all binary irreducible polynomials of degree 31? or how i calculate all irreducible $f$ in $\mathbb Z_2[x]$? (The irreducible polynomial in $\mathbb Z_2[x]$ and $\mathbb R$ are ...
1
vote
3answers
216 views

Number theory: Problem involving rational numbers

Use RandomRat to test whether ((-1)^(1/Denominator[q]))^Numerator[q] is identical with (-1)^q...
7
votes
5answers
1k 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 ...
3
votes
3answers
244 views

What is the formula for this numerical series?

I'm developing a questions game. My goal is that the score for each correct answer will increase as the user answers more questions. Initially there are 15 points for each correct answer. Every 4 ...
7
votes
1answer
841 views

Implementation of the Polynomial Chinese Remainder Theorem

I would like an implementation of the Chinese Remainder Theorem for polynomials in $\mathbb{Z}[x]$, that is, a function ...
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 ...
-1
votes
3answers
368 views

Find integer values of p such that $(2^p - (2^2)(3^2))/ (3^3)$ is an integer

Find integer values of p such that $(2^p - (2^2)(3^2))/ (3^3)$ is an integer.
4
votes
0answers
118 views

Simplifying expressions involving Divisible

FullSimplify[ Divisible[p^2 - 1, 24] , Element[p, Primes] && p > 3] Should evaluate to True, but I get ...
16
votes
4answers
869 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. ...
2
votes
1answer
466 views

Expressing large numbers in index form

I have a quick question. Is there anyway of expressing a large number as a power of another number in Mathematica? By this, I mean for example, $1237940039285380274899124224 = 512^{10}$. Is there a ...