6
$\begingroup$

http://oeis.org/A178157

A178157 is a number sequence that describes numbers that are divisible by all of their prefixes. For example, 2020 is in the sequence because 2020 is divisible by 2, 20, and 202, (and 2020). However, I noticed after 100, all the numbers in the sequence end with a zero. So my question is, is there a number in sequence A178157 greater than 100 that does not end with a zero?

My own progress:

A friend of mine wrote a code and checked all the numbers up to 100 million with no luck. Is there some proof that all numbers greater than 100 in this sequence must end with a zero?

The only lead I could think of in trying to prove it was that the number must not contain any zeros either because there would be a suffix that ends in a zero.

Interestingly enough, there's a similar sequence, A178158, which looks at the suffixes instead of the prefixes, and there are many large numbers in the sequence that do not contain a zeroes, for example, 53125 is divisible by 5, 25, 125, 3125, (and 53125). None of the numbers in this sequence end in a zero, which is much easier to prove, since the first prefix is zero and you can't divide by zero.

$\endgroup$
8
$\begingroup$

The answer is that any such three or more digit number must end in $0.$

If $n\geq 10$ then for $10n+d$ to be divisible by $n,$ you must have $d$ divisible by $n.$ But if $d$ is a digit, then $0\leq d<10\leq n,$ so the only possible $d$ is $0.$

This argument works in any base.


As Ross mentioned in comments, if the number has $2k+1,$ or more digits, it must end in $k$ zeros.

This can be seen by a similar argument, or using base $10^k,$ noting that any number which satisfies the property for base $10$ is also a number for base $10^k,$ and a number with $2k+1$ or more digits in base $10$ is $3$ or more digits in base $10^k.$


Unrelated to the question, but given any such number, not only can we add zeros to the end, we can also add zeros right before the last non-zero digit. That is, if $$n=d_1d_2d_3\dots d_k\underbrace{0\dots0}_{p\text{ times}}$$ then we can find a non-zero number of $0$ to add between $d_{k-1}$ and $d_k.$

Specifically, $$n_1=d_1\dots d_{k-1}\underbrace{0\dots 0}_{m\text{ times}} d_k$$ then $$10^{m+1}n-n_1=d_k(10^{m+1}-1)\cdot 10^p$$

Now, if $f(N)$ is the number of $N$ with all the factors of $2$ and $5$ removed, you can define $$D=\operatorname{lcm}\left(f(d_1),f(d_1d_2),\cdots,f(d_1d_2\dots d_{k-1})\right)$$

Then you can define $m$ to be one less the order of $10$ modulo $D.$

For example, with $n=14490000$ you have $$\operatorname{lcm}\left(f(1),f(14),f(144)\right)=\operatorname{lcm}(1,7,9)=63.$$

The order of $10$ mod $9$ is $1,$ so you just need the order of $10$ mod $7,$ and that is $6$, and $m$ is $5.$ Then:

$$144000009\cdot 10^9$$

You have to pad the right side with zeros, too.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The same argument says that any $2k+1$ digit number ends in $k\ 0$s. Appending a $0$ to a number that is acceptable makes another that is acceptable. It is useful to consider $140700$ as most of the six digit examples end in at least three $0$s. As this proof indicates, the difficult prefix is $140$. You need the two factors of $10$ to make the divisibility by $140$ work. $\endgroup$ – Ross Millikan Sep 23 at 4:27
  • $\begingroup$ Yes, because the works in any base. (Which I was just adding when I saw your comment, @RossMillikan ) $\endgroup$ – Thomas Andrews Sep 23 at 4:30
  • $\begingroup$ Although I guess using base $10^k$ is even stronger, I guess, since base 100 includes more numbers than base 10. $\endgroup$ – Thomas Andrews Sep 23 at 4:32
  • $\begingroup$ While correct, that comment is in a different direction than mine. I was looking at how few zeros a number of a given length could end with. You had my +1 already. $\endgroup$ – Ross Millikan Sep 23 at 4:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.