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

learn more… | top users | synonyms

17
votes
8answers
297 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. ...
9
votes
5answers
223 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
258 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
149 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
7answers
255 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
234 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 ...
22
votes
8answers
756 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 ...
22
votes
15answers
911 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
351 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
748 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
175 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
648 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 ...
9
votes
3answers
177 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
468 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 ...
29
votes
31answers
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
601 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 ...
16
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
480 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
608 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 ...
16
votes
39answers
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
938 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 ...
33
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
356 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
406 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 ...
51
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 ...
11
votes
4answers
238 views

Crazy Librarian's Interesting Prime Permutation Index Number Generator

You saved the day with your prime sequence code, and the math teacher loved it. So much so that a new challenge was posed to the librarian (a/k/a, your boss). Congratulations, you get to code the ...
6
votes
3answers
274 views

Symmetric boolean functions as Zhegalkin polynomials

Let 𝔹 = ℤ2 = {0, 1} be the set of booleans. A symmetric boolean function in n arguments is a function fS : 𝔹n ↦ 𝔹 that checks if the number of its true arguments is in S, i. e. a ...
7
votes
20answers
1k views

N numbers closest to zero staying balanced

Objective: Given a positive integer n: If n is odd, output the list of n numbers closest to 0 in increasing order If n is even, output a Falsey value. Test cases: 5 -> [-2,-1,0,1,2] 4 -> ...
23
votes
8answers
1k views

Print all 3 by 3 sturdy squares

A sturdy square (akin to a magic square) is an arrangement of the integers 1 to N2 on an N by N grid such that every 2 by 2 subgrid has the same sum. For example, for N = 3 one sturdy square is 1 5 ...
15
votes
4answers
419 views

Crazy Librarian's Arithmetic Sequence of Primes

Well, the librarian caught you cheating at your job by using your sorting algorithm, so now you're being punished. You've been ordered to create some code so the librarian can impress the object of ...
10
votes
3answers
713 views

Math in manhattan

I define the following operators: Manhattan Addition a +M b, for single-digit numbers, is the result of concatenating b onto a. So, a +M b = 10a + b. Therefore, the general operator +M is defined as ...
6
votes
2answers
199 views

Print a table of numbers in decimal and 2**i bases

Computers live by binary. All programmers know binary. But the 2**x bases are often neglected as non-practical, while they have beautiful relations to binary. To show you one example of such a ...
23
votes
19answers
3k views

Am I perfect (number)?

This is my first challenge! Background Perfect number is a positive integer, that is equal to the sum of all its divisors, except itself. So 6 is perfect number, since 1 + 2 + 3 = 6. On the other ...
87
votes
142answers
18k views

Is this number a prime?

Believe it or not, we do not yet have a code golf challenge for a simple primality test. While it may not be the most interesting challenge, particularly for "usual" languages, it can be nontrivial in ...
12
votes
13answers
745 views

Composite Number Sequences

Composite Number Sequences Inspired by this question Given a positive integer n, your code must output the first n composite numbers. Input / Output You may write a program or a function. Input is ...
40
votes
12answers
4k views

A naturally occurring prime generator

There are quite a large number of prime generating functions. Pretty much all of them are constructed and are based on the sieve of Eratosthenes, the Möbius function or the Wilson's theorem and are ...
-7
votes
7answers
233 views

Puzzle: Factor these 256-bit semiprimes [closed]

Challenge Write a program to factor this set of 10 numbers: 15683499351193564659087946928346254200387478295674004601169717908835380854917 ...
31
votes
6answers
1k views

Can you reach this number by doubling and rearranging?

Inspired by this question on Math.SE. Starting with 1 you can repeatedly perform one of the following two operations: Double the number. or Rearrange its digits in any way you want, except that ...
9
votes
5answers
469 views

Cycle lengths for Perfect shuffles of decks of any size

Challenge In the shortest amount of code: Compute the length of the permutation cycle of a perfect shuffle on a deck of cards of any size n (where n ≥ 2 and n is even). Output a table of all cycle ...
2
votes
8answers
258 views

Exponentiation of natural numbers using only primitive integer operations [duplicate]

The challenge Implement the C equivalent of the pow() function (exponentiation) for natural numbers, in a language of your choosing, using only addition, subtraction (which includes negation and ...
21
votes
2answers
775 views

Row of natural numbers

Definition There is infinite row of concatenated natural numbers (positive integers, starting with 1): 1234567891011121314151617181920212223... Challenge Write program in any language, that ...
9
votes
4answers
711 views

The Untouchables

Untouchable Numbersα An untouchable number is a positive integer that cannot be expressed as the sum of all the proper divisors of any positive integer (including the untouchable number itself). ...