Questions tagged [primes]
For challenges about identifying and manipulating prime numbers
346
questions
14
votes
10
answers
1k
views
Sylvester primes
Sylvester's sequence can be defined recursively S(n) = S(n-1)*(S(n-1) + 1) for n >= 1 starting S(0) = 1.
Since S(n) and S(n) + 1 have no common divisors, it follows that S(n) has at least one more ...
- 241
13
votes
8
answers
884
views
Lexicographically earliest permutation of the initial segment of nonnegative integers subject to divisibility constraints
The challenge is simple: Reorder the first integers {0, 1, 2, ..., n} into an ordered list so that the following three conditions are met:
If k is the last element in the list, then all of its prime ...
- 251
13
votes
12
answers
2k
views
Odds for second smallest prime factor
Given a prime number \$p\$ output the asymptotic density of the set of positive integers which have \$p\$ as their second-smallest distinct prime factor
Input/Output
Input: one of the following ...
- 12.7k
10
votes
6
answers
954
views
Unnecessary Fluff
Following the great advice (what do you mean it's not advice?!) on Adding unnecessary fluff we can devise the following task:
Take a list of positive integers and a positive integer \$m\$ as input.
...
- 10.6k
8
votes
20
answers
1k
views
Piecing Paired Primes
Problem
You've stumbled upon a paradoxical mathematical phenomenon related to prime numbers. Consider the following scenario:
You have an infinite list of prime numbers: $$2, 3, 5, 7, 11, 13, 17, 19, ....
- 383
8
votes
8
answers
405
views
Near miss prime multiples
This challenge was originally posted on codidact.
Given a number \$n \geq 3\$ as input output the smallest number \$k\$ such that the modular residues of \$k\$ by the first \$n\$ primes is exactly \$\...
- 99.5k
11
votes
12
answers
1k
views
The all-high powerful numbers
We've had powerful numbers, yes, but what about highly powerful numbers?
Highly powerful numbers
Let \$n\$ be a positive integer in the form
$$n = p_1^{e_{p_1}(n)}p_2^{e_{p_2}(n)}\cdots p_k^{e_{p_k}(n)...
- 50.1k
6
votes
19
answers
2k
views
Number of bits needed to represent the product of the first primes
Input
An integer \$n\$ greater than or equal to 1.
Output
The number of bits in the binary representation of the integer that is the product of the first \$n\$ primes.
Example
The product of the first ...
- 3,143
23
votes
31
answers
3k
views
Is this a powerful number?
A powerful number is a positive integer \$n\$ such that for every prime \$p\$ that divides \$n\$, \$p^2\$ also divides \$n\$. Or equivalently, \$n\$ is powerful if and only if it can be written in the ...
- 49.3k
-3
votes
7
answers
1k
views
Straight pen strokes for Prime Numbers
Challenge
You are supposed to output the series I recently designed which goes as follows which are pen stroke counts of ascending prime numbers:
...
- 1,802
14
votes
7
answers
1k
views
Gödel encoding - Part II (decoding)
Part I
Previous part was considered encoding of non-empty nested lists with a positive integer.
Reminding the coding procedure \$G(x)\$:
If \$x\$ is a number, \$G(x) = 2^x\$
If \$x\$ is a list \$[n_0,...
- 3,423
31
votes
18
answers
3k
views
Gödel encoding - Part I
Related but different.
Part II
Taken from the book: Marvin Minsky 1967 – Computation:
Finite and Infinite Machines, chapter 14.
Background
As the Gödel proved, it is possible to encode with a unique ...
- 3,423
16
votes
7
answers
2k
views
How Super is this Prime?
A super prime is a prime whose index in the list of primes is also a prime:
...
- 1,155
15
votes
19
answers
2k
views
Sophie Safe primes
Description
Write a program or function that takes in a positive integer \$n\$ as input and outputs all Sophie Germain primes that are safe primes less than or equal to \$n\$. A prime number \$p\$ is ...
- 1,802
15
votes
16
answers
2k
views
Imtiaz Germain Primes
Description
"Imtiaz Germain primes" is not a technical name in Mathematics, but my weird creation, in the memoir of the famous mathematician Sophie Germain. These primes can be generated by ...
- 1,802
12
votes
18
answers
645
views
Primes with Distinct Prime Digits
There are 18 primes with distinct prime digits (A124674). Namely, they are:
\$2, 3, 5, 7, 23, 37, 53, 73, 257, 523, 2357, 2753, 3257, 3527, 5237, 5273, 7253, 7523\$
Your task is to output this ...
- 309
5
votes
15
answers
815
views
Shortest code to generate a list of prime numbers within a given range
Strangely never asked before, this question pertains to the generation of a list of prime numbers within a given range using the shortest possible code. Several algorithms, such as the Sieve of ...
- 1,802
15
votes
18
answers
2k
views
Distance to the average of the next two prime numbers
Suppose we have a sequence \$P\$. Every element \$P_n\$ represents the distance between the \$n^{th}\$ prime number and the average of the next two prime numbers.
For example, \$P_1\$ would be the ...
- 487
14
votes
14
answers
1k
views
n-digit primes given the first m digits
I just discovered this site and this is my first question, I hope I'm doing it correctly.
The challenge is the following, you must write a code that prints all the prime numbers of \$n\$ digits. Since ...
- 241
13
votes
25
answers
1k
views
Find the Prime Signature
The Prime Signature of a number is the list of the exponents of the prime factors of a number, sorted in descending order (exponents of 0 are ignored). Inspired by ...
- 505
38
votes
15
answers
3k
views
Base Neutral Numbering System
It frustrates me that when you say "base 16", the 16 is in base 10. We need a base neutral way of writing down numbers when favoring a specific base would be inappropriate.
How it works
We ...
- 13k
19
votes
13
answers
890
views
As many near-repdigit primes as possible
A near-repdigit number is a positive integer where all the digits are the same, except one. For example 101 and 227 are near-repdigits. A near-repdigit prime is a near-repdigit that is also prime. For ...
user108721
16
votes
15
answers
2k
views
Generate the n'th Fermi-Dirac Prime
A Fermi-Dirac Prime is a prime power of the form \$p^{2^k}\$, where \$p\$ is prime and \$k \geq 0\$, or in other words, a prime to the power of an integer power of two. They are listed as integer ...
- 1,646
13
votes
22
answers
1k
views
Even and Odd kinds
Let \$n\$ be some positive integer. We say that \$n\$ is of even kind if the prime factorisation of \$n\$ (counting duplicates) has an even number of integers. For example, \$6 = 2 \times 3\$ is of ...
- 50.1k
12
votes
20
answers
2k
views
Prime number checksum
Given a message, append checksum digits using prime numbers as weights.
A checksum digit is used as an error-detection method.
Take, for instance, the error-detection method of the EAN-13 code:
The ...
- 9,428
12
votes
18
answers
1k
views
Find the nth Mersenne Prime
A number is a Mersenne Prime if it is both prime and can be written in the form 2m-1, where m is a positive integer.
For example:
7 is a Mersenne Prime because it is 23-1
11 is not a Mersenne Prime ...
- 18.2k
6
votes
3
answers
585
views
Generate Fibonacci Primes Quickly
Unsurprisingly, fibonacci primes are primes that are also Fibonacci numbers. There are currently 34 known Fibonacci primes and an additional 15 probable Fibonacci primes. For the purpose of this ...
- 2,485
22
votes
12
answers
3k
views
How many Sieve of Eratosthenes hits?
Sieve of Eratosthenes is a method for finding prime numbers:
take the sequence of all positive integer numbers starting from 2 then for each remaining number drop all its multiples.
...
- 10.9k
18
votes
16
answers
1k
views
Long period primes
A long period prime is a prime number \$p\$ such that decimal expansion of \$1/p\$ has period of length \$(p-1)\$. Your task is to output this number sequence. For purposes of this challenge we will ...
- 17.8k
8
votes
7
answers
705
views
Factorials of primes decomposition
You have to decompose a positive integer/fraction as a product of powers of factorials of prime numbers.
For example
...
- 5,097
16
votes
2
answers
894
views
Golf the prime numbers in Shue
I'd like to introduce a new? programming language I call Shue (Simplified Thue). It has very simple syntax.
Here is a program that checks if an input is divisible by three:
...
- 7,918
17
votes
27
answers
2k
views
Prime a*b+c of N
Given an integer \$N\$, print or return integers \$a\$, \$b\$, and \$c\$ that satisfy all of the following conditions, if such integers exist:
\$a \times b + c = N\$
\$a\$, \$b\$, and \$c\$ are all ...
- 757
12
votes
6
answers
1k
views
High throughput prime numbers
This challenge is inspired by the High throughput Fizz Buzz challenge.
The goal
Generate a list of prime numbers up to 10,000,000,000,000,000. The output of primes should be in decimal digits followed ...
- 2,375
6
votes
2
answers
869
views
Write the most optimized assembly program to detect a prime number (from a bigger range!)
This is the second version of the task. The original task had a defect that the given range of integers was too small. This was pointed out by @harold that other methods couldn't defeat the way of ...
- 2,375
10
votes
10
answers
585
views
Primes dividing consecutive composites
Grimm's conjecture states that, for any set of consecutive composite numbers \$n+1, n+2, ..., n+k\$, there exist \$k\$ distinct primes \$p_i\$, such that \$p_i\$ divides \$n+i\$ for each \$1 \le i \le ...
- 50.1k
14
votes
4
answers
619
views
The Most Wanted Prime Numbers
Output a sequence of all the primes that are of the following form:
123...91011...(n-1)n(n-1)..11109...321. That is, ascending decimal numbers up to some ...
- 7,918
16
votes
15
answers
2k
views
Print Gobar Primes
Gobar primes (A347476) are numbers which give a prime number when 0's and 1's are interchanged in their binary representation.
For example, \$10 = 1010_2\$, and if we flip the bits, we get \$0101_2 = ...
- 193
30
votes
14
answers
2k
views
Is it a Giuga number?
Giuga numbers (A007850) are composite numbers \$n\$ such that, for each prime factor \$p_i\$ of \$n\$, \$p_i \mid \left( \frac n {p_i} -1 \right)\$. That is, that for each prime factor \$p_i\$, you ...
- 50.1k
26
votes
7
answers
2k
views
Recognize most smaller primes with a regex
This time, you are working on a regex. Your regex is meant to approximately full-match the base-10 representations of primes \$0 \le p < 1000\$, while ignoring any non-numeric string or composite ...
- 3,849
1
vote
1
answer
226
views
No of subsets of a given array such that their product is in the form of p1*p2*p3 [closed]
Given an array \$A\$ of size \$n\$.
You have to find the number of subsets such that their product is in the form of \$p_1 \times p_2 \times p_3 \dots\$
where \$p_1, p_2, p_3, \dots\$ are prime ...
- 27
23
votes
17
answers
2k
views
Reconstruct a recursively prime-encoded integer
Recursively prime-encoded integers
Consider \$11681169775023850 = 2 \times 5 \times 5 \times 42239 \times 5530987843\$. This isn't a nice prime factorisation, as \$42239\$ and \$5530987843\$ make it ...
- 50.1k
16
votes
15
answers
898
views
Outputting Blum Integers
According to Wikipedia,
In mathematics, a natural number \$n\$ is a Blum integer if \$n = p \times q\$ is a semiprime for which \$p\$ and \$q\$ are distinct prime numbers congruent to \$3 \bmod 4\$. ...
user100752
12
votes
7
answers
829
views
Prime Factorization - but on the exponents too
Though there is a prime factorization challenge and it's here, this, I feel, will be a bit more interesting than that one.
To understand this, let's have an example; I will use 5,184 for this. \$5184 =...
- 1,141
0
votes
4
answers
214
views
Prime Factorization [duplicate]
Although there was a prime factors challenge posted ten years ago, it has tedious I/O and restricted time. In this challenge, your task is to write a program or function which takes an integer \$n \ge ...
- 18.9k
22
votes
21
answers
3k
views
Gödel numbering of a string
Background
Gödel numbers are a way of encoding any string with a unique positive integer, using prime factorisations:
First, each symbol in the alphabet is assigned a predetermined integer code.
Then, ...
- 24.2k
22
votes
22
answers
1k
views
Make it prime with the smallest suffix
Given a positive integer as input, output the smallest positive integer such that appending its digits (in base 10) to the end of the input number will form a prime number.
Examples
...
- 9,971
26
votes
25
answers
1k
views
Calculate Home Primes
The Home Prime of an integer \$n\$ is the value obtained by repeatedly factoring and concatenating \$n\$'s prime factors (in ascending order, including repeats) until reaching a fixed point (a prime). ...
- 50.1k
7
votes
10
answers
966
views
Random pair of primes
Given a positive input \$n\$, output a random pair of primes whose difference is \$n\$. It's fine if there's another prime between them.
Every pair should possibly appear and the program should have ...
- 26k
8
votes
6
answers
690
views
Finding Distant Primes
Let us call a prime \$p\$ an \$(m,k)\$-distant prime \$(m \ge 0, k \ge 1, m,k \in\mathbb{Z})\$ if there exists a power of \$k\$, say \$k^x (x \ge 0, x \in\mathbb{Z})\$, such that \$|k^x-p| = m. \$ For ...
- 5,290
13
votes
4
answers
1k
views
I ain't no Fortunate sum
The primorial \$p_n\#\$ is the product of the first \$n\$ primes. The sequence begins \$2, 6, 30, 210, 2310\$.
A Fortunate number, \$F_n\$, is the smallest integer \$m > 1\$ such that \$p_n\# + m\$ ...
- 50.1k