Project Euler #712

Question

I've been stuck in this problem for a time, now. The problem is as follows:

For any integer $n \gt0$ and prime number $p,$ define $\nu_p(n)$ as the greatest integer $r$ such that $p^r$ divides $n$.

Define $$D(n, m) = \sum_{p \text{ prime}} \left| \nu_p(n) - \nu_p(m)\right|.$$ For example, $D(14,24) = 4$.

Furthermore, define $$S(N) = \sum_{1 \le n, m \le N} D(n, m).$$ You are given $S(10) = 210$ and $S(10^2) = 37018$.

Find $S(10^{12})$. Give your answer modulo $1\,000\,000\,007$.

I have written the simpler forms of these functions, and I get $D(14,24) = 4$, as well as $S(10) = 210$ and $S(100) = 37018$. Furthermore, I have ''discovered'' the relationship

\begin{equation} \sum_{n=1}^N \nu_p(n) = \sum_{k=1}^{p^k \lt N} \Bigl \lfloor\frac{N}{p^k} \Bigr \rfloor \end{equation}

But it didn't help me, since the absolute value was taken from the expression and I was not able to generalize. Nonetheless, I could not find a way to approach it without creating a sieve of the the prime numbers bellow $10^{12}$. I believe that in order to solve this problem, one would need to have some deeper knowledge of number theory that I have. I would like some insights to solve this problem (I am not asking for a solution, just some mathematical hints to approach it).

Answer 1

As with every Project Euler problem, you should start by inspecting what is really going on inside the function. In this specific case, the numbers $n,m$ don't actually matter - what you sum is the exponent difference of primes. You have to consider every prime $p$ up to $N$, and note its occurences for every exponent $e$ such that $p^e \le N$. Let's take a closer look at the case of $N=10$. As I've said, I will rather look at the primes than on the numbers $n,m$ themselves. Looking at $n,m$ themselves is highly misleading, which is my first tip to you and the first onion shell you have to remove off of this problem in order to solve it.

For $p=2$:

There are $5$ numbers in which $0$ is the highest power of $2$ in their prime decomposition: $1,3,5,7,9$

There are $3$ numbers in which $1$ is the highest power of $2$ in their prime decomposition: $2,6,10$

There is $1$ number in which $2$ is the highest power of $2$ in its prime decomposition: $4$

There is $1$ number in which $3$ is the highest power of $2$ in its prime decomposition: $8$

It is of curicial importance not to forget about the $0$'th exponent that is also possible. As a verification, there are obviously $10$ numbers in the range $[1,10]$, and here we have listed them all, exactly 10 numbers - $5 + 3 + 1+1 = 10$. It is easy enough to derive a "formula" to find how many numbers exist in which $p^e$ appears for each prime $p$ and each exponent $e$ in a given range $[1,N]$. I will leave it for you to deduce.

In a similiar manner, we find for the other primes:

For $p=3$:

There are $7$ numbers in which $0$ is the highest power of $3$ in their prime decomposition: $1,2,4,5,7,8,10$

There are $2$ numbers in which $1$ is the highest power of $3$ in their prime decomposition: $3,6$

There is $1$ number in which $2$ is the highest power of $3$ in its prime decomposition: $9$

For $p=5$:

There are $8$ numbers in which $0$ is the highest power of $5$ in their prime decomposition: $1,2,3,4,6,7,8,9$

There are $2$ numbers in which $1$ is the highest power of $5$ in their prime decomposition: $5,10$

For $p=7$:

There are $9$ numbers in which $0$ is the highest power of $7$ in their prime decomposition: $1,2,3,4,5,6,8,9,10$

There is $1$ number in which $1$ is the highest power of $7$ in their prime decomposition: $7$

Now, for each prime seperately, we match every group with all the others. Take 2 for example. There are $5$ numbers with $2^0$ in their prime decomposition. Similiarly, there are $3$ numbers with $2^1$ in their prime decomposition. We can match every number from the first group with a number from the second group, to get an exponent difference of exactly $1$. And there are $3\cdot 5 = 15$ such matchings, each contributing exponent difference of $1$ to the final sum. Because the problem does not state that $n<m$ or otherwise, then the pairs $(3,10) , (10,3)$ are to be counted seperately. Therefore the contribution I have just described has to be multiplied by 2, resulting in total contribution to the final sum of $30$. It is easier to find the "half-contribution" of all group matchings and multiply by 2 in the end.

Similiarly, for each prime, we match 2 groups in turns to get the final sum. I will now quickly sketch this to see where this $210$ comes from:

For $p = 2$:

As per my example, $5 \cdot 3\cdot \lvert(0 - 1)\rvert = 15$ (1st and 2nd group)

$5 \cdot 1\cdot \lvert(0 - 2)\rvert = 10$ (1st and 3rd group)

$5 \cdot 1\cdot \lvert(0 - 3)\rvert = 15$ (1st and 4th group)

$3 \cdot 1\cdot \lvert(1 - 2)\rvert = 3$ (2nd and 3rd group)

$3 \cdot 1\cdot \lvert(1 - 3)\rvert = 6$ (2nd and 4th group)

$1 \cdot 1\cdot \lvert(2 - 3)\rvert = 1$ (3rd and 4th group)

For $p = 3$:

$7 \cdot 2\cdot \lvert(0 - 1)\rvert = 14$ (1st and 2nd group)

$7 \cdot 1\cdot \lvert(0 - 2)\rvert = 14$ (1st and 3rd group)

$2 \cdot 1\cdot \lvert(1 - 2)\rvert = 2$ (2nd and 3rd group)

For $p = 5$:

$8 \cdot 2\cdot \lvert(0 - 1)\rvert = 16$ (1st and 2nd group)

For $p = 7$:

$9 \cdot 1\cdot \lvert(0 - 1)\rvert = 9$ (1st and 2nd group)

Summing it all up, we find:

$$S(10^2) = 2\cdot [(15 + 10 + 15 + 3 + 6 + 1) + (14 + 14 + 2) + (16) + (9)]=2\cdot[(50)+(30)+(16)+(9)] = 2 \cdot 105 = 210$$

(and not forgetting to multiply the sum by 2 in the end, because the order in which we choose the groups matters! i.e, "1st and 2nd" group is different than "2nd and 1st" group, but they both have the same contribution)

So, $S(10^2) = 210$ indeed. I encourage you to experiment with it a little, and with a computer program you will find more key observations.

Some hints and tips towards solving this problem:

• The primes $p \le \sqrt N$ have a very different behaviour than the primes $p > \sqrt N$, so I highly suggest you to split the sum to these 2 sub-sums
• You should learn about the Sieve of Eratosthenes, to tabulate the needed primes. Hint: The primes themselves whose values actually matter are the primes $p \le \sqrt N$. For the rest of the primes, $p > \sqrt N$, only their count matters (how many there are), rather than their values. Tabulating the primes $p \le 10^6$ should be an easy task.
• And, finally, to have a computer program solve this in reasonable time, you need to have a good prime-counting-function, denoted by $\pi (x)$. With that being said, a clever, efficient implementation of a brute-force-like algorithm, this problem can be solved without the prime-counting-function. However, this may take several hours. Hint: Segmented Sieve of Eratosthenes

Additionally, here are some more test values for you to compare your algorithm and know you're on the right path:

$S(10^1) = 210$

$S(10^2) = 37018$

$S(10^3) = 4654406$

$S(10^4) = 529398010$

$S(10^5) = 57689386540$

$S(10^6) = 6149855192622$

$S(10^7) = 646886370938854$

$S(10^8) = 67436388950708040$

$S(10^9) = 6985053526514689852$

$S(10^{10}) = 720037271618744270714$

Bare in mind that $S(10^9)$ is as far as a "dumb"-brute-force may get you. Getting beyond that requires further research, and clever as well as efficient implementations of algorithms I have described above as tips. I have included $S(10^{10})$ for you to know you have indeed managed to create such implementations. As a side note, my algorithm computes $S(10^{12})$ in less than a second, so it is indeed possible. All you have to do to solve it is sketch the inner machinery of this function as I have done thoroughly, and explore the behaviour of the primes.

Answer 2

most recent I've noticed on MSE Meta:

http://meta.math.stackexchange.com/questions/21383/project-euler-again

September 2015

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

about similar site, from author:

Solve Diophantine equation with three variables part two

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Magazine article by James Sommers :

http://www.theatlantic.com/technology/archive/2011/06/how-i-failed-failed-and-finally-succeeded-at-learning-how-to-code/239855/

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

discussion on MO:

http://tea.mathoverflow.net/discussion/1226/project-euler-questions/

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

discussion at Project Euler's own forum:

http://projecteuler.chat/viewtopic.php?f=5&t=2707

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

email letter from "hk", Novemeber 2011

Hi Will,

let me introduce myself to you. I'm hk at Project Euler. The philosophy of Colin Hughes, the founder of Project Euler was the philosophy of inductive self learning. Just Googling on the subject will reveal you quite a lot about this educational subject. (The top item on my version of Google was this one: http://mate.calpoly.edu/media/files/Review_inductive_learning.pdf)

My personal view on this matter is: if you lack the attitude, when faced with a new problem, to break it down into smaller parts or to investigate smaller cases you will never never become a successful scientist or academically schooled person. The problem in question that raised attention to Project Euler is particularly fit for scaling down and discover some useful facts.

I think we are facing a cultural clash here: The rationalisations shown to us by e.g. rbharvs are from the level: I have to be told how to do things. I'm afraid that has to do with a failing educational system that shows students rules and formulas without giving them enough room to experiment before formalising knowledge.

To do some work that is new to you, be it research mathematics or toying around with problems for which all underlying maths is known, you will need to doodle around with the problem or parts of it. How else can one do essentially new work? Top down teaching that doesn't help their students to develop this kind of ability produces people that start shouting: tell me how to do it and I will try to copy it. Some people that are badly educated in the way I sketched are just using Project Euler to develop those skills. I hope that they will benefit from that in their professional life. Some have even indicated that it was Project Euler that ultimately made them decide to choose mathematics for their academic study despite the poor level of the mathematical education in their country.

The people that posed the questions at Math Overflow, in my opinion have shown to lack the mental attitude to do the necessary doodling around. (Take for instance the fact that one of them copied the radius 10^10. Some experimenting would have shown them that ______).

Well, you can consider this private communication as lunch talk if it doesn't interest you, but I hope I gave you some information about the philosophy of Project Euler. Feel free to paraphrase it to your wish when communicating with your colleagues at Math Overflow. If you like to know more feel free to email me.

Thanks again for the effort you have invested in the case.

Regards

hk

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=