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

learn more… | top users | synonyms

20
votes
27answers
2k views

Calculate Euler's totient function

Background Euler's totient function φ(n) is defined as the number of whole numbers less than or equal to n that are relatively prime to n, that is, the number of possible values of x in 0 < x <=...
7
votes
2answers
446 views

All Armstrong numbers

An Armstrong number (AKA Plus Perfect number, or narcissistic number) is a number which is equal to its sum of n-th power of the digits, where n is the number of digits of the number. For example, ...
18
votes
9answers
826 views
+200

Fibonacci Factorization

Fibonacci Numbers Fibonacci Numbers start with f(1) = 1 and f(2) = 1 (some includes f(0) = 0 but this is irrelevant to this challenge. Then, for n > 2, f(n) = f(n-1) + f(n-2). The challenge Your ...
6
votes
14answers
936 views

Golf the repeated totient function

You will take two positive integers n and x as input, and output Euler's totient function (number of positive integers less than x co-prime to x) applied n times. Testcases n x result 1 10 4 2 10 ...
2
votes
4answers
171 views

OMG! We're Twinning! [duplicate]

Introduction We define twin primes as two natural numbers p,p+2 which both are prime. Example: 5 and 7 are twin primes. Let's define the twin number of some set of numbers as the number of twin ...
20
votes
18answers
1k views

Swap bits with their neighbours

Task description Given an integer, swap its (2k–1)-th and 2k-th least significant bits for all integers k > 0. This is sequence A057300 in the OEIS. (The number is assumed to have “...
8
votes
10answers
245 views

N-uniquely additive sets

Remember that a set is unordered without duplicates. Definition An N-uniquely additive set S whose length is K is a set such that all N-length subsets in S sum to different numbers. In other words, ...
13
votes
4answers
330 views

My “keybore” is key-boring me! Help me find a minimal keystrokes

Credits to @Agawa001 for coming up with this question. Explanation My new "keybore" only has 2 buttons, namely + and -. The number in the memory starts at 0. Each consecutive press of + or - will ...
11
votes
6answers
449 views

Longest arithmetic subsequence

Given a non empty finite sequence of integers, return an arithmetic subsequence of maximal length. If there are multiple of the same maximal length, any of them can be returned. Definitions: An ...
1
vote
9answers
733 views

Generate an infinite group of infinite galaxies [closed]

Here is the challenge as proposed by @trichoplax thanks to him for consolidating my post and standarizing it to PPCG common-rules. A galaxy is a group of numbers where each one is mapped to ...
2
votes
0answers
137 views

What's so great about 1729? [closed]

This is not a duplicate of this question. This is asking for the nth number that can be represented as the sum of two cubes in two different ways, while that is asking for the n-th number that can be ...
4
votes
3answers
178 views

Surjective, Injective, Bijective, or Nothing?

Given a mapping from the integers from 1 to N to the integers from 1 to N, determine if the mapping is surjective, injective, bijective, or nothing. You may choose any character/digit for the four ...
10
votes
11answers
728 views

Discrete Convolution or Polynomial Multiplication

Given two non empty lists of integers, your submission should calculate and return the discrete convolution of the two. Interestingly, if you consider the list elements as coefficients of polynomials, ...
14
votes
4answers
281 views

Shortest paths in a divisor graph

Introduction In this challenge, we will be dealing with a certain infinite undirected graph, which I call the high divisor graph. Its nodes are the integers starting from 2. There is an edge between ...
19
votes
19answers
2k views

Finite Cantor's Diagonal

Given a list of N integers, each with N digits, output a number which differs from the first number because of the first digit, the second number because of the second digit, etc. Example Given this ...
12
votes
3answers
351 views

Minimize Those Ones [closed]

Your task is to build a natural number using the fewest number of ones and only the operators + or -. For example, the number seven can be written 1+1+1+1+1+1+1=7, but it can also be written as 11-1-1-...
9
votes
8answers
371 views

Draw a phi triangle

Clarification: Basically, you need to make this Euler's totient function has the name phi. Let's try to calculate phi(8) First, list all numbers 8 and under backwards, not including 0 or under 8 7 ...
6
votes
12answers
310 views

Polygonal numbers

A polygonal number is the number of dots in a k-gon of size n. You will be given n and k, and your task is to write a program/function that outputs/prints the corresponding number. Scoring This is ...
14
votes
15answers
917 views

Find the n-th perfect power!

A perfect power is a number of the form a**b, where a>0 and b>1. For example, 125 is a perfect power because it can be expressed as 5**3. Goal Your task is to write a program/function that ...
6
votes
15answers
299 views

Find the positive divisors!

Definition A number is positive if it is greater than zero. A number (A) is the divisor of another number (B) if A can divide B with no remainder. For example, 2 is a divisor of 6 because 2 can ...
9
votes
7answers
285 views

Find the repetend of the decimal representation!

In this challenge 2 years ago, we found the period of a unit fraction (1/n where n is a natural number). Now, your task is to write a program/function to find the repetend of a unit fraction. The ...
8
votes
8answers
334 views

m-nomial coefficient

While binomial coefficient is the coefficient of (1+x)**n, m-nomial coefficient is the coefficient of (1+x+x**2+...+x**(m-1))**n. For example, m(3,5,6) is the coefficient of x**6 in the expansion of (...
20
votes
14answers
882 views

Generate the minimal remainder sequence

Every number can be represented using an infinitely long remainder sequence. For example, if we take the number 7, and perform 7mod2, then 7mod3, then 7mod4, and so on, we get 1,1,3,2,1,0,7,7,7,7,.......
3
votes
10answers
1k views

Is it really a comcoin?

Very interesting background Comcoins are a currency like any other. The residents of Multibaseania (an economically robust system of city-states with very few residents in a galaxy far, far away) use ...
-3
votes
1answer
161 views

Ponderous primality testing [closed]

One of my favorite algorithms was posted on Stack Overflow as an answer to What is the fastest way to generate prime number recursively?. In pseudocode: Nathan's algorithm bool isPrime(int n): ...
25
votes
39answers
2k views

Greatest Common Divisor

Your task is to compute the greatest common divisor (GCD) of two given integers in as few bytes of code as possible. You may write a program or function, taking input and returning output via any of ...
27
votes
14answers
2k views

The Arithmetic Derivative

The derivative of a function is a cornerstone of mathematics, engineering, physics, biology, chemistry, and a large number of other sciences as well. Today we're going to be calculating something only ...
28
votes
2answers
264 views

Addition on Elliptic Curves

Addition on Elliptic Curves Disclaimer: This does not do any justice on the rich topic of elliptic curves. It is simplified a lot. As elliptic curves recently got a lot of media attention in the ...
20
votes
9answers
851 views

Highly composite numbers

A highly composite number is a positive integer that has more divisors than any smaller positive integer has. This is OEIS sequence A002182. Its first 20 terms are 1, 2, 4, 6, 12, 24, 36, 48, 60, 120,...
27
votes
12answers
2k views

One-zero dividend

Challenge description For every positive integer n there exists a number having the form of 111...10...000 that is divisible by n i.e. a decimal number that starts with all 1's and ends with all 0's. ...
45
votes
13answers
2k views

Calculate the number of primes up to n

π(n) is the number of primes less than or equal to n. Input: a natural number, n. Output: π(n). Scoring: This is a fastest-code challenge. Score will be the sum of times for the score cases. I ...
21
votes
9answers
1k views

Generate lazy values

Related: Program my microwave oven. Inspired by Generate lazy microwave input. The lazy value of the non-negative integer N is the smallest of the integers that are closest to N while all their ...
24
votes
8answers
2k views

That's a prime… almost

If you've ever learned about primes in math class, you've probably have had to, at one point, determine if a number is prime. You've probably messed up while you were still learning them, for example, ...
13
votes
20answers
1k views

Output the juggler sequence

The juggler sequence is described as follows. Beginning with an input a1, the next term is defined by the recurrence relation The sequence terminates when it reaches 1, as all subsequent terms ...
24
votes
19answers
3k views

Implement the divisibility-by-7 rule

To check whether a decimal number is divisible by 7: Erase the last digit. Multiply it by 2 and subtract from what is left. If the result is divisible by 7, the original number is divisible by 7. ...
1
vote
0answers
45 views

Quotient in base 31 numeral system [closed]

You're given two numbers a and b in base 31 numeral system and number k with no more than 10000 decimal digits. It is known that b is divisor of a. The task is to find last k 31-based-digits of ...
10
votes
1answer
212 views

Residue Number System

In the vein of large number challenges I thought this one might be interesting. In this challenge, we will be using the Residue Number System (RNS) to perform addition, subtraction, and ...
17
votes
8answers
400 views

Print the Super Collatz numbers

The Collatz Sequence (also called the 3x + 1 problem) is where you start with any positive integer, for this example we will use 10, and apply this set of steps to it: if n is even: Divide it by ...
16
votes
10answers
1k views

Split, flip and recombine integers

Background It's well known in mathematics that integers can be put into a one-to-one correspondence with pairs of integers. There are many possible ways of doing this, and in this challenge, you'll ...
20
votes
26answers
7k views

List Prime Numbers [duplicate]

Introduction Prime numbers are simple, right? Well, now you get your chance to find out! Challenge You must write a program or function that takes an input n and outputs the first n prime numbers. ...
19
votes
20answers
2k views

The Möbius Function

The Möbius Function The Möbius function is an important number theoretic function. Your submission should accept a positive integer n and return the value of the Möbius function evaluated at n. ...
10
votes
5answers
271 views

Bézout's Identity

Introduction to Bézout's identity The GCD of two integers A, B is the largest positive integer that divides both of them leaving no remainder. Now because of Euclid's property that each integer N can ...
10
votes
8answers
276 views

Primitive Roots of Unity

Let z be a complex number. z is an nth primitive root of unity if for a certain positive integer n and for any positive integer k < n . Challenge Write a full program or function that, given a ...
11
votes
1answer
171 views

Calculate the Number, Divisors Edition

Inspired by this question over on Math. Let the prime factorization of a number, n, be represented as P(n) = 2a x 3b x 5c x .... (Using x as the multiplication symbol.) Then the number of divisors of ...
12
votes
8answers
397 views

Base Conversion With Strings

Introduction We've have a few base conversion challenges here in the past, but not many designed to tackle arbitrary length numbers (that is to say, numbers that are long enough that they overflow ...
19
votes
4answers
240 views

Partitioning reciprocals

Given a number n > 77, write a program or function that finds a set of distinct positive integers such that the sum of the set equals n, and the sum of the reciprocals of the set equals 1. Example ...
24
votes
8answers
957 views

Visualize the greatest common divisor

Background The greatest common divisor (gcd for short) is a convenient mathematical function, since it has many useful properties. One of them is Bézout's identity: if d = gcd(a, b), then there exist ...
25
votes
20answers
3k views

What's a half on the clock?

In my room, I have this geeky clock (click for full size): Most of these are not difficult to figure out, but the one for 4-o-clock is particularly tricky: Normally, a fraction like 1/2 doesn't ...
23
votes
17answers
1k views

Co-primality and the number pi

Introduction Number theory is full of wonders, in the form of unexpected connections. Here's one of them. Two integers are co-prime if they have no factors in common other than 1. Given a number N, ...
18
votes
6answers
411 views

The Kimberling Sequence

Introduction Of course, we've got a lot of sequence challenges, so here is another one. The Kimberling sequence (A007063) goes as following: 1, 3, 5, 4, 10, 7, 15, 8, 20, 9, 18, 24, 31, 14, 28, 22,...