0
$\begingroup$

I was pondering over this question

For a positive integer $n$, define $s(n)$ to be the sum of $n$ and its digits. For example, $ s(2009) = 2009+2+0+0+9 = 2020$. Compute the number of elements in the set $\{s(0), s(1), s(2), . . . , s(9999)\}$.

Then I thought that (for each positive integer at most $9999$) there exists a unique quaterns $(a,b,c,d)$ such that $a,b,c,d\in\{0,1,2,3,4,5,6,7,8,9\}$ and $s(n)=1001a+101b+11c+2d$. For the ultimate step I would find all the quaterns that has the same image under $s$. Here I'm stopped.

I come up with python that the set $\{s(0), s(1), s(2), . . . , s(9999)\}$ has $9046$ elements and that $ \#\ s^{-1}(n)$ is at most two. The repeated values are 954 (for example $4\cdot1001 + 0\cdot101 + 9\cdot11 + 1\cdot 2 = 4\cdot1001 + 1\cdot101 + 0\cdot11 + 0\cdot2=4105$)

Are there better approaches to solve it?

Could someone help me understanding the behavior of the integers solution of the equation $1001a+101b+11c+2d=0$?

$\endgroup$
6
  • $\begingroup$ Could you show how you derived that pattern? $\endgroup$
    – Mailbox
    Commented May 25 at 19:04
  • $\begingroup$ I would start by looking at the equation modulo any of the five prime factors of the coefficients: $2,$ $7,$ $11,$ $13$ and $101.$ For example, the equation modulo 11 gives $b+d\equiv0.$ Modulo 2 gives $a+b+c$ must be even. $\endgroup$
    – Lieven
    Commented May 25 at 19:06
  • $\begingroup$ @Mailbox do you mean to paste the code that i wrote to find all the couples of quaterns that have the same image ? $\endgroup$
    – Alberto
    Commented May 25 at 19:10
  • $\begingroup$ or simply suspecting that there are multiple choices of quarterns for some values.$(1001\quad 101\quad 11\quad 2)\ (a\quad b\quad c\quad d)^{T}=(1001\quad 101\quad 11\quad 2 )(a'\quad b'\quad c'\quad d')^{T} $ bring me to solve $(1001\quad 101\quad 11\quad 2 )(x\quad y\quad z\quad w)=0$ $\endgroup$
    – Alberto
    Commented May 25 at 19:17
  • $\begingroup$ We are really only interested in solutions where all 4 unknowns are differences of 2 decimal digits, i.e., $\{a,b,c,d\}\subset\{-9,-8,\ldots,8,9\}.$ $\endgroup$
    – Lieven
    Commented May 25 at 19:26

1 Answer 1

Reset to default
2
$\begingroup$

Let $m$ and $n$ be nonnegative integers less than 10000 with $m>n$ and $s(m)=s(n).$ Let $a,$ $b,$ $c$ and $d$ represent the differences between their digits in each of the $4$ positions, which implies that they lie in the range $[-9,+9].$ Below I am restricting myself to solutions of your equation where the unknowns lie in that range.

If $a>0$ then it can only be $1$ because $101.9+11.9+2.9<1001.2.$ Then $b=-9$ because $101.8+11.9+2.9<1001.$ Then $c=-8$ and $d=-2.$ From $a=1$ we get $9$ possibilities for the first digits of $m$ and $n.$ From $b=-9$ we only have one possibility (the second digit of $m$ is $0$ and the second digit of $n$ is $9$), $c=-8$ gives 2 possibilities and $d=-2$ gives $8$ possibilities, or a total of $9.1.2.8=144$ combinations.

If $a=0$ and $b>0$ then $b=1,$ $c=-9$ and $d=-1$ yielding $10.9.1.9=810$ combinations.

Finally if $a=b=0$ then $c$ should be $1$ and there are no solutions for $d$ in the given range.

Thus there are $144+810=954$ pairs of integers $m>n$ in that range having $s(m)=s(n).$

$\endgroup$

You must log in to answer this question.

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