19
$\begingroup$

Let us call a positive integer having in decimal representation no common digits with all its proper divisors "a good number".

  • $54$ is a good number : $1,2,3,6,9,18,27$.
  • $48$ is not a good number : $1,2,3,\color{red}{4},6,\color{blue}{8},12,16,2\color{red}{4}$

Good numbers : $2,3,4,5,6,7,8,9,23,27,29,34,37,38,43,46,47,49,53,54,\cdots$

I've been interested in these numbers, and I noticed that OEIS has this sequence. One can easily see the followings :

  • $1$ is not included in the digits of good numbers.
  • The right-most digit of a good number $n\ge 6$ is neither $0,1,2$ nor $5$.

Let $d(n)$ be the number of divisors of $n$. I noticed that $d(n)$ is relatively small for (smaller) good numbers $n$. The following shows $d(n)$ for good numbers $n$ except prime numbers.

$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n&4&6&8&9&27&34&38&46&49&54&56&57&58&68&69\\ \hline d(n)&3&4&4&3&4&4&4&4&3&8&8&4&4&6&4 \\\hline \end{array}$$ $$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n&76&78&86&87&247&249&259&267&289&323&329&334\\ \hline d(n)&6&8&4&4&4&4&4&4&3&4&4&4 \\\hline \end{array}$$

It seems that there exists the maximum of $d(n)$ for good numbers $n$. Also, it seems that the number of sets of four consecutive good numbers, such as $\{56,57,58,59\}$, is finite. However, though I've been trying to prove/disprove the two conjectures, I can neither prove nor disprove them. So, here are my questions.

Question 1 : Does there exist the maximum of $d(n)$ for good numbers $n$? If yes, what is it? If no, how can we show that?

Question 2 : Is the number of sets of four consecutive good numbers finite? If yes, what is the biggest such set? If no, how can we show that?

Added : For Question 1, a user san showed that the answer is yes and that an upper bound for $d(n)$ is 16. However, the maximum of $d(n)$ has not been obtained yet.

For Question 2, san showed that the answer is yes, and that the biggest such set is $\{56,57,58,59\}$.

$\endgroup$
3
  • $\begingroup$ just an observation, I do not have a computer now (tablet) so I can not check it, but looking to the examples you show, there is the possibility that if $d(n)\mid n$ then $\frac{n}{d(n)}=p\in \Bbb P$. There is not enough data in your samples so probably there is a counterexample, or maybe there are not more $n$ than $\{8,9,56\}$, but it could be an interesting property if it happens for all $n$. $\endgroup$
    – iadvd
    May 7, 2015 at 13:01
  • $\begingroup$ @iadvd: That's interesting if $n\gt 3$ because $n=2$ is a counterexample (It seems true that there exist finitely many good numbers $n$ such that $d(n)$ divides $n$). (btw, it'd be nice if you could show some relation between your conjecture and my questions). $\endgroup$
    – mathlove
    May 20, 2015 at 20:22
  • $\begingroup$ that observation came from another observation I did about the Totient function. Every time I see a set of numbers like this I tend to look for those kind of patterns automatically. This one: math.stackexchange.com/questions/1235390/… $\endgroup$
    – iadvd
    May 21, 2015 at 0:17

1 Answer 1

17
+50
$\begingroup$

For the first question the answer is yes, and an upper bound is 16.

We define a nearly good number to be such that the last digit is not the last digit of any of its proper divisors. We have the following result: $$ \text{Every nearly good number is the product of at most 4 prime numbers.}\ \ \ \ \ (*) $$ Hence every nearly good number (and also every good number) has at most 16 divisors.

The proof of (*) is very long, but straightforward. Here a sketch of the proof:

Assume that $n>10$ is a nearly good number. Write $\bar n$ for the last digit (or, by abuse of notation, also for the class in $\Bbb{Z}/10\Bbb{Z}$). We first prove that if $\bar n=9$, then it has only two prime factors at most. In fact, the only valid factorizations of $\bar 9$ in two factors are $$ \bar9=\bar 3\cdot \bar 3\quad\text{and}\quad \bar9=\bar 7\cdot \bar 7 $$ Since the only valid factorization of $\bar 3$ is $\bar 3=\bar 9\cdot \bar 7$ and the only valid factorization of $\bar 7$ is $\bar 7=\bar 9\cdot \bar 3$, both factors must be prime factors.

Arguing similarly, one obtains that if $\bar n=3$, then it has at most three prime factors, and in that case $\bar n=\bar 7\cdot\bar 7\cdot\bar 7$. And it is also straightforward to show that if $\bar n=7$, then it has at most three prime factors, and in that case $\bar n=\bar 3\cdot\bar 3\cdot\bar 3$.

Now comes the clumsy part: If $\bar n=8$, then the only valid factorizations in two factors are $$ \bar n=\bar 2\cdot \bar 4,\quad\bar n=\bar 3\cdot \bar 6,\quad\bar n=\bar 2\cdot \bar 9 \quad\text{and}\quad \bar n=\bar 4\cdot \bar 7. $$ In the four cases one shows that there are only three prime factors possible. For example, if we assume $\bar 8=\bar 2\cdot \bar 4$, then the factor $\bar 2$ correspond to the prime factor 2 (Else the factor is even and of the form $\bar m\cdot 2$ with $m>1$, hence $\bar 8=\bar m\cdot \bar 2\cdot\bar 4$ and the proper factor $\bar 2\cdot \bar 4$ has 8 as last digit). Since the factor with $\bar 4$ is even, it has a factorization $\bar 4=\bar m\cdot \bar 2$, and once again $\bar 2$ is the prime factor 2, and $\bar m=2$ or $\bar m=7$. In the first case all three factors are 2 and in the second case we cannot factorize $\bar 7$ (else $\bar 7=\bar 3\cdot \bar 9$, and the original number has a proper factor corresponding to $\bar 2\cdot \bar 9$, with last digit 8). The other cases are similar and prove that if $\bar n=8$, then there are at most three factors.

Finally one deals with the cases $\bar n=4$ and $\bar n=6$. Here the valid factorizations for $\bar n=4$ in two factors are $$ \bar n=\bar 2\cdot \bar 2=\bar 7\cdot \bar 2=\bar 3\cdot \bar 8=\bar 9\cdot \bar 6. $$ One verifies that there are at most 4 prime factors, with the only possible configuration $$ \bar n=\bar 3\cdot \bar 3\cdot\bar 3\cdot \bar 2. $$

Similarly the valid factorizations for $\bar n=6$ in two factors are $$ \bar n=\bar 2\cdot \bar 3=\bar 8\cdot \bar 2=\bar 4\cdot \bar 4=\bar 9\cdot \bar 4=\bar 7\cdot \bar 8. $$ One verifies that there are at most 4 prime factors, and the only possible configurations are then $$ \bar n=\bar 2\cdot \bar 2\cdot \bar 2\cdot \bar 7,\quad \bar n=\bar 2\cdot \bar 2\cdot \bar 7\cdot \bar 7\quad \text{and}\quad \bar n=\bar 2\cdot \bar 7\cdot\bar 7\cdot \bar 7. $$

So we have proved: If $n$ is a (nearly) good number, then $d(n)\le k(\bar n)$ where $$ k(9)=4,\quad k(3)=8,\quad k(7)=8,\quad k(8)=8,\quad k(4)=16,\quad\text{and}\quad k(6)=16. $$ Clearly $\bar n=0,1,2,5$ is not possible if $n>10$.

Although there are good numbers with four prime factors, I have never seen any with more than 8 divisors. It is highly probable that the maximum $d(n)$ for good numbers is 8. It is nearly impossible that it is 16, and there is a small chance that it is 9 or 12: If $d(n)>8$, then $n$ must have 4 prime factors and the valid configurations are $$ \bar n=\bar 2\cdot \bar 3\cdot \bar 3\cdot \bar 3,\quad \bar n=\bar 2\cdot \bar 7\cdot \bar 7\cdot \bar 7\quad \text{and}\quad \bar n=\bar 2\cdot \bar 2\cdot\bar 7\cdot \bar 7. $$ In the first case $1,2,3,6,7,8,9\ne Dig(n)$, and the combinations $50$ and $40$ in the string of digits of $n$ are impossible, hence the decimal representation of $n$ is a string with only 5's and 4's. How many of these numbers are product of 4 primes ending in 3,3,3,2? At least 54 is one of them, but as I said, I find it nearly impossible that there is a bigger good number like that.

In the second case $1,2,3,4,7,8,9\ne Dig(n)$, and the combinations $50$ and $60$ in the string of digits of $n$ are impossible, hence the decimal representation of $n$ is a string with only 5's and 6's. How many of these numbers are product of 4 primes ending in 7,7,7,2? I find it nearly impossible that there is number like that.

In the third case $1,2,4,7,8,9\ne Dig(n)$, hence the decimal representation of $n$ is a string with only 0's,3's,5's and 6's. If the two primes ending in 7 are equal, then $n$ has 9 divisors, else it has 12. Although the chance seems bigger than in the two previous cases, the bigger the number are that one tests, the more digits can yield a failure in being a good number, so the chance is very small.

$\textbf{Second question:}$ For the second question the answer is yes, and $56,57,58,59$ is the biggest such set. In particular, the only sets of four consecutive good numbers are $$ \{2,3,4,5\},\{3,4,5,6\},\{4,5,7,8\},\{5,6,7,8\},\{6,7,8,9\},\{56,57,58,59\}. $$

Note that if $m>0$, then $10m+5$ and $10m+1$ are not good numbers, so the only possible configuration for four consecutive numbers greater than 10 is $10m+6,10m+7,10m+8,10m+9$. Moreover, 1,2,3 and 4 are divisors of at least one of them, so the set $Dig(m)$ of the digits of $m$, cannot contain 1,2,3 or 4, in particular $\bar m\ne 1,2,3,4$. Now we assume $m>0$ and that $10m+6,10m+7,10m+8,10m+9$ are good numbers. We have to prove that $m=5$ is the only possible case.

$\textbf{Remark:}$

a) 3 divides at least one of the four numbers, and it cannot divide $10m+6$, since then $6$ would be a proper divisor of $10m+6$. Hence it divides $10m+7$ or $10m+8$.

b) If $4|10m+8$, then $\overline{10m+8}=2\cdot 2\cdot \bar 7$, since there are at most three prime factors, and $10m+8=\bar 2\cdot \bar 2\cdot \bar 2$ leads to $m=0$. In particular, in this case $3\not| 10m+8$.

We will analyse all possible cases of $\bar m$, the last digit of $m$.

$\textbf {CASE}\ \bar m=9$:

Clearly $\bar m\ne 9$, since then $10m+8$ is not a good number: $$ 10m+8=100k+98\quad\text{and}\quad d:=(10m+8)/2=50k+49, $$ so 9 is the last digit of the proper divisor $d$ and $9\in Dig(10m+8)$, a contradiction.

$\textbf {CASE}\ \bar m=0$:

In this case $4|10m+8=100k+8$, and, since $m>0$, we have that $k$ must be odd (otherwise $8|10m+8$). Write $k=2j+1$, then $(10m+8)/2=100 j+54$, hence $\bar k\ne 5$ and $(10m+8)/4=50 j+27$, hence $\bar k\ne 7$. Since $\bar k\ne 1,3$, we have only to discard the case $\bar k=9$. But $3|10m+7$ (by a) and b) above), and so $\overline{10m+7}= 3\cdot \bar 9$, which implies in this case $9\in Dig(10m+7)\cap Dig((10m+7)/3)$.

$\textbf {CASE}\ \bar m=8$:

In this case $4|10m+8=100k+88$, and, since $m>0$, we have that $k$ must be odd (otherwise $8|10m+8$). Write $k=2j+1$, then $(10m+8)/2=100 j+94$, hence $\bar k\ne 9$ and $(10m+8)/4=50 j+47$, hence $\bar k\ne 7$. Since $\bar k\ne 1,3$, we have only to discard the case $\bar k=5$. But $3|10m+7$ (by a) and b) above), hence, if $\bar k=5$, we have $10m+7=1000(3r+1)+587$ and so $(10m+7)/3=1000 r+529$ which implies $5\in Dig(10m+7)\cap Dig((10m+7)/3)$, a contradiction.

$\textbf {CASE}\ \bar m=6$:

In this case $4|10m+8=100k+68$, and, since $m>0$, we have that $k$ must be even (otherwise $8|10m+8$). Since $\bar k\ne 2,4$, we have to discard the cases $\bar k=0,6,8$. As above $3|10m+7$, hence, if $\bar k=8$, we have $10m+7=3000r+867$ and so $(10m+7)/3=1000 r+289$ which implies $8\in Dig(10m+7)\cap Dig((10m+7)/3)$, a contradiction. Similarly, if $\bar k=0$, we have $10m+7=1000(3r+2)+67$ and so $(10m+7)/3=1000 r+689$ which implies $6\in Dig(10m+7)\cap Dig((10m+7)/3)$, a contradiction. Finally, if $\bar k=6$, we have $10m+8=1000r+668$. Then $(10m+8)/2=500r+334$. If $r$ is odd ($r=2j+1$), then $(10m+8)/2=1000j+834$, impossible ($8\in Dig(10m+8)\cap Dig((10m+8)/2)$), and if $r$ is even, then $(10m+8)/2=1000j+334$ and so $(10m+8)/4=500j+167$, which leads to the contradiction $6\in Dig(10m+8)\cap Dig((10m+8)/4)$.

$\textbf {CASE}\ \bar m=7$:

In this case $4|10m+6$. Write $m=10k+7$. We will discard all possibilities for $\bar k$. Clearly $\bar k\ne 1,2,3,4$. If $\bar k=9$, then $9\in Dig(10m+8)\cap Dig((10m+8)/2)$, if $\bar k=8$, then $8\in Dig(10m+6)\cap Dig((10m+6)/2)$ and if $\bar k=7$, then $8\in Dig(10m+8)\cap Dig((10m+8)/2)$ (note that $(1000j+778)/2=500j+389$).

If $\bar k=6$, we have $10m+6=1000r+676$. Then $(10m+6)/2=500r+338$. If $r$ is odd ($r=2j+1$), then $(10m+8)/2=1000j+839$, impossible ($8\in Dig(10m+8)\cap Dig((10m+8)/2)$), and if $r$ is even, then $(10m+6)/2=1000j+338$ and so $(10m+6)/4=500j+169$, which leads to the contradiction $6\in Dig(10m+6)\cap Dig((10m+6)/4)$.

If $\bar k=5$ we have two options: If $3|10m+7$, then we have $10m+7=1000(3r+2)+577$ and so $(10m+7)/3=1000 r+859$ which implies $5\in Dig(10m+7)\cap Dig((10m+7)/3)$, a contradiction. If $3|10m+8$, then we have $10m+8=1000(3r+1)+578$ and so $(10m+7)/3=1000 r+526$ which implies $5\in Dig(10m+8)\cap Dig((10m+8)/3)$, a contradiction.

So we are left with the case $\bar k=0$. Here the only digits that can appear in $m$ are 0,5,6,7: if $9\in Dig(m)$, then $9\in Dig(10m+8)\cap Dig((10m+8)/2$, since $10m+8=1000r+78$. Similarly, if $8\in Dig(m)$, then $8\in Dig(10m+6)\cap Dig((10m+6)/2$, since $10m+6=1000r+76$.

Now we discard combinations of two consecutive digits of $m$. Clearly the combination $50$ can be discarded, since then $m/2$ has the combination 25 or the combination 75, leading to $5\in Dig(10m+6)\cap Dig((10m+6)/2$. We can also discard $70$: In that case $m/2$ admits the combination 35 (the other possibility $85$ leads to $8\in Dig(10m+8)\cap Dig((10m+8)/2)$), and so $m/4$ admits the combination 17 or 67, leading to $7\in Dig(10m+6)\cap Dig((10m+6)/4)$, a contradiction. The combinations 56 and 76 can be also discarded, since they lead to $8\in Dig(10m+8)\cap Dig((10m+8)/2$.

Resuming the restrictions, we have that on the left of a zero there can be only zero or 6, and to the left of a 6 there can be only a 0 or a 6. Since the two last digits of $m$ are 07, the only digits in the expansion to the left are 0 and 6. But then $m=600r+7$ and so $3|10m+7$ is impossible and $3|10m+8$ leads to $(10m+8)/3=(6000r+78)/3=2000r+26$, which implies $6\in Dig(10m+8)\cap Dig((10m+8)/3)$.

$\textbf {CASE}\ \bar m=5$:

In this case $4|10m+6$. Write $m=10k+5$. We will discard all possibilities for $\bar k$. Clearly $\bar k\ne 1,2,3,4$. If $\bar k=9$, then $9\in Dig(10m+8)\cap Dig((10m+8)/2)$, if $\bar k=8$, then $8\in Dig(10m+6)\cap Dig((10m+6)/2)$ and if $\bar k=7$, then $7\in Dig(10m+8)\cap Dig((10m+8)/2)$ (note that $(1000j+758)/2=500j+379$).

If $\bar k=6$, we have $10m+6=1000r+656$. Then $(10m+6)/2=500r+328$. If $r$ is odd ($r=2j+1$), then $(10m+8)/2=1000j+829$, impossible ($8\in Dig(10m+8)\cap Dig((10m+8)/2)$), and if $r$ is even, then $(10m+6)/2=1000j+328$ and so $(10m+6)/4=500j+164$, which leads to the contradiction $6\in Dig(10m+6)\cap Dig((10m+6)/4)$.

If $\bar k=5$ we have two options: If $3|10m+7$, then we have $10m+7=1000(3r+1)+557$ and so $(10m+7)/3=1000 r+519$ which implies $5\in Dig(10m+7)\cap Dig((10m+7)/3)$, a contradiction. If $3|10m+8$, then we have $10m+8=3000r+558$ and so $(10m+7)/3=1000 r+186$ which implies $8\in Dig(10m+8)\cap Dig((10m+8)/3)$, a contradiction.

So we are left with the case $\bar k=0$. Here the only digits that can appear in $m$ are 0,5,6,7: if $9\in Dig(m)$, then $9\in Dig(10m+8)\cap Dig((10m+8)/2)$, since $10m+8=1000r+58$. Similarly, if $8\in Dig(m)$, then $8\in Dig(10m+6)\cap Dig((10m+6)/2)$, since $10m+6=1000r+56$.

Now we discard combinations of two consecutive digits of $m$. Clearly the combination $50$ can be discarded, since then $m/2$ has the combination 25 or the combination 75, leading to $5\in Dig(10m+6)\cap Dig((10m+6)/2)$. Similarly the combination $70$ can be discarded, since then $m/2$ has the combination 35 or the combination 85, leading to $5\in Dig(10m+6)\cap Dig((10m+6)/2)$.

The combination $60$ can be discarded, since then $m/2$ has the combination 30 (the other possibility $80$ leads to $8\in Dig(10m+8)\cap Dig((10m+8)/2)$), and then $(10m+6)/4$ has the combination $15$ or the combination $65$, which both imply $5\in Dig(10m+6)\cap Dig((10m+6)/2)$.

Since the two last digits of $m$ are 05, we are left we the only case $m=5$, as desired.

$\endgroup$
10
  • $\begingroup$ That's an interesting idea, but maybe I don't understand well what you mean. A few questions : (1) Why isn't $\bar 8=\bar 2\cdot \bar 4$ valid? (2) Can you elaborate on how to show that for $\bar n=8$ there are only three prime factors possible? (why isn't $\bar 8=\bar 2\cdot \bar 2\cdot \bar 3\cdot\bar 7\cdot\bar 7$, for example, valid?) (3) Similarly, why isn't $\bar 4=(\bar 3)^{4m-1}\cdot \bar 2$, for example, valid? $\endgroup$
    – mathlove
    May 21, 2015 at 12:35
  • 1
    $\begingroup$ $\bar 8=\bar 2\cdot\bar 4$ is valid (mistake corrected). If you write $\bar 8=\bar 2\cdot\bar 2\cdot \bar 3\cdot\bar 7\cdot\bar7$, then there is a proper factor $\bar 2\cdot\bar 2\cdot\bar 7$, which has 8 as last digit. Similarly, if you write $\bar 4=(\bar 3)^{4m-1}\cdot \bar 2$ with $m>1$, then there is a proper factor $\bar 4=\bar 3^{3}\cdot \bar 2$ with $4$ as last digit. $\endgroup$
    – san
    May 21, 2015 at 15:29
  • $\begingroup$ Ah, I think I can get what you mean. Thanks. (btw, for $\bar n=4$, we also have $\bar 8\cdot \bar 8$, right? Also, the valid factorization you wrote for $\bar n=6$ in two factors are the same as those for $\bar n=4$. Are they typos, right?) $\endgroup$
    – mathlove
    May 21, 2015 at 21:18
  • $\begingroup$ $\bar n=\bar 8\cdot\bar 8$ is not a valid configuration, since then $4$ would be a factor of $n$, since 2 divides $\bar 8$. The other was a typo (fixed). $\endgroup$
    – san
    May 21, 2015 at 21:42
  • $\begingroup$ I would +10 this, if I could. $\endgroup$ May 21, 2015 at 21:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .