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

learn more… | top users | synonyms

37
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
184 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
416 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
230 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
711 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
663 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). ...
9
votes
3answers
318 views

Knödel numbers - Find Kn

Knödel Numbers The Knödel numbers are a set of sequences. Specifically, the Knödel numbers for a positive integer n are the set of composite numbers m, such that all i < m, coprime to m, satisfy ...
10
votes
2answers
259 views

Naturally linear Diophantine equations

A linear Diophantine equation in two variables is an equation of the form ax + by = c, where a, b and c are constant integers and x and y are integer variables. For many naturally occurring ...
23
votes
11answers
1k views

Generate Keyboard Friendly Numbers

Most common computer keyboard layouts have the decimal digit keys 1234567890 running along at their top, above the keys for letters. Let a decimal digit's neighborhood be the set of digits from ...
16
votes
7answers
632 views

Last Nonzero Digits of a Factorial in Base

You should write a program or function which given three positive integers n b k as input outputs or returns the last k digits before the trailing zeros in the base b representation of n!. Example ...
16
votes
4answers
401 views

Testing if a number is a square

Write a GOLF assembly program that given a 64-bit unsigned integer in register n puts a non-zero value into register s if n is a square, otherwise 0 into s. Your GOLF binary (after assembling) must ...
20
votes
2answers
488 views

Factoring a 64-bit integer

Write a GOLF assembly program that reads an integer from stdin (followed by a trailing newline), and outputs its prime factors seperated by newlines, followed by a trailing newline on stdout. The ...
10
votes
9answers
1k views

Generate The SUDSI Sequence

The SUDSI sequence (sum, difference, swap, increment) is a curious integer sequence that appears to exhibit rather chaotic behavior. It can be generated as follows: Let S be an infinite list of the ...
17
votes
6answers
2k views

Chinese Remainder Theorem

The Chinese Remainder Theorem tells us that we can always find a number that produces any required remainders under different prime moduli. Your goal is to write code to output such a number in ...
4
votes
1answer
167 views

Find a numeric coincidence when representing numbers in various bases

Recently, when doing some code-golf challenge, I came up with with two solutions, in 69 and 105 bytes. It's a remarkable coincidence, because: 69 (decimal) = 105 (octal) 69 (hexadecimal) = 105 ...
12
votes
6answers
615 views

Iterated Divisor Twist

Definitions Let m and n be positive integers. We say that m is a divisor twist of n if there exists integers 1 < a ≤ b such that n = a*b and m = (a - 1)*(b + 1) + 1. If m can be obtained from n ...
19
votes
18answers
4k views

Generate Lucky Numbers

Story: Lucy asked George what his Lucky Number was. After some contemplation, George replied that he had several Lucky Numbers. After some brief confusion, Lucy asked George what his first n Lucky ...
11
votes
5answers
848 views

How many ways to write N as a product of M integers?

Given an integer N, count how many ways it can be expressed as a product of M integers > 1. Input is simply N and M, and output is the total count of distinct integer groups. Meaning you can use an ...
3
votes
3answers
584 views

Generate all 4-perfect numbers

Your program or function should output all the 36 4-perfect numbers in increasing order separated by newlines. An n positive integer is a k-perfect number (multiply perfect number) if the sum of its ...
12
votes
3answers
346 views

Nearest partition numbers

The number of partitions of an integer is the number of ways that integer can be represented as a sum of positive integers. For example: 5 4 + 1 3 + 2 3 + 1 + 1 2 + 2 + 1 2 + 1 + 1 + 1 1 + 1 + 1 + 1 ...
7
votes
4answers
655 views

Build a Primitive Root Diffuser

Introduction When a room has bare, parallel walls, it can create unpleasant repeating acoustic reflections (echoes). A diffuser is a device mounted on a wall which creates a blocky surface of many ...
12
votes
9answers
700 views

Combinatorial products of unique primes

Statement of problem Given a set of unique, consecutive primes (not necessarily including 2), generate the products of all combinations of first powers of these primes — e.g., no repeats — and also ...
8
votes
6answers
1k views

Mixed Base Conversion

Background Most people on here should be familiar with several base systems: decimal, binary, hexadecimal, octal. E.g. in the hexadecimal system, the number 1234516 would represent 1*16^4 + 2*16^3 + ...
25
votes
1answer
869 views

Standardise a Phinary Number

Background Most people on here should be familiar with a few integer base systems: decimal, binary, hexadecimal, octal. E.g. in the hexadecimal system, a number abc.de16 would represent a*16^2 + ...
7
votes
16answers
1k views

Generate Recamán's sequence

Recamán's sequence (A005132) is a mathematical sequence, defined as such: A(0) = 0 A(n) = A(n-1) - n if A(n-1) - n > 0 and is new, else A(n) = A(n-1) + n A pretty LaTex version of the above ...
14
votes
8answers
1k views

Generate Hofstadter's Figure-Figure Sequence

In Gödel, Escher, Bach, Douglas Hofstadter introduces an integer sequence which is commonly referred to as the figure-figure sequence: 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, ...
14
votes
15answers
2k views

Generate Ulam Numbers

Given an integer n (where n < 10001) as input, write a program that will output the first n Ulam numbers. An Ulam number is defined as follows: U1 = 1, U2 = 2. For n > 2, Un is the smallest ...
12
votes
8answers
756 views

Digit sum of central binomial coefficients

The task is simply to see how much faster you can calculate n choose n/2 (for even n) than the builtin function in python. Of course for large n this is a rather large number so rather than output ...
11
votes
6answers
627 views

Given r and n, find first n numbers of x where moving first digit of x to last gives x/r = y

Objective Given input r and n find the first n natural numbers x such that if we rotate the first digit to the last place we obtain x/r. You may assume that 2 <= r <= 9 and 1 <= n <= ...
39
votes
26answers
8k views

Find the Smoothest Number

Your challenge is to find the smoothest number over a given range. In other words, find the number whose greatest prime factor is the smallest. A smooth number is one whose largest prime factor is ...
7
votes
1answer
255 views

Minimal cover of bases for quadratic residue testing of squareness

Challenge Find the smallest cover of bases (e.g., moduli) whose sets of quadratic residue can be tested via table-lookup to definitively determine whether or not a given non-negative integer n is a ...
1
vote
5answers
489 views

Modular exponentiation using only addition and subtraction

The challenge In the least number of source code characters, in a language of your choosing, devise a function which raises base a to power b, modulo m, using purely integer arithmetic, where a, b, ...
11
votes
9answers
2k views

Write program which verifies Erdős–Straus conjecture

Write program, which verifies Erdős–Straus conjecture. Program should take as input one integern (3 <= n <= 1 000 000) and print triple of integers satisfying identity 4/n = 1/x + 1/y + 1/z, 0 ...
-2
votes
9answers
319 views

Restricted minumum

You need to find the sum of minimum values of two list (same size) of small numbers. In a C like language, that could be expressed as: v = min(a[0],b[0]) + min(a[1],b[1])+ min(a[2],b[2]) ... The ...
22
votes
13answers
3k views

Calculate `n % 12`

Calculate n modulo 12 for an unsigned 32 bit integer. The Rules: Must work for all n between 0 and 23. Other numbers optional. Must only use any of the operators +-*, ~&^| or <<, ...
1
vote
2answers
535 views

Find nth root of variable without using math operators/functions

Write a program which, given two positive integers n and x, will display the n-th root of x (which is also x1/n) in decimal to an accuracy of 0.00001. The program must output the resulting number in ...
13
votes
14answers
2k views

Four Squares Together

Lagrange's four square theorem tells us any natural number can be represented as the sum of four square numbers. Your task is to write a program that does this. Input: A natural number (below 1 ...
11
votes
5answers
1k views

Cheap, Fast, Good - Common Factor (Greatest)

Inspired by Cheap, Fast, Good, we're going to implement an algorithm which has exactly two of them. The Math Given two nonzero integers a and b, the GCF d is the largest integer that divides both a ...
8
votes
2answers
813 views

Collatz Attack!

This challenge is based on some new findings related to the Collatz conjecture and designed somewhat in the spirit of a collaborative polymath project. Solving the full conjecture is regarded as ...
13
votes
4answers
790 views

Calculate practical numbers

Definition A positive integer n is a practical number (OEIS sequence A005153) iff all smaller positive integers can be represented as sums of distinct divisors of n. For example, 18 is a practical ...
4
votes
6answers
600 views

Count how many numbers are divisible by perfect numbers in a given range

Given two arbitrary integers a and b. Count how many numbers are divisible by perfect numbers in that given range (a and b both are inclusive). In mathematics, a perfect number is a positive ...
14
votes
6answers
858 views

Period of the decimal representation

Write a function which takes a single positive integer n and returns the period of the decimal representation of 1/n. Test cases: 1 -> 1 # 1/1 = 1.0000...... = 1._0 2 -> 1 ...
12
votes
5answers
356 views

Hardy–Ramanujan number generalization

1729, known as the Hardy–Ramanujan number, is the smallest positive integer that can be expressed as the sum of two cubes of positive integers in two ways (12^3+1^3=10^3+9^3=1729). Given an integer n ...
6
votes
13answers
1k views

List the first 20 friendly number pairs

I just started reading about friendly numbers and I think they sound great. In number theory, friendly numbers are two or more natural numbers with a common abundancy, the ratio between the sum of ...
4
votes
1answer
279 views

Decompose a range in aligned blocks of size 2^n

Given an arbitrary contiguous range of positive integers, find the decomposition in the minimum number of sub-ranges of size L = 2^n, with the constraint that each range must be aligned, that is the ...
11
votes
10answers
1k views

N Doors, K Monkeys

There are N doors and K monkeys. Initially, all the doors are closed. Round 1: The 1st monkey visits every door and toggles the door (if the door is closed, it gets opened it; if it is open, it gets ...
4
votes
7answers
564 views

Nth K-Ugly Number

Write the shortest code in any language of your choice to find the Nth K-ugly number. A K-ugly number is a number whose only prime factors are the prime numbers <= K. This K-ugly number is ...
6
votes
3answers
860 views

The making of “Spot It!”: Finding almost unique sets

Puzzle: Find a deck of c cards, each containing p pictures, such that no two pictures match on a given card, and exactly 1 picture on each card matches exactly 1 picture on each of the other cards, ...
16
votes
6answers
1k views

Find largest prime which is still a prime after digit deletion

Over at http://math.stackexchange.com/questions/33094/deleting-any-digit-yields-a-prime-is-there-a-name-for-this the following question is asked. How many primes are there that remain prime after you ...