Skip to main content
added 1779 characters in body
Source Link
Lucia
  • 43.7k
  • 6
  • 193
  • 219

Indeed such problems have been studied before. First note I claim that if $[k_1,\ldots,k_r]$ is a given multiset (with all $k_j\ge 1$) then the count of numbers below $x$ with factorization type $p_1^{k_1}\cdots p_{r}^{k_r}$ will be at most the number of integers below $x$ with factorization type $p_1\cdots p_r$: this is clear because if $p_1^{k_1} p_2^{k_2}\cdots p_r^{k_r} \le x$ then automatically $p_1p_2\cdots p_r \le x$, so that any integer counted in the first case gives rise to a corresponding one counted in the second case. Thus the champion multisets will alwaysjust be in the form of a numberstring of $1$'s. If you have $r$ ones (for a suitable $r$), then you're asking for the number ofand in this case one is counting square-free integers up to $x$ with exactly $r$ prime factors. This hascase has been widely investigated. For example, Balazard establishing a conjecture of Erdős showed that for each large $x$ this sequence is unimodal in $r$ (see Theorem E on page 24), and (as one can see by Hardy-Ramanujan/Erdős-Kac) attains its maximum for $r$ close to $\log \log x$. Balazard's paper will have more references -- in particular to work of Hildebrand and Tenenebaum giving asymptotics in wide ranges. In particular, it follows that the maximum number of integers up to $x$ having a factorization of type $p_1 \cdots p_r$ is $$ \sim \frac{6}{\pi^2} x \frac{1}{\sqrt{2\pi \log \log x}}, \tag{1} $$ which is attained for $r$ around $\log \log x$. (The $6/\pi^2$ comes from counting square-free numbers.)

Now consider a general factorization type $[k_1,\ldots, k_s, 1, 1,\ldots ,1]$ where $k_1$, $\ldots$, $k_s$ are all at least $2$ (and the number of $1$'s in the multiset could possibly be zero). We'll show that these factorization types will contribute an amount smaller than the largest possibility for all ones given above. Write every number of this factorization type as $n=ab$ where $a$ is square-full and $b$ is square-free and coprime to $a$ (thus $a$ has type $[k_1,\ldots, k_s]$ and $b$ is of type $[1,\ldots, 1]$). Thus the number of integers of this factorization type is (with $a$ and $b$ having the above meaning) $$ \sum_{1< a=p_1^{k_1}\cdots p_s^{k_s}} \sum_{b \le x/a} 1 \le \sum_{a >\sqrt{x}} \frac{x}{a} + \sum_{a\le \sqrt{x}} \Big(\frac{6}{\pi^2} +o(1)\Big) \frac{x}{a \sqrt{2\pi \log \log x}}, \tag{2} $$
where we bounded the sum over $b$ trivially in the first sum, and using (1) in the second sum (note $\log \log (x/a) \sim \log \log x$ there, and we also ignored the condition that $b$ is coprime to $a$). Since the number of square-full integers up to $x$ is $\ll \sqrt{x}$, the first sum in (2) may be bounded by $\ll x^{\frac 34}$. We may of course evaluate the second term exactly, for any given choice of $[k_1,\ldots,k_s]$. Alternatively, we could bound that term by letting $a$ run over all square-full integers $>1$: since $$ \sum_{1<a, a\text{ square-full}} \frac 1a =\prod_{p} \Big(1+\frac{1}{p^2}+\frac{1}{p^3}+\ldots \Big) -1 = \frac{\zeta(2)\zeta(3)}{\zeta(6)}- 1 =0.943\ldots . $$ This completes our proof that factorization types having at least one number strictly larger than $1$ contribute an amount that is strictly smaller than the maximum attained by all ones.

One can be extract more information than given above. For example, after types involving all $1$'s the next champion will be $[2,1,1,1,\ldots,1]$, and here one can give an asymptotic like (1) for the maximum such number etc.

Indeed such problems have been studied before. First note that if $[k_1,\ldots,k_r]$ is a given multiset (with all $k_j\ge 1$) then the count of numbers below $x$ with factorization type $p_1^{k_1}\cdots p_{r}^{k_r}$ will be at most the number of integers below $x$ with factorization type $p_1\cdots p_r$: this is clear because if $p_1^{k_1} p_2^{k_2}\cdots p_r^{k_r} \le x$ then automatically $p_1p_2\cdots p_r \le x$, so that any integer counted in the first case gives rise to a corresponding one counted in the second case. Thus the champion multisets will always be in the form of a number of $1$'s. If you have $r$ ones, then you're asking for the number of square-free integers up to $x$ with exactly $r$ prime factors. This has been widely investigated. For example, Balazard establishing a conjecture of Erdős showed that for each large $x$ this sequence is unimodal in $r$ (see Theorem E on page 24), and (as one can see by Hardy-Ramanujan/Erdős-Kac) attains its maximum for $r$ close to $\log \log x$. Balazard's paper will have more references -- in particular to work of Hildebrand and Tenenebaum giving asymptotics in wide ranges.

Indeed such problems have been studied before. I claim that the champion multisets will just be a string of $r$ ones (for a suitable $r$), and in this case one is counting square-free integers up to $x$ with exactly $r$ prime factors. This case has been widely investigated. For example, Balazard establishing a conjecture of Erdős showed that for each large $x$ this sequence is unimodal in $r$ (see Theorem E on page 24), and (as one can see by Hardy-Ramanujan/Erdős-Kac) attains its maximum for $r$ close to $\log \log x$. Balazard's paper will have more references -- in particular to work of Hildebrand and Tenenebaum giving asymptotics in wide ranges. In particular, it follows that the maximum number of integers up to $x$ having a factorization of type $p_1 \cdots p_r$ is $$ \sim \frac{6}{\pi^2} x \frac{1}{\sqrt{2\pi \log \log x}}, \tag{1} $$ which is attained for $r$ around $\log \log x$. (The $6/\pi^2$ comes from counting square-free numbers.)

Now consider a general factorization type $[k_1,\ldots, k_s, 1, 1,\ldots ,1]$ where $k_1$, $\ldots$, $k_s$ are all at least $2$ (and the number of $1$'s in the multiset could possibly be zero). We'll show that these factorization types will contribute an amount smaller than the largest possibility for all ones given above. Write every number of this factorization type as $n=ab$ where $a$ is square-full and $b$ is square-free and coprime to $a$ (thus $a$ has type $[k_1,\ldots, k_s]$ and $b$ is of type $[1,\ldots, 1]$). Thus the number of integers of this factorization type is (with $a$ and $b$ having the above meaning) $$ \sum_{1< a=p_1^{k_1}\cdots p_s^{k_s}} \sum_{b \le x/a} 1 \le \sum_{a >\sqrt{x}} \frac{x}{a} + \sum_{a\le \sqrt{x}} \Big(\frac{6}{\pi^2} +o(1)\Big) \frac{x}{a \sqrt{2\pi \log \log x}}, \tag{2} $$
where we bounded the sum over $b$ trivially in the first sum, and using (1) in the second sum (note $\log \log (x/a) \sim \log \log x$ there, and we also ignored the condition that $b$ is coprime to $a$). Since the number of square-full integers up to $x$ is $\ll \sqrt{x}$, the first sum in (2) may be bounded by $\ll x^{\frac 34}$. We may of course evaluate the second term exactly, for any given choice of $[k_1,\ldots,k_s]$. Alternatively, we could bound that term by letting $a$ run over all square-full integers $>1$: since $$ \sum_{1<a, a\text{ square-full}} \frac 1a =\prod_{p} \Big(1+\frac{1}{p^2}+\frac{1}{p^3}+\ldots \Big) -1 = \frac{\zeta(2)\zeta(3)}{\zeta(6)}- 1 =0.943\ldots . $$ This completes our proof that factorization types having at least one number strictly larger than $1$ contribute an amount that is strictly smaller than the maximum attained by all ones.

One can be extract more information than given above. For example, after types involving all $1$'s the next champion will be $[2,1,1,1,\ldots,1]$, and here one can give an asymptotic like (1) for the maximum such number etc.

added 414 characters in body
Source Link
Lucia
  • 43.7k
  • 6
  • 193
  • 219

Indeed such problems have been studied before. First note that if $p_1^{k_1} p_2^{k_2}\cdots \le x$$[k_1,\ldots,k_r]$ is a given multiset (with all $k_j\ge 1$) then the count of numbers below $p_1p_2\cdots \le x$$x$ with factorization type $p_1^{k_1}\cdots p_{r}^{k_r}$ will be at most the number of integers below $x$ with factorization type $p_1\cdots p_r$: this is clear because if $p_1^{k_1} p_2^{k_2}\cdots p_r^{k_r} \le x$ then automatically $p_1p_2\cdots p_r \le x$, so that any integer counted in the first case gives rise to a corresponding one counted in the second case. Thus the championschampion multisets will always be in the form of a number of $1$'s. If you have $r$ ones, then you're asking for the number of square-free integers up to $x$ with exactly $r$ prime factors. This has been widely investigated. For example, Balazard establishing a conjecture of Erdős showed that for each large $x$ this sequence is unimodal in $r$ (see Theorem E on page 24), and (as one can see by Hardy-Ramanujan/Erdős-Kac) attains its maximum for $r$ close to $\log \log x$. Balazard's paper will have more references -- in particular to work of Hildebrand and Tenenebaum giving asymptotics in wide ranges.

Indeed such problems have been studied before. First note that if $p_1^{k_1} p_2^{k_2}\cdots \le x$ then $p_1p_2\cdots \le x$. Thus the champions will always be in the form of a number of $1$'s. If you have $r$ ones, then you're asking for the number of square-free integers up to $x$ with exactly $r$ prime factors. This has been widely investigated. For example, Balazard establishing a conjecture of Erdős showed that for each large $x$ this sequence is unimodal in $r$ (see Theorem E on page 24), and (as one can see by Hardy-Ramanujan/Erdős-Kac) attains its maximum for $r$ close to $\log \log x$. Balazard's paper will have more references -- in particular to work of Hildebrand and Tenenebaum giving asymptotics in wide ranges.

Indeed such problems have been studied before. First note that if $[k_1,\ldots,k_r]$ is a given multiset (with all $k_j\ge 1$) then the count of numbers below $x$ with factorization type $p_1^{k_1}\cdots p_{r}^{k_r}$ will be at most the number of integers below $x$ with factorization type $p_1\cdots p_r$: this is clear because if $p_1^{k_1} p_2^{k_2}\cdots p_r^{k_r} \le x$ then automatically $p_1p_2\cdots p_r \le x$, so that any integer counted in the first case gives rise to a corresponding one counted in the second case. Thus the champion multisets will always be in the form of a number of $1$'s. If you have $r$ ones, then you're asking for the number of square-free integers up to $x$ with exactly $r$ prime factors. This has been widely investigated. For example, Balazard establishing a conjecture of Erdős showed that for each large $x$ this sequence is unimodal in $r$ (see Theorem E on page 24), and (as one can see by Hardy-Ramanujan/Erdős-Kac) attains its maximum for $r$ close to $\log \log x$. Balazard's paper will have more references -- in particular to work of Hildebrand and Tenenebaum giving asymptotics in wide ranges.

edited body
Source Link
GH from MO
  • 105.4k
  • 8
  • 293
  • 398

Indeed such problems have been studied before. First note that if $p_1^{k_1} p_2^{k_2}\cdots \le x$ then $p_1p_2\cdots \le x$. Thus the champions will always be in the form of a number of $1$'s. If you have $r$ ones, then you're asking for the number of square-free integers up to $x$ with exactly $r$ prime factors. This has been widely investigated. For example, Balazard establishing a conjecture of ErdosErdős showed that for each large $x$ this sequence is unimodal in $r$ (see Theorem E on page 24), and (as one can see by Hardy-Ramanujan/ErdosErdős-Kac) attains its maximum for $r$ close to $\log \log x$. Balazard's paper will have more references -- in particular to work of Hildebrand and Tenenebaum giving asymptotics in wide ranges.

Indeed such problems have been studied before. First note that if $p_1^{k_1} p_2^{k_2}\cdots \le x$ then $p_1p_2\cdots \le x$. Thus the champions will always be in the form of a number of $1$'s. If you have $r$ ones, then you're asking for the number of square-free integers up to $x$ with exactly $r$ prime factors. This has been widely investigated. For example, Balazard establishing a conjecture of Erdos showed that for each large $x$ this sequence is unimodal in $r$ (see Theorem E on page 24), and (as one can see by Hardy-Ramanujan/Erdos-Kac) attains its maximum for $r$ close to $\log \log x$. Balazard's paper will have more references -- in particular to work of Hildebrand and Tenenebaum giving asymptotics in wide ranges.

Indeed such problems have been studied before. First note that if $p_1^{k_1} p_2^{k_2}\cdots \le x$ then $p_1p_2\cdots \le x$. Thus the champions will always be in the form of a number of $1$'s. If you have $r$ ones, then you're asking for the number of square-free integers up to $x$ with exactly $r$ prime factors. This has been widely investigated. For example, Balazard establishing a conjecture of Erdős showed that for each large $x$ this sequence is unimodal in $r$ (see Theorem E on page 24), and (as one can see by Hardy-Ramanujan/Erdős-Kac) attains its maximum for $r$ close to $\log \log x$. Balazard's paper will have more references -- in particular to work of Hildebrand and Tenenebaum giving asymptotics in wide ranges.

Source Link
Lucia
  • 43.7k
  • 6
  • 193
  • 219
Loading