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

learn more… | top users | synonyms

8
votes
7answers
243 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
326 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
854 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 ...
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
145 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): ...
22
votes
36answers
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
247 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
839 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, ...
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. ...
43
votes
12answers
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
44 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
194 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
361 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
257 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
273 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
164 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
364 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
238 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
901 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
389 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, ...
12
votes
9answers
782 views

Pentagonal numbers made from pentagonal numbers

Introduction A pentagonal number (A000326) is generated by the formula Pn= 0.5×(3n2-n). Or you can just count the amount of dots used: You can use the formula, or the gif above to find the first ...
5
votes
2answers
188 views

Convolve integers in subquadratic time

An linear discrete convolution is an operation that turns two vectors of numbers into a third vector of numbers by multiplying elements inside-out. Formally, for two vectors a and b with elements 0 to ...
17
votes
8answers
688 views

Novel Prime Factors of Repunits

The Background Folks were talking prime factorization in chat and we found ourselves talking about repunits. Repunits are a subset of the numbers known as repdigits, which are numbers consisting of ...
10
votes
3answers
211 views

Priming a Pristine World

Heavily inspired by Programming a Pristine World. Also closely related to this challenge. Let's define a pristine prime as a number which is itself prime, but will no longer be prime if you remove ...
15
votes
11answers
479 views

Find the sets of sums

I've enjoyed reading this site; this is my first question. Edits are welcome. Given positive integers n and m, compute all ordered partitions of m into exactly n parts positive integer parts, and ...
31
votes
32answers
4k views

Catalan Numbers

The Catalan numbers (OEIS) are a sequence of natural numbers often appearing in combinatorics. The nth Catalan number is the number of Dyck words (balanced strings of parenthesis or brackets such as ...
24
votes
29answers
1k views

AGM Series Hole 1: Calculate the Arithmetic–Geometric Mean

This question was inspired by this HNQ. About the series This question is now part of a series about the AGM method. This first post in the series will be about actually calculating the AGM. You may ...
16
votes
6answers
619 views

Converging Sums of a Fractal Sequence

Background A fractal sequence is an integer sequences where you can remove the first occurrence of every integer and end up with the same sequence as before. A very simple such sequence is called ...
17
votes
9answers
1k views

Hilbert Primes Golf

Hilbert numbers are defined as positive integers of the form 4n + 1 for n >= 0. The first few Hilbert numbers are: 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77, 81, ...
64
votes
22answers
6k views

Well that's odd… no wait, that's even!

Preamble Integers are always either even or odd. Even integers are divisible by two, odd integers are not. When you add two integers you can infer whether the result will be even or odd based on ...
15
votes
4answers
485 views

How many squares, cubes, fourth powers, etc. do I need to sum to n?

You are given a nonnegative integer n and an integer p >= 2. You need to add some p-th powers (p=2 means squares, p=3 means cubes) together to get n. This is always for any nonnegative n, but you ...
9
votes
6answers
661 views

Calculate the Kronecker symbol

Relevant links here and here, but here is the short version: You have an input of two integers a and b between negative infinity and infinity (though if necessary, I can restrict the range, but the ...
21
votes
20answers
1k views

Is q a quadratic residue of n?

Given two inputs q n determine if q is a quadratic residue of n. That is, is there an x where x**2 == q (mod n) or is q a square mod n? Input Two integers q and n, where q and n are any integers 0 ...
17
votes
18answers
1k views

Reverse and square

In this challenge you will compute numbers from a curious sequence. Your input is a single decimal nonnegative integer. Reverse the bits in this integer and then square the number to get the required ...
18
votes
40answers
1k views

Count the divisors of a number

Introduction This is a very simple challenge: simply count the divisors of a number. We've had a similar but more complicated challenge before, but I'm intending this one to be entry-level. The ...
13
votes
15answers
967 views

Simple Task Solved Thrice

You should write 3 programs and/or functions in one language. All of these programs should solve the same task but they all should give different (but valid) outputs. (I.e. for every pair of programs ...
34
votes
36answers
3k views

Count sums of two squares

Given a non-negative number n, output the number of ways to express n as the sum of two squares of integers n == a^2 + b^2 (OEIS A004018). Note that a and b can be positive, negative, or zero, and ...
16
votes
6answers
361 views

Find maximal matching in divisibility relation

You are given a set of positive integers. You must arrange them into pairs such that: Each pair contains 2 numbers, one of which is a multiple of another. For example, 8 is a multiple of 4, and 9 is ...
21
votes
5answers
420 views

Decimal concatenation of squares

Premise One night, I was just contemplating on numbers. I found out about something unique about numbers like 7, 10, 12, 13, and more. They are squares of squares! Meaning, that when squared, are ...
52
votes
16answers
4k views

Calculate Phi (not Pi)

No, I don't mean ϕ = 1.618... and π = 3.14159.... I mean the functions. φ(x) is the number of integers less than or equal to x that are relatively prime to x. π(x) is the number of primes less than ...