4
$\begingroup$

Let $d,d',n\in \mathbb N$ be given. If you want, assume $(d,d')=1$. How many positive integer solutions does $$dx+d'x'=n$$ have?

(Assuming $(d,d')=1$). I know there are $n/dd'+\mathcal O(1)$ solutions, but I thought initially it's possible to have an exact value with the greatest integer function. (Initially I thought it was $\lfloor n/dd'\rfloor $ but this is wrong right?)

More precisely the number of solutions is $$\sum _{x\leq n\atop {d'|n-dx\atop {n-dx\geq 0}}}\sum _{x'=(n-dx)/d'}1=\sum _{x\leq n/d\atop {dx\equiv n(d')}}1=\lfloor \frac {n/d-\overline dN}{d'}\rfloor =\lfloor \frac {n}{dd'}-\frac {\overline dN}{d'}\rfloor \hspace {10mm}N:=n\text{ mod }(d')$$ but is there anything I can really do with this except bound a fractional part by $\mathcal O(1)$? Can I get rid of the inverse in any way? Thanks in advance.

$\endgroup$
3
  • 1
    $\begingroup$ This probably leads to a gross closed form so I'll leave it as a comment: If you have $dd'|n$, then your formula becomes exact. Otherwise we can count it with: $\frac{1}{n!} \frac{d^n}{dz^n}\left.\left(\frac{z^d}{1-z^d}\frac{z^{d'}}{1-z^{d'}}\right)\right|_{z=0}$ since the counting is done with exponents. $xd+x'd'=n$ and $yd+y'd'=n$ can only double count when $xd=y'd'$ and $yd=x'd'$. But this implies $d'|n$ and $d|n$ which are relatively prime so $dd'|n$ which contradicts our initial assumption so there is no double counting. $\endgroup$
    – Merosity
    Commented Apr 7 at 23:37
  • $\begingroup$ and counting it with that object is... useful? :D (more than happy to hear it is!) $\endgroup$
    – tomos
    Commented Apr 8 at 4:22
  • $\begingroup$ I wouldn't say it's "useful", then again I don't know what the use of counting these ways of making $n$ has in the first place either. I'm just playing around here lol. $\endgroup$
    – Merosity
    Commented Apr 8 at 4:28

0

Reset to default

You must log in to answer this question.