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

learn more… | top users | synonyms

10
votes
2answers
251 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
618 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 ...
13
votes
3answers
296 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 ...
19
votes
2answers
428 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
969 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
160 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
608 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 ...
10
votes
5answers
809 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
569 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
339 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
636 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
683 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
998 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
800 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
15answers
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 ...
13
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
734 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
607 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 <= ...
40
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
248 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
460 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
313 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
513 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
796 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
764 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
587 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
855 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
330 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
979 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
996 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
537 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
812 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 ...
7
votes
5answers
424 views

Bijection between binary strings and pairs thereof

Input: Either one or two strings of '0's and '1's. If there are 2, they are separated by a space. All strings are of length at least 1. Output: If one string was input, 2 are output. If 2 were ...
3
votes
2answers
391 views

List ALL prime-factorized natural numbers in ANY order

This is a variant of List prime-factorized natural numbers up to N in ascending order, but the solutions can be very different. Write a program that outputs prime factorizations of all natural ...
5
votes
2answers
1k views

List prime-factorized natural numbers up to N in ascending order

For a given n list prime factorization of all natural numbers between 1 and n in ascending order. For example, for n = 10 the output would be: 1: 2: 2^1 3: 3^1 4: 2^2 5: 5^1 6: 2^1 3^1 7: 7^1 8: 2^3 ...
16
votes
16answers
1k views

Calculate hamming weight with low hamming weight

Create a program that computes the hamming weight of a string. Winner is the program with the lowest hamming weight. Rules: Hamming weight for an ASCII character is defined as the total number of ...
16
votes
38answers
1k views

Undulant numbers

An undulant number is a number where its digits go up and down like the following number: 461902 or 708143, or even 1010101, but not 123, because 2 < 3. write function which returns true if a ...
5
votes
12answers
557 views

Another amicable number problem

Two numbers are said to be 'amicable' or 'friends' if the sum of the proper divisors of the first is equal to the second, and viceversa. For example, the proper divisors of 220 are: 1, 2, 4, 5, 10, ...
15
votes
7answers
551 views

Square Number Digit Density

The square number digit density (SNDD) of a number - invented by myself - is the ratio of the count of square numbers found in consecutive digits to the length of the number. For instance, 169 is a ...
6
votes
4answers
595 views

Greatest greatest common divisor

Find the greatest gcd of the numbers nm + k and (n+1)m + k for given m and k. For example, for m=3, k=1 we have: gcd(1^3 + 1, 2^3 + 1) = 1 gcd(2^3 + 1, 3^3 + 1) = 1 ... gcd(5^3 + 1, 6^3 + 1) = 7 ...