Project Euler 429

Sum of squares of unitary divisors



I got stucked on this problem for a while(about 30min). My code runs in 0.826311s with primesieve library.
In my opinion, this is a median task and not a very easy one said by others. It’s evident that gcd(d, n / d) = 1 is an important condition. Besides, you have to know how to compute all primes of a factorial and finally you should come up with a simpley DP method.
There are totaly 1435 person got this task solved by today.

Project Euler 249

Prime Subset Sums

I get this task solved with Dynamic Programming. My code runs in 3.52223s. Cause it needs a large amount of modulo operations, so we’d better replace them with minus operations and it boosts my solution from 5.xxxx seconds to 3.xxx seconds.
Back to the problem description. As we all known, the number of subsets is too large that it’s impossible to iterate each subset. But the main idea here is the sum of elements of each subset is relatively small.
Overall, this is an easy one but with 60% difficulty rating.

Project Euler 214

Totient Chains

Nothing is new in this problem. I solved it by the first try, and my code runs in 2.57885s.
First I compute the value of Euler’s totient function for each number from 1 to $4 \times 10^7$. This can be done like prime seive in $O(N \log N)$.
Then using another array to keep the length of totient chain start from each integer (this can be done fast because length of current integer number i only depends on length of chain start with phi[i]) and what we need is those chains that start with a prime and length equal to 25.

Project Euler 211

Divisor Square Sum

I first solved this problem by bruteforce. It cost 14.7125 seconds to yield the result which is definitly below my expectation.
The method is for each number i, add its contribution (e.g. i * i) to all its multiples. Time complexity of this method should be $O(n \log{n})$.

trying to improve bruteforce method……

Project Euler 187

Semiprimes

This is a rather simply problem whose difficulty rating is only 25%. I solve it by generating all primes smaller than $10^8$ and according to the definition of Semiprimes, a semiprime is composed by the product of two primes. So we can iterate all possible pair of primes until their product larger than $10^8$.
My code runs in about 1.8s and actually I generated primes under $\frac{10^8}{2}$.
Besides, there is a builtin function named PrimePi or something similar in a few programming languages. Also we can use primeseive to generate primes we need when using C++.

Zeckendorf Representation

Zeckendorf Representation says that every positive integer can be uniquely written as a sum of nonconsecutive terms of the Fibonacci sequence.
For example, 100 = 3 + 8 + 89.

  • existence proof
    Take n as a positive integer and f_i is the largest Fibonacci number that smaller than n.
    If we eliminate fi from n, than n shall smaller than f{i-1} (why?).
    n will be zero at then end. you can simulate the process for deeper understanding.

  • uniqueness proof
    As we all known, there is no way to represent a Fibonacci number as a nonconsecutive distinct Fibonacci numbers sequenc except itself(think why?).
    Assume x is a Fibonacci number, then we can not find a nonconsecutive distinct Fibonacci numbers sequence that smaller than x whose sum equals to x(why?).
    To be more specifically, sum of two different(at least one element differs) nonconsecutive Fibonacci Number sequence can not be equal.

I found a coding method occasionally called Fibonacci coding that is closely related to Zeckendorf Representation. and in this article, they offered a way to compute Zeckendorf Representation of a particular integer and it’s easy understanding and simulating, of course very fast.

And Here is challenge from Project Euler which can be solved using method which similar with the way mentioned by the former link.

Project Euler Problem 193

Problem Link

Problem Description

A positive integer n is called squarefree, if no square of a prime divides n, thus 1, 2, 3, 5, 6, 7, 10, 11 are squarefree, but not 4, 8, 9, 12.
How many squarefree numbers are there below $2^{50}$?

Let’s introduce mobius function first, it looks like this:
Mobius Function

Now the answer should be equal to: $\sum_{k=1}^{sqrt{N}} floor(N / k^2) * mobius(k)$

A quick way to compute mobius(k) for all 1 <= k <= n is to use a sieve to find a prime divisor for each such k. After this, it is easy to apply following equation:
mobius(n) = 0 if n % p^2 = 0 else -mobius(n / p).
here p is a prime divisor of n.
below is my code,

Alternatively, we can also use inclusion-exclusion princple which is more intuitive.

Actually, mobius function is the sign in the inclusion-exclusion principle :-)

Hausdorff distance

This post is a basic introduction to Hausdorff distance.

  • Definition

(eq. 1)

where $d(\cdot,\cdot)$ is any metric between points, A and B are point sets.

Brute force algorithm:

1
2
3
4
5
6
7
8
9
1. h = 0
2. for everty point $a_i$ of A,
2.1 shortest = Inf;
2.2 for every point $b_i$ of B,
$d_{ij} = d(a_i, b_j)$
if $d_{ij}$ < shortest then
shortest = $d_{ij}$
2.3 if shortest > h then
h = shortest

  • Application examples
    One of the main application of the Hausdorff distance is image matching, used for instance in image analysis, visual navigation of robots, computer-assisted surgery, etc. Basically, the Hausdorff metric will serve to check if a template image is present in a test image ; the lower the distance value, the best the match. That method gives interesting results, even in presence of noise or occlusion (when the target is partially hidden).

Say the small image below is our template, and the large one is the test image :
template test
We want to find if the small image is present, and where, in the large image. The first step is to extract the edges of both images, so to work with binary sets of points, lines or polygons :

template test

Edge extraction is usually done with one of the many edge detectors known in image processing, such as Canny edge detector, Laplacian, Sobel, etc. After applying Rucklidge’s algorithm that minimizes Hausdorff distance between two images, the computer found a best match :

Convex Function

Today I come cross a question about ‘why raised functions are called concave functions’ on zhihu. It is obviously that some pepole misunderstand the concept of convex function and concave function.

  1. So let we start with ‘convex set’.
    In Euclidean space, a convex set is the region such that, for every pair of points within the region, every point on the straight line segment that joins the pair of points is also within the region.
    for example:
    Illustration of a convex set

  2. epigraph(or supergraph)
    the epigraph or supergraph of a function $f : R^n\rightarrow R$ is the set of points lying on or above its graph:
    $$epi\ f = {(x, \mu): x \in \mathbb{R}^n, \mu \in \mathbb{R}, \mu \geq f(x)} \subseteq \mathbb{R}^{n+1}$$
    Illustration of epigraph

  3. judge convex function using epigraph
    A function is convex if and only if its epigraph is a convex set.

  4. Convex Hull
    the convex hull may be defined as the intersection of all convex sets containing X.
    Illustration of convex hull
    The easiest and most popular method to calculate convex hull is Graham Algorithm which costs $O(n\times log\ n)$ time.

Matrix Factorization

Matrix Factorization is an important method for matrix completion.
Besides, there are many matrix factorization methods and this post only offers a simple implementation of matrix factorization.

script>