Draft:Yuuki
Yuuki, colloquially known as Yuuki Kindergarten, is a virtual research institute.
24
edit24 is a game in which the objective is to create an expression whose value is 24 using four given numbers, basic arithmetic operations, and parentheses. Such a problem can be easily solved by a computer program using brute force method. However, the problem is that a bunch of expressions that look essentially "equivalent" are output, such as ((1*2)*3)*4
and ((4*3)*2)*1
. Computer algebra systems (CAS) such as SymPy cannot be used to deal with this problem, because they consider all expressions whose values are equal, such as (1+(2+3))*4
and (1+3)*(2+4)
, to be equal.
Mark Dominus proposed the Ezpr data structure to solve this problem and wrote a Perl solver based on it.[1] It converts expressions into certain canonical forms so that the equivalence of the expressions can be determined by the string equivalence of the canonical forms.
Prime numbers in C
editProgramming prime numbers is often the first challenge for beginners.
- Definition (Prime number)
- An integer n > 1 is prime iff it is not divisible by any integer i such that 2 <= i <= n - 1.
Here's a simple C program to print the primes less than 100:
prime.c
#include <stdio.h> /** * Determines if an integer is prime. */ int is_prime(const int n) { int i; /* Integers less than or equal to 1 are not prime. */ if (n <= 1) { return 0; } /* Performs trial division by every integer `i` such that 2 <= `i` <= `n` - 1. */ for (i = 2; i < n; i++) { if (n % i == 0) { return 0; } } return 1; } int main(void) { int i; /* Prints the primes less than 100. */ for (i = 2; i < 100; i++) { if (is_prime(i)) { printf("%d\n", i); } } return 0; }
$ gcc -Wall -Wextra -o prime prime.c $ ./prime 2 3 ... 97
This program determines if a number is prime by dividing it by smaller numbers, as is the definition. Such an algorithm is called trial division.
One of the most curious is, actually, whether a number is prime, and if not, what its prime factors are. That's called prime factorization and discussed later.
We can improve our program using knowledge of arithmetic.
- Definition (Divisibility)
- Let n, d, and k be integers with d != 0. We say that n is divisible by d (or d is a divisor of n) iff there exists k such that n = kd.
- Theorem (Upper bound for the greatest non-trivial divisor)
- If d < n, then d <= n/2.
- Proof
- From d < n, we have:
- n = kd < kn
- => 1 < k
- => 2 <= k.
- Then we have:
- 2d <= kd = n
- => d <= n/2.
So, it is sufficient to do trial division for an integer i <= n/2, instead of i <= n - 1.
Algebra
edit
Notes
editReferences
edit- Dominus, Mark Jason (2017). "Recognizing when two arithmetic expressions are essentially the same".