I want to find $$f(n) = \max\left\{\frac{\varphi(k)}{\lambda(k)} : 1 \leq k \leq n\right\}$$
In other words, I want to find the maximal value of $\frac{\varphi(k)}{\lambda(k)}$ when $k$ is restricted.
$\lambda(n)$ is the Carmichael function, the smallest $k$ such that for all $a$ such that $\gcd(a,n)=1$ the following congruence holds: $a^{k} \equiv 1 \mod n$. $\varphi(n)$ is the Euler-phi function. Note that $\lambda(n) \mid \varphi(n)$.
Since I don't expect $f(n)$ to have a nice expression in terms of elementary and number theoretic functions, I started to search for some lower bounds. I found that $$\frac{\varphi(2^k \cdot p_{k+1}\#)}{\lambda(2^k \cdot p_{k+1}\#)} \geq 2^k$$
Here $k\#$ is the primorial function.
Therefore I know that the fraction is unbounded, and that $$f(n) \in \Omega(n^{1/ \ln \ln n})$$
However $n^{1/ \ln \ln n}$ is still bounded above by all power functions with a positive power. Does anyone have an asymptotically better bound or a proof that this is the best bound?
I looked to OEIS, which has this sequence A034380. I found that the smallest $n$ such that $f(n)\geq 108$ is $n=3591$, the smallest $n$ such that $f(n)\geq 128$ is $n=5440$. However my method gives $1241560320$ as a number such that it is bigger than 128. Clearly, there is some room for improvement.
Conjecture: Will Jagy found strong numerical evidence that $f(n)$ eventually outgrows $n^{1-\varepsilon}$ for every $\varepsilon > 0$. A proof (or disproof) of this would be very welcome.
This time I let the target Carmichael number be the least common multiple of the numbers from $1$ to $w.$ This is more efficient in terms of the number of divisors. The Superior Highly Composite Numbers and the Colossally Abundant Numbers share the main property of this LCM, which is that the exponent of some prime $p$ is proportional to $1/ \log p.$ As a result, the multiplicative contribution from each prime is (very) roughly equal, because $$ x^{1/ \log x} = e. $$
We know from Legendre's theorem on the exponent of a prime dividing a factorial that the exponent here of $p$ is proportional to $1/p.$ So the smaller primes give a large multiplicative part, as $x^{1/x}$ goes to $1$ as $x \rightarrow \infty.$ Not an astonishing difference, I guess.
The program got incredibly slow doing the lcm of the numbers up to $23,$ so I will just paste in the lcm's up to $19.$
Got a much abbreviated output, so the whole thing goes much faster and I am able to compare things. It turns out the first time $\log f(n) / \log n$ passes 0.999 is actually when the assigned Carmichael number is the LCM up to $31,$ and the first time we pass 0.9999 is when the assigned Carmichael number is the LCM up to $43.$ I had it put in logs base 10 as well.
As far as proving anything, let me describe the construction this way: for a number $L,$ we let $C = \operatorname{lcm} (1,2,3,\ldots,L).$ We find all positive divisors $d | C.$ For each such $d,$ we check $q = 1 + d.$ If $q$ is prime, then $q$ becomes a factor of $n.$ Now if, in addition, $q \leq L,$ then $q$ gets an exponent larger than $1,$ because we get $q | C$ this way. In fact, we give $q$ the largest possible exponent such that the Carmichael number of $q^a$ divides $C.$ If, instead, $q > L,$ then the exponent of $q$ is precisely $1.$
This means that the number of primes that arise as $q=1+d$ with $d | L$ is a big part of the giant size of $n.$ It is easy to predict the number of positive divisors of $C$ because we know how it factors. Add one to each, many become prime, many do not. I made a table, it suggests that the number of primes is faster than polynomial as a function of $L,$ but slower than exponential.
Let's see. In the table above, the value of $L$ is on the left, let $P$ be the count of primes constructed. The final number, called "log ratio," is just $\log P / \log L.$ This seems to keep growing, so $P$ seems to be growing faster than a polynomial in $L.$
Next I repeated the table, but this time the "log ratio" is $\log P / L,$ which seems to be decreasing to $0,$ so it seems $P$ is growing slower than an exponential in $L$
There are infinitely many growth rates between polynomial and exponential as a function of $L;$ one of the easiest to type is $$ e^{\sqrt L} $$