Draft:Yuuki

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

24

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

Stub

This section is a stub. You can help Wikiversity by expanding it.

Prime numbers in C

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.

Stub

This section is a stub. You can help Wikiversity by expanding it.

Algebra

$(a+b)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}a^{n-k}b^{k}$ (Binomial theorem)

Stub

This section is a stub. You can help Wikiversity by expanding it.

References

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

Link to any subpages this page might have