Questions tagged [prime-numbers]
Questions on testing and computing prime numbers.
185
questions
2
votes
0
answers
60
views
Optimizing getting a large number of values from PrimePi
I found out yesterday that there is a conjecture that the following function generates an addition chain:
$f(n)=\pi({n(n+1)\over 2}+1)$ for and integer $n\ge 1$. $\pi(x)$ is the prime counting ...
1
vote
0
answers
53
views
How to solve quartic equation modulo a composite? [closed]
I have an univariate polynomial equation over a composite moduli.
Namely the composite is of for $q=(2p)^{2}-1$ where $p$ is odd and $2p-1$ and $2p+1$ are distinct primes.
The modular equation is
$$ax^...
1
vote
2
answers
110
views
Solving a-two-variable equation in primes
How solve the following equation in Mathematica (preferably in one line) for pairs of $(x,y)$ such that $x$ and $y$ are primes?
$x^3-y^4=1$
0
votes
0
answers
27
views
Largest n in Prime[n] [duplicate]
What is the largest integer $n$ that the function Prime[n] can take?
2
votes
2
answers
97
views
Binary Distance between the two Primes
Given a prime number p, is there always a smaller positive integer exponent k such that p+2^k...
3
votes
3
answers
112
views
Prime $p$ that results in a power of 2
For every prime number $p$, the function ${\rm ms_2}(p)$ gives the smallest prime number that results in a power of 2 when added to $p$.
For example: ${\rm ms_2}(857) = 167$, since $857+167 = 1024 = 2^...
3
votes
6
answers
692
views
Make a list of the first 100 primes, keeping only ones whose last digit is less than 3 [closed]
This is a question from an "Elementary Introduction to the Wolfram Language" Section 28: Tests and Conditionals. We are asked to "Make a list of the first 100 primes, keeping only ones ...
1
vote
1
answer
82
views
Select primes from their Zeckendorf representation
I'm working with the Zeckendorf representation of prime numbers. I'm using
ResourceFunction["ZeckendorfRepresentation"][Prime[n]]
and I would like to select from all the results, the ones ...
0
votes
1
answer
92
views
Select odd numbers in table column that have bitmask set to 1
For this table:
(edit: the odd values in the table are highlighted green. In column8 the value 27 should also be highlighted green)
Using the spreadsheet axes the 8 columns are C:J (8 columns) and ...
1
vote
0
answers
97
views
How can I check whether a 10k digit integer is a probable prime?
I would like to detect prime numbers within an interval $\mathcal{I}:[a,b]$. The only problem is that the interval contains very large numbers - in excess of 10000 digits each and $\# \mathcal{I}$ is ...
4
votes
1
answer
80
views
Efficient primorial memoization?
Thinking on this recent question asking to create an primorial list, led me to think
How could we exploit something similar to memoization for primorial?
Maybe something that stored only the largest ...
7
votes
3
answers
371
views
What is a good way to compute successive primorials with Mathematica?
Recall that the primorial of a positive integer $n$ is the product of the prime numbers smaller than $n$. One can define a primorial function in Mathematica quite easily:
...
2
votes
1
answer
141
views
Use of PrimeQ in Solve
I fail to use PrimeQ in Solve. Simple example:
...
5
votes
1
answer
357
views
Writing a number 'm' as a sum of 'n' prime numbers
We can write {2 = 2}, {3 = 2+1, 3 = 3}, {4 = 2+2, 4 = 3+1}, {5 = 3+2, 5 = 2+2+1}, {6 = 3+3, 6 = 5+1, 6 = 3+2+1} and so on. I am trying to write every positive integer as a sum of Prime numbers.
In ...
2
votes
1
answer
173
views
Make a plot of the nth prime divided by n*log(n) ,for n from 2to1000 [closed]
ListPlot[Table[RandomReal[n, Prime[1000]]/n*log (n), {n, 2, 1000}]]
this is all i can do.
5
votes
2
answers
637
views
Can I use NextPrime[n] up to n=10^14?
I would like to perform computations with primes up to $n=10^{14}$. To do so, I would like to go through all primes, from $2$ to $10^{14}$ and perform some calculation on each prime.
I saw that one ...
1
vote
2
answers
147
views
Number of primes p less than or equal to X satisfying a congruence relation
I'm looking for a code that finds the number of primes p less than or equal to X satisfying p is congruent to 1 (mod 4) and another code that finds the number of primes p less than or equal to X ...
2
votes
1
answer
160
views
Code request for a loop searching for primes with certain condition
I am stuck in trying to understand how to write a code (perhaps a for-cycle, or a do-while?) that returns the values of $n$ for which $$2^n + 1$$ is a prime, but searching only amongst the values of $...
0
votes
0
answers
120
views
efficient code to search for formulas for calculating primes
I had an idea for calculating primes using smaller primes given the following:
p1=(p2-p3/p4)+(p5-p6/p7)
where p1>p5>p2 and p2>p3>p4 and p5>p6>p7 and p1 through p7 are all prime ...
4
votes
2
answers
229
views
Strange behavior of 'SquareFreeQ'
What is the cause of this strange behavior of SquareFreeQ while PrimePowerQ works correctly:
...
5
votes
8
answers
1k
views
Making the number 12345...n
Well, I am trying to write a code that makes the number:
$$123456\dots n\tag1$$
So, when $n=10$ we get:
$$12345678910$$
And when $n=15$ we get:
$$123456789101112131415$$
And when $n=4$ we get:
$$1234$$...
0
votes
1
answer
148
views
How to use every number between 2^50 and 2^100 without having to rewrite the code? [closed]
What I have currently written returns a numerical value and stores it in b100. p and q are random integers of size 2^50. I want to use the same code to calculate values where p and q ranges from 2^50 -...
0
votes
0
answers
131
views
Inverse/Division in finite field?
Think of multiplictavie group of finite field F[p,n], where p is a prime number and n is a positive integer.
The whole elements of F[p,n] can be represented as
p^n-p^(n-1) positive integers in the ...
4
votes
1
answer
347
views
Largest k such that p^k divides n
(Here all variables are integer.)
Is there a built-in function f[n,p] such that
f[n,p] = largest k such that p^k divides n
For ...
3
votes
0
answers
151
views
Approximate integer factorization
Suppose we would like to compute an approximate prime factorization of a large integer x in the sense that the difference between ...
4
votes
1
answer
610
views
How to make a graphic for Sieve of Eratosthenes with a legend
Definition
The Sieve of Eratosthenes is a simple algorithm to find the primes before a given $n$.
Starting from $n=2$ you delete all multiples of 2, and keep incrementing till all that are left are ...
2
votes
0
answers
92
views
Faster Prime[n] for large n, and for n larger than 10^12
Is there a faster implementation of Prime[] available somewhere, already implemented by someone? (Maybe as a compiled routine?)
The default function in Mathematica is slow for large values, and does ...
2
votes
1
answer
713
views
How to return two values from function
I have a function that generates cipher text for ElGamal encryption and I want to make return two values, but it returns only one. This is the code:
...
0
votes
1
answer
161
views
How to prime factorise rational numbers [closed]
I'm aware of the built-in FactorInteger command for finding the prime factorisation of integers. Is there a convenient way of determining the same thing for a rational number, where the prime ...
0
votes
1
answer
133
views
Factorizing large numbers [closed]
I am trying to factorize large prime numbers with the code bellow. The code works properly for values like 1927 and 69527 (results), but gives no result for larger values like 655051. The code goes as ...
5
votes
1
answer
118
views
PrimeQ versus Baillie-PSW primality test [closed]
I read here that Baillie-PSW primality test is proven correct up to $2^{64}$, but I understand PrimeQ is only proven correct up to $10^{16}$, or was that extended ...
1
vote
1
answer
93
views
Chinese remainder theorem large modulo [closed]
I have the following modulo congruences:
x ≡ 0 (mod 2)
x ≡ 2 (mod 5)
x ≡ 21 (mod 41)
x ≡ 16793129237622992703097532489897447320171386 (mod 648250901^5)
I know, ...
0
votes
0
answers
85
views
PowerMod solve for b (exponent)
Using PowerMod[a, b, m] = x I get
...
0
votes
1
answer
100
views
One 1 minute (mathematica)
I wanna evaluate how large prime numbers my computer work at most 60 seconds. Of course, I can evalutate this manaully e.g. by trying different values.
However, can I do this differently, e.g. by ...
5
votes
3
answers
301
views
Speeding up FactorInteger for product of two primes
I have a large integer $N$ of size about 10^150. I know that $N$ is a product of two primes $p$ and $q$. I also know that both $p$ and $q$ are of roughly equal size, so one of them is not, for example,...
1
vote
2
answers
276
views
Plotting Riemann Prime Counting
I want to program the formula in this page. Didn't take me long to get to my code below. But 1) it only plots the prime counting function and 2) evaluation takes incredibly long. How can I fix it?
<...
1
vote
0
answers
72
views
Geting all prime numbers from the fibonacci sequence in a range of <1000 [closed]
So my attempt was:
PrimePi[Fibonacci[Range[1, 999]]]
But that doesnt compile into anything. no result no error.
i hope one of you got an idea.
0
votes
0
answers
172
views
Goldbach's Conjecture?
If we have a list of even integers, how can we find partitions of size 2, then determine if the partitions are composed of prime numbers? So far, I think I would have to use ...
1
vote
1
answer
159
views
Find the first 20 primes found by the classical proof of the infinitude of the set of primes
Begin with P={2}; then form,m, the sum of 1 with the product overall elements of P. Place the smallest prime factor of m into P and repeat.
Suppose p = {p1,p2,...,pr}, then m = 1+ p1p2p3...pr.
Example:...
2
votes
2
answers
353
views
A Wilson prime is a prime p such that (p−1)!≡−1 mod p^2. Write a procedure which determines all Wilson primes less than10^4
I try to use the for loop to solve this question, but it does not work. And here is what I did.
For[p = 2,p<=10000,(p-1)! = -1 mod (p^2),Print[p]]
I am not sure ...
2
votes
1
answer
88
views
How to write this simple task of unimodular prime search in mathematica?
For testing a particular algorithm I found mathematica is the best way as it has all the tools I need. I am stuck in a number theory part and since I am not an expert in mathematica I do not know how ...
5
votes
4
answers
129
views
Incrementing Numbers
I want to take a prime number p0 = 3, add 2 to it to get a new number p1 = 5, then add four to p1 to get p2, then add 6 to p2 to get p3, etc for a total of 50 times. How do I do that and place my ...
1
vote
0
answers
63
views
finding primes using chebyshev bias
Using the problem from my previous question link. For each n, that is n= $10^3$ to $10^6$ with a ten-fold increase, how do I use Chebyshev Bias to display the number of primes (which are in the ...
1
vote
1
answer
94
views
How do I find how many numbers are prime(taking absolute value of negatives) in a list? When i use count it returns zero
f = 9x^2 - 78x-10000
list1 = PrimeQ[Abs[f /. x -> {Range[1, 20]}]]
Count[list1,True]
This is my code. Im trying to find how many prime numbers ...
2
votes
1
answer
235
views
Trying to create a list that counts the number primes for each remainder class
Considier the remainder of the first $2500$ prime numbers by the numbers from $3$ to $30$, included.
Calculate how many primes are in each remainder class. That is, create a list that for each number ...
1
vote
1
answer
79
views
A modular version of LinearRecurrence?
I'm playing around with implementing the Lucas probable prime test (mainly so I can understand it better), and would love a version of the LinearRecurrence function that used addition modulo n (with n ...
4
votes
0
answers
216
views
Prime factorization over the Eisenstein integers $\mathbb{Z}[\zeta]$
I am trying to write a function f[a_,b_] which takes in two integers $a,b$ and returns the unique factorization of $a+be^{2\pi i/3}$ into the primes belonging to $\...
3
votes
1
answer
204
views
Riemann Prime Counting Function correction/pairing terms by Mathematica
Riemann Prime Counting Function:
$$f(x)=\operatorname{li}(x)-\sum_\rho\operatorname{li}(x^\rho)-\ln 2+\int_x^\infty \frac{\mathrm dt}{t(t^2-1)\ln t}$$
The second correction/paring terms:
$$\sum_\rho\...
3
votes
0
answers
122
views
Prime Matrix with determinant of powers $2^x$
Mathematica has commands for finding prime matrices, for example, here is a matrix with randoms in the range $<100$:
RandomPrime[100, {3, 3}]
This $2 \times 2$ ...
9
votes
2
answers
516
views
Evenly spaced Tick marks for Primes
I'm trying to have the integers evenly spaced on the x axis of a ListPlot, and the prime numbers evenly spaced on the y axis.
...