Questions tagged [primes]

For challenges about identifying and manipulating prime numbers

Filter by
Sorted by
Tagged with
20
votes
11answers
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 ...
20
votes
6answers
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 ...
1
vote
1answer
164 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 ...
17
votes
16answers
1k 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 ...
15
votes
13answers
730 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\$. ...
10
votes
7answers
731 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 =...
0
votes
4answers
105 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
votes
20answers
2k 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, ...
20
votes
20answers
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 ...
23
votes
19answers
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). ...
6
votes
10answers
885 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 ...
7
votes
6answers
672 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 ...
12
votes
4answers
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\$ ...
23
votes
27answers
2k views

Reconstruct an integer from its prime exponents

All integers \$n > 0\$ can be expressed in the form $$n = \prod_{\text{prime } p} p^e = 2^{e_2} 3^{e_3} 5^{e_5} 7^{e_7} \cdots$$ This form is also known as it's prime factorisation or prime ...
-3
votes
1answer
150 views

Python Prime Problem [duplicate]

Your challenge is to write a Python program to print all the primes (separated by whitespace) less than a given integer N with an asterisk (...
46
votes
24answers
4k views

Ginormous number

Output this 1364-digit base-10 number: ...
6
votes
15answers
841 views

Prime generating function

Background The Python code ((((((((n%35)^11)*195)|53)&181)+n)%168)*n)+83 produces 74 distinct primes for \$0 \le n \le 73\$. This code also works in Java. The ...
17
votes
13answers
1k views

All-inclusive semi-primes

\$723 = 3 \times 241\$ is a semi-prime (the product of two primes) whose prime factors include all digits from \$1\$ to \$n\$, where \$n\$ is the total number of digits between them. Another way to ...
31
votes
20answers
3k views

Looks prime to me!

Figuring out whether a given number is prime, while not very complicated, is kind of hard. But making a guess doesn't need to be. Seeing whether a number is a multiple of 2 or 5 is easy - you can just ...
30
votes
7answers
3k views

Shortest “arithmetic” formula to output 1000 primes

Write a formula using only the digits 0-9, +, *, -, <...
22
votes
16answers
2k views

Delicate primes

Inspired by Find the largest fragile prime. By removing at least 1 digit from a positive integer, we can get a different non-negative integer. Note that this is different to the ...
15
votes
21answers
1k views

Double Prime Words

Consider a word/string of length \$n\$, only including the letters A-Z, a-z. A word/string is a double prime word if and only if n is prime and the sum of the letters, s, is also prime, using their ...
20
votes
26answers
2k views

Prime Power Switch

Input: A positive integer n=p^q where p and q are prime. Output: Output the result of ...
-3
votes
5answers
183 views

Prime decimal representations of prime binary numbers [duplicate]

Problem Statement: Consider a number n in base-10. Find the smallest base-10 integer i greater than ...
30
votes
31answers
5k views

Is it almost-prime?

Sandbox Definition: A positive integer n is almost-prime, if it can be written in the form n=p^k where ...
5
votes
16answers
743 views

Prime Challenge

CODE GOLF & Coding Challenges: In today's challenge, you'll be asked to print the following very special AND tricky AND satisfying Prime Number...! Are you golfers ready? ...
19
votes
9answers
639 views

Prime Modified Z-Factorials

Let me explain one by one the above terms... We will call \$\text{Z-Factorial}(n)\$ of a positive integer \$n\$, \$n!\$ (i.e. \$n\$ factorial) without any trailing zeros. So, \$\text{Z-Factorial}(30)\$...
27
votes
19answers
3k views

Legendre's (Unsolved) Conjecture

Legendre's Conjecture is an unproven statement regarding the distribution of prime numbers; it asserts there is at least one prime number in the interval \$(n^2,(n+1)^2)\$ for all natural \$n\$. The ...
12
votes
10answers
888 views

Find all Belphegor primes

A Belphegor number is a number of the form \$(10^{n+3}+666)*10^{n+1}+1\$ (1{n zeroes}666{n zeroes}1) where \$n\$ is an non-negative integer. A Belphegor prime is a ...
15
votes
7answers
1k views

Generate *all* coprime tuples

Given integers k and n, generate a sequence of n unique k-tuples of pairwise coprime ...
6
votes
10answers
872 views

Draw the prime race tracks

Odd prime numbers are either in the form of 4k+1 or 4k+3 where k is a non-negative integer. ...
-8
votes
22answers
313 views

Produce all even primes

A prime number is a positive integer that has exactly two divisors 1 and the number itself. For example number 7 is a prime since it is divisible by 1 and 7. Number 1 is not a prime since it has only ...
3
votes
3answers
327 views

Generate A298757 [closed]

Miller-Rabin test Given a base \$b\$ and an odd number \$n\$: Write \$n\$ as \$2^{s}\times d + 1\$ where \$d\$ is odd \$n\$ is a strong probable prime if either: \$b^d\equiv 1 \pmod n\$ \$b^{d\cdot2^...
8
votes
2answers
407 views

Find the largest recurring prime

Inspired by Find the largest fragile prime A recurring prime (or whatever you choose to call it) is a prime that, when removing leading digits, always remain prime regardless of how many digits are ...
16
votes
1answer
628 views

Is this ordinal prime?

You are given an countable ordinal \$1 < r < \varepsilon_0\$. Determine whether or not it is prime. If not, provide exactly two ordinals \$r_0, r_1 < r\$ such that \$r_0r_1 = r\$, following ...
30
votes
5answers
2k views

Longest Prime Sums

Sandbox There are special sets S of primes such that \$\sum\limits_{p\in S}\frac1{p-1}=1\$. In this challenge, your goal is to find the largest possible set of primes that satisfies this condition. ...
14
votes
11answers
2k views

Letters associated with prime numbers

If we assign each letter a respective integer, starting from 1, then a is 1, b is 2, c is 3, and so on. After z, the letters loop back around, but with a in front (aa, ab, ac). It then goes to ba, bb, ...
5
votes
13answers
452 views

Please Read Primes

Do you know the book Murderous Maths, in the Horrible Science series? In the book, the Laplace Princess' "ridiculous" cipher might be interesting enough and simple enough to be a code-golf challenge. ...
24
votes
21answers
1k views

Some Prime Peerage

(Randomly inspired by https://mathoverflow.net/q/339890) (Related: 1, 2) Given an input list of distinct prime numbers (e.g., [2, 5, 7]), and a integer ...
28
votes
17answers
4k views

Infinitely many primes

Since Euclid, we have known that there are infinitely many primes. The argument is by contradiction: If there are only finitely many, let's say \$p_1,p_2,...,p_n\$, then surely \$m:=p_1\cdot p_2\cdot.....
-4
votes
3answers
127 views

Geiger counter prime generation [closed]

This challenge is quite simple to conceptualise, but likely a lot harder to execute. In this challenge, the program will have to detect the number N of its characters that have been randomly changed (...
45
votes
12answers
3k views

Prime parity peregrination

The purpose of this challenge is to graphically depict a walk on the plane, where the direction of each step \$k\$ is determined by the primality of \$k\$ and the parity of its binary expansion. ...
21
votes
16answers
3k views

​Cuban​ ​Primes

Given a natural number \$n\$, return the \$n\$-th cuban prime. Cuban Primes A cuban prime is a prime number of the form $$p = \frac{x^3-y^3}{x-y}$$ where \$y>0\$ and \$x = 1+y\$ or \$x = 2+y\$ ...
3
votes
11answers
427 views

Composite Factor Soup

Per the fundamental theorem of arithmetic, for a given number \$n\$, it is possible to find it's prime factors, and they are unique. Let's imagine we talk only of \$n\$ that is non-prime (composite). ...
17
votes
7answers
636 views

Make some Prime Squares!

What is a Prime Square? A Prime Square is a square where all four edges are different prime numbers. But which ones? And how do we construct them? Here is an example of a 4x4 Prime Square ...
27
votes
2answers
1k views

Can a neural network recognize primes?

Background Recognizing primality seems like a poor fit for (artificial) neural networks. However, the universal approximation theorem states that neural networks can approximate any continuous ...
33
votes
41answers
7k views

Return the Closest Prime Number

Challenge This is a simple one: Given a positive integer up to 1,000,000, return the closest prime number. If the number itself is prime, then you should return that number; if there are two primes ...
26
votes
6answers
1k views

Prime containment numbers (speed edition)

This is sequence A054261 The \$n\$th prime containment number is the lowest number which contains the first \$n\$ prime numbers as substrings. For example, the number \$235\$ is the lowest number ...
22
votes
14answers
2k views

Prime containment numbers (golf edition)

This is sequence A054261. The \$n\$th prime containment number is the lowest number which contains the first \$n\$ prime numbers as substrings. For example, the number \$235\$ is the lowest number ...
15
votes
11answers
914 views

Generate some rough numbers

Background A number n can be described as B-rough if all of the prime factors of n strictly ...

1
2 3 4 5
7