# Tagged Questions

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

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 ...
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 ...
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. ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
938 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 -> ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
233 views

### Puzzle: Factor these 256-bit semiprimes [closed]

Challenge Write a program to factor this set of 10 numbers: 15683499351193564659087946928346254200387478295674004601169717908835380854917 ...
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 ...
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 ...
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 ...