Subway Math is a personal project, dedicated to come up with a random Math question (they pop out whenever I am bored) and intending to eventually prove/solve it. It's called this way because I am mostly bored on the way home on subway.
Let \(\Phi:\mathbb{N}\longrightarrow\mathbb{N}\) be a function that, given \(n\in\mathbb{N}\), \(\Phi(n)\) gives the LCM (Least Common Multiple) of the numbers between \(1\) and \(n\). Then:
We can also deduce that, in case \(\Phi(n)\) increases, \(\Phi(n)=p\cdot\Phi(n-1)\) for some \(p\) prime.
Corollary. As a result, given \(n>0\), the direct formula of \(\Phi(n)\) is:
With \(a(n,p)\) being the maximum integer exponent of \(p\) such that \(p^{a(n,p)}<=n\).
Useful example. Let's compute \(\Phi(10)\). By the corollary we first get all primes \(<=10\), which are \(2,3,5,7\). So \(\Phi(10)=2^3\cdot 3^2\cdot 5 \cdot 7\), since \(2^3=8\leq 10\) and \(3^2=9 \leq 10\).
The part (1) is trivial. Left as exercise for the dear reader. (Please don't get mad)
Part (2):
If \(n\) is prime, then \(n\) cannot divide \(\Phi(n-1)\), otherwise it means some prime factor of the previous numbers divides \(n\), which would contradict the definition of a prime number.
If \(n\) is an \(m\)-th power of a prime \(p\), it is the smallest number that can be factorised into \(p^m\). By definition of LCM, since none of the previous numbers contains \(p^m\) factor, LCM cannot "contain" the \(p^m\) factor. Therefore \(\Phi(n)\) must increase from \(\Phi(n-1)\).
By contradiction. Suppose \(\Phi(n)>\Phi(n-1)\) but \(n\) is neither prime nor a power of a prime. So We have that \(n = \prod_{i\in I}{p_i ^{\alpha_i}}\) (\(p_i\) is a prime, each \(p_i\) is a different prime, and \(\alpha_i\) is the multiplicity of the prime), with \(I\) having more than 1 element. Then we have that for all \(i\in I\), \(p_i ^{\alpha_i}\in\mathbb{N}\) is a strictly smaller natural than \(n\). Therefore, \(p_i ^{\alpha_i}\) divides \(\Phi(n-1)\). Since this happens for all \(i\in I\) (note that if \(A\) and \(B\) are coprimes and \(A\) divides \(N\) and \(B\) divides \(N\) then \(AB\) divides \(N\)), in particular \(\prod_{i\in I}{p_i ^{\alpha_i}}\) also divides \(\Phi(n-1)\), so \(n\) divides \(\Phi(n-1)\) and \(\Phi(n)\) cannot increase from \(\Phi(n-1)\). Contradiction.
Now this is a corollary (well everything until now have been corollaries honestly). We have that \(n\) is either a prime number or \(n=p^m\) with \(p\) being a prime number. In the former case \(\Phi(n)=n\cdot\Phi(n-1)\), and in the latter case, since \(p^{m-1}\) is smaller then \(p^m\), it holds that \(p^{m-1}\) divides \(\Phi(n-1)\), therefore "the LCM only needs one more \(p\) such that \(p^m\) divide \(\Phi(n)\)". And LCM cannot "need" anything smaller than \(p\) because \(p\) is prime.
I thought it could be somewhat more challenging since I didn't see it instantly. But after seeing it, and more importantly, seeing it this short, kind of disappoints me. At first, I wrote a program for it to have a insight about the patterns of the \(\Phi(n)\) function, and then formalized the proof, and the total time invested might be in roughly one hour.
(Update) And that's why I added a final deduction which results as a corollary XD. It is slightly more interesting since it means that \(\Phi(n)\) can only increase by a prime, and not some non-prime number.
Anyways, math is still fun!
Implemented in Python. Time complexity of computing \(\Phi(n)\) is \(O(n^{3/2}\log(n))\). However, given \(\Phi(n-1)\), computing \(\Phi(n)\) would be at most \(O(\sqrt{n}\log(n))\) (here lcm keeps track of \(\Phi(n-1)\)).
def is_prime(num):
if (num < 2):
return False
i = 2
while (i*i <= num):
if (num % i == 0):
return False
i += 1
return True
lcm = 2 # Phi(n) accumulator
# Prints Phi(n) from n=2 to n=299
for i in range(2,300):
prime = False
if (lcm % i != 0):
if (is_prime(i)):
prime = True
lcm *= i
else:
tmp_i = i
divided = True
while (divided):
divided = False
for j in range(2,tmp_i):
if (tmp_i % j == 0):
divided = True
tmp_i //= j
break
lcm *= tmp_i
print(f"n:{i} \tPhi(n)={lcm} \t{'x' if prime else ' '}")
The Regional Iron Cup of Phi gets us to the winner program described below. (Just a small competition between me and a mate, credits to Sergio D.).
The result: being able to process the 243.455.492-th \(\Phi(n)\) number using C++ in under 1 second (run on Colab) on one single thread. Locally it can blow up to 572.003.868-th number.
Rules:
Code:
const int CHS = 32000;
const int PRMC = 15000;
char v[CHS];
int prm[PRMC];
int solution(int x) {
int64_t res = 1;
const int MOD = 1000000007;
memset(v, 0, CHS);
memset(prm, 0, PRMC*sizeof(int));
int p_idx = 0;
for (int chunk_start = 2; chunk_start <= x; chunk_start += CHS) {
memset(v, 0, CHS);
int chunk_border = chunk_start+CHS;
for (int i = 0; i < p_idx; i++) {
int64_t p = prm[i];
if (p*p < chunk_border) {
for (int j = ((x*p-chunk_start)%p); j < CHS; j += p) {
v[j] = 1;
}
}
}
for (int p = chunk_start; p < chunk_border; p++) {
if (p <= x) {
if (!v[p-chunk_start]) {
if (((int64_t) p)*p <= (int64_t)x){
prm[p_idx] = p;
p_idx++;
for (int i = p*p; i < chunk_border; i+=p) {
v[i-chunk_start] = 1;
}
}
int64_t va = p;
while (va <= (int64_t) x) {
res = (res*p)%MOD;
va *= p;
}
}
}
}
}
return res;
}
Optimizations:
bitmap), experimentally one can see that the former gives more performance.All in all, the time complexity behavior is \(O(\frac{n^{3/2}}{\log n})\).
Time flies by as you're not taking action.
Click for another sentence