A prime gap is the difference between two consecutive prime numbers. For example, 7 and 11 are consecutive primes, and the gap between them has size 4.
Write a program that reads an integer N ≥ 3 and prints the largest prime gap among primes that are less than N. The program should print the pair of consective primes along with the gap size.
Goldbach's conjecture says that
Every even integer greater than 2 is the sum of two primes.
The conjecture seems obvious, but after more than 350 years it remains unproven.
Write a program that reads an integer N and checks whether Goldbach's conjecture is true for all integers that are ≤ N.
Write a program that reads an integer N and generates a random array of N integers in ascending order. The first number in the array should be 0, and the difference between each pair of consecutive array elements should be a random number from 1 to 10.
Next, the program should generate N new random integers in the range from 0 to 10 · N. The program should count how many of these integers are present in the array, and print this count.
If the input number N is large, what value do you think this program will print, approximately?
Observe the following facts:
23 mod 3 = 8 mod 3 = 2
24 mod 4 = 16 mod 4 = 0
25 mod 5 = 32 mod 5 = 2
26 mod 6 = 64 mod 4 = 4
27 mod 7 = 128 mod 7 = 2
Consider the following hypothesis:
For all integers k ≥ 3, 2k mod k = 2 if and only if k is prime.
Do you believe that this is true, or false? Write a Python program to investigate this question.
Write a function that takes an array a with N – 1 elements. The array will contain all the integers from 1 .. N in order, except that one integer from that range will be missing. Your function should return the value of the missing integer. It should run in time O(log N) in the worst case.
Write a function that takes a list of integers 'a' that is guaranteed to contain a strictly increasing sequence of values followed by a strictly decreasing sequence. For example, the integers might be
4, 8, 10, 20, 37, 50, 52, 48, 7
It's guaranteed that the values will increase at least once and decrease at least once.
Your function should find and return the largest value in the list. It must run in sub-linear time.
Suppose that we have a function f(x) that is defined on all integers and is monotonic, i.e. f(x) ≤ f(y) whenever x < y. (For example, f(x) = x3 is one such function.) Now we are given a value k, and would like to find the largest value n such that f(n) ≤ k. Write a program that can solve this problem in O(log n) (assuming that f runs in constant time).