# Questions tagged [primes]

For challenges about identifying and manipulating prime numbers

346 questions
Filter by
Sorted by
Tagged with
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 ...
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
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
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
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
405 views

• 3,423
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
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
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
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
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
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
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
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 ...
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 ...
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
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 ...
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
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
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
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
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
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
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
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
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
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
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
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
585 views

• 193
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
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
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 ...
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
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$. ...
829 views

• 18.9k
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
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
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
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
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
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$ ...