Questions tagged [number-theory]

Number theory involves properties and relationships of numbers, primarily positive integers.

Filter by
Sorted by
Tagged with
15
votes
16answers
2k views

Exponentiation Sequence

The oldest Polish salt mine, located in Bochnia*, was started in year 1248, which we can consider a magical number. We can see that it's equal to 4 digits from the sequence of exponentiations: . As ...
14
votes
22answers
1k views

The Uncommon Factor Number

Based on a chat message The Challenge Given an input number \$n > 9\$, construct its reverse, ignoring leading zeros. Then, construct a list of all prime factors that the number and its reverse don'...
14
votes
14answers
2k views

Compute the Wilson numbers

Given a positive integer n, compute the nth Wilson number W(n) where and e = 1 if n has a primitive root modulo n, otherwise e = -1. In other words, n has a primitive root if there does not exist an ...
2
votes
1answer
212 views

Collatz's First Conjecture [duplicate]

Background The Collatz Conjecture is quite well-known. Take any natural number. Triple and increment if odd; cut in half if even. Repeat, and it will reach 1 eventually. This famous conjecture, ...
3
votes
6answers
617 views

Perfect, Germain, Vampire, Mersenne! (Don't forget narcissistic) [duplicate]

Six is a number perfect in itself, and not because God created all things in six days; rather, the converse is true. God created all things in six days because the number six is perfect. I am ...
16
votes
16answers
2k views

How many partitions do I have?

The partition number of a positive integer is defined as the number of ways it can be expressed as a sum of positive integers. In other words, the number of integer partitions it has. For example, the ...
8
votes
16answers
1k views

First spiral, then diagonal

Given a positive input number \$n\$, construct a spiral of numbers from \$1\$ to \$n^2\$, with \$1\$ in the top-left, spiraling inward clockwise. Take the sum of the diagonals (if \$n\$ is odd, the ...
23
votes
23answers
3k views

Modular multiplicative inverse

Your task is to given two integer numbers, a and b calculate the modular multiplicative inverse of a modulo b, if it exists. ...
27
votes
8answers
2k views

Smallest unseen, but no sharing digits!

Challenge Here at PPCG, we sure do like our sequences, so here's a fun another one. Let's define a(n) as being the smallest non-negative integer ...
21
votes
19answers
2k views

Pascal's Alternating Triangle

Pascal's triangle is generated by starting with 1 and having each row formed from successive additions. Here, instead, we're going to form a triangle by alternating ...
27
votes
23answers
2k views

Find prime gaps

A prime gap is the difference between two consecutive primes. More specifically, if p and q are primes with p <q and p+1, p+2, ..., _q_−1 are not primes, the primes p and q define a gap of n = q_−...
13
votes
4answers
379 views

How Fermat is this number?

Fermat numbers are positive integers that can be expressed as 22x+1 with an integer x. Let us now define an attribute of a number called "Fermat-ness": The Fermat-ness of the number is one less than ...
25
votes
36answers
2k views

How does the square end?

In base-10, all perfect squares end in \$0\$, \$1\$, \$4\$, \$5\$, \$6\$, or \$9\$. In base-16, all perfect squares end in \$0\$, \$1\$, \$4\$, or \$9\$. Nilknarf describes why this is and how to work ...
29
votes
16answers
3k views

Primitive Pythagorean Triples

(related) A Pythagorean Triple is a list (a, b, c) that satisfies the equation a2 + b2 = c2. A Primitive Pythagorean Triple (PPT) is one where ...
23
votes
6answers
554 views

Factorize a Gaussian integer

A Gaussian integer is a complex number whose real and imaginary parts are integers. Gaussian integers, like ordinary integers, can be represented as a product of Gaussian primes, in a unique manner. ...
19
votes
44answers
2k views

Subtract my odds from my evens

Given a non-negative integer, return the absolute difference between the sum of its even digits and the sum of its odd digits. Default Rules Standard Loopholes apply. You can take input and provide ...
28
votes
21answers
3k views

Is it a Chen prime?

A number is a Chen prime if it satisfies two conditions: It is prime itself Itself plus two is either a prime or a semi-prime. A prime is a number where it has exactly two divisors and those ...
20
votes
26answers
2k views

Find the nearest biquadratic number

A biquadratic number is a number that is the fourth power of another integer, for example: 3^4 = 3*3*3*3 = 81 Given an integer as input, output the closest ...
14
votes
28answers
1k views

Am I a Sophie Germain prime? [duplicate]

A Sophie Germain Prime is a prime number P such that 2P+1 is prime as well. Given a prime number as input, your task is to determine whether it is a Sophie Germain Prime. Standard Input/Output rules ...
18
votes
6answers
1k views

Fastest tweetable integer factorizer

The task is to find a non-trivial factor of a composite number. Write code that finds a non-trivial factor of a composite number as quickly as possible subject to your code being no more than 140 ...
26
votes
23answers
3k views

Is it a weak prime?

A prime is weak if the closest other prime is smaller than it. If there is a tie the prime is not weak. For example 73 is a weak prime because 71 is prime but 75 is composite. Task Write some ...
24
votes
42answers
2k views

Product of Divisors

Challenge Given a positive integer, return the product of its divisors, including itself. This is sequence A007955 in the OEIS. Test Cases 1: 1 2: 2 3: 3 4: 8 5: 5 6: 36 7: 7 8: 64 9: 27 10: 100 ...
26
votes
26answers
3k views

Is it a super-prime?

Background A super-prime is a prime number whose index in the list of all primes is also prime. The sequence looks like this: 3, 5, 11, 17, 31, 41, 59, 67, 83, 109, 127, 157, 179, 191, ... This ...
7
votes
11answers
445 views

Find the numbers coprime to their decimal digits

Two numbers are coprime if their greatest common divisor is 1. Given a positive integer N, your task is to compute the first N terms of OEIS A061116, which is the sequence of positive integers higher ...
9
votes
5answers
608 views

Increasing Goldbach partitions

The Goldbach conjecture states that: every even number that is greater than 2 is the sum of two primes. We will consider a Goldbach partition of a number n to be a pair of two primes adding to n. ...
40
votes
73answers
5k views

Am I divisible by double the sum of my digits?

Given a positive integer as input, your task is to output a truthy value if the number is divisible by the double of the sum of its digits, and a falsy value otherwise (OEIS A134516). In other words: <...
10
votes
2answers
537 views

Find a number which generates all the integers mod q

Consider the integers modulo q where q is prime, a generator is any integer 1 < x < q ...
21
votes
23answers
2k views

Is my number a de Polignac number?

A number is a de Polignac number if and only if it is odd and cannot be represented in the form p + 2n where n is a non-negative integer and p is a prime integer. Task Write some code that takes a ...
21
votes
38answers
1k views

Proper Divisor mash-up

A proper divisor is a divisor of a number n, which is not n itself. For example, the proper divisors of 12 are 1, 2, 3, 4 and 6. You will be given an integer x, x ≥ 2, x ≤ 1000. Your task is to sum ...
24
votes
13answers
2k views

Divinacci Sequence

Divinacci (OEIS) Perform the Fibonacci sequence but instead of using: f(n) = f(n-1)+f(n-2) Use: ...
12
votes
14answers
1k views

How many ways to write numbers as sums of squares?

Task Given two integers \$d\$ and \$n\$, find the number of ways to express \$n\$ as a sum of \$d\$ squares. That is, \$n = r_1^2 + r_2^2 + ... + r_d^2\$, such that \$r_m\$ is an integer for all ...
-5
votes
13answers
260 views

Am a I square repdigit? [closed]

Your Task You will write a program or function to return a truthy value if the integer inputted to it is a square repdigit, and a falsy value if it is not. A repdigit is an integer that contains ...
8
votes
3answers
576 views

Prime of my Life

This year my age is a prime number, and so is this year. This conjunction will repeat in 10 years and again in 12. If I live to 100, I will lived exactly 11 years in which my age and the year are both ...
16
votes
3answers
1k views

Miller-Rabin Strong Pseudoprimes

Given a non-negative integer N, output the smallest odd positive integer that is a strong pseudoprime to all of the first N ...
13
votes
4answers
457 views

Fastest Approximate Common Divisor

Overview In this challenge, you will be given two numbers which are both a small offset larger than a multiple of a medium-size number. You must output a medium-sized number that is almost a divisor ...
16
votes
14answers
1k views

Trithagorean Triples

A Pythagorean Triple is a positive integer solution to the equation: A Trithagorean triple is a positive integer solution to the equation: Where Δn finds the nth triangular number. All Trithagorean ...
15
votes
20answers
1k views

Sum my Fibonaccified divisors!

The famous Fibonacci sequence is F(0) = 0; F(1) = 1; F(N+1) = F(N) + F(N-1) (for this challenge we are beginning with 0). Your challenge: Given n, output the sum ...
19
votes
28answers
1k views

Calculate the inverse modulus

The task: Output a value for x, where a mod x = b for two given values a,b. Assumption <...
18
votes
7answers
705 views

Gilbreath's Conjecture

Suppose we start with the infinite list of prime numbers: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, ... Then, we take the ...
15
votes
15answers
800 views

Maximal mutually co-prime factorization

Definitions Two numbers are co-prime if their only positive common divisor is 1. A list of numbers is mutually co-prime if every pair of numbers within that list ...
36
votes
23answers
3k views

Abandon all squares, ye who divide me

Definitions A perfect square is an integer which can be expressed as the square of another integer. For example, 36 is a perfect square because ...
48
votes
32answers
2k views

Divisor skyline

For any positive integer \$k\$, let \$d(k)\$ denote the number of divisors of \$k\$. For example, \$d(6)\$ is \$4\$, because \$6\$ has \$4\$ divisors (namely \$1, 2, 3, 6\$). Given a positive integer \...
43
votes
42answers
4k views

Replace twos with threes

Given a positive integer n write some code to take its prime factorization and replace all of its factors of 2 with 3. For ...
15
votes
10answers
559 views

Reachable numbers

Definitions Euler Phi Function (AKA totient function): a function which takes in a positive number and returns the number of positive numbers less than the given number which are co-prime with given ...
23
votes
12answers
1k views

Reverse and add degeneracy

Intro Reverse and add is as simple as it sounds, take n and add it to its digits in reverse order. (e.g. 234 + 432 = 666). If you apply this process repeatedly ...
24
votes
5answers
1k views

Fermat's factorization helper

We'd like to factorize a semiprime \$N\$. The goal of this challenge is to find two small integers \$u\$ and \$v\$ such that \$uvN\$ can be trivially factorized with Fermat's method, thus allowing to ...
13
votes
1answer
317 views

Help Gödel with his β function [closed]

Gödel's β function takes three natural numbers as arguments. It is defined as β(x,y,z) = rem(x, 1 + (z + 1) · y) = rem(x, (z · y + y + 1) ) where rem(a, b) ...
15
votes
16answers
4k views

Never odd or even

Did you notice, that this is a palindrome? Input Non-negative integer number or string representing it Output 4 possible outputs, representing two properties of number: is it palindrome tricky #2 ...
25
votes
14answers
3k views

Reuse your code!

In this challenge we try to solve two important problems at once. They are: Given integers \$a\$ and \$b\$, tell if \$a^b-1\$ is a prime number. Given integers \$a\$ and \$b\$, return \$a\choose b\$. ...
27
votes
14answers
1k views

Palindromic Residue

Today, as I'm writing this, is March 31st. In the US, this is 3/31. I was playing around with 331 as a number to come up with a ...

1 2 3
4
5
9