# Draft:Yuuki

**Yuuki**, colloquially known as **Yuuki Kindergarten**, is a virtual research institute.

## 24 edit

24 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 edit

Programming 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 edit

## References edit

- Dominus, Mark Jason (2017). "Recognizing when two arithmetic expressions are essentially the same".