Week 1: Exercises

1. Multiples

Solve Project Euler's Problem 1 in C#:

Find the sum of all the multiples of 3 or 5 below 1000.

2. Fibonacci Sum

Solve Project Euler's Problem 2 in C#:

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

3. Prime Factor

Solve Project Euler's Problem 3 in C#:

What is the largest prime factor of the number 600851475143 ?

4. Largest Palindrome Product

Solve Project Euler's Problem 4 in C#:

Find the largest palindrome made from the product of two-digit numbers.

5. 10001st Prime

Solve Project Euler's Problem 7 in C#:

What is the 10001st prime number?

6. Prime Counting

In number theory, the prime-counting function π(x) denotes the number of prime numbers that are less than or equal to x. (It is unrelated to the number π.)

a) Write a C# program that computes and prints π(1,000,000). Use trial division for primality testing.

b) Write the same program in Python.

c) Compare the running time of the two programs.

7. Last Digits

Write a program that computes and prints the last 5 digits of the integer 2¹⁰⁰⁰.

8. Primality Claim

Consider this claim:

For every integer n ≥ 2, n is prime if and only if 2ⁿ – 2 is divisible by n.

For example:

• n = 2: 2² – 2 = 4 – 2 = 2 is divisible by 2

• n = 3: 2³ – 2 = 8 – 2 = 6 is divisible by 3

• n = 4: 2⁴ – 2 = 16 – 2 = 14 is not divisible by 4

• n = 5: 2⁵ – 2 = 32 – 2 = 30 is divisible by 5

We see that the claim is true at least through n = 5.

Write a C# program that determines whether the claim is true for all values through n = 1000. If the claim fails for any such n, print its value.

9. Integer Conversions

What value do you think each of these programs will print?

a)

int k = 1050;
WriteLine((int) (byte) k);

b)

long l = 256_256_256_256;
WriteLine((long) (byte) (int) l);

10. Lots of Casts

Consider these functions:

a)

int a(int i) {
    return (int) (float) i;
}

b)

int b(int i) {
    return (int) (double) i;
}

c)

long c(long l) {
    return (long) (double) l;
}

Which of these functions, if any, do you believe is equal to the identity function, i.e. it always returns the same value it was given? If you're not sure, run experiments to find out the answer.

11. Double Experiment

Consider these questions:

a) A double has an initial value of 1.0. How many times can we divide it by 2 before it becomes 0?

b) A double has an initial value of 1.0. How many times can we multiply it by 2 before it becomes Double.PositiveInfinity?

Guess at the answers to (a) and (b). Then write a problem that performs these experiments and prints out the resulting values.